We study boosting in the filtering setting, where the booster draws examples from an oracle instead of using a fixed training set and so may train efficiently on very large datasets. Our algorithm, which is based on a logistic regression technique proposed by Collins, Schapire, & Singer, represents the first boostingbyfiltering algorithm which is truly adaptive and does not need the less realistic assumptions required by previous work. Moreover, we give the first proof that the algorithm of Collins et al. is a strong PAC learner, albeit within the filtering setting. Our proofs demonstrate the algorithm’s strong theoretical properties for both classification and conditional probability estimation, and we validate these results through extensive experiments. Empirically, our algorithm proves more robust to noise and overfitting than batch boosters in conditional probability estimation and proves competitive in classification.
Author Information
Joseph K Bradley (University of California, Berkeley)
Robert E Schapire (MIcrosoft Research)
Robert Schapire received his ScB in math and computer science from Brown University in 1986, and his SM (1988) and PhD (1991) from MIT under the supervision of Ronald Rivest. After a short postdoc at Harvard, he joined the technical staff at AT&T Labs (formerly AT&T Bell Laboratories) in 1991 where he remained for eleven years. At the end of 2002, he became a Professor of Computer Science at Princeton University. His awards include the 1991 ACM Doctoral Dissertation Award, the 2003 Gödel Prize and the 2004 Kanelakkis Theory and Practice Award (both of the last two with Yoav Freund). His main research interest is in theoretical and applied machine learning.
More from the Same Authors

2016 Poster: Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale »
Firas Abuzaid · Joseph K Bradley · Feynman T Liang · Andrew Feng · Lee Yang · Matei Zaharia · Ameet S Talwalkar 
2014 Poster: A DriftingGames Analysis for Online Learning and Applications to Boosting »
Haipeng Luo · Robert E Schapire 
2014 Poster: Parallel Double Greedy Submodular Maximization »
Xinghao Pan · Stefanie Jegelka · Joseph Gonzalez · Joseph K Bradley · Michael Jordan 
2010 Poster: A Reduction from Apprenticeship Learning to Classification »
Umar Syed · Robert E Schapire 
2010 Oral: A Theory of Multiclass Boosting »
Indraneel Mukherjee · Robert E Schapire 
2010 Poster: A Theory of Multiclass Boosting »
Indraneel Mukherjee · Robert E Schapire 
2010 Poster: NonStochastic Bandit Slate Problems »
Satyen Kale · Lev Reyzin · Robert E Schapire 
2007 Oral: A Multiplicative Weights Algorithm for Apprenticeship Learning »
Umar Syed · Robert E Schapire 
2007 Poster: FilterBoost: Regression and Classification on Large Datasets »
Joseph K Bradley · Robert E Schapire 
2007 Poster: A Multiplicative Weights Algorithm for Apprenticeship Learning »
Umar Syed · Robert E Schapire 
2007 Tutorial: Theory and Applications of Boosting »
Robert E Schapire