Method for boosting the performance of machine-learning classifiers
First Claim
Patent Images
1. A computer-implemented process for using feature selection to obtain a strong classifier from a combination of weak classifiers, comprising using a computer to perform the following process actions:
- (a) inputting a set of training examples, a prescribed maximum number of weak classifiers, a cost function capable of measuring the overall cost, and an acceptable maximum cost;
(b) computing a set of weak classifiers, each classifier being associated to a particular feature of the training examples,(c) determining which of the set of weak classifiers is the most significant classifier;
(d) adding said most significant classifier to a current set of optimal weak classifiers;
(e) determining which of the current set of optimal weak classifiers is the least significant classifier;
(f) computing the overall cost for the current set of optimal weak classifiers using the cost function;
(g) conditionally removing the least significant classifier for the current set of optimal weak classifiers;
(h) computing the overall cost for the current set of optimal weak classifiers less the least significant classifier using the cost function;
(i) determining whether the removal of the least significant classifier results in a lower overall cost;
(j) whenever it is determined that the removal of the least significant classifier results in a lower overall cost, eliminating the least significant classifier;
(k) recomputing each classifier in the current set of optimal weak classifiers associated with a feature added subsequent to the eliminated classifier while keeping the earlier optimal weak classifiers unchanged;
(l) repeat actions (f) through (k) until it is determined the removal of the least significant classifier does not result in a lower overall cost and then reinstating the last identified least significant classifier to the current set of optimal weak classifiers;
(m) determining if the number of weak classifiers in the current set of optimal weak classifiers equals the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers is less than the acceptable maximum cost; and
(n) whenever it is determined that the number of weak classifiers in the current set of optimal weak classifiers does not equal the prescribed maximum number of weak classifiers and the last computed overall cost for the current set of optimal weak classifiers exceeds the acceptable maximum cost, repeating actions (c) through (m) until it is determined that the number of weak classifiers in the current set of optimal weak classifiers does equal the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers becomes less than the maximum allowable cost, then outputting the sum of the individual weak classifiers as the trained strong classifier.
3 Assignments
0 Petitions
Accused Products
Abstract
A novel statistical learning procedure that can be applied to many machine-learning applications is presented. Although this boosting learning procedure is described with respect to its applicability to face detection, it can be applied to speech recognition, text classification, image retrieval, document routing, online learning and medical diagnosis classification problems.
108 Citations
15 Claims
-
1. A computer-implemented process for using feature selection to obtain a strong classifier from a combination of weak classifiers, comprising using a computer to perform the following process actions:
-
(a) inputting a set of training examples, a prescribed maximum number of weak classifiers, a cost function capable of measuring the overall cost, and an acceptable maximum cost; (b) computing a set of weak classifiers, each classifier being associated to a particular feature of the training examples, (c) determining which of the set of weak classifiers is the most significant classifier; (d) adding said most significant classifier to a current set of optimal weak classifiers; (e) determining which of the current set of optimal weak classifiers is the least significant classifier; (f) computing the overall cost for the current set of optimal weak classifiers using the cost function; (g) conditionally removing the least significant classifier for the current set of optimal weak classifiers; (h) computing the overall cost for the current set of optimal weak classifiers less the least significant classifier using the cost function; (i) determining whether the removal of the least significant classifier results in a lower overall cost; (j) whenever it is determined that the removal of the least significant classifier results in a lower overall cost, eliminating the least significant classifier; (k) recomputing each classifier in the current set of optimal weak classifiers associated with a feature added subsequent to the eliminated classifier while keeping the earlier optimal weak classifiers unchanged; (l) repeat actions (f) through (k) until it is determined the removal of the least significant classifier does not result in a lower overall cost and then reinstating the last identified least significant classifier to the current set of optimal weak classifiers; (m) determining if the number of weak classifiers in the current set of optimal weak classifiers equals the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers is less than the acceptable maximum cost; and (n) whenever it is determined that the number of weak classifiers in the current set of optimal weak classifiers does not equal the prescribed maximum number of weak classifiers and the last computed overall cost for the current set of optimal weak classifiers exceeds the acceptable maximum cost, repeating actions (c) through (m) until it is determined that the number of weak classifiers in the current set of optimal weak classifiers does equal the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers becomes less than the maximum allowable cost, then outputting the sum of the individual weak classifiers as the trained strong classifier. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A system for detecting a person'"'"'s face in an input image and identifying a face pose range into which the face pose exhibited by the detected face falls, the system comprising:
-
a general purpose computing device; and a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to; create database comprising a plurality of training feature characterizations, each of which characterizes the face of a person at a known face pose or a non-face; train a plurality of detectors arranged in a pyramidal architecture to determine whether a portion of an input image depicts a person'"'"'s face having a face pose falling within a face pose range associated with one of the detectors using the training feature characterizations; and
whereinsaid detectors using a greater number of feature characterizations are arranged at the bottom of the pyramid, and said detectors arranged to detect finer ranges of face pose are arranged at the bottom of the pyramid; and
wherein the program module to train a plurality of detectors comprises sub-modules to,(a) input a set of training examples, a prescribed maximum number of weak classifiers, a cost function capable of measuring the overall cost, and an acceptable maximum cost; (b) compute a set of weak classifiers, each classifier being associated to a particular feature of the training examples, (c) determine which of the set of weak classifiers is the most significant classifier; (d) add said most significant classifier to a current set of optimal weak classifiers; (e) determine which of the current set of optimal weak classifiers is the least significant classifier; (f) compute the overall cost for the current set of optimal weak classifiers using the cost function; (g) conditionally remove the least significant classifier for the current set of optimal weak classifiers; (h) compute the overall cost for the current set of optimal weak classifiers less the least significant classifier using the cost function; (i) determine whether the removal of the least significant classifier results in a lower overall cost; (j) whenever it is determined that the removal of the least significant classifier results in a lower overall cost, eliminate the least significant classifier; (k) recompute each classifier in the current set of optimal weak classifiers associated with a feature added subsequent to the eliminated classifier while keeping the earlier optimal weak classifiers unchanged; (l) repeat actions (f) through (k) until it is determined the removal of the least significant classifier does not result in a lower overall cost and then reinstate the last identified least significant classifier to the current set of optimal weak classifiers; (m) determine if the number of weak classifiers in the current set of optimal weak classifiers equals the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers is less than the acceptable maximum cost; and (n) whenever it is determined that the number of weak classifiers in the current set of optimal weak classifiers does not equal the prescribed maximum number of weak classifiers and the last computed overall cost for the current set of optimal weak classifiers exceeds the acceptable maximum cost, repeat actions (c) through (m) until it is determined that the number of weak classifiers in the current set of optimal weak classifiers does equal the prescribed maximum number of weak classifiers or the last computed overall cost for the current set of optimal weak classifiers becomes less than the maximum allowable cost, then output the sum of the individual weak classifiers as the trained strong classifier.
-
Specification