swMATH ID: 8517
Software Authors: Freund, Yoav; Schapire, Robert E.
Description: A decision-theoretic generalization of on-line learning and an application to boosting. In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone-Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in \(bfR^n\). In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.
Homepage: http://www.sciencedirect.com/science/article/pii/S002200009791504X
Keywords: boosting algorithm; learning functions
Related Software: UCI-ml; C4.5; ElemStatLearn; R; LIBSVM; bootstrap; PRMLT; XGBoost; SMOTE; BoosTexter; Scikit; AdaCost; AdaBoost-SAMME; AlexNet; ImageNet; gbm; darch; AdaBoost.RT; rpart; randomForest
Cited in: 410 Documents
all top 5

Cited by 972 Authors

11 Schapire, Robert E.
8 Zhang, Chunxia
7 Freund, Yoav
7 Zhang, Jiangshe
5 Mansour, Yishay
5 Warmuth, Manfred K.
5 Zhou, Zhihua
4 Kanamori, Takafumi
4 Rudin, Cynthia
4 Takimoto, Eiji
4 Vovk, Vladimir G.
3 Aria, Massimo
3 Bartlett, Peter L.
3 Busa-Fekete, Róbert
3 Carrizosa, Emilio
3 Cesa-Bianchi, Nicolò
3 D’Ambrosio, Antonio
3 Geurts, Pierre
3 Hastie, Trevor John
3 Jin, Rong
3 Khachay, Mikhail Yur’evich
3 Kuncheva, Ludmila I.
3 Long, Philip M.
3 Nielsen, Frank
3 Nock, Richard
3 Romero Morales, Dolores
3 Servedio, Rocco A.
3 Siciliano, Roberta
3 Wang, Guanwei
3 Wehenkel, Louis A.
3 Wu, Yingnian
3 Yu, Bin
3 Zhang, Tong
3 Zhu, Song-Chun
2 Biau, Gérard
2 Bourel, Mathias
2 Brown, Gavin
2 Cadre, Benoît
2 Cai, Suxian
2 Chen, Jie
2 Chipman, Hugh A.
2 Crammer, Koby
2 Darnstädt, Malte
2 Daubechies, Ingrid Chantal
2 Davison, Anthony C.
2 Eckstein, Jonathan
2 Ernst, Damien
2 Feng, Jufu
2 Figueiras-Vidal, Aníbal Ramón
2 George, Edward I.
2 Gey, Servane
2 Goldberg, Noam
2 Gray, J. Brian
2 Gweon, Hyukjun
2 Han, Guoqiang
2 Hatano, Kohei
2 Hayashi, Kenichi
2 Hazan, Elad
2 Holmes, Christopher C.
2 Hothorn, Torsten
2 Huang, Hanwen
2 Huerta, Ramón
2 Jasra, Ajay
2 Jiang, Wenxin
2 Kale, Satyen
2 Kamel, Mohamed S.
2 Kégl, Balázs
2 Kontorovich, Leonid Aryeh
2 Koolen, Wouter M.
2 Kotłowski, Wojciech
2 Lecué, Guillaume
2 Lee, Yoonkyung
2 Li, Shu
2 Lopes, Miles E.
2 Lugosi, Gábor
2 Maruoka, Akira
2 McCulloch, Robert Edward
2 Meynet, Julien
2 Murphy, Thomas Brendan
2 Ries, Christoph
2 Rodriguez-Lujan, Irene
2 Shamir, Ohad
2 Simon, Hans-Ulrich
2 Singer, Yoram
2 Takeda, Akiko
2 Takenouchi, Takashi
2 Thiran, Jean-Philippe
2 Tibshirani, Robert John
2 V’yugin, Vladimir V.
2 Wang, Liwei
2 Wilbur, W. John
2 Wong, Hau-San
2 Wu, Yunfeng
2 Yang, Qinglong
2 Yang, Shanshan
2 Yang, Tianbao
2 Yeganova, Lana E.
2 Yeung, Dit-Yan
2 You, Jane
2 Yu, Zhiwen
...and 872 more Authors
all top 5

Cited in 127 Serials

42 Machine Learning
39 Pattern Recognition
20 The Annals of Statistics
17 Computational Statistics and Data Analysis
13 Journal of Computer and System Sciences
13 Theoretical Computer Science
11 Journal of Machine Learning Research (JMLR)
8 European Journal of Operational Research
7 Artificial Intelligence
7 Statistical Science
7 Neural Networks
7 The Annals of Applied Statistics
6 Computational Statistics
5 Information Sciences
5 Journal of Classification
5 Mathematical Problems in Engineering
5 Data Mining and Knowledge Discovery
5 Journal of Applied Statistics
4 New Generation Computing
4 Annals of Mathematics and Artificial Intelligence
4 Computational Biology and Chemistry
4 Advances in Data Analysis and Classification. ADAC
4 Journal of Computational and Graphical Statistics
3 Mathematics of Operations Research
3 Operations Research
3 Computers & Operations Research
3 Annals of Operations Research
3 Automation and Remote Control
3 Journal of Statistical Computation and Simulation
3 Computational & Mathematical Methods in Medicine
3 Statistical Analysis and Data Mining
3 Electronic Journal of Statistics
3 Statistics and Computing
3 Journal of Theoretical Biology
2 Computers & Mathematics with Applications
2 Computer Methods in Applied Mechanics and Engineering
2 Applied Mathematics and Computation
2 Journal of Econometrics
2 Quarterly of Applied Mathematics
2 SIAM Journal on Computing
2 Statistics & Probability Letters
2 International Journal of Approximate Reasoning
2 International Journal of Computer Vision
2 Complexity
2 Bernoulli
2 INFORMS Journal on Computing
2 Quantitative Finance
2 Statistical Methods and Applications
2 Journal of Statistical Mechanics: Theory and Experiment
2 Journal of Zhejiang University. Science A
2 Risk and Decision Analysis
1 Discrete Applied Mathematics
1 Information Processing Letters
1 Journal of Computational Physics
1 Physics Reports
1 Chaos, Solitons and Fractals
1 Annals of the Institute of Statistical Mathematics
1 Automatica
1 British Journal of Mathematical & Statistical Psychology
1 Fuzzy Sets and Systems
1 Journal of the American Statistical Association
1 Journal of Computational and Applied Mathematics
1 Journal of Multivariate Analysis
1 Journal of Statistical Planning and Inference
1 Kybernetes
1 Mathematics and Computers in Simulation
1 Insurance Mathematics & Economics
1 Acta Mathematicae Applicatae Sinica. English Series
1 Information and Computation
1 Computational Mechanics
1 Journal of Economic Dynamics & Control
1 Mathematical and Computer Modelling
1 SIAM Journal on Discrete Mathematics
1 Journal of Intelligent & Robotic Systems
1 The Annals of Applied Probability
1 Journal of Global Optimization
1 Games and Economic Behavior
1 Proceedings of the National Academy of Sciences of the United States of America
1 Mathematical Programming. Series A. Series B
1 Celestial Mechanics and Dynamical Astronomy
1 SIAM Journal on Optimization
1 Test
1 Journal of Computer and Systems Sciences International
1 Applied and Computational Harmonic Analysis
1 Statistical Papers
1 Advances in Applied Clifford Algebras
1 Top
1 The Journal of Artificial Intelligence Research (JAIR)
1 The Journal of Fourier Analysis and Applications
1 European Series in Applied and Industrial Mathematics (ESAIM): Probability and Statistics
1 Nonlinear Dynamics
1 Abstract and Applied Analysis
1 Soft Computing
1 Mathematical Methods of Operations Research
1 Journal of Combinatorial Optimization
1 Journal of the Royal Statistical Society. Series B. Statistical Methodology
1 Informatica (Vilnius)
1 Statistical Inference for Stochastic Processes
1 Journal of Systems Science and Complexity
1 Natural Computing
...and 27 more Serials

Citations by Year