Efficient Optimal Linear Boosting of A Pair of Classifiers Victor Boyarshinov Malik Magdon-Ismail 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 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 2 dimensions. Specifically, let each point z be assigned a weight W(z) > 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” ` defined as follows. Let Q be the set of points mis-classified by `. 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 mis-classification 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. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 10/10/2005 cs-05-22
Efficient Optimal Linear Boosting of A Pair of Classifiers
Victor Boyarshinov
Malik Magdon-Ismail
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 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 2 dimensions. Specifically, let each point z be assigned a weight W(z) > 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” ` defined as follows. Let Q be the set of points mis-classified by `. 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 mis-classification 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.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
10/10/2005
cs-05-22