Combining resilient classifiers

• US 7,873,583 B2
• Filed: 01/19/2007
• Issued: 01/18/2011
• 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
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US11/625,266
• Publication Number:
  US 20080177684A1
• Time in Patent Office: 1,460 Days
• Field of Search: 706 1- 62, 382/155, 382/159
• 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 wherein a combined support vector machine associated with a classifier receives an input, x, and computes a classification for the received input as ĝ

(x)=ψ

(Σ

_i=1^l{circumflex over (α

)}_iy_iK(x_i,x)+{circumflex over (b)}).

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 computed based on 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 computed based on 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 computed based on 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. A system for combining multiple support vector machines, comprising:

a computing device having a central processing unit and memory;

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, wherein the combined support vector machine receives an input, x, and computes a classification for the received input as ĝ

(x)=ψ

(Σ

_i=1^l{circumflex over (α

)}_iy_iK(x_i,x)+{circumflex over (b)}).

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

12. The system of claim 10 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.

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

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

15. 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, wherein the combined support vector machine receives an input, x, and computes a classification for the received input as ĝ

(x)=ψ

(Σ

_i=1^l{circumflex over (α

)}_iy_iK(x_i,x)+{circumflex over (b)}).

16. The computer-readable medium of claim 15 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.

17. The computer-readable medium of claim 15 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.

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

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