User:Sam.BYH/sandbox

Randomized Multiplicative Weights Update Algorithm

Given N experts and a penalty parameter β (with a value ranging from 0 to 1), the initial weight of each expert is all 1. In each round of prediction, we listen to the opinions of all experts and randomly select one expert to adopt their opinions based on the weight. Compare this opinion with the facts and reduce the weight of all experts with incorrect predictions based on β.

      Input: Penalty parameter β∈ (0,1)
      1: Set $w_{1},w_{2},\dots ,w_{n}\leftarrow 1$
      2: for $t=1,2,\dots ,T$：do
      3: Receive $v_{1,t},v_{2,t},\dots ,v_{n,t}$
      4: choose a $u_{t}\leftarrow v_{I,t}$ according to the probability:
      5: $\Pr[I=i]=w_{i}$ / $\sum _{i=1}^{n}w_{i}$ ,
      6: Receive $u_{t}$
      7:  ${\text{for all }}1\leq i\leq n$：$w_{i}\leftarrow {\begin{cases}\beta \cdot w_{i},&{\text{if }}v_{i,t}\neq u_{t}\\w_{i},&{\text{otherwise}}\end{cases}}$

The number of mistakes made by the Randomized Multiplicative Weights Update Algorithm is bounded as:

 $E\left[\#{\text{mistakes of the learner}}\right]\leq \alpha _{\beta }\left(\#{\text{ mistakes of the best expert}}\right)+c_{\beta }\ln(N)$

where $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ and $c_{\beta }={\frac {1}{1-\beta }}$.

Proof: we know that $\Phi _{t}:=W_{t}=\sum _{i=1}^{n}w_{i,t}$ and $F_{t}:={\frac {W_{{\text{wrong}},t}}{W_{t}}}$ While $F_{t}$ is the weighted average error rate among all experts at round $t$, $W_{{\text{wrong}},t}$ denotes the total weight of the experts who made a wrong prediction.We also suppose the best expert makes a total of $M$ mistakes, so its final weight is at least:

$\Phi _{T}\geq \beta ^{M}$

We can deduce that :

$W_{t+1}=\beta F_{t}W_{t}+(1-F_{t})W_{t}=(1-(1-\beta )F_{t})W_{t}$

so：

$W_{T}=W_{0}\prod _{t=1}^{T}(1-(1-\beta )F_{t})$

Take the logarithms on both sides.：

$\ln W_{T}=\ln n+\sum _{t=1}^{T}\ln(1-(1-\beta )F_{t})$

By inequality: $\ln(1-x)\leq -x$（when $x<1$）：

$\ln W_{T}\leq \ln n-(1-\beta )\sum _{t=1}^{T}F_{t}$

On the other hand，$\ln W_{T}\geq M\ln \beta$，

Comprehensively obtained：

$M\ln \beta \leq \ln n-(1-\beta )\sum _{t=1}^{T}F_{t}$

$\sum _{t=1}^{T}F_{t}\leq {\frac {\ln n-M\ln \beta }{1-\beta }}$

Ultimately, the expected total number of errors of the algorithm satisfies:

$E\left[\#{\text{mistakes of the learner}}\right]\leq {\frac {M\ln(1/\beta )+\ln n}{1-\beta }}=\alpha _{\beta }\left(\#{\text{ mistakes of the best expert}}\right)+c_{\beta }\ln(N)$

Note that only the learning algorithm is randomized. The underlying assumption is that the examples and experts' predictions are not random. The only randomness is the randomness where the learner makes his own prediction. In this randomized algorithm, $\alpha _{\beta }\rightarrow 1$ if $\beta \rightarrow 1$. Compared to weighted algorithm, this randomness halved the number of mistakes the algorithm is going to make. However, it is important to note that in some research, people define $\eta =1/2$ in weighted majority algorithm and allow $0\leq \eta \leq 1$ in randomized weighted majority algorithm.