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} $$

8.5-8.8

[解析]：由式(8.4)可知 $$H(\boldsymbol{x})=\sum{t=1}^{T} \alpha{t} h_{t}(\boldsymbol{x})$$

又由式(8.11)可知 $$ \alpha{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon{t}}{\epsilon_{t}}\right) $$ 该分类器的权重只与分类器的错误率负相关(即错误率越大，权重越低)

(1)先考虑指数损失函数$e^{-f(x) H(x)}$的含义：$f$为真实函数，对于样本$x$来说，$f(\boldsymbol{x}) \in{-1,+1}$只能取和两个值，而$H(\boldsymbol{x})$是一个实数； 当$H(\boldsymbol{x})$的符号与$f(x)$一致时，$f(\boldsymbol{x}) H(\boldsymbol{x})>0$，因此$e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}=e^{-|H(\boldsymbol{x})|}<1$，且$|H(\boldsymbol{x})|$越大指数损失函数$e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}$越小（这很合理：此时$|H(\boldsymbol{x})|$越大意味着分类器本身对预测结果的信心越大，损失应该越小；若$|H(\boldsymbol{x})|$在零附近，虽然预测正确，但表示分类器本身对预测结果信心很小，损失应该较大）； 当$H(\boldsymbol{x})$的符号与$f(\boldsymbol{x})$不一致时，$f(\boldsymbol{x}) H(\boldsymbol{x})<0$，因此$e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}=e^{|H(\boldsymbol{x})|}>1$，且$| H(\boldsymbol{x}) |$越大指数损失函数越大（这很合理：此时$| H(\boldsymbol{x}) |$越大意味着分类器本身对预测结果的信心越大，但预测结果是错的，因此损失应该越大；若$| H(\boldsymbol{x}) |$在零附近，虽然预测错误，但表示分类器本身对预测结果信心很小，虽然错了，损失应该较小）； (2)符号$\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}[\cdot]$的含义：$\mathcal{D}$为概率分布，可简单理解为在数据集$D$中进行一次随机抽样，每个样本被取到的概率；$\mathbb{E}[\cdot]$为经典的期望，则综合起来$\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}[\cdot]$表示在概率分布$\mathcal{D}$上的期望，可简单理解为对数据集$D$以概率$\mathcal{D}$进行加权后的期望。 f(x)是概率分布函数

$$ \begin{aligned} \ell{\mathrm{exp}}(H | \mathcal{D})=&\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right] \ =&P(f(x)=1|x)*e^{-H(x)}+P(f(x)=-1|x)*e^{H(x)} \end{aligned} $$

由于$P(f(x)=1|x)和P(f(x)=-1|x)$为常数

故式(8.6)可轻易推知

$$ \frac{\partial \ell_{\exp }(H | \mathcal{D})}{\partial H(\boldsymbol{x})}=-e^{-H(\boldsymbol{x})} P(f(\boldsymbol{x})=1 | \boldsymbol{x})+e^{H(\boldsymbol{x})} P(f(\boldsymbol{x})=-1 | \boldsymbol{x}) $$

令式(8.6)等于0可得

式(8.7) $$ H(\boldsymbol{x})=\frac{1}{2} \ln \frac{P(f(x)=1 | \boldsymbol{x})}{P(f(x)=-1 | \boldsymbol{x})} $$ 式(8.8)显然成立 $$ \begin{aligned} \operatorname{sign}(H(\boldsymbol{x}))&=\operatorname{sign}\left(\frac{1}{2} \ln \frac{P(f(x)=1 | \boldsymbol{x})}{P(f(x)=-1 | \boldsymbol{x})}\right) \ & =\left{\begin{array}{ll}{1,} & {P(f(x)=1 | \boldsymbol{x})>P(f(x)=-1 | \boldsymbol{x})} \ {-1,} & {P(f(x)=1 | \boldsymbol{x})<P(f(x)=-1 | \boldsymbol{x})}\end{array}\right. \ & =\underset{y \in{-1,1}}{\arg \max } P(f(x)=y | \boldsymbol{x}) \end{aligned} $$

8.16

$$ \begin{aligned} h{t}(\boldsymbol{x}) &=\underset{h}{\arg \max } \mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \ &=\underset{\boldsymbol{h}}{\arg \max } \mathbb{E}{\boldsymbol{x} \sim \mathcal{D}_{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \end{aligned} $$

[推导]：假设x的概率分布是f(x) (注:本书中概率分布全都是$\mathcal{D(x)}$)

$$ \mathbb{E(g(x))}=\sum_{i=1}^{|D|}f(x)g(x) $$ 故可得

$$ \mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right]=\sum{i=1}^{|D|} \mathcal{D}\left(\boldsymbol{x}{i}\right) e^{-f\left(\boldsymbol{x}{i}\right) H\left(\boldsymbol{x}{i}\right)} $$ 由式(8.15)可知 $$ \mathcal{D}{t}\left(\boldsymbol{x}{i}\right)=\mathcal{D}\left(\boldsymbol{x}{i}\right) \frac{e^{-f\left(\boldsymbol{x}{i}\right) H{t-1}\left(\boldsymbol{x}{i}\right)}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} $$

所以式(8.16)可以表示为 $$ \begin{aligned} & \mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \=& \sum{i=1}^{|D|} \mathcal{D}\left(\boldsymbol{x}{i}\right) \frac{e^{-f\left(\boldsymbol{x}{i}\right) H{t-1}\left(\boldsymbol{x}{i}\right)}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x}) }] \right.}f(x_i)h(xi) \=& \sum{i=1}^{|D|} \mathcal{D}{t}\left(\boldsymbol{x}{i}\right) f\left(\boldsymbol{x}{i}\right) h\left(\boldsymbol{x}{i}\right) \=& \mathbb{E}{\boldsymbol{x} \sim \mathcal{D}{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \end{aligned} $$