AdaBoost集成学习算法理论解读以及公式为什么这么设计?

本文致力于阐述AdaBoost基本步骤涉及的每一个公式和公式为什么这么设计。
AdaBoost集成学习算法基本上遵从Boosting集成学习思想，通过不断迭代更新训练样本集的样本权重分布获得一组性能互补的弱学习器，然后通过加权投票等方式将这些弱学习器集成起来得到性能较优的集成模型。

图1：Boosting集成算法思想。
下面以二分类任务(标签不是为-1，就是为+1)为例介绍该算法的具体过程。值得注意的是，下面的公式推导是以二分类任务下得出来，所以公式(比如样本权重更新公式)才会显得比较整洁，但如果换成其他任务，如多分类，那么公式会复杂很多。
对于训练样本集$D=\left(x_1,y_1\right),\left(x_2,y_2\right),\dots ,(x_n,y_n)$，其中标签 y i ∈ { − 1 , + 1 } y_i\in\left\{-1,+1\right\} yi​∈{−1,+1}，由AdaBoost集成学习算法构造集成模型的基本步骤如下：
（1）令$i=1$并设定弱学习器的数目m。对应第一次迭代，使用均匀分布初始化训练样本集的权重分布，令$n$维向量${\mathbf{w}}^i$表示第$i$次需更新的样本权重，则有：
${\mathbf{w}}^1={\left(w_{11},w_{12},\dots ,w_{1n}\right)}^T={\left(\frac{1}{n},\frac{1}{n},\dots ,\frac{1}{n}\right)}^T$
（2）使用权重分布为${\mathbf{w}}^i$，此时$i=1$的训练样本集$D_i$学习得到第$i$个弱学习器$L_i$；
（3）计算$L_i$在训练样本集$D_i$上的分类错误率$e_i$：
$e_i={\sum }_{k=1}^n{w}_{ik}I\left(L_i\left(X_k\right)\ne y_k\right)$
（4）确定弱学习器$L_i$的组合权重${\alpha }_i$(${\alpha }_i$在最后得到最终的集成模型上用到)。由于弱学习器$L_i$的权重取值应与其分类性能相关，对于分类错误率$e_i$越小的$L_i$，则其权重${\alpha }_i$应该越大，故有：
${\alpha }_i=\frac{1}{2}\text{ln}\frac{1-e_i}{e_i}=\frac{1}{2}\text{ln}(\frac{1}{e_i}-1)$
可能会有人会为，为什么要这么设计${\alpha }_i$？我在下面给出了解释。
（5）(重点)依据弱学习器$L_i$对训练样本集$D_i$的分类错误率$e_i$更新样本权重，样本权重更新公式为：
$w_{i+1,j}=\frac{w_{ij}\exp (-{\alpha }_i{y}_k{L}_i(x_k))}{Z_i}$
其中：
$Z_i={\sum }_{k=1}^n{w}_{ij}\exp (-{\alpha }_i{y}_k{L}_i(X_k))$
为归一化因子，保证更新后权重向量为概率分布；
对权重更新公式的解释：
回顾开头，这是一个二分类任务，所以若样本$(x_k,y_k)$分类正确，则要不$y_k=L_i(x_k)=1$，要不$y_k=L_i(x_k)=-1$，因此有$y_k\ast L_i(x_k)=1$**。**若样本$(x_k,y_k)$分类错误，则要不$y_k=-1,L_i(x_k)=1$，要不$y_k=1,L_i(x_k)=-1$，因此有$y_k\ast L_i(x_k)=-1$。
因此公式
$w_{i+1,j}=\frac{w_{ij}\exp (-{\alpha }_i{y}_k{L}_i(x_k))}{Z_i}$
可以改写
$w_{i+1,j}=\{\begin{array}{l}\frac{w_{ij}}{Z_i}\exp (-{\alpha }_i),y_k=L_i(x_k)\\ \frac{w_{ij}}{Z_i}\exp ({\alpha }_i),y_k\ne L_i(x_k)\end{array}$
这样，对于错误的样本会被放大$\frac{1-e_i}{e_i}$倍，以便在后续弱学习器构造过程得到应有的重视。
为什么是$\frac{1-e_i}{e_i}$倍？
$\frac{w_{i+1,j},y_k\ne L_i(x_k)}{w_{i+1,j},y_k=L_i(x_k)}=\frac{\frac{w_{ij}}{Z_i}\exp ({\alpha }_i)}{\frac{w_{ij}}{Z_i}\exp (-{\alpha }_i)}=\frac{\exp ({\alpha }_i)}{\exp (-{\alpha }_i)}=e^{2\ast {\alpha }_i}=e^{2\ast \frac{1}{2}\text{ln}\frac{1-e_i}{e_i}}=e^{\text{ln}\frac{1-e_i}{e_i}}=\frac{1-e_i}{e_i}$
另外$Z_i$的作用是归一化，使得${\sum }_{j=1}^n{w}_{i+1,j}=1$
（6）若$i<m$，则令$i=i+1$并返回步骤（2），否则执行步骤（7）；
（7）对于$m$个弱分类器$L_1{,L}_2,\dots ,L_m$，分别将每个$L_i$按权重${\alpha }_i$进行组合：
$L=\text{sign}({\sum }_{i=1}^m{\alpha }_i{L}_i(X))$
得到并输出所求集成模型$L$，算法结束。

参考资料：《机器学习及其应用》汪荣贵等编著