Forward feature selection for support vector machines

• US 8,756,174 B2
• Filed: 12/22/2011
• Issued: 06/17/2014
• Est. Priority Date: 05/15/2008
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Krupka, Eyal, Bar-Hillel, Aharon
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Kim, David H
• Application Number:
  US13/334,313
• Publication Number:
  US 20120095944A1
• Time in Patent Office: 908 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: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

In one embodiment, the present invention includes a method for training a Support Vector Machine (SVM) on a subset of features (d′) of a feature set having (d) features of a plurality of training instances to obtain a weight per instance, approximating a quality for the d features of the feature set using the weight per instance, ranking the d features of the feature set based on the approximated quality, and selecting a subset (q) of the features of the feature set based on the ranked approximated quality. Other embodiments are described and claimed.

Claims

1. A method comprising:

defining an iteration counter to a predetermined value;

training, using a processor of a computer system, a Support Vector Machine (SVM) on a subset of features (d′

) of a feature set having (d) features of a plurality of training instances to obtain a weight per instance ({right arrow over (α

)}′

);

approximating a quality for the d features of the feature set using the weight per instance;

ranking the d features of the feature set based on the approximated quality;

selecting a subset (q) of the features of the feature set based on the ranked approximated quality; and

iterating training the SVM, approximating the quality, ranking the d features, and selecting the q subset until the q subset is less than a selected threshold.

2. The method of claim 1, further comprising incrementing the iteration counter.

3. The method of claim 2, further comprising iterating training the SVM, approximating the quality, ranking the d features, and selecting the q subset if the iteration counter is less than a second predetermined value.

4. The method of claim 1, wherein ranking the d features includes comparing rank values each based at least in part on each of the approximated quality to a threshold.

5. The method of claim 4, wherein selecting the q subset includes selecting features having a corresponding approximated quality greater than the threshold.

6. The method of claim 5, further comprising approximating the feature quality by an approximate weighted correlation between instance labels and values for the features.

7. The method of claim 1, wherein d′

is substantially less than d and is a random subset of d.

8. The method of claim 7, wherein d′

is less than d by at least a factor of one hundred.

9. The method of claim 1, wherein each of the plurality of training instances corresponds to an image.

10. The method of claim 1, wherein the SVM comprises a linear SVM.

11. The method of claim 1, wherein the weight per instance comprises a vector (α

′

) of a length N corresponding to the plurality of training instances.

12. An article comprising a non-transitory machine-accessible medium including instructions that when executed cause a system to:

define an iteration counter to a predetermined value;

train a Support Vector Machine (SVM) according to a forward feature selection algorithm in which only a random subset of features (d′

) of a feature set (d) of a plurality of training instances are used to obtain a weight per instance (α

′

);

approximate a quality for the d features of the feature set using the weight per instance;

rank the d features of the feature set based on the approximated quality, and select a subset (q) of the features of the feature set based on the ranked approximated quality;

classify unlabeled data using the trained SVM; and

determine whether the q subset is less than a first threshold, and if so conclude the SVM training, and otherwise iterate training the SVM, approximating the quality, ranking the remaining q features from the previous iteration, and selecting the q subset until the q subset is less than the first threshold.

13. The article of claim 12, further comprising instructions to compare rank values each based at least in part on the approximated quality of each of the features to a second threshold.

14. The article of claim 13, further comprising instructions to select the q subset by selecting features having a corresponding approximated quality greater than the second threshold.

15. A system comprising:

a processor to perform instructions; and

a memory coupled to the processor to store instructions that enable the processor to define an iteration counter to a predetermined value, train a Support Vector Machine (SVM) on a subset of features (d′

) of a feature set having (d) features of a plurality of training instances to obtain a weight per instance, approximate a quality for each of the d features of the feature set using the weight per instance, rank the d features of the feature set based on the approximated quality, select a subset (q) of the features of the feature set based on the ranked approximated quality, determine whether the q subset is less than a first threshold, and if so conclude the SVM training, and iterate training the SVM, approximating the quality, ranking the remaining q features from the previous iteration, and selecting the q subset until the q subset is less than the first threshold if the q subset is greater than the first threshold.

16. The system of claim 15, further comprising instructions to compare rank values each based at least in part on each of the approximated quality to a second threshold.

17. The system of claim 16, further comprising instructions to select features having a corresponding approximated quality greater than the second threshold.

18. The system of claim 15, further comprising instructions to approximate the quality by an approximate weighted correlation between a label per instance and values for the features.

19. The system of claim 15, wherein the SVM is a forward feature selection SVM.

20. The system of claim 15, wherein the d′

subset is a random subset.