Improving Algorithms for Boosting

Javed A. Aslam
Department of Computer Science
Dartmouth College
6211 Sudikoff Laboratory
Hanover, NH 03755
jaa@cs.dartmouth.edu
http://www.cs.dartmouth.edu/  jaa/

Abstract
Motivated by results in informationtheory, we describe 
a modification of the popular boosting algorithm 
AdaBoost and assess its performance both
theoretically and empirically. We provide theoretical
and empirical evidence that the proposed
boosting scheme will have lower training and testing 
error than the original (non confidencerated)
version of AdaBoost. Our modified boosting algorithm 
and its analysis also suggests an explana
tion for why boosting with confidencerated predictions 
often markedly outperforms boosting with
out confidencerated predictions. Finally, our motivations 
and analyses provide further impetus for
the study of boosting in an informationtheoretic,
as opposed to decisiontheoretic, light.


References
[1] Eric Bauer and Ron Kohavi. An empirical comparison
of voting classification algorithms: bagging, boosting,
and variants. Unpublished manuscript, 1997.
[2] Leo Breiman. Arching classifiers. Annals of Statistics,
to appear.
[3] Harris Drucker and Corinna Cortes. Boosting decision
trees. Advances in Neural Information Processing Systems, (8):479--485, 1996.
[4] Yoav Freund and Robert Schapire. Experiments with
a new boosting algorithm. In Proceedings of the Thirteenth 
International Conference on Machine Learning,
1996.
[5] Yoav Freund and Robert Schapire. A decision-theoretic
generalization of online learning and an application to
boosting. Journal of Computer and System Sciences,
55(1):119--139, 1997.
[6] Jyrki Kivinen and Manfred K. Warmuth. Boosting as
entropy projection. In Proceedings of the Twelfth An
nual Conference on Computational Learning Theory,
1999.
[7] Richard Maclin and David Opitz. An empirical evaluation 
of bagging and boosting. In Prodeedings of
the Fourteenth National Conference on Artificial Intelligence, 1997.
[8] J. R. Quinlan. Bagging, boosting, and c4.5. In Prodeed
ings of the Thirteenth National Conference on Artificial
Intelligence, 1996.
[9] Robert Schapire. Using output codes to boost multi
class machine learning problems. In Proceedings of
the Fourteenth International Conference on Machine
Learning, 1997.
[10] Robert Schapire, Yoav Freund, Peter Bartlett, and
Wee Sun Lee. Boosting the margin: a new explanation 
for the effectiveness of the voting method. Annals
of Statistics, to appear.
[11] Robert Schapire and Yoram Singer. Improved boosting
algorithms using confidencerated predictions. In Proceedings 
of the Eleventh Annual Conference on Computational Learning Theory, 1998.

