Accelerating the boosting approach to training classifiers

• US 7,639,869 B1
• Filed: 08/11/2008
• Issued: 12/29/2009
• Est. Priority Date: 11/22/2004
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Brandt, Jonathan
• Primary Examiner(s): Desire; Gregory M
• Application Number:
  US12/189,676
• Time in Patent Office: 505 Days
• Field of Search: 382/156, 382/159, 382/170, 382/224, 706/6, 706/12, 706/20
• US Class Current: 382/159
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

Systems, methods, and computer program products implementing techniques for training classifiers. The techniques include receiving a training set that includes positive samples and negative samples, receiving a restricted set of linear operators, and using a boosting process to train a classifier to discriminate between the positive and negative samples. The boosting process is an iterative process. The iterations include a first iteration where a classifier is trained by (1) testing some, but not all linear operators in the restricted set against a weighted version of the training set, (2) selecting for use by the classifier the linear operator with the lowest error rate, and (3) generating a re-weighted version of the training set. The iterations also include subsequent iterations during which another classifier is trained by repeating steps (1), (2), and (3), but using in step (1) the re-weighted version of the training set generated during a previous iteration.

Claims

1. A method for training a classifier, the method comprising:

receiving a training set that includes data samples that correspond to an object of interest (positive samples) and data samples that do not correspond to an object of interest (negative samples);

receiving a restricted set of linear operators; and

using a boosting process to train a classifier to discriminate between the positive and negative samples in the training set, the classifier being an aggregate of multiple individual classifiers, the boosting process being an iterative process, the iterations including;

a first iteration where an individual classifier in the aggregate is trained by;

(1) testing some, but not all linear operators in the restricted set against a weighted version of the training set, wherein testing is performed by a computer;

(2) selecting for use by the individual classifier the linear operator with the lowest error rate (error-minimizing operator); and

(3) generating a re-weighted version of the training set that is weighted such that data samples that were misclassified by the error-minimizing operator are weighted more than data samples that were classified correctly by the error-minimizing operator; and

subsequent iterations during which another individual classifier in the aggregate is trained by repeating steps (1), (2), and (3), but using in step (1) the re-weighted version of the training set generated during a previous iteration.

2. The method of claim 1, wherein:

the data samples include one or more of textual data, graphical data, or audio data.

3. The method of claim 1, wherein:

the restricted set of operators includes one or more of the following types of linear operators;

wavelet families, Gabor filters, Laplacian of Gaussian masks, or edge and corner detectors.

4. The method of claim 1, wherein testing some, but not all of the operators includes:

computing a relevance estimate for each operator in the restricted set of operators, the relevance estimate being an estimate of how accurately the operator can discriminate between the positive samples and the negative samples in the training set;

ranking the operators according to their relevance estimate; and

testing only the operators above a threshold ranking.

5. The method of claim 4, wherein computing the relevance estimate for each operator includes:

computing mean and standard deviation statistics for positive and negative samples in the training set;

computing a separation vector for the training set using the mean and standard deviation statistics; and

computing the relevance estimate for the operator using the separation vector.

6. The method of claim 5, wherein computing the relevance estimate for the operator using the separation vector includes:

multiplying the operator against the separation vector.

7. The method of claim 1, wherein:

the iterations further include at least one iteration where the individual classifier is trained by testing all the operators in the restricted set of operators.

8. A computer program product, tangibly embodied in a computer-readable storage medium, for training a classifier, the product being operable to cause data processing apparatus to perform operations comprising:

receiving a training set that includes data samples that correspond to an object of interest (positive samples) and data samples that do not correspond to an object of interest (negative samples);

receiving a restricted set of linear operators; and

using a boosting process to train a classifier to discriminate between the positive and negative samples in the training set, the classifier being an aggregate of multiple individual classifiers, the boosting process being an iterative process, the iterations including;

a first iteration where an individual classifier in the aggregate is trained by;

(1) testing some, but not all linear operators in the restricted set against a weighted version of the training set;

(2) selecting for use by the individual classifier the linear operator with the lowest error rate (error-minimizing operator); and

(3) generating a re-weighted version of the training set that is weighted such that data samples that were misclassified by the error-minimizing operator are weighted more than data samples that were classified correctly by the error-minimizing operator; and

subsequent iterations during which another individual classifier in the aggregate is trained by repeating steps (1), (2), and (3), but using in step (1) the re-weighted version of the training set generated during a previous iteration.

9. The computer program product of claim 8, wherein:

the data samples include one or more of textual data, graphical data, or audio data.

10. The computer program product of claim 8, wherein:

the restricted set of operators includes one or more of the following types of linear operators;

wavelet families, Gabor filters, Laplacian of Gaussian masks, or edge and corner detectors.

11. The computer program product of claim 8, wherein testing some, but not all of the operators includes:

computing a relevance estimate for each operator in the restricted set of operators, the relevance estimate being an estimate of how accurately the operator can discriminate between the positive samples and the negative samples in the training set;

ranking the operators according to their relevance estimate; and

testing only the operators above a threshold ranking.

12. The computer program product of claim 11, wherein computing the relevance estimate for each operator includes:

computing mean and standard deviation statistics for positive and negative samples in the training set;

computing a separation vector for the training set using the mean and standard deviation statistics; and

computing the relevance estimate for the operator using the separation vector.

13. The computer program product of claim 12, wherein computing the relevance estimate for the operator using the separation vector includes:

multiplying the operator against the separation vector.

14. The computer program product of claim 8, wherein:

the iterations further include at least one iteration where the individual classifier is trained by testing all the operators in the restricted set of operators.

15. A system for training a classifier comprising:

one or more computers operable to perform instructions to;

receive a training set that includes data samples that correspond to an object of interest (positive samples) and data samples that do not correspond to an object of interest (negative samples);

receive a restricted set of linear operators; and

use a boosting process to train a classifier to discriminate between the positive and negative samples in the training set, the classifier being an aggregate of multiple individual classifiers, the boosting process being an iterative process, the iterations including;

a first iteration where an individual classifier in the aggregate is trained by;

(1) testing some, but not all linear operators in the restricted set against a weighted version of the training set;

(2) selecting for use by the individual classifier the linear operator with the lowest error rate (error-minimizing operator); and

(3) generating a re-weighted version of the training set that is weighted such that data samples that were misclassified by the error-minimizing operator are weighted more than data samples that were classified correctly by the error-minimizing operator; and

subsequent iterations during which another individual classifier in the aggregate is trained by repeating steps (1), (2), and (3), but using in step (1) the re-weighted version of the training set generated during a previous iteration.

16. The system of claim 15, wherein:

the data samples include one or more of textual data, graphical data, or audio data.

17. The system of claim 15, wherein:

the restricted set of operators includes one or more of the following types of linear operators;

wavelet families, Gabor filters, Laplacian of Gaussian masks, or edge and corner detectors.

18. The system of claim 15, wherein testing some, but not all of the operators includes:

computing a relevance estimate for each operator in the restricted set of operators, the relevance estimate being an estimate of how accurately the operator can discriminate between the positive samples and the negative samples in the training set;

ranking the operators according to their relevance estimate; and

testing only the operators above a threshold ranking.

19. The system of claim 18, wherein computing the relevance estimate for each operator includes:

computing mean and standard deviation statistics for positive and negative samples in the training set;

computing a separation vector for the training set using the mean and standard deviation statistics; and

computing the relevance estimate for the operator using the separation vector.

20. The system of claim 19, wherein computing the relevance estimate for the operator using the separation vector includes:

multiplying the operator against the separation vector.

21. The system of claim 15, wherein:

the iterations further include at least one iteration where the individual classifier is trained by means for testing all the operators in the restricted set of operators.