1989 TheWeightedMajorityAlgorithm

• (Littlestone et al., 1989) ⇒ Nick Littlestone, and Manfred K. Warmuth. (1989). “The Weighted Majority Algorithm.” In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1989.63487

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22The+weighted+majority+algorithm%22+1989
• http://dl.acm.org/citation.cfm?id=1398514.1398700&preflayout=flat#citedby

Quotes

Author Keywords

• error bounds; weighted majority algorithm; prediction algorithms; weighted voting

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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1989 TheWeightedMajorityAlgorithm	Nick Littlestone Manfred K. Warmuth			The Weighted Majority Algorithm				10.1109/SFCS.1989.63487