Support vector machine—recursive feature elimination (SVM-RFE)

• US 8,095,483 B2
• Filed: 12/01/2010
• Issued: 01/10/2012
• Est. Priority Date: 10/27/1999
• Status: Expired due to Fees

• Current Assignee: Curtis Anderson, Health Discovery Corporation, James Roberts, Joe Mckenzie, Jules B. Paderewski, Julian N. Stern, Memorial Health Systems Incorporated, Timothy P. O'Hayer
• Original Assignee: Health Discovery Corporation
• Inventors: Weston, Jason, Guyon, Isabelle
• Primary Examiner(s): FERNANDEZ RIVAS, OMAR F
• Application Number:
  US12/957,411
• Publication Number:
  US 20110119213A1
• Time in Patent Office: 405 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2115 by evaluating different subsets according to an optimisation criterion, e.g. class separability, forward selection or backward elimination
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis
• CPC Class Codes: G16B 40/30 Unsupervised data analysis

Abstract

Identification of a determinative subset of features from within a group of features is performed by training a support vector machine using training samples with class labels to determine a value of each feature, where features are removed based on their the value. One or more features having the smallest values are removed and an updated kernel matrix is generated using the remaining features. The process is repeated until a predetermined number of features remain which are capable of accurately separating the data into different classes.

Claims

1. A computer-implemented method comprising:

(a) inputting into a computer processor programmed to execute a support vector machine a set of training examples having known labels with regard to two or more classes, each training example described by a vector of feature values for a plurality of features, the support vector machine comprising a decision function having a plurality of weights, wherein each feature has a corresponding weight;

(b) training the support vector machine by optimizing the plurality of weights so that a cost function is minimized and support vectors comprising a subset of the training examples are defined, wherein the decision function is based on the support vectors;

(c) computing ranking criteria using the optimized plurality of weights, wherein the ranking criterion estimates for each feature the effect on the cost function of removing that feature, and wherein features having the smallest effect on the cost function have the smallest ranking criteria;

(d) eliminating one or more features corresponding to the smallest ranking criteria to yield a reduced set of features;

(e) repeating steps (c) through (d) for the reduced set of features for a plurality of iterations until a subset of features of predetermined size remains, wherein the subset of features comprises determinative features for separating the set of training examples into the two or more classes; and

(f) generating at a printer or display device an output comprising a listing of the determinative features.

2. The method of claim 1, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria in a single iteration of steps (c) and (d).

3. The method of claim 1, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria in at least the first iteration of steps (c) and (d) and in later iterations, eliminating one feature for each iteration.

4. The method of claim 1, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria so that the number of features is reduced by a factor of two for each iteration.

5. The method of claim 1, wherein the set of training examples comprises gene expression values obtained from DNA microarrays and the determinative features comprise determinative genes.

6. The method of claim 1, further comprising generating an observation tree having a plurality of nodes, a first path comprising nodes corresponding to the determinative features, and a plurality of alternative paths, wherein nodes in the alternative paths are identified by removing a top ranked feature of the determinative features and repeating steps (c) and (d) so that alternative determinative features are identified.

7. A computer-program product embodied on a non-transitory computer-readable medium comprising instructions for executing a support vector machine, and further comprising instructions for:

training the support vector machine to determine a value for each feature in a group of features provided by a set of training samples having known labels corresponding to two or more classes, wherein training comprises generating a kernel matrix of components, each component comprising a dot product of two training samples, and adjusting a multiplier corresponding to each training sample to minimize a cost function;

eliminating at least one feature with a minimum value from the group to provide a reduced group of features;

generating an updated kernel matrix using the reduced group of features while keeping the multiplier unchanged;

determining an updated value for each feature in the reduced group of features;

repeating the steps of eliminating at least one feature, generating an updated kernel matrix and determining an updated value until a predetermined number of features remains; and

outputting a ranked list of features.

8. The computer-program product of claim 7, wherein the minimum value of a feature corresponds to a smallest change in the cost function when the feature is eliminated.

9. The computer-program product of claim 7, wherein the value of a feature corresponds to a weight in a decision function of the support vector machine.

10. The computer-program product of claim 7, wherein the step of eliminating comprises eliminating more than one feature corresponding to the minimum value.

11. The computer-program product of claim 7, wherein the step of eliminating comprises eliminating more than one feature corresponding to the minimum value in at least the first iteration of the step of eliminating and in later iterations, eliminating one feature for each iteration.

12. The computer-program product of claim 7, wherein the step of eliminating comprises eliminating more than one feature corresponding to the minimum value so that the number of features is reduced by a factor of two for each iteration.

30. The computer-program product of claim 7, wherein outputting a ranked list of features comprises transferring the ranked list of features to a disk drive or a removable media.

31. The computer-program product of claim 7, wherein outputting a ranked list of features comprises displaying the ranked list of features on a display device.

37. The non-transitory machine-readable medium of claim 31, further comprising displaying the listing on a display device.

38. The non-transitory machine-readable medium of claim 31, wherein the media comprises a disk drive or a removable media.

13. A non-transitory machine-readable medium comprising a plurality of instructions, which in response to being executed, result in a computing system:

(a) training a support vector machine by generating a kernel matrix from a set of training samples and adjusting a multiplier corresponding to each training sample to minimize a cost function;

(b) determining a weight value for each feature in a group of features that describe the training samples;

(c) eliminating at least one feature with a minimum weight value from the group;

(d) generating an updated kernel matrix while keeping the multiplier unchanged;

(e) updating the weight value for each feature of the group based on the updated kernel matrix;

(f) repeating steps (c) through (e) until a predetermined number of features remains to generate a ranked list of features; and

(g) generating a report to a printer or display device comprising the ranked list of features.

14. The non-transitory machine-readable medium of claim 13, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value in a single iteration of steps (b) and (c).

15. The non-transitory machine-readable medium of claim 13, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value in at least the first iteration of steps (b) and (c) and in later iterations, eliminating one feature for each iteration.

16. The non-transitory machine-readable medium of claim 13, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value so that the number of features is reduced by a factor of two for each iteration.

17. The non-transitory machine-readable medium of claim 13, wherein the set of training examples comprises gene expression values obtained from DNA microarrays and the determinative features comprise determinative genes.

18. A non-transitory machine-readable medium comprising a plurality of instructions, which in response to being executed, result in a computing system:

identifying a determinative subset of features that are most correlated to patterns in sample data by;

retrieving a training data having class labels with respect to the patterns from a memory in communication with a computer processor programmed for executing a support vector machine comprising a kernel;

calculating a kernel matrix using the training data to determine a value for each feature in the group of features;

eliminating at least one feature with a minimum value from the group;

calculating an updated kernel matrix, each component of the updated kernel matrix comprising a dot product of two training samples provided by at least a part of the training data that corresponds to the eliminated feature;

determining an updated value for each remaining feature of the group of features based on the updated kernel matrix;

repeating steps eliminating, calculating an updated kernel matrix and determining an updated value for a plurality of iterations until a pre-determined number of features in the group remain; and

generating an output comprising a ranked list of features, wherein the features in the ranked list comprise the determinative subset of features for predicting patterns in new data.

19. The non-transitory machine-readable medium of claim 18, wherein eliminating comprises eliminating multiple features from the group so that the number of features is reduced by the closest power of two to the number of remaining features.

20. The non-transitory machine-readable medium of claim 18, wherein the one or more features removed in eliminating comprises up to half of the remaining features.

21. The non-transitory machine-readable medium of claim 18, wherein eliminating comprises eliminating a plurality of features so that the number of features in the first iteration is reduced by up to half of the remaining features until a specified number of features remain and thereafter removing one feature per iteration.

28. The non-transitory machine-readable medium of claim 18, wherein generating an output comprises transferring the output to a disk drive or a removable media.

29. The non-transitory machine-readable medium of claim 18, wherein generating an output comprises displaying the output on a display device.

22. A computer-implemented method comprising:

(a) inputting into a computer processor programmed to execute a support vector machine a set of training examples having known labels with regard to two or more classes, each training example described by a vector of feature values for a plurality of features, the support vector machine comprising a decision function having a plurality of weights, wherein each feature has a corresponding weight;

(b) training the support vector machine by optimizing the plurality of weights so that a cost function is minimized and support vectors comprising a subset of the training examples are defined, wherein the decision function is based on the support vectors;

(c) computing ranking criteria using the optimized plurality of weights, wherein the ranking criterion estimates for each feature the effect on the cost function of removing that feature, and wherein features having the smallest effect on the cost function have the smallest ranking criteria;

(d) eliminating one or more features corresponding to the smallest ranking criteria to yield a reduced set of features;

(e) repeating steps (c) through (d) for the reduced set of features for a plurality of iterations until a subset of features of predetermined size remains, wherein the subset of features comprises determinative features for separating the set of training examples into the two or more classes; and

(f) transferring a listing of the determinative features to a media.

23. The method of claim 22, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria in a single iteration of steps (c) and (d).

24. The method of claim 22, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria in at least the first iteration of steps (c) and (d) and in later iterations, eliminating one feature for each iteration.

25. The method of claim 22, wherein step (d) comprises eliminating more than one feature corresponding to the smallest ranking criteria so that the number of features is reduced by a factor of two for each iteration.

26. The method of claim 22, further comprising displaying the listing on a display device.

27. The method of claim 22, wherein the media comprises a disk drive or a removable media.

32. A non-transitory machine-readable medium comprising a plurality of instructions, which in response to being executed, result in a computing system:

(a) training a support vector machine by generating a kernel matrix from a set of training samples and adjusting a multiplier corresponding to each training sample to minimize a cost function;

(b) determining a weight value for each feature in a group of features that describe the training samples;

(c) eliminating at least one feature with a minimum weight value from the group;

(d) generating an updated kernel matrix while keeping the multiplier unchanged;

(e) updating the weight value for each feature of the group based on the updated kernel matrix;

(f) repeating steps (c) through (e) until a predetermined number of features remains to generate a ranked list of features; and

(g) transferring the ranked list of features to a media.

33. The non-transitory machine-readable medium of claim 32, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value in a single iteration of steps (b) and (c).

34. The non-transitory machine-readable medium of claim 32, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value in at least the first iteration of steps (b) and (c) and in later iterations, eliminating one feature for each iteration.

35. The non-transitory machine-readable medium of claim 32, wherein step (c) comprises eliminating more than one feature corresponding to the minimum weight value so that the number of features is reduced by a factor of two for each iteration.

36. The non-transitory machine-readable medium of claim 32, wherein the set of training examples comprises gene expression values obtained from DNA microarrays and the determinative features comprise determinative genes.