Randomized weighted majority algorithm

The randomized weighted majority algorithm is an algorithm in machine learning theory for aggregating expert predictions to a series of decision problems.^[1] It is a simple and effective method based on weighted voting which improves on the mistake bound of the deterministic weighted majority algorithm. In fact, in the limit, its prediction rate can be arbitrarily close to that of the best-predicting expert.

Example

Imagine that every morning before the stock market opens, we get a prediction from each of our "experts" about whether the stock market will go up or down. Our goal is to somehow combine this set of predictions into a single prediction that we then use to make a buy or sell decision for the day. The principal challenge is that we do not know which experts will give better or worse predictions. The RWMA gives us a way to do this combination such that our prediction record will be nearly as good as that of the single expert which, in hindsight, gave the most accurate predictions.

Motivation

In machine learning, the weighted majority algorithm (WMA) is a deterministic meta-learning algorithm for aggregating expert predictions. In pseudocode, the WMA is as follows:

initialize all experts to weight 1
for each round:
    add each expert's weight to the option they predicted
    predict the option with the largest weighted sum
    multiply the weights of all experts who predicted wrongly by  ${\frac {1}{2}}$

Suppose there are $n$ experts and the best expert makes $m$ mistakes. Then, the weighted majority algorithm (WMA) makes at most $2.4(\log _{2}n+m)$ mistakes. This bound is highly problematic for cases with highly error-prone experts. Suppose, for example, the best expert makes a mistake 20% of the time; that is, in $N=100$ rounds using $n=10$ experts, the best expert makes $m=20$ mistakes. Then, the weighted majority algorithm only guarantees an upper bound of $2.4(\log _{2}10+20)\approx 56$ mistakes.

As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on $m$ . In particular, we can do better by introducing randomization. We can draw inspiration from the randomized [[Multiplicative weight update method#Randomized weighted majority algorithm[2][8]|Multiplicative Weights Update Method]] algorithm, where we probabilistically make predictions based on how the experts have performed in the past. Like in the WMA, every time an expert makes a wrong prediction, we decrement their weight. However, in MWUM, instead of deterministically picking the majority vote, we use the weights to make a probability distribution over the actions and draw our action from this distribution.^[2]

Randomized weighted majority algorithm (RWMA)

The randomized weighted majority algorithm is an attempt to improve the dependence of the mistake bound of the WMA on $m$ . Instead of predicting based on majority vote, the weights are used as probabilities (hence the name randomized weighted majority).

Precisely, if $w_{i}$ is the weight of expert $i$ , let $W=\sum _{i}w_{i}$ . We will follow expert $i$ with probability ${\frac {w_{i}}{W}}$ . This results in the following algorithm:

initialize all experts to weight 1.
for each round:
    add all experts' weights together to obtain the total weight  $W$ 
    randomly select an expert; choose expert  $i$  with probability  ${\frac {w_{i}}{W}}$  
    predict as the chosen expert predicts
    multiply the weights of all experts who predicted wrongly by  $\beta$

The goal is to bound the worst-case expected number of mistakes, assuming that the adversary has to select one of the answers as correct before we make our coin toss. This is a reasonable assumption in, for instance, the stock market example provided above: the variance of a stock price should not depend on the opinions of experts that influence private buy or sell decisions, so we can treat the price change as if it was decided before the experts gave their recommendations for the day.

The randomized algorithm is better in the worst case than the deterministic algorithm (weighted majority algorithm): in the latter, the worst case was when the weights were split 50/50. But in the randomized version, since the weights are used as probabilities, there would still be a 50/50 chance of getting it right. In addition, generalizing to multiplying the weights of the incorrect experts by $\beta <1$ instead of strictly ${\frac {1}{2}}$ allows us to trade off between dependence on $m$ and $\log _{2}n$ . This trade-off will be quantified in the analysis section.

Analysis

Let $W_{t}$ denote the total weight and $F_{t}$ denote the fraction of weight on the wrong answers at round $t$ . By definition, $F_{t}$ is the probability that the algorithm makes a mistake on round $t$ . It follows, then, from the linearity of expectation, that if $M$ denotes the total number of mistakes made during the entire process, $E[M]=\sum _{t=1}^{N}F_{t}$ .

Now, notice that after round $t$ , the total weight is decreased by $\ (1-\beta )F_{t}W_{t}$ , since all weights corresponding to a wrong answer are multiplied by $\ \beta$ . It then follows that $W_{t+1}=W_{t}(1-(1-\beta )F_{t})$ . By telescoping, since $W_{1}=n$ , it follows that the total weight after the process concludes is

{\begin{aligned}W=n\prod _{t=1}^{N}(1-(1-\beta )F_{t}).\end{aligned}}

On the other hand, suppose that $\ m$ is the number of mistakes made by the best-performing expert. At the end, this expert has weight $\ \beta ^{m}$ . It follows, then, that the total weight is at least this much; in other words, $\ W\geq \beta ^{m}$ . This inequality and the above result imply

{\begin{aligned}n\prod _{t=1}^{N}(1-(1-\beta )F_{t})\geq \beta ^{m}.\end{aligned}}

Taking the natural logarithm of both sides yields

{\begin{aligned}\ln n+\sum _{t=1}^{N}\ln(1-(1-\beta )F_{t})\geq m\ln \beta .\end{aligned}}

Now, the Taylor series of the natural logarithm is

{\begin{aligned}\ln(1-x)=-x-{\frac {x^{2}}{2}}-{\frac {x^{3}}{3}}-\cdots \end{aligned}}

In particular, it follows that $\ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}$ .
Thus,

{\begin{aligned}\ln n-(1-\beta )\sum _{t=1}^{N}F_{t}\geq m\ln \beta .\end{aligned}}

Recalling that $E[M]=\sum _{t=1}^{N}F_{t}$ and rearranging, it follows that

{\begin{aligned}E[M]\leq {\frac {m\ln(1/\beta )+\ln(n)}{1-\beta }}={\frac {\ln(1/\beta )}{1-\beta }}m+{\frac {1}{1-\beta }}\ln(n).\end{aligned}}

Now, as $\beta \to 1$ from below, the first constant tends to $1$ ; however, the second constant tends to $+\infty$ . To quantify this relationship, define $\varepsilon =1-\beta$ to be the penalty associated with getting a prediction wrong. Then, again applying the Taylor series of the natural logarithm,

{\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}=-{\frac {\ln(\beta )}{1-\beta }}={\frac {-\ln(1-\varepsilon )}{\varepsilon }}={\frac {\varepsilon +{\frac {\varepsilon ^{2}}{2}}+{\frac {\varepsilon ^{3}}{3}}+\cdots }{\varepsilon }}=1+{\frac {\varepsilon }{2}}+O(\varepsilon ^{2})\end{aligned}}

It then follows that the mistake bound, for small $\varepsilon$ , can be written in the form $\ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)$ .

In English, the less that we penalize experts for their mistakes, the more that additional experts will lead to initial mistakes but the closer we get to capturing the predictive accuracy of the best expert as time goes on. In particular, given a sufficiently low value of $\varepsilon$ and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.

To establish a more concrete optimum $\beta$ and more concrete bound on $E(M)$ we fix $n$ and $m$ as constants and ${\frac {\partial }{\partial \epsilon }}\left(-{\frac {{\text{ln}}(1-\epsilon )m}{\epsilon }}+{\frac {{\text{ln}}(n)}{\epsilon }}\right)={\frac {m(\epsilon /(1-\epsilon )+{\text{ln}}(1-\epsilon ))-{\text{ln}}(n)}{\epsilon ^{2}}}$ . We notice that for $\epsilon$ sufficiently close to 0 the derivative is negative, while for $\epsilon$ sufficiently close to 1 the derivative is positive, furthermore, this expression is strictly increasing with respect to $\epsilon$ . Thus We must have a local minimum for some $0<\epsilon <1$ , specifically we see that the upper bound of $E(M)$ is minimized when $m(\epsilon /(1-\epsilon )+{\text{ln}}(1-\epsilon ))-{\text{ln}}(n)=0\iff {\frac {\epsilon }{1-\epsilon }}+{\text{ln}}(1-\epsilon )={\frac {{\text{ln}}(n)}{m}}$ . This final equality tells us that as m increases we want to choose a smaller $\epsilon$ (ergo, larger $\beta$ ) to minimize expected error, while as n increases we want to choose a larger $\epsilon$ (ergo, smaller $\beta$ ).

Revisiting the motivation

Recall that the motivation for the randomized weighted majority algorithm was given by an example where the best expert makes a mistake 20% of the time. Precisely, in $N=100$ rounds, with $n=10$ experts, where the best expert makes $m=20$ mistakes, the deterministic weighted majority algorithm only guarantees an upper bound of $2.4(\log _{2}10+20)\approx 56$ . By the analysis above, it follows that minimizing the number of worst-case expected mistakes is equivalent to minimizing the function

{\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}20+{\frac {1}{1-\beta }}\ln(10).\end{aligned}}

Computational methods show that the optimal value is roughly $\beta \approx 0.641$ , which results in the minimal worst-case number of expected mistakes of $E[M]\approx 31.19$ . When the number of rounds is increased (say, to $N=1000000$ ) while the accuracy rate of the best expert is kept the same the improvement can be even more dramatic; the weighted majority algorithm guarantees only a worst-case mistake rate of 48.0%, but the randomized weighted majority algorithm, when properly tuned to the optimal value of $\varepsilon \approx 0.0117$ , achieves a worst-case mistake rate of 20.2%.

Uses of Randomized Weighted Majority Algorithm (RWMA)

The Randomized Weighted Majority Algorithm can be used to combine multiple algorithms in which case RWMA can be expected to perform nearly as well as the best of the original algorithms in hindsight.

Furthermore, one can apply the Randomized Weighted Majority Algorithm in situations where experts are making choices that cannot be combined (or can't be combined easily). For example, RWMA can be applied to repeated game-playing or the online shortest path problem. In the online shortest path problem, each expert is telling you a different way to drive to work. You pick one path using RWMA. Later you find out how well you would have done using all of the suggested paths and penalize appropriately. To do this right, we want to generalize from "losses" of 0 or 1 to losses in [0,1]. The goal is to have an expected loss not much larger than the loss of the best expert. We can generalize the RWMA by applying a penalty of $\beta ^{\text{loss}}$ (i.e. two losses of one half result in the same weight as one loss of 1 and one loss of 0). The analysis given in the previous section does not change significantly.

RWMA can be generalized to cases where the problem at hand does not have binary mistake variables. Hedge algorithm can be used for instances where at each iteration all actions incur a continuous loss value.

Extensions

Multi-armed bandit problem.
Efficient algorithm for some cases with many experts.
Sleeping experts/"specialists" setting.

References

^ Littlestone, N.; Warmuth, M. (1994). "The Weighted Majority Algorithm". Information and Computation. 108 (2): 212–261. doi:10.1006/inco.1994.1009.
^ "COS 511: Foundations of Machine Learning" (PDF). 20 March 2006.