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.
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 benearly as good as that of the single expert which, in hindsight, gave the most accurate predictions.
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
| 1 | |
| 2 |
Suppose there are
n
m
2.4(log2n+m)
N=100
n=10
m=20
2.4(log210+20) ≈ 56
As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on
m
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
m
Precisely, if
wi
i
W=\sumiwi
i
| wi | |
| W |
initialize all experts to weight 1. for each round: add all experts' weights together to obtain the total weight
W
i
| wi | |
| W |
\beta
The goal is to bound the worst-case expected number of mistakes,assuming that the adversary has to select one of the answersas 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
| 1 | |
| 2 |
m
log2n
Let
Wt
t
Ft
t
N
By definition,
Ft
t
M
E[M]=
| N | |
| \sum | |
| t=1 |
Ft
After round
t
(1-\beta)FtWt
\beta<1
Wt+1=Wt(1-(1-\beta)Ft)
W1=n
\begin{align}W=n
| N | |
| \prod | |
| t=1 |
(1-(1-\beta)Ft).\end{align}
On the other hand, suppose that
m
\betam
W\geq\betam
\begin{align}n
| N | |
| \prod | |
| t=1 |
(1-(1-\beta)Ft)\geq\betam.\end{align}
Taking the natural logarithm of both sides yields
\begin{align}lnn+
| N | |
| \sum | |
| t=1 |
ln(1-(1-\beta)Ft)\geqmln\beta.\end{align}
Now, the Taylor series of the natural logarithm is
\begin{align}ln(1-x)=-x-
| x2 | |
| 2 |
-
| x3 | |
| 3 |
- … \end{align}
In particular, it follows that
ln(1-(1-\beta)Ft)<-(1-\beta)Ft
\begin{align}lnn-(1-\beta)
| N | |
| \sum | |
| t=1 |
Ft\geqmln\beta.\end{align}
Recalling that
E[M]=
| N | |
| \sum | |
| t=1 |
Ft
\begin{align}E[M]\leq
| mln(1/\beta)+ln(n) | |
| 1-\beta |
=
| ln(1/\beta) | |
| 1-\beta |
m+
| 1 | |
| 1-\beta |
ln(n).\end{align}
Now, as
\beta\to1
1
+infty
\varepsilon=1-\beta
\begin{align}
| ln(1/\beta) | |
| 1-\beta |
=-
| ln(\beta) | |
| 1-\beta |
=
| -ln(1-\varepsilon) | |
| \varepsilon |
=
| |||||||||
| \varepsilon |
=1+
| \varepsilon | |
| 2 |
+O(\varepsilon2)\end{align}
It then follows that the mistake bound, for small
\varepsilon
| \left(1+ | \epsilon |
| 2 |
+O(\varepsilon2)\right)m+\epsilon-1ln(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
In particular, as long as
m
ln(n)
\begin{align}\varepsilon=\sqrt{
| ln(n) | |
| m |
we can obtain an upper bound on the number of mistakes equal to
\begin{align}m+O(\sqrt{mln(n)}).\end{align}
This implies that the "regret bound" on the algorithm (that is, how much worse it performs than the best expert) is sublinear, at
O(\sqrt{mln(n)})
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
n=10
m=20
2.4(log210+20) ≈ 56
\begin{align}
| ln(1/\beta) | |
| 1-\beta |
20+
| 1 | |
| 1-\beta |
ln(10).\end{align}
Computational methods show that the optimal value is roughly
\beta ≈ 0.641
E[M] ≈ 31.19
N=1000000
\varepsilon ≈ 0.0117
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. Note that the RWMA can be generalized to solve problems which do not have binary mistake variables, which makes it useful for a wide class of problems.
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. The goal is to have an expected loss not much larger than the loss of the best expert.
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.