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

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 0 ;

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

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

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 0 ;

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

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

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.