The weighted majority algorithm
Abstract
The construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes is studied. It is assumed that the learner has reason to believe that one of some pool of known algorithms will perform well but does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. It is called the weighted majority algorithm and is shown to be robust with respect to errors in the data. Various versions of the weighted majority algorithm are discussed, and error bounds for them that are closely related to the error bounds of the best algorithms of the pool are proved.>
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The first instances of ensemble learning include Weighted Majority Algorithm, boosting, bootstrap aggregating (bagging), and Random Forests.
“The first instances of ensemble learning include Weighted Majority Algorithm (WMA) [279], boosting [403], bootstrap aggregating (or bagging) [75], and Random Forests (RF) [191].”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [279]
Cites
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Springer eBooks · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,160 · see citing works
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448 · see citing works
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839 · see citing works
Self-citationLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1023/a:1022869011914 · Cited by 1,514 · see citing works
Self-citationMistake bounds and logarithmic linear-threshold learning algorithms
Littlestone, N. (1990) · Cited by 183 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Boutaba, R., Salahuddin, M. A., Limam, N., Ayoubi, S., Shahriar, N., Estrada-Solano, F., & Caicedo, O. M. (2018) · Journal of Internet Services and Applications · doi:10.1186/s13174-018-0087-2 · Cited by 1,036 · see citing works
Automated trading with performance weighted random forests and seasonality
Booth, A., Gerding, E., & McGroarty, F. (2014) · Expert Systems with Applications · doi:10.1016/j.eswa.2013.12.009 · Cited by 154 · see citing works
Smart Experts for Network State Estimation
Edalat, Y., Ahn, J.-S., & Obraczka, K. (2016) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2016.2586506 · Cited by 27 · see citing works
- Authors
- Littlestone, N., & Warmuth, M. K.
- Affiliations
- Harvard University (US)
- University of California, Santa Cruz (US)
- Venue
- 30th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 1989
- Pages
- 256-261
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2054716087
- Cited by
- 295
- References
- 5
- Citations by year
- 2026: 3 · 2025: 3 · 2024: 3 · 2023: 7 · 2022: 2 · 2021: 8 · 2020: 7 · 2019: 6 · 2018: 19 · 2017: 14 · 2016: 15 · 2015: 12 · 2014: 27 · 2013: 25 · 2012: 12
- FWCI
- 7.00
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Keywords
- weighted majority algorithm, boosting, weighted voting, prediction algorithm, error bounds, noisy data robustness, online learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
