Weighted Majority Algorithm (WMA)

In machine learning, Weighted Majority Algorithm (WMA) is a meta-learning algorithm used to construct a compound algorithm from a pool of prediction algorithms, which could be any type of learning algorithms, classifiers, or even real human experts. The algorithm assumes that we have no prior knowledge about the accuracy of the algorithms in the pool, but there are sufficient reasons to believe that one or more will perform well.

In machine learningWeighted Majority Algorithm (WMA) is a meta-learning algorithm used to construct a compound algorithm from a pool of prediction algorithms, which could be any type of learning algorithms, classifiers, or even real human experts. The algorithm assumes that we have no prior knowledge about the accuracy of the algorithms in the pool, but there are sufficient reasons to believe that one or more will perform well.

Assume that the problem is a binary decision problem. To construct the compound algorithm, a positive weight is given to each of the algorithms in the pool. The compound algorithm then collects weighted votes from all the algorithms in the pool, and gives the prediction that has a higher vote. If the compound algorithm makes a mistake, the algorithms in the pool that contributed to the wrong predicting will be discounted by a certain ratio β where 0<β<1.

It can be shown that the upper bounds on the number of mistakes made in a given sequence of predictions from a pool of algorithms  \mathbf{A}  is

\mathbf{O(log|A|+m)}

if one algorithm in  \mathbf{x}_i  makes at most  \mathbf{m}  mistakes.

There are many variations of the Weighted Majority Algorithm to handle different situations, like shifting targets, infinite pools, or randomized predictions. The core mechanism remain similar, with the final performances of the compound algorithm bounded by a function of the performance of the specialist (best performing algorithm) in the pool.

See also[edit]

References[edit]

  • Littlestone,N. & Warmuth,M. (1989). Weighted Majority Algorithm. IEEE Symposium on Foundations of Computer Science.
RELATED ARTICLESExplain
Machine Learning Methods & Algorithms
Supervised learning
Ensemble learning
Boosting (meta-algorithm)
Weighted Majority Algorithm (WMA)
LogitBoost
Randomized weighted majority algorithm
Graph of this discussion
Enter the title of your article


Enter a short (max 500 characters) summation of your article
Enter the main body of your article
Lock
+Comments (0)
+Citations (0)
+About
Enter comment

Select article text to quote
welcome text

First name   Last name 

Email

Skip