Randomized weighted majority algorithm
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 RWMA gives us a way to do this combination such that our prediction record will be nearly as good as that of the single best expert in hindsight.
initialize all experts to weight 1. for each round: poll all the experts and predict based on a weighted majority vote of their predictions. cut in half the weights of all experts that make a mistake.
Suppose there are experts and the best expert makes mistakes. The weighted majority algorithm (WMA) makes at most mistakes, which is not a very good bound. We can do better by introducing randomization.
Randomized weighted majority algorithm (RWMA)
The nonrandomized weighted majority algorithm (WMA) only guarantees an upper bound of , which is problematic for highly error-prone experts (e.g. the best expert still makes a mistake 20% of the time.) Suppose we do rounds using experts. If the best expert makes mistakes, we can only guarantee an upper bound of on our number of mistakes.
As this is a known limitation of WMA, attempts to improve this shortcoming have been explored in order to improve the dependence on . Instead of predicting based on majority vote, the weights are used as probabilities: hence the name randomized weighted majority. If is the weight of expert , let . We will follow expert with probability . The goal is to bound the worst-case expected number of mistakes, assuming that the adversary (the world) has to select one of the answers as correct before we make our coin toss. Why is this better in the worst case? Idea: the worst case for the deterministic algorithm (weighted majority algorithm) was when the weights split 50/50. But, now it is not so bad since we also have a 50/50 chance of getting it right. Also, to trade-off between dependence on and , we will generalize to multiply by , instead of necessarily by .
At the -th round, define to be the fraction of weight on the wrong answers. so, is the probability we make a mistake on the -th round. Let denote the total number of mistakes we made so far. Furthermore, we define , using the fact that expectation is additive. On the -th round, becomes . Reason: on fraction, we are multiplying by . So,
Let's say that is the number of mistakes of the best expert so far. We can use the inequality . Now we solve. First, take the natural log of both sides. We get: , Simplify:
Now, use , and the result is:
Let's see if we made any progress:
If , we get, ,
if , we get, .
so we can see we made progress. Roughly, of the form .
Uses of Randomized weighted Majority(RWMN)
Can use to combine multiple algorithms to do nearly as well as best in hindsight.
can apply Randomized weighted majority algorithm in situations where experts are making choices that cannot be combined (or can't be combined easily).For instance, repeated game-playing or 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 using Randomized weighted majority algorithm. Later you find out how well you would have done, and penalize appropriately. To do this right, we want to generalize from just "losS" of 0 to 1 to losses in [0,1]. Goal of having expected loss be not too much worse than loss of best expert.We generalize by penalize , meaning having two examples of loss gives same weight as one example of loss 1 and one example of loss 0 (Analysis still oes through).
- "Bandit" problem
- Efficient algorithm for some cases with many experts.
- Sleeping experts/"specialists" setting.
- Littlestone, N.; Warmuth, M. (1994). "The Weighted Majority Algorithm". Information and Computation 108: 212–261. doi:10.1006/inco.1994.1009.