Randomized weighted majority algorithm - Revision history

Citation bot: Alter: title, template type. Add: isbn, chapter. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2023-12-30T05:15:58Z

Alter: title, template type. Add: isbn, chapter. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 05:15, 30 December 2023
Line 123:		Line 123:

	===Applications in software===		===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.<ref name="VL21">{{cite ~~journal~~		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.<ref name="VL21">{{cite book
	\| last1 = Suresh		\| last1 = Suresh
	\| first1 = P. Varsha		\| first1 = P. Varsha
	\| last2 = Madhavu		\| last2 = Madhavu
	\| first2 = Minu Lalitha		\| first2 = Minu Lalitha
	\| ~~title~~ = Insider Attack: Internal Cyber Attack Detection Using Machine Learning		\| chapter = Insider Attack: Internal Cyber Attack Detection Using Machine Learning
	\| ~~journal~~ = 2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT)		\| title = 2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT)
	\| date = 2021		\| date = 2021
	\| pages = 1–7		\| pages = 1–7
	\| doi= 10.1109/ICCCNT51525.2021.9579549		\| doi= 10.1109/ICCCNT51525.2021.9579549
			\| isbn = 978-1-7281-8595-8
	}}</ref> <ref name="SE18">{{cite journal		}}</ref> <ref name="SE18">{{cite journal
	\| last1 = Moustafa		\| last1 = Moustafa

RobinTruax: Clarifying

2023-12-17T18:40:26Z

Clarifying

← Previous revision		Revision as of 18:40, 17 December 2023
Line 100:		Line 100:
	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 <math> \varepsilon </math> and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.		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 <math> \varepsilon </math> 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 <math>m</math> is sufficiently large compared to <math>\ln(n)</math> (so that their ratio is sufficiently small), we can assign
	In particular, by choosing

	<div class="center"><math> \begin{align} \varepsilon = \sqrt{\frac{\ln(n)}{m}} \end{align} </math></div>		<div class="center"><math> \begin{align} \varepsilon = \sqrt{\frac{\ln(n)}{m}} \end{align} </math></div>

OAbot: Open access bot: doi updated in citation with #oabot.

2023-12-16T01:11:01Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 01:11, 16 December 2023
Line 149:		Line 149:
	\| pages = 2763–2774		\| pages = 2763–2774
	\| doi= 10.1016/j.aej.2018.01.003		\| doi= 10.1016/j.aej.2018.01.003
			\| doi-access = free
	}}</ref> 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.		}}</ref> 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.

171.66.133.178: revert previously deleted link, add clearer wording in algo description

2023-12-14T21:35:46Z

revert previously deleted link, add clearer wording in algo description

← Previous revision		Revision as of 21:35, 14 December 2023
Line 42:		Line 42:
	== Randomized weighted majority algorithm (RWMA) ==		== 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 <math>m</math>. Instead of predicting based on majority vote, the weights are used as probabilities (hence the name randomized weighted majority).		The randomized weighted majority algorithm is an attempt to improve the dependence of the mistake bound of the WMA on <math>m</math>. 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).

	Precisely, if <math>w_i</math> is the weight of expert <math>i</math>,		Precisely, if <math>w_i</math> is the weight of expert <math>i</math>,
Line 171:		Line 171:
	* [https://www.cs.cmu.edu/~avrim/ML98/lect0121 Predicting From Experts Advice]		* [https://www.cs.cmu.edu/~avrim/ML98/lect0121 Predicting From Experts Advice]
	* [http://www.wisdom.weizmann.ac.il/~naor/COURSE/AGT/agt_dec_24th_regret.ppt Uri Feige, Robi Krauthgamer, Moni Naor. Algorithmic Game Theory]		* [http://www.wisdom.weizmann.ac.il/~naor/COURSE/AGT/agt_dec_24th_regret.ppt Uri Feige, Robi Krauthgamer, Moni Naor. Algorithmic Game Theory]
			* [https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/12_online2.pdf Nika Haghtalab 2020 Theoretical Foundations of Machine Learning (Notes)]

	[[Category:Machine learning algorithms]]		[[Category:Machine learning algorithms]]

RobinTruax: Grammatical edits and removing a few redundancies.

2023-12-14T19:09:24Z

Grammatical edits and removing a few redundancies.

← Previous revision		Revision as of 19:09, 14 December 2023
Line 32:		Line 32:
	Suppose there are <math>n</math> experts and the best expert makes <math>m</math> mistakes.		Suppose there are <math>n</math> experts and the best expert makes <math>m</math> mistakes.
	Then, the [[weighted majority algorithm]] (WMA) makes at most <math>2.4(\log_2n+ m)</math> mistakes.		Then, the [[weighted majority algorithm]] (WMA) makes at most <math>2.4(\log_2n+ m)</math> mistakes.
	This bound is highly problematic ~~for~~ ~~cases~~ ~~with~~ highly error-prone experts.		This bound is highly problematic in the case of highly error-prone experts.
	Suppose, for example, the best expert makes a mistake 20% of the time; that is, in <math>N = 100</math> rounds using <math>n = 10</math> experts, the best expert makes <math>m = 20</math> mistakes.		Suppose, for example, the best expert makes a mistake 20% of the time; that is, in <math>N = 100</math> rounds using <math>n = 10</math> experts, the best expert makes <math>m = 20</math> mistakes.
	Then, the [[weighted majority algorithm]] only guarantees an upper bound of <math>2.4 (\log_2 10 + 20) \approx 56</math> mistakes.		Then, the [[weighted majority algorithm]] only guarantees an upper bound of <math>2.4 (\log_2 10 + 20) \approx 56</math> mistakes.

	As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on <math>m</math>. In particular, we can do better by introducing randomization. ~~We can draw~~ inspiration from the ~~randomized~~ [[Multiplicative weight update method#Randomized weighted majority algorithm\|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.<ref name=ref6>{{cite web \|url=http://www.cs.princeton.edu/courses/archive/spr06/cos511/scribe_notes/0330.pdf \|title=COS 511: Foundations of Machine Learning \|date=20 March 2006}}</ref>		As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on <math>m</math>. In particular, we can do better by introducing randomization.

			Drawing inspiration from the [[Multiplicative weight update method#Randomized weighted majority algorithm\|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).<ref name=ref6>{{cite web \|url=http://www.cs.princeton.edu/courses/archive/spr06/cos511/scribe_notes/0330.pdf \|title=COS 511: Foundations of Machine Learning \|date=20 March 2006}}</ref>

	== Randomized weighted majority algorithm (RWMA) ==		== Randomized weighted majority algorithm (RWMA) ==
Line 63:		Line 65:
	Let <math>W_t</math> denote the total weight of all experts at round <math>t</math>. Also let <math>F_t</math> denote the fraction of weight placed on experts which predict the '''wrong''' answer at round <math>t</math>. Finally, let <math>N</math> be the total number of rounds in the process.		Let <math>W_t</math> denote the total weight of all experts at round <math>t</math>. Also let <math>F_t</math> denote the fraction of weight placed on experts which predict the '''wrong''' answer at round <math>t</math>. Finally, let <math>N</math> be the total number of rounds in the process.

	By definition, <math>F_t</math> is the probability that the algorithm makes a mistake on round <math>t</math>. It follows~~, then,~~ from the linearity of expectation, that if <math>M</math> denotes the total number of mistakes made during the entire process, <math> E[M] = \sum_{t=1}^N F_t</math>.		By definition, <math>F_t</math> is the probability that the algorithm makes a mistake on round <math>t</math>. It follows from the linearity of expectation that if <math>M</math> denotes the total number of mistakes made during the entire process, <math> E[M] = \sum_{t=1}^N F_t</math>.

	~~Now, notice that after~~ round <math>t</math>, the total weight is decreased by <math>\ (1-\beta)F_tW_t</math>, since all weights corresponding to a wrong answer are multiplied by <math>\ \beta</math>. It then follows that <math>W_{t+1} = W_t(1-(1-\beta)F_t)</math>. By telescoping, since <math>W_1 = n </math>, it follows that the total weight after the process concludes is		After round <math>t</math>, the total weight is decreased by<math>\ (1-\beta)F_tW_t</math>, since all weights corresponding to a wrong answer are multiplied by<math>\ \beta < 1</math>. It then follows that <math>W_{t+1} = W_t(1-(1-\beta)F_t)</math>. By telescoping, since <math>W_1 = n </math>, it follows that the total weight after the process concludes is

	<div class="center"><math> \begin{align} W=n \prod_{t=1}^N (1-(1-\beta)F_t). \end{align} </math></div>		<div class="center"><math> \begin{align} W=n \prod_{t=1}^N (1-(1-\beta)F_t). \end{align} </math></div>
Line 89:		Line 91:
	<div class="center"><math> \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} </math></div>		<div class="center"><math> \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} </math></div>

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

	<div class="center"><math> \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} </math></div>		<div class="center"><math> \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} </math></div>

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

	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 <math> \varepsilon </math> and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.		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 <math> \varepsilon </math> and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.

			In particular, by choosing
	To establish a more concrete optimum <math>\beta</math> and more concrete bound on <math>E(M)</math> we fix <math>n</math> and <math>m</math> as constants and <math>\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}</math>. We notice that for <math>\epsilon</math> sufficiently close to 0 the derivative is negative, while for <math>\epsilon</math> sufficiently close to 1 the derivative is positive, furthermore, this expression is strictly increasing with respect to <math>\epsilon</math>. Thus We must have a local minimum for some <math>0<\epsilon<1</math>, specifically we see that the upper bound of <math>E(M)</math> is minimized when <math>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}</math>. This final equality tells us that as m increases we want to choose a smaller <math>\epsilon</math> (ergo, larger <math>\beta</math>) to minimize expected error, while as n increases we want to choose a larger <math>\epsilon</math> (ergo, smaller <math>\beta</math>).

			<div class="center"><math> \begin{align} \varepsilon = \sqrt{\frac{\ln(n)}{m}} \end{align} </math></div>

			we can obtain an upper bound on the number of mistakes equal to

			<div class="center"><math> \begin{align} m + O(\sqrt{m \ln(n)}). \end{align} </math></div>

			This implies that the "regret bound" on the algorithm (that is, how much worse it performs than the best expert) is sublinear, at <math>O(\sqrt{m \ln(n)})</math>.

	== Revisiting the motivation ==		== Revisiting the motivation ==
Line 107:		Line 118:

	== Uses of Randomized Weighted Majority Algorithm (RWMA) ==		== 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.		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~~. 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 <math>\beta^{\text{loss}}</math> (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.

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

	===Applications in software===		===Applications in software===

RobinTruax: /* Analysis */ Re-adding some definitions for clarity.

2023-12-14T18:47:19Z

Analysis: Re-adding some definitions for clarity.

← Previous revision		Revision as of 18:47, 14 December 2023
Line 61:		Line 61:
	== Analysis ==		== Analysis ==

	Let <math>W_t</math> denote the total weight ~~and~~ <math>F_t</math> denote the fraction of weight on the '''wrong''' ~~answers~~ at round <math>t</math>. By definition, <math>F_t</math> is the probability that the algorithm makes a mistake on round <math>t</math>. It follows, then, from the linearity of expectation, that if <math>M</math> denotes the total number of mistakes made during the entire process, <math> E[M] = \sum_{t=1}^N F_t</math>.		Let <math>W_t</math> denote the total weight of all experts at round <math>t</math>. Also let <math>F_t</math> denote the fraction of weight placed on experts which predict the '''wrong''' answer at round <math>t</math>. Finally, let <math>N</math> be the total number of rounds in the process.

			By definition, <math>F_t</math> is the probability that the algorithm makes a mistake on round <math>t</math>. It follows, then, from the linearity of expectation, that if <math>M</math> denotes the total number of mistakes made during the entire process, <math> E[M] = \sum_{t=1}^N F_t</math>.

	Now, notice that after round <math>t</math>, the total weight is decreased by <math>\ (1-\beta)F_tW_t</math>, since all weights corresponding to a wrong answer are multiplied by <math>\ \beta</math>. It then follows that <math>W_{t+1} = W_t(1-(1-\beta)F_t)</math>. By telescoping, since <math>W_1 = n </math>, it follows that the total weight after the process concludes is		Now, notice that after round <math>t</math>, the total weight is decreased by <math>\ (1-\beta)F_tW_t</math>, since all weights corresponding to a wrong answer are multiplied by <math>\ \beta</math>. It then follows that <math>W_{t+1} = W_t(1-(1-\beta)F_t)</math>. By telescoping, since <math>W_1 = n </math>, it follows that the total weight after the process concludes is
Line 95:		Line 97:
	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 <math> \varepsilon </math> and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert.		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 <math> \varepsilon </math> 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 <math>\beta</math> and more concrete bound on <math>E(M)</math> we fix <math>n</math> and <math>m</math> as constants and <math>\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}</math>. We notice that for <math>\epsilon</math> sufficiently close to 0 the derivative is negative, while for <math>\epsilon</math> sufficiently close to 1 the derivative is positive, furthermore, this expression is strictly increasing with respect to <math>\epsilon</math>. Thus We must have a local minimum for some <math>0<\epsilon<1</math>, specifically we see that the upper bound of <math>E(M)</math> is minimized when <math>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}</math>. This final equality tells us that as m increases we want to choose a smaller <math>\epsilon</math> (ergo, larger <math>\beta</math>) to minimize expected error, while as n increases we want to choose a larger <math>\epsilon</math> (ergo, smaller <math>\beta</math>).		To establish a more concrete optimum <math>\beta</math> and more concrete bound on <math>E(M)</math> we fix <math>n</math> and <math>m</math> as constants and <math>\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}</math>. We notice that for <math>\epsilon</math> sufficiently close to 0 the derivative is negative, while for <math>\epsilon</math> sufficiently close to 1 the derivative is positive, furthermore, this expression is strictly increasing with respect to <math>\epsilon</math>. Thus We must have a local minimum for some <math>0<\epsilon<1</math>, specifically we see that the upper bound of <math>E(M)</math> is minimized when <math>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}</math>. This final equality tells us that as m increases we want to choose a smaller <math>\epsilon</math> (ergo, larger <math>\beta</math>) to minimize expected error, while as n increases we want to choose a larger <math>\epsilon</math> (ergo, smaller <math>\beta</math>).

	== Revisiting the motivation ==		== Revisiting the motivation ==

171.66.12.95: /* Randomized weighted majority algorithm (RWMA) */

2023-12-09T00:36:21Z

Randomized weighted majority algorithm (RWMA)

← Previous revision		Revision as of 00:36, 9 December 2023
Line 49:		Line 49:
	for each round:		for each round:
	add all experts' weights together to obtain the total weight <math>W</math>		add all experts' weights together to obtain the total weight <math>W</math>
	~~randomly select an expert;~~ choose expert <math>i</math> with probability <math>\frac{w_i}{W}</math>		choose expert <math>i</math> randomly with probability <math>\frac{w_i}{W}</math>
	predict as the chosen expert predicts		predict as the chosen expert predicts
	multiply the weights of all experts who predicted wrongly by <math>\beta</math>		multiply the weights of all experts who predicted wrongly by <math>\beta</math>

171.66.9.79: small capitalization typo fixed

2023-12-08T05:20:42Z

small capitalization typo fixed

← Previous revision		Revision as of 05:20, 8 December 2023
Line 111:		Line 111:
	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.		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.

	===Applications in ~~Software~~===		===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.<ref name="VL21">{{cite journal		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.<ref name="VL21">{{cite journal
	\| last1 = Suresh		\| last1 = Suresh
Line 138:		Line 138:
	\| pages = 2763–2774		\| pages = 2763–2774
	\| doi= 10.1016/j.aej.2018.01.003		\| doi= 10.1016/j.aej.2018.01.003
	}}</ref> 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.		}}</ref> 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.

	== Extensions ==		== Extensions ==

171.66.9.79: Added subsection on proposed applications of the RWMA in software

2023-12-08T05:20:06Z

Added subsection on proposed applications of the RWMA in software

← Previous revision		Revision as of 05:20, 8 December 2023
Line 110:		Line 110:

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

			===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.<ref name="VL21">{{cite journal
			\| last1 = Suresh
			\| first1 = P. Varsha
			\| last2 = Madhavu
			\| first2 = Minu Lalitha
			\| title = Insider Attack: Internal Cyber Attack Detection Using Machine Learning
			\| journal = 2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT)
			\| date = 2021
			\| pages = 1–7
			\| doi= 10.1109/ICCCNT51525.2021.9579549
			}}</ref> <ref name="SE18">{{cite journal
			\| last1 = Moustafa
			\| first1 = Sammar
			\| last2 = El Nainay
			\| first2 = Mustafa Y
			\| last3 = El Makky
			\| first3 = Nagwa
			\| last4 = Abougabal
			\| first4 = Mohamed S.
			\| title = Software bug prediction using weighted majority voting techniques
			\| journal = Alexandria Engineering Journal
			\| volume = 57
			\| issue = 4
			\| date = 2018
			\| pages = 2763–2774
			\| doi= 10.1016/j.aej.2018.01.003
			}}</ref> 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.

	== Extensions ==		== Extensions ==

Bananasoldier: /* Motivation */ link correction

2023-12-07T05:20:55Z

Motivation: link correction

← Previous revision		Revision as of 05:20, 7 December 2023
Line 36:		Line 36:
	Then, the [[weighted majority algorithm]] only guarantees an upper bound of <math>2.4 (\log_2 10 + 20) \approx 56</math> mistakes.		Then, the [[weighted majority algorithm]] only guarantees an upper bound of <math>2.4 (\log_2 10 + 20) \approx 56</math> mistakes.

	As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on <math>m</math>. 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.<ref name=ref6>{{cite web \|url=http://www.cs.princeton.edu/courses/archive/spr06/cos511/scribe_notes/0330.pdf \|title=COS 511: Foundations of Machine Learning \|date=20 March 2006}}</ref>		As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on <math>m</math>. In particular, we can do better by introducing randomization. We can draw inspiration from the randomized [[Multiplicative weight update method#Randomized weighted majority algorithm\|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.<ref name=ref6>{{cite web \|url=http://www.cs.princeton.edu/courses/archive/spr06/cos511/scribe_notes/0330.pdf \|title=COS 511: Foundations of Machine Learning \|date=20 March 2006}}</ref>

	== Randomized weighted majority algorithm (RWMA) ==		== Randomized weighted majority algorithm (RWMA) ==