Lagrangian support vector machine

• US 20030093393A1
• Filed: 04/01/2002
• Published: 05/15/2003
• Est. Priority Date: 06/18/2001
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Mangasarian, Olvi, Musicant, David
• Granted Patent: US 7,395,253 B2
• Time in Patent Office: Days
• US Class Current: 706/16
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

A Lagrangian support vector machine solves problems having massive data sets (e.g., millions of sample points) by defining an input matrix representing a set of data having an input space with a dimension of n that corresponds to a number of features associated with the data set, generating a support vector machine to solve a system of linear equations corresponding to the input matrix with the system of linear equations defined by a positive definite matrix, and calculating a separating surface with the support vector machine to divide the set of data into two subsets of data

Claims

1. A method of classifying data comprising the steps of:

defining an input matrix representing a set of data having an input space with a dimension of n, wherein n corresponds to a number of features associated with the data set;

generating a support vector machine to solve a system of linear equations corresponding to the input matrix, wherein the system of linear equations is defined by a positive definite matrix; and

calculating a separating surface with the support vector machine to divide the set of data into at least two subsets of data.

2. A method according to claim 1, wherein a dimension of the positive definite matrix is equal to the dimension of (n+1).

3. A method according to claim 2, wherein the separating surface is a linear surface.

4. A method according to claim 2, wherein the separating surface is a nonlinear surface.

5. A method according to claim 3, wherein the separating surface is midway between a pair of parallel bounding planes.

6. A method according to claim 5, wherein the positive definite matrix is defined as:

7. A method according to claim 6, further comprising the step of minimizing a function defined by:

8. A method according to claim 7, wherein the separating plane is generating by iteratively calculating a value u defined by:

uⁱ⁺¹=Q<sup>−

1</sup>(e+((Quⁱ−

e)−

α

uⁱ)₊),i=0,1, . . . ,

9. A method according to claim 8, wherein global linear convergence is achieved by satisfying a condition defined by:

10. A method according to claim 9, wherein the separating surface is defined by a vector that is orthogonal to the pair of parallel bounding planes, and a coordinate that represents the location of the separating surface relative to an origin.

11. A method according to claim 10, wherein the vector is represented by:

12. A method according to claim 10, wherein the coordinate is represented by:

γ

=−

e′

Du.

13. A method according to claim 4, wherein the positive definite matrix is defined as:

14. A method according to claim 13, wherein the kernel K is a positive semidefinite kernel function.

15. A method according to claim 14, wherein the kernel K(A,B) maps R^m×

n×

R<sup>n×

1</sup> into R<sup>m×

1</sup> for Aε

R<sup>m×

n</sup> and Bε

R<sup>n×

1</sup>.

16. A method according to claim 15, wherein the kernel K(A,B) is a Gaussian kernel.

17. A method according to claim 16, further comprising the step of minimizing a function defined by:

18. A method according to claim 17, wherein the nonlinear separating surface is generated by iteratively calculating a value u defined by:

uⁱ⁺¹=Q<sup>−

1</sup>(e+((Quⁱ−

e)−

α

uⁱ)₊),i=0,1, . . . ,

19. A method according to claim 18, wherein the nonlinear separating surface is defined by:

20. A method of classifying data comprising the steps of:

defining an input matrix representing a set of data having an input space with a dimension of n, wherein n corresponds to a number of features associated with the data set;

generating a support vector machine to solve a system of linear equations corresponding to the input matrix, wherein the system of linear equations is defined by a positive definite matrix; and

calculating a linear separating surface with the support vector machine to divide the set of data into a plurality of subsets of data.

21. A method according to claim 20, wherein a dimension of the positive definite matrix is equal to the dimension of (n+1).

22. A method according to claim 21, wherein the separating surface is midway between a pair of parallel bounding planes.

23. A method according to claim 22, wherein the positive definite matrix is defined as:

24. A method according to claim 23, further comprising the step of minimizing a function defined by:

25. A method according to claim 24, wherein the separating plane is generating by iteratively calculating a value u defined by:

uⁱ⁺¹=Q<sup>−

1</sup>(e+((Qu<sup>i−

e</sup>)−

α

uⁱ)₊),i=0,1, . . . ,

26. A method according to claim 25, wherein global linear convergence is achieved by satisfying a condition defined by:

27. A method according to claim 26, wherein the separating surface is defined by a vector that is orthogonal to the pair of parallel bounding planes, and a coordinate that represents the location of the separating surface relative to an origin.

28. A method according to claim 27, wherein the vector is represented by:

29. A method according to claim 28, wherein the coordinate is represented by:

γ

=−

e′

Du.

30. A method of classifying data comprising the steps of:

defining an input matrix representing a set of data having an input space with a dimension of n, wherein n corresponds to a number of features associated with the data set;

generating a support vector machine to solve a system of linear equations corresponding to the input matrix, wherein the system of linear equations is defined by a positive definite matrix; and

calculating a nonlinear separating surface with the support vector machine to divide the set of data into a plurality of subsets of data.

31. A method according to claim 30, wherein a dimension of the positive definite matrix is equal to the dimension of (n+1).

32. A method according to claim 31, wherein the positive definite matrix is defined as:

33. A method according to claim 32, wherein the kernel K is a positive semidefinite kernel.

34. A method according to claim 33, wherein the kernel K(A,B) maps R^m×

n×

R<sup>n×

1</sup> into R<sup>m×

1</sup> for Aε

R<sup>m×

n</sup> and Bε

R<sup>m×

1</sup>.

35. A method according to claim 34, wherein the kernel K(A,B) is a Gaussian kernel.

36. A method according to claim 35, further comprising the step of minimizing a function defined by:

37. A method according to claim 36, wherein the nonlinear separating surface is generated by iteratively calculating a value u defined by:

uⁱ⁺¹=Q<sup>−

1</sup>(e+((Quⁱ−

e)−

α

uⁱ)₊),i=0,1, . . . ,

38. A method according to claim 37, wherein the nonlinear separating surface is defined by:

39. A method of determining a separating surface between features of a data set comprising the steps of:

defining an input matrix A representing the data set having an input space with a dimension of n, wherein n corresponds to a number of the features associated with the data set;

constructing a support vector machine to define the separating surface by solving a system of linear equations corresponding to the input matrix A, wherein the system of linear equations is defined by a positive definite matrix with a dimension equal to (n+1); and

dividing the data set into a plurality of subsets of data based on the separating surface calculated by the support vector machine.

40. A method according to claim 39, wherein the separating surface is a linear surface.

41. A method according to claim 39, wherein the separating surface is a nonlinear surface.

42. A support vector machine comprising:

an input module that generates an input matrix representing a set of data having an input space with a dimension of n, wherein n corresponds to a number of features associated with the data set;

a processor that receives an input signal from the input module representing the input matrix, wherein the processor calculates an output signal representing a solution to a system of linear equations corresponding to the input signal, and the system of linear equations is defined by a positive definite matrix; and

an output module that divides the set of data into a plurality of subsets of data based on the output signal from the processor that corresponds to a separating surface between the plurality of subsets of data.

43. A method according to claim 42, wherein a dimension of the positive definite matrix is equal to the dimension of (n+1). A method according to claim 43, wherein the separating surface is a linear surface.

44. A method according to claim 44, wherein the separating surface is a nonlinear surface.

45. A method of classifying patients comprising the steps of:

defining an input matrix representing a set of patient data having an input space with a dimension of n, wherein n corresponds to a number of features associated with each patent in the set of patient data;

generating a support vector machine to solve a system of linear equations corresponding to the input matrix, wherein the system of linear equations is defined by a positive definite matrix; and

calculating a separating surface with the support vector machine to divide the set of patient data into a plurality of subsets of data.

46. A method according to claim 46, wherein a dimension of the positive definite matrix is equal to the dimension of (n+1).

47. A method according to claim 47, wherein the separating surface is a linear surface.

48. A method according to claim 47, wherein the separating surface is a nonlinear surface.

49. A method according to claim 48, wherein the plurality of subsets of data include a node-positive set of data and a node-negative set of data.

50. A method according to claim 49, wherein the plurality of subsets of data include a good prognostic set of data, an intermediate prognostic set of data, and a poor prognostic set of data.