COMBINING RESILIENT CLASSIFIERS

• US 20080177684A1
• Filed: 01/19/2007
• Published: 07/24/2008
• Est. Priority Date: 01/19/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Venkatesan, Ramarathnam, Laxman, Srivatsan
• Granted Patent: US 7,873,583 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A classification system is described for resiliently classifying data. In various embodiments, the classification system constructs a combined classifier based on multiple classifiers that are constructed to classify a set of training data. The combined classifier can be constructed in parallel with the multiple classifiers and applied to classify data.

Claims

1. A method performed by a computer system for combining multiple classifiers, comprising:

for each classifier, setting to zero multipliers associated with data elements that were not used to construct the classifier; and

constructing a combined classifier by setting its multiplier values to a weighted average of the multipliers associated with the multiple classifiers.

2. The method of claim 1 further comprising:

receiving data to be classified; and

classifying the received data based on the classification provided by the combined classifier.

3. The method of claim 1 wherein the weight for each of the multiplier values associated with a classifier is a margin of a support vector machine associated with the classifier.

4. The method of claim 1 wherein the weight for each of the multiplier values associated with a support vector machine is one minus a fraction of points in a training data subset that is used to construct the classifier.

5. The method of claim 1 wherein the weight for each of the multiplier values associated with a classifier is an absolute value of a decision function corresponding to a created support vector machine at the received data that is associated with the classifier.

6. The method of claim 1 wherein the weights are specified when creating the classifiers.

7. The method of claim 1 wherein the constructing includes adjusting the weighted average by a bias.

8. The method of claim 7 wherein the bias is a weighted average of a bias for each classifier.

9. The method of claim 8 wherein weights used to compute the weighted average of a bias for each support vector machine are weights used to compute the weighted average of the multipliers, further wherein each multiplier is a Lagrange multiplier.

10. The method of claim 1 wherein a combined support vector machine associated with a classifier receives an input, x, and computes a classification for the received input as

11. A system for combining multiple support vector machines, comprising:

a component that computes at least two Lagrange multipliers, each Lagrange multiplier computed to construct a support vector machine based on a subset of original training data that is randomly selected from the original training data; and

a combined support vector machine, the combined support vector machine computed based at least in part on an aspect of the support vector machines based on the subsets of original training data.

12. The system of claim 11 wherein the combined support vector machine is computed based at least in part on a combination of the at least two Lagrange multipliers.

13. The system of claim 11 wherein the combined support vector machine is computed based at least in part on classifications of the original training data produced by the support vector machines.

14. The system of claim 13 wherein the combined support vector machine is adapted to receive and classify an input.

15. The system of claim 14 wherein a classification of the input is equivalent to a majority of classifications for the input that the support vector machines would provide.

16. A computer-readable medium storing computer-executable instructions that, when executed, cause a computer system to perform a method for combining multiple support vector machines, the method comprising:

receiving at least two support vector machines constructed from an original set of training data;

creating a new training data set based on classifications provided by each of the at least two support vector machines for the original training data set from which the support vector machines were derived; and

constructing a combined support vector machine based on the new training data set.

17. The computer-readable medium of claim 16 wherein the constructing includes:

selecting a majority of the new training data to train the combined support vector machine; and

selecting a remaining portion of the new training data to verify classifications provided by the combined support vector machine.

18. The computer-readable medium of claim 16 wherein when an input is received, a classification for the input provided by the combined support vector machine is equivalent to classifications that a majority of the at least two support vector machines would provide.

19. The computer-readable medium of claim 16 wherein the constructing is performed in parallel with the received support vector machines.

20. The computer-readable medium of claim 19 wherein the combining includes calculating a weight for each of the at least two support vector machines.