Efficient optimal linear boosting of a pair of classifiers.
Boosting is a meta-learning algorithm which takes as input a set of classifiers and combines these classifiers to obtain a better classifier. We consider the combinatorial problem of efficiently and optimally boosting a pair of classifiers by reducing this problem to that of constructing the optimal linear separator for two sets of points in two dimensions. Specifically, let each point x element of R be assigned a weight W(x) > 0, where the weighting function can be an arbitrary positive function. We give efficient (low-order polynomial time) algorithms for constructing an optimal linear "separator" l defined as follows. Let Q be the set of points misclassified by l. Then, the weight of Q, defined as the sum of the weights of the points in Q, is minimized. If W(z) = 1 for all points, then the resulting separator minimizes (exactly) the misclassification error. Without an increase in computational complexity, our algorithm can be extended to output the leave-one-out error, an unbiased estimate of the expected performance of the resulting boosted classifier.
Boyarshinov
Victor
V
Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. boyarv@cs.rpi.edu
Magdon-Ismail
Malik
M
D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D016247:Information Storage and Retrieval / Q000379:methods*; D016014:Linear Models; D010363:Pattern Recognition, Automated / Q000379:methods*