nips nips2011 nips2011-49 nips2011-49-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Charles Dubout, Francois Fleuret
Abstract: Classical Boosting algorithms, such as AdaBoost, build a strong classifier without concern about the computational cost. Some applications, in particular in computer vision, may involve up to millions of training examples and features. In such contexts, the training time may become prohibitive. Several methods exist to accelerate training, typically either by sampling the features, or the examples, used to train the weak learners. Even if those methods can precisely quantify the speed improvement they deliver, they offer no guarantee of being more efficient than any other, given the same amount of time. This paper aims at shading some light on this problem, i.e. given a fixed amount of time, for a particular problem, which strategy is optimal in order to reduce the training loss the most. We apply this analysis to the design of new algorithms which estimate on the fly at every iteration the optimal trade-off between the number of samples and the number of features to look at in order to maximize the expected loss reduction. Experiments in object recognition with two standard computer vision data-sets show that the adaptive methods we propose outperform basic sampling and state-of-the-art bandit methods. 1
[1] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235–256, 2002.
[2] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2003.
[3] R. Busa-Fekete and B. Kegl. Accelerating AdaBoost using UCB. JMLR W&CP;, Jan 2009.
[4] R. Busa-Fekete and B. Kegl. Fast Boosting using adversarial bandits. In ICML, 2010.
[5] N. Duffield, C. Lund, and M. Thorup. Priority sampling for estimation of arbitrary subset sums. J. ACM, 54, December 2007.
[6] G. Escudero, L. M` rquez, and G. Rigau. Boosting applied to word sense disambiguation. a Machine Learning: ECML 2000, pages 129–141, 2000.
[7] F. Fleuret and D. Geman. Stationary features and cat detection. Journal of Machine Learning Research (JMLR), 9:2549–2578, 2008.
[8] Z. Kalal, J. Matas, and K. Mikolajczyk. Weighted sampling for large-scale Boosting. British machine vision conference, 2008.
[9] A. Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Master’s thesis, 2009. http://www.cs.toronto.edu/˜kriz/cifar.html.
[10] Y. Lecun and C. Cortes. The mnist database of handwritten digits. http://yann.lecun. com/exdb/mnist/. 9