article · 1992

THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16)

Cited by 0Abstract and details only

Abstract

We study 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. We are interested in the case that the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner 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. We call this method the Weighted Majority Algorithm. We show that this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will make at most c(log |A| + m) mistakes on that sequence, where c is fixed constant.

Cite this paper

APA 7

Littlestone, N., & Warmuth, M. K. (1992). THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16).

MLA 9

Littlestone, Nick, and Manfred K. Warmuth. “THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16).” 1992.

Chicago

Littlestone, Nick, and Manfred K. Warmuth. 1992. “THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16).”

Harvard

Littlestone, N. and Warmuth, M.K. (1992) ‘THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16)’.

BibTeX

@article{littlestone1992weighted,
  title = {{THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16)}},
  author = {Littlestone, Nick and Warmuth, Manfred K.},
  year = {1992}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.