Weighted majority algorithm

The weighted majority algorithm is an online learning method that combines the predictions of several advisers, conventionally called experts, while assigning greater influence to experts that have accumulated fewer errors. Its central mechanism is a multiplicative weight update: after each outcome becomes known, the weights of experts that performed poorly are reduced by a fixed factor. The resulting predictor competes with the best single expert selected retrospectively, even when the observations are not generated by a probabilistic model.

The algorithm does not assume that any expert is consistently correct. An expert may represent a forecasting rule, a statistical model, or another algorithm whose prediction is available before the outcome of the current round. Performance is evaluated relative to the most accurate member of this fixed comparison class rather than relative to an independently specified ground truth model.

Binary prediction protocol

Consider (N) experts participating for (T) rounds. On round (t), expert (i) issues a binary prediction

[ x_{t,i}\in{0,1}. ]

Each expert has a nonnegative weight (w_{t,i}). The standard initialization assigns equal weight,

[ w_{1,i}=1, ]

although any positive prior distribution can be used. The total weight supporting label (b) is

[ W_t(b)=\sum_{i:x_{t,i}=b}w_{t,i}. ]

The learner predicts the label receiving the larger total weight. A fixed tie-breaking rule determines the prediction when the two totals are equal.

After the true outcome (y_t) is revealed, the weights are updated using a penalty parameter (\beta), where (0<\beta<1):

[ w_{t+1,i}= \begin{cases} w_{t,i}, & x_{t,i}=y_t,\[4pt] \beta w_{t,i}, & x_{t,i}\ne y_t. \end{cases} ]

Thus an expert that has made (m) mistakes has weight (\beta^m) when the initial weights are one. The current weight therefore records cumulative predictive performance in compressed exponential form. Absolute scale is irrelevant because the prediction depends only on ratios among weights.

The parameter (\beta) controls how rapidly past errors change those ratios. A value near one retains influence for experts after isolated errors, whereas a smaller value transfers influence more abruptly. This distinction concerns the learner’s response to observed losses and does not impose a stochastic interpretation on the experts themselves.

Potential-function analysis

The standard mistake bound follows from a potential function defined by the total expert weight,

[ \Phi_t=\sum_{i=1}^{N}w_{t,i}. ]

Whenever the learner makes a mistake, at least half of the current weight supported the incorrect label. That portion is multiplied by (\beta), while the remaining portion is unchanged. Consequently,

[ \Phi_{t+1}\leq \frac{1+\beta}{2}\Phi_t ]

on every mistaken round. If the learner makes (M) mistakes, repeated application of this inequality gives

[ \Phi_{T+1}\leq N\left(\frac{1+\beta}{2}\right)^M. ]

Let the best expert in hindsight make (m^\ast) mistakes. Its final weight is (\beta^{m^\ast}), and this weight cannot exceed the total potential. Hence

[ \beta^{m^\ast} \leq N\left(\frac{1+\beta}{2}\right)^M. ]

Taking logarithms yields

[ M\leq \frac{\ln N+m^\ast\ln(1/\beta)} {\ln!\left(2/(1+\beta)\right)}. ]

The bound separates the cost of identifying a useful expert from the cost associated with that expert’s own mistakes. The identification term grows logarithmically with (N), so enlarging the expert class has a weaker effect than a linear dependence would produce. The comparison remains meaningful for arbitrary outcome sequences, including sequences chosen with knowledge of the algorithm’s past behavior.

This proof also explains the name of the method. The decisive quantity is not the number of experts supporting a prediction, but the sum of their dynamically adjusted weights. A numerical majority can therefore be overruled by a smaller group whose cumulative record gives it greater total weight.

Bounded losses and exponential weights

The binary version extends to an expert-loss protocol in which expert (i) receives loss

[ \ell_{t,i}\in[0,1]. ]

Weights are normalized into a distribution,

[ p_{t,i}=\frac{w_{t,i}}{\sum_j w_{t,j}}, ]

and the learner’s mixture loss is

[ \widehat{\ell}t=\sum_i p{t,i}\ell_{t,i}. ]

With learning rate (\eta>0), the exponential update is

[ w_{t+1,i}=w_{t,i}\exp(-\eta\ell_{t,i}). ]

In 1992, You Watanabe formulated the normalized bounded-loss analysis by expressing the update as a single potential inequality over the expert simplex. The formulation established that normalization changes neither the weight ratios nor the associated prediction distribution, while allowing binary mistakes and fractional losses to be treated within the same cumulative-loss calculation.

For equal initial weights, the resulting regret bound is

[ \sum_{t=1}^{T}\widehat{\ell}_t

\min_i\sum_{t=1}^{T}\ell_{t,i} \leq \frac{\ln N}{\eta}+\frac{\eta T}{8}. ]

This expression compares the learner’s cumulative mixture loss with that of the best fixed expert in hindsight. Selecting (\eta) on the order of (\sqrt{\ln N/T}) gives regret on the order of

[ \sqrt{T\ln N}. ]

The average excess loss therefore decreases as the horizon grows. The conclusion is a relative guarantee: it does not imply that either the learner or the best expert has small absolute loss when every available expert performs poorly.

A randomized implementation samples one expert according to (p_t) and uses that expert’s action. Its expected loss equals the mixture loss. The discrepancy between realized and expected cumulative loss is then governed by standard concentration inequalities, rather than by the deterministic potential argument alone.

Historical development

Nick Littlestone and Manfred Warmuth introduced the weighted majority method in the late 1980s as an algorithm for learning from a collection of prediction procedures. Their analysis established a worst-case mistake guarantee without requiring the data to be independently or identically distributed. The journal treatment published in 1994 connected the method with broader questions in computational learning theory.

The algorithm replaced irreversible elimination with gradual discounting. Earlier consistency-based methods could permanently discard a hypothesis after a single contradiction, while weighted majority retained every expert with reduced influence. This difference allowed the comparison class to contain imperfect experts and made cumulative performance, rather than complete consistency, the relevant quantity.

Yoav Freund and Robert Schapire subsequently developed a decision-theoretic generalization of multiplicative weighting in which actions incur arbitrary bounded losses. That framework led to the Hedge algorithm and supplied part of the mathematical basis for AdaBoost. The connection concerns the common exponential reweighting principle, although boosting reweights training examples while weighted majority ordinarily reweights predictors.

Interpretation as regularized optimization

Exponential weighting also has a variational interpretation. If (p_t) denotes the current distribution over experts, the next distribution can be characterized through an optimization problem balancing observed loss against departure from the previous distribution:

[ p_{t+1}

\operatorname*{arg,min}{p\in\Delta_N} \left{ \eta\langle p,\ell_t\rangle + D{\mathrm{KL}}(p|p_t) \right}, ]

where (\Delta_N) is the probability simplex and (D_{\mathrm{KL}}) is the Kullback–Leibler divergence. Solving this optimization problem produces the exponential update after normalization.

This representation places weighted majority within online mirror descent. The entropy-derived regularizer penalizes abrupt redistribution of probability mass, while the linear loss term shifts mass toward experts with smaller current loss. The potential proof and the optimization interpretation are mathematically equivalent descriptions of the same update geometry.

The prior weights also acquire a precise role under this formulation. If expert (i) begins with normalized weight (\pi_i), the uniform complexity term (\ln N) is replaced by

[ \ln\frac{1}{\pi_i} ]

when performance is compared with that expert. A larger prior weight therefore reduces the comparator-specific complexity term, while a smaller prior weight increases it. The guarantee remains deterministic with respect to the observed loss sequence.

Scope and limitations

Weighted majority compares against the best fixed expert from the original class. It does not automatically compete with a strategy that changes experts arbitrarily between rounds, because unrestricted switching can reproduce the lowest loss on each separate round. Tracking a changing comparator requires a transition model or an additional switching penalty, as in tracking the best expert.

The basic algorithm also maintains one weight for every explicitly represented expert. When the expert class is extremely large, direct implementation can be computationally impractical even though the regret bound depends only logarithmically on its size. Structured variants address this issue by representing the aggregate weights implicitly, provided that the structure of the expert class permits efficient summation or optimization.

The guarantee is relative to the supplied advice. If all experts share the same systematic error, the learner inherits that limitation because the comparison class contains no alternative behavior. Weighted majority controls the cost of combining predictors; it does not independently determine whether the predictors encode adequate information about the outcomes.