Efficient Optimal Linear Boosting of a Pair of Classifiers
Victor Boyarshinov, Malik Magdon‐Ismail · IEEE Transactions on Neural Networks · 2007
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.