The randomized weighted majority algorithm is an algorithm in machine learning theory for aggregating expert predictions to a series of decision problems.
In fact, in the limit, its prediction rate can be arbitrarily close to that of the best-predicting expert.
The principal challenge is that we do not know which experts will give better or worse predictions.
Then, the weighted majority algorithm only guarantees an upper bound of
As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on
Drawing inspiration from the Multiplicative Weights Update Method algorithm, we will probabilistically make predictions based on how the experts have performed in the past.
Similarly to the WMA, every time an expert makes a wrong prediction, we will decrement their weight.
Mirroring the MWUM, we will then use the weights to make a probability distribution over the actions and draw our action from this distribution (instead of deterministically picking the majority vote as the WMA does).
[2] The randomized weighted majority algorithm is an attempt to improve the dependence of the mistake bound of the WMA on
Instead of predicting based on majority vote, the weights, are used as probabilities for choosing the experts in each round and are updated over time (hence the name randomized weighted majority).
This results in the following algorithm: 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.
In addition, generalizing to multiplying the weights of the incorrect experts by
denote the fraction of weight placed on experts which predict the wrong answer at round
denotes the total number of mistakes made during the entire process,
, it follows that the total weight after the process concludes is On the other hand, suppose that
Then, again applying the Taylor series of the natural logarithm, It then follows that the mistake bound, for small
and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.
(so that their ratio is sufficiently small), we can assign we can obtain an upper bound on the number of mistakes equal to This implies that the "regret bound" on the algorithm (that is, how much worse it performs than the best expert) is sublinear, at
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.
mistakes, the deterministic weighted majority algorithm only guarantees an upper bound of
By the analysis above, it follows that minimizing the number of worst-case expected mistakes is equivalent to minimizing the function Computational methods show that the optimal value is roughly
, which results in the minimal worst-case number of expected mistakes of
) 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
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.
The randomized weighted majority algorithm has been proposed as a new method for several practical software applications, particularly in the domains of bug detection and cyber-security.
[3] [4] For instance, Varsha and Madhavu (2021) describe how the randomized weighted majority algorithm can be used to replace conventional voting within a random forest classification approach to detect insider threats.
Using experimental results, they show that this approach obtained a higher level of accuracy and recall compared to the standard random forest algorithm.
Moustafa et al. (2018) have studied how an ensemble classifier based on the randomized weighted majority algorithm could be used to detect bugs earlier in the software development process, after being trained on existing software repositories.