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. 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.

The randomized weighted majority algorithm is an algorithm in machine learning theory for aggregating expert predictions to a series of decision problems. 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. 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. 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). let W=\sum_iw_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 choose expert i randomly 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 instead of strictly \frac{1}{2} allows us to trade off between dependence on m and \log_2n . This trade-off will be quantified in the analysis section. By definition, F_t is the probability that the algorithm makes a mistake on round t . It follows 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 . After round t , the total weight is decreased by \ (1-\beta)F_tW_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{align} W=n \prod_{t=1}^N (1-(1-\beta)F_t). \end{align} 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{align} n \prod_{t=1}^N (1-(1-\beta)F_t) \geq \beta^m. \end{align} Taking the natural logarithm of both sides yields \begin{align} \ln n + \sum_{t=1}^N \ln (1-(1-\beta)F_t) \geq m \ln\beta . \end{align} Now, the Taylor series of the natural logarithm is \begin{align} \ln (1-x)= - x - \frac {x^2}{2} - \frac {x^3}{3} - \cdots \end{align} In particular, it follows that \ \ln (1-(1-\beta)F_t) . Thus, \begin{align} \ln n - (1-\beta) \sum_{t=1}^N F_t \geq m \ln\beta . \end{align} Recalling that E[M] = \sum_{t=1}^N F_t and rearranging, it follows that \begin{align} 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{align} Now, as \beta \to 1 from below, the first constant tends to 1 ; however, the second constant tends to +\infty . To quantify this tradeoff, 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{align} \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{align} 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. In particular, as long as m is sufficiently large compared to \ln(n) (so that their ratio is sufficiently small), we can assign \begin{align} \varepsilon = \sqrt{\frac{\ln(n)}{m}} \end{align} we can obtain an upper bound on the number of mistakes equal to \begin{align} m + O(\sqrt{m \ln(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{m \ln(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 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{align} \frac{ \ln (1/\beta) }{1-\beta}20 + \frac{1}{1-\beta}\ln (10) . \end{align} 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%. ===Applications in software=== 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1315104093 under CC BY-SA 4.0; modifications have been made.