Method and apparatus for classifying data using R-functions

1. A method for constructing a classifier that distinguishes between different classes of data points, comprising:

receiving a data set, which includes class-one data points and class-two data points;

for each class-one data point in the data set,

using a separating primitive to produce a set of point-to-point separating boundaries, wherein each point-to-point separating boundary separates the class-one data point from a different class-two data point; and

combining separating boundaries in the set of separating boundaries to produce a point-to-class separating boundary that separates the class-one data point from all of the class-two data points in the data set; and

combining the point-to-class separating boundaries for each of the class-one data points to produce a class-to-class separating boundary for the classifier that separates all of the class-one data points from all of the class-two data points in the data set.

2. The method of claim 1 , wherein the separating primitive is a real-valued function ρ(x; u, v) that comprises a vector-variable x, and two vector-parameters u and v, such that ρ(x; u, v) divides an n-dimensional space into two subspaces, wherein the first subspace contains point u, and the second subspace contains point v, and wherein,

ρ(x; u, v)>0 for all x in the first subspace containing u;

ρ(x; u, v)<0 for all x in the second subspace containing v; and

ρ(x; u, v)=0 for all x defining the point-to-point separating boundary that separates u and v.

3. The method of claim 2 , wherein the separating primitive function ρ(x; u, v) can include:

a linear separating primitive function;

a spherical separating primitive function;

a parabolic separating primitive function;

a hyperbolic separating primitive function; or

an elliptic separating primitive function.

4. The method of claim 1 , wherein combining the set of point-to-point separating boundaries to produce the point-to-class separating boundary involves:

computing the intersection of a set of subspaces defined by the set of point-to-point separating boundaries, wherein each subspace in the set of subspaces contains the class-one data point; and

constructing the point-to-class separating boundary from the boundary of the intersection.

5. The method of claim 4 , wherein computing the intersection of the set of subspaces and constructing the point-to-class separating boundary involves using R-functions, wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes.

6. The method of claim 5 , wherein producing the point-to-class separating boundary involves using the R-function to perform a logical conjunction operation on the set of point-to-point separating boundaries to produce the point-to-class separating boundary.

7. The method of claim 1 , wherein combining the point-to-class separating boundaries for each of the class-one data points to produce the class-to-class separating boundary involves:

computing the union of a set of subspaces defined by the point-to-class separating boundaries, wherein each subspace in the set of subspaces contains at least one class-one data point; and

constructing the class-to-class separating boundary from the boundary of the union.

8. The method of claim 7 , wherein producing the class-to-class separating boundary involves using an R-function to perform a logical disjunction operation on the set of point-to-class separating boundaries to produce the class-to-class separating boundary.

9. The method of claim 1 , wherein the class-to-class separating boundary is defined in an n-dimensional space by an equation R(x)=0, wherein x is an n-dimensional vector-variable, and

wherein R(x (1) )>0 for all class-one data points x (1) in the data set; and

wherein R(x (2) )<0 for all class-two data points x (2) in the data set.

10. The method of claim 9 , wherein function R(x) is generated by the R-function, wherein R(x) has an analytical representation and is continuously differentiable.

11. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for constructing a classifier that distinguishes between different classes of data points, the method comprising:

receiving a data set, which includes class-one data points and class-two data points;

for each class-one data point in the data set,

using a separating primitive to produce a set of point-to-point separating boundaries, wherein each point-to-point separating boundary separates the class-one data point from a different class-two data point; and

combining separating boundaries in the set of separating boundaries to produce a point-to-class separating boundary that separates the class-one data point from all of the class-two data points in the data set; and

combining the point-to-class separating boundaries for each of the class-one data points to produce a class-to-class separating boundary for the classifier that separates all of the class-one data points from all of the class-two data points in the data set.

12. The computer-readable storage medium of claim 11 , wherein the separating primitive is a real-valued function ρ(x; u, v) that comprises a vector-variable x, and two vector-parameters u and v, such that ρ(x; u, v) divides an n-dimensional space into two subspaces, wherein the first subspace contains point u, and the second subspace contains point v, and wherein,

ρ(x; u, v)>0 for all x in the first subspace containing u;

ρ(x; u, v)<0 for all x in the second subspace containing v; and

ρ(x; u, v)=0 for all x defining the point-to-point separating boundary that separates u and v.

13. The computer-readable storage medium of claim 12 , wherein the separating primitive function ρ(x; u, v) can include:

a linear separating primitive function;

a spherical separating primitive function;

a parabolic separating primitive function;

a hyperbolic separating primitive function; or

an elliptic separating primitive function.

14. The computer-readable storage medium of claim 11 , wherein combining the set of point-to-point separating boundaries to produce the point-to-class separating boundary involves:

computing the intersection of a set of subspaces defined by the set of point-to-point separating boundaries, wherein each subspace in the set of subspaces contains the class-one data point; and

constructing the point-to-class separating boundary from the boundary of the intersection.

15. The computer-readable storage medium of claim 14 , wherein computing the intersection of the set of subspaces and constructing the point-to-class separating boundary involves using R-functions, wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes.

16. The computer-readable storage medium of claim 15 , wherein producing the point-to-class separating boundary involves using the R-function to perform a logical conjunction operation on the set of point-to-point separating boundaries to produce the point-to-class separating boundary.

17. The computer-readable storage medium of claim 11 , wherein combining the point-to-class separating boundaries for each of the class-one data points to produce the class-to-class separating boundary involves:

computing the union of a set of subspaces defined by the point-to-class separating boundaries, wherein each subspace in the set of subspaces contains at least one class-one data point; and

constructing the class-to-class separating boundary from the boundary of the union.

18. The computer-readable storage medium of claim 17 , wherein producing the class-to-class separating boundary involves using an R-function to perform a logical disjunction operation on the set of point-to-class separating boundaries to produce the class-to-class separating boundary.

19. The computer-readable storage medium of claim 11 , wherein the class-to-class separating boundary is defined in an n-dimensional space by an equation R(x)=0, wherein x is an n-dimensional vector-variable, and

wherein R(x (1) )>0 for all class-one data points x (1) in the data set; and

wherein R(x (2) )<0 for all class-two data points x (2) in the data set.

20. The computer-readable storage medium of claim 19 , wherein function R(x) is generated by the R-function, wherein R(x) has an analytical representation and is continuously differentiable.

21. An apparatus that constructs a classifier that distinguishes between different classes of data points, comprising:

a receiving mechanism configured to receive a data set, which includes class-one data points and class-two data points;

a point-to-class separating boundary mechanism, wherein for each data pattern in the training data set the mechanism is configured to:

use a separating primitive to produce a set of point-to-point separating boundaries, wherein each point-to-point separating boundary separates the class-one data point from a different class-two data point; and to

combine separating boundaries in the set of separating boundaries to produce a point-to-class separating boundary that separates the class-one data point from all of the class-two data points in the data set; and

a class-to-class separating boundary mechanism configured to combine the point-to-class separating boundaries for each of the class-one data points to produce a class-to-class separating boundary for the classifier that separates all of the class-one data points from all of the class-two data points in the data set.

22. The apparatus of claim 21 , wherein the separating primitive is a real-valued function ρ(x; u, v) that comprises a vector-variable x, and two vector-parameters u and v, such that ρ(x; u, v) divides an n-dimensional space into two subspaces, wherein the first subspace contains point u, and the second subspace contains point v, and wherein,

ρ(x; u, v)>0 for all x in the first subspace containing u;

ρ(x; u, v)<0 for all x in the second subspace containing v; and

ρ(x; u, v)=0 for all x defining the point-to-point separating boundary that separates u and v.

23. The apparatus of claim 22 , wherein the separating primitive function ρ(x; u, v) can include:

a linear separating primitive function;

a spherical separating primitive function;

a parabolic separating primitive function;

a hyperbolic separating primitive function; or

an elliptic separating primitive function.

24. The apparatus of claim 21 , wherein while combining the set of point-to-point separating boundaries, the point-to-class separating boundary mechanism is configured to:

compute the intersection of a set of subspaces defined by the set of point-to-point separating boundaries, wherein each subspace in the set of subspaces contains the class-one data point; and to

construct the point-to-class separating boundary from the boundary of the intersection.

25. The apparatus of claim 24 , wherein computing the intersection of the set of subspaces and constructing the point-to-class separating boundary involves using R-functions, wherein an R-function is a function whose sign can change if and only if the sign of one of its arguments changes.

26. The apparatus of claim 25 , wherein the point-to-class separating boundary mechanism is further configured to use the R-function to perform a logical conjunction operation on the set of point-to-point separating boundaries to produce the point-to-class separating boundary.

27. The apparatus of claim 21 , wherein while combining the point-to-class separating boundaries for each of the class-one data points, the class-to-class separating boundary mechanism is configured to:

compute the union of a set of subspaces defined by the point-to-class separating boundaries, wherein each subspace in the set of subspaces contains at least one class-one data point; and to

construct the class-to-class separating boundary from the boundary of the union.

28. The apparatus of claim 27 , wherein the class-to-class separating boundary mechanism is further configured to use an R-function to perform a logical disjunction operation on the set of point-to-class separating boundaries to produce the class-to-class separating boundary.