Forward feature selection for support vector machines

• US 20090287621A1
• Filed: 05/15/2008
• Published: 11/19/2009
• 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: Bar-Hillel, Aharon, Krupka, Eyal
• Granted Patent: US 8,108,324 B2
• Time in Patent Office: Days
• 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:

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 ({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; and

selecting a subset (q) of the features of the feature set based on the ranked approximated weights.

2. The method of claim 1, further comprising otherwise iterating training the SVM, approximating the quality, ranking the d features, and selecting the q subset until the q subset is less than the predetermined number of iterations.

3. 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.

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

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

6. The method of claim 1, wherein d′

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

7. The method of claim 6, wherein d′

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

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

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

classify unlabeled data using the trained SVM.

9. The article of claim 8, further comprising instructions to determine whether the q subset is less than a first threshold, and if so conclude the SVM training, and otherwise iterate training the SVM, approximate the quality, rank the remaining q features from the previous iteration, and select the q subset until the q subset is less than the first threshold.

10. The article of claim 8, 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.

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

12. A system comprising:

a processor to perform instructions; and

a memory coupled to the processor to store instructions that enable the processor to 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, and select a subset (q) of the features of the feature set based on the ranked approximated quality.

13. The system of claim 12, further comprising instructions to determine whether the q subset is less than a first threshold, and if so conclude the SVM training.

14. The system of claim 13, further comprising instructions to iterate training the SVM, approximate the quality, rank the remaining q features from the previous iteration, and select the q subset until the q subset is less than the first threshold, if the q subset is greater than the first threshold.

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

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

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

18. The system of claim 12, wherein the SVM is a forward feature selection SVM.

19. The system of claim 18, wherein the d′

subset is a random subset.