The weighted majority algorithm
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 256-261
- https://doi.org/10.1109/sfcs.1989.63487
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.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- The weighted majority algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Learning quickly when irrelevant attributes abound: A new linear-threshold algorithmMachine Learning, 1988
- On the Uniform Convergence of Relative Frequencies of Events to Their ProbabilitiesTheory of Probability and Its Applications, 1971