AdaBoost算法详解

李航统计学习方法

回顾上一篇文章Gradient Boosting方法, 其中，经典用于分类AdaBoost。
具体算法步骤如下：

注：步骤(2)(b)中，计算得到$e_m$判断其值是否小于0.5.如果是，请继续以下步骤，否则需要重启：数据的权重分布设置为离散均匀分布、重新采样和训练基分类器。重启的原因很简单，因为 $e_m>0.5$时，权重 $\alpha <0$，这显然不是我们想看到的。

大体流程
它是在新提取（根据概率权重提取）的样本集中不断训练（同一）基分类器，然后计算整体训练集中分类结果和分类误差率，决定了基分类器的整体权重；上一个基分类器对整体训练集的分类结果及其分类误差率决定了下一个样本的权重（即下一个基分类器的训练样本）。

(2)(d) 训练集数据权值更新公式可写为：
$$w_{m1,i}\{\begin{array}{rl}\frac{w_{m,i}}{Z_m}\exp (-{\alpha }_m),& if{G}_m(x_i)=y_i\\ \frac{w_{m,i}}{Z_m}\exp ({\alpha }_m),& if{G}_m(x_i)\ne y_i\end{array}$$

注意重启步骤保证了$e_m<0.5$，则${\alpha }_m>0$，说明在第m个分类器下被正确分类的样本观测 i 的（在下一轮抽样中的）权重会缩小，反之被错误分类的观测的权重会增大。说明后续基分类器将着重解决分类效果差的样本，从而提升整体分类正确率。

接下来讨论$f(x)$的损失函数。
考虑二分类问题，求指数损失函数对应的风险（损失函数的期望即为风险函数）:
$$\mathcal{R}(f)=\mathbb{E}[l(f)|X]={\mathbb{E}}_Y[e^{-Yf(X)}|X]=Pr(Y=1|X)e^{-f(X)}+Pr(Y=-1|X)e^{f(X)}$$
求导：
$$\frac{\partial }{\partial f}\mathcal{R}(f|X)=-Pr(Y=1|X)e^{-f(X)}+Pr(Y=-1|X)e^{f(X)}=0$$
得到：
$$f(X)=\frac{1}{2}log(\frac{Pr(Y=1|X)}{Pr(Y=-1|X)})$$

上面这些推导可以说明指数损失函数是合理的。因为最小化风险函数得到的分类器结果即为理想状况下的分类器。当$Pr(Y=1|X)>Pr(Y=-1|X)$时，显然分类器预测结果为1，这与真实情况吻合。
另外，上面这个式子对应${\alpha }_m$的计算公式，因此最终的基分类器线性组合式子$f(x)={\sum }_{m=1}^M{\alpha }_m{G}_m(x)$是合理的。
也可以通过举例子说明，比如当损失函数最小时，$Yf(X)$达到最大，Y与$f(X)$最接近，即当$y=1$，$f(x)={\sum }_m{\alpha }_m$时损失函数最小。

贪心算法
AdaBoost使用贪心算法进行优化。$f(x)={\sum }_m{\alpha }_m{G}_m(x)$
只考虑最近的一步，即
$$\begin{array}{rl}\mathcal{R}({\alpha }_m{G}_m|X_m)& ={\mathbb{E}}_{X\sim {\mathcal{D}}_m}[e^{-Y{\alpha }_m{G}_m(X)}]\\ & =e^{-{\alpha }_m}P{r}_{X\sim {\mathcal{D}}_m}(Y=G_m(X))+e^{{\alpha }_m}P{r}_{X\sim {\mathcal{D}}_m}(Y\ne G_m(X))\\ & =e^{-{\alpha }_m}(1-{ϵ}_m)+e^{{\alpha }_m}{ϵ}_m\end{array}$$
在上式中对${\alpha }_m$求导即可得到其更新公式: ${\alpha }_m=\frac{1}{2}log(\frac{1-{ϵ}_m}{{ϵ}_m})$

数据分布 ${\mathcal{D}}_m$的更新
理想状况下，我们想要最小化：
$$\begin{array}{rl}\mathcal{R}(f_{m-1}+G_m|\mathcal{D})& ={\mathbb{E}}_{X\sim \mathcal{D}}[e^{-Y(f_{m-1}+G_m)}]\\ & ={\mathbb{E}}_{X\sim \mathcal{D}}[e^{-Y{f}_{m-1}}{e}^{-Y{G}_m})]\\ & \approx {\mathbb{E}}_{X\sim \mathcal{D}}[e^{-Y{f}_{m-1}}(1-Y{G}_m(X)+\frac{1}{2})]\end{array}$$
只考虑第m步的情况，并假设前m-1步的情况如$f_{m-1}$已知。则上述优化问题等价于最大化以下式子：
$$\text{maximize}{\mathbb{E}}_{X\sim \mathcal{D}}[e^{-Y(X)f_{m-1}}Y{G}_m(X)]$$等价于：$$\text{maximize}{\mathbb{E}}_{X\sim {\mathcal{D}}_m}[Y(X)G_m(X)]$$
其中, （为了使得上面两个最小化问题的最优解相同）
$${\mathcal{D}}_m=\frac{\mathcal{D}{e}^{-Y(X)f_{m-1}}}{{\mathbb{E}}_{X\sim \mathcal{D}}(e^{-Y(X)f_{m-1}})}$$

下标加1则得到
$$\begin{array}{rl}{\mathcal{D}}_{m+1}& =\frac{\mathcal{D}{e}^{-Y{f}_m}}{{\mathbb{E}}_{X\sim \mathcal{D}}(e^{-Y{f}_m})}\\ & =\frac{\mathcal{D}{e}^{-Y{f}_{m-1}}{e}^{-{\alpha }_{m}Y{G}_m}}{{\mathbb{E}}_{X\sim {\mathcal{D}}_m}(e^{-Y(X)f_m})}\\ & =e^{-{\alpha }_{m}Y{G}_m}\frac{{\mathbb{E}}_{X\sim \mathcal{D}}(e^{-Y{f}_{m-1}})}{{\mathbb{E}}_{X\sim \mathcal{D}}(e^{-Y(X)f_m})}\end{array}$$
此即对应第m步时数据的分布 { w m , i , i = 1 , . . . , n } \{w_{m,i},i=1,...,n\} { wm,i​,i=1,...,n}
基分类器$G_m$在$G_{m-1}$没有训练好的样本上加强训练，这与Boosting的思想一致。