PumpkinBook/docs/chapter8/chapter8.md

8.3

$$ \begin{aligned} P(H(\boldsymbol{x}) \neq f(\boldsymbol{x})) &=\sum{k=0}^{\lfloor T / 2\rfloor} \left( \begin{array}{c}{T} \ {k}\end{array}\right)(1-\epsilon)^{k} \epsilon^{T-k} \ & \leqslant \exp \left(-\frac{1}{2} T(1-2 \epsilon)^{2}\right) \end{aligned} $$ [推导]:由基分类器相互独立，设X为T个基分类器分类正确的次数，因此$\mathrm{X} \sim \mathrm{B}(\mathrm{T}, 1-\mathrm{\epsilon})$ $$ \begin{aligned} P(H(x) \neq f(x))=& P(X \leq\lfloor T / 2\rfloor) \ & \leqslant P(X \leq T / 2) \ & =P\left[X-(1-\varepsilon) T \leqslant \frac{T}{2}-(1-\varepsilon) T\right] \ & =P\left[X- (1-\varepsilon) T \leqslant -\frac{T}{2}\left(1-2\varepsilon\right)]\right] \end{aligned} $$ 根据Hoeffding不等式$P(X-(1-\epsilon)T\leqslant -kT) \leq \exp (-2k^2T)$ 令$k=\frac {(1-2\epsilon)}{2}$得 $$ \begin{aligned} P(H(\boldsymbol{x}) \neq f(\boldsymbol{x})) &=\sum{k=0}^{\lfloor T / 2\rfloor} \left( \begin{array}{c}{T} \ {k}\end{array}\right)(1-\epsilon)^{k} \epsilon^{T-k} \ & \leqslant \exp \left(-\frac{1}{2} T(1-2 \epsilon)^{2}\right) \end{aligned} $$