Method and apparatus for functional relationship approximation through nonparametric regression using R-functions

• US 7,933,850 B1
• Filed: 11/13/2006
• Issued: 04/26/2011
• Est. Priority Date: 11/13/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Bougaev, Anton A., Gross, Kenny C., Urmanov, Aleksey M.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US11/598,608
• Time in Patent Office: 1,625 Days
• Field of Search: 706/20
• US Class Current: 706/20
• CPC Class Codes: G06F 11/0706 the processing taking place on a specific hardware platform or in a specific software environment
• CPC Class Codes: G06F 11/0748 in a remote unit communicating with a single-box computer node experiencing an error/fault remote testing G06F11/2294
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

One embodiment of the present invention provides a system that constructs a functional relationship approximation from a set of data points through nonparametric regression. During operation, the system receives a training data set in an n-dimensional space. Next, the system defines a set of regression primitives in the n-dimensional space, wherein a regression primitive in the set passes through N data points in the training data set, wherein N≧n. The system then logically combines the set of regression primitives to produce a convex envelope F, such that for each point p in the n-dimensional space: (1) F(p)=0, if p is on the convex envelope; (2) F(p)<0, if p is inside the convex envelope; and (3) F(p)>0, if p is outside the convex envelope. The system next obtains the functional relationship approximation by computing an argument of the minimum of F in the n-dimensional space. The system subsequently uses the functional relationship approximation to classify data.

Claims

1. A method for constructing a functional relationship approximation from a set of data points through nonparametric regression, the method comprising:

receiving a training data set in an n-dimensional space, wherein the training data set represents normal system data values from a system, wherein the normal system data values are collected from a system with a known-good behavior pattern;

defining a set of regression primitives in the n-dimensional space, wherein a regression primitive in the set passes through N data points in the training data set, wherein N≧

n;

logically combining the set of regression primitives to produce a convex envelope F, wherein logically combining the set of regression primitives involves using R-function operations by, for each subset of (N−

1) data points in the training data set, grouping a subset of regression primitives in the set which pass through the (N−

1) data points; and

performing an R-conjunction operation on the subset of regression primitives to produce a combined functional relationship associated with the (N−

1) data points; and

performing an R-disjunction operation on a set of combined functional relationship associated with different subsets of (N−

1) data points in the training data set to produce the convex envelope F, such that for each point p in the n-dimensional space;

F(p)=0 if p is on the convex envelope, F(p)<

0 if p is inside the convex envelope, and F(p)>

0 if p is outside the convex envelope;

using at least a computer for obtaining the functional relationship approximation by computing an argument of the minimum of F in the n-dimensional space, wherein the functional relationship approximation is constructed based on the training data set, and wherein the functional relationship approximation enables prediction of normal system behavior; and

using the functional relationship approximation to classify data from the system.

2. The method of claim 1, wherein classifying the data involves determining whether a telemetry signal from a computer system is deviating from a normal telemetry signal from the computer system.

3. The method of claim 1, wherein defining the set of regression primitives in the n-dimensional space involves iteratively:

selecting a set of N data points from the training data set; and

generating a regression primitive which passes through the selected N data points,

wherein between any two sets of selected N data points, there is at least one different data point in each of the sets.

4. The method of claim 1, wherein a regression primitive can be:

a linear function;

or

a nonlinear function.

5. The method of claim 1,

wherein a regression primitive defines a hyperplane g(p)=0 in the n-dimensional space;

wherein the hyperplane g(p)=0 divides the n-dimensional space into three regions such that for each point p;

g(p)=0 if p is on the hyperplane;

g(p)<

0 if p is on one side of the hyperplane; and

g(p)>

0 if p is on the other side of the hyperplane.

6. The method of claim 1,

wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes;

and

wherein the R-function operations mimic logical operations.

7. The method of claim 1, wherein each data point in the training data set comprises:

one dependent variable y; and

(n−

1) independent variables x;

wherein the value of y is functionally related to the values of x.

8. The method of claim 7, wherein prior to defining the set of regression primitives, the method further comprises preprocessing the received training data set which involves:

receiving a query point x=x₀;

selecting k-nearest-neighbors of x₀ from the training data set; and

replacing the training data set with the k data points associated with the k-nearest-neighbors of x₀.

9. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for constructing a functional relationship approximation from a set of data points through nonparametric regression, the method comprising:

receiving a training data set in an n-dimensional space, wherein the training data set represents normal system data values from a system, wherein the normal system data values are collected from a system with a known-good behavior pattern;

defining a set of regression primitives in the n-dimensional space, wherein a regression primitive in the set passes through N data points in the training data set, wherein N≧

n;

logically combining the set of regression primitives to produce a convex envelope F, wherein logically combining the set of regression primitives involves using R-function operations by, for each subset of (N−

1) data points in the training data set, grouping a subset of regression primitives in the set which pass through the (N−

1) data points; and

performing an R-conjunction operation on the subset of regression primitives to produce a combined functional relationship associated with the (N−

1) data points; and

performing an R-disjunction operation on a set of combined functional relationship associated with different subsets of (N−

1) data points in the training data set to produce the convex envelope F, such that for each point p in the n-dimensional space;

F(p)=0 if p is on the convex envelope, F(p)<

0 if p is inside the convex envelope, and F(p)>

0 if p is outside the convex envelope;

obtaining the functional relationship approximation by computing an argument of the minimum of F in the n-dimensional space, wherein the functional relationship approximation is constructed based on the training data set, and wherein the functional relationship approximation enables prediction of normal system behavior; and

using the functional relationship approximation to classify data from the system.

10. The computer-readable storage medium of claim 9, wherein classifying the data involves determining whether a telemetry signal from a computer system is deviating from a normal telemetry signal from the computer system.

11. The computer-readable storage medium of claim 9, wherein defining the set of regression primitives in the n-dimensional space involves iteratively:

selecting a set of N data points from the training data set; and

generating a regression primitive which passes through the selected N data points,

wherein between any two sets of selected N data points, there is at least one different data point in each of the sets.

12. The computer-readable storage medium of claim 9, wherein a regression primitive can be:

a linear function;

or

a nonlinear function.

13. The computer-readable storage medium of claim 9,

wherein a regression primitive defines a hyperplane g(p)=0 in the n-dimensional space;

wherein the hyperplane g(p)=0 divides the n-dimensional space into three regions such that for each point p;

g(p)=0 if p is on the hyperplane;

g(p)<

0 if p is on one side of the hyperplane; and

g(p)>

0 if p is on the other side of the hyperplane.

14. The computer-readable storage medium of claim 9,

wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes;

and

wherein the R-function operations mimic logical operations.

15. The computer-readable storage medium of claim 9, wherein each data point in the training data set comprises:

one dependent variable y; and

(n−

1) independent variables x;

wherein the value of y is functionally related to the values of x.

16. The computer-readable storage medium of claim 15, wherein prior to defining the set of regression primitives, the method further comprises preprocessing the received training data set which involves:

receiving a query point x=x₀;

selecting k-nearest-neighbors of x₀ from the training data set; and

replacing the training data set with the k data points associated with the k-nearest-neighbors of x₀.

17. A hardware apparatus that constructs a functional relationship approximation from a set of data points through nonparametric regression, comprising:

a receiving mechanism configured to receive a training data set in an n-dimensional space, wherein the training data set represents normal system data values from a system, wherein the normal system data values are collected from a system with a known-good behavior pattern;

a fitting mechanism configured to define a set of regression primitives in the n-dimensional space, wherein a regression primitive in the set passes through N data points in the training data set, wherein N≧

n;

a logic operation mechanism configured to logically combine the set of regression primitives to produce a convex envelope F, by using R-function operations to produce the convex envelope F, by, for each data point d in the training data set, grouping a subset of regression primitives in the set which pass through d; and

performing an R-conjunction operation on the subset of regression primitives to produce a combined functional relationship associated with d; and

performing an R-disjunction operation on a set of combined functional relationship associated with different d to produce the convex envelope F, such that for each point p in the n-dimensional space;

F(p)=0 if p is on the convex envelope, F(p)<

0 if p is inside the convex envelope, and F(p)>

0 if p is outside the convex envelope;

an computing mechanism configured to obtain the functional relationship approximation by computing an argument of the minimum of F in the n-dimensional space, wherein the functional relationship approximation is constructed based on the training data set, and wherein the functional relationship approximation enables prediction of normal system behavior; and

an applying mechanism configured to use the functional relationship approximation to classify data from the system.

18. The apparatus of claim 17, wherein the applying mechanism is further configured to use the functional relationship approximation to determine whether a telemetry signal from a computer system is deviating from a normal telemetry signal from the computer system.

19. The apparatus of claim 17, wherein the fitting mechanism is configured to:

select a set of N data points from the training data set; and

to

generate a regression primitive which passes through the selected N data points,

wherein between any two sets of selected N data points, there is at least one different data point in each of the sets.

20. The apparatus of claim 17,

wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes;

and

wherein the R-function operations are logical operations.