AdaBoost

AdaBoost的设计

AdaBoost二分类算法

1. 初始化训练数据的权值分布
$$D_1=\left(w_{11},\cdots,w_{1i},\cdots,w_{1N}\right),w_{1i}=\frac{1}{N},i=1,2,\cdots,N$$
第一步训练数据集具有均匀的权值分布，保证第一步能够在原始数据上学习基本分类器$$G_1(x)$$。

2. 对$$m=1,2\cdots,M$$
1. 使用具有权值分布$$D_m$$的训练数据集学习，得到基本分类器
$$G_m(x):\mathcal{X}\rightarrow\{-1,+1\}$$
2. 计算$$G_m(x)$$在加权训练数据上的分类误差率
$$e_m(x)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)=\sum_{G_m(x_i)\neq y_i}w_{mi}$$
3. 计算$$G_m(x)$$的系数
$$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$$
当$$e_m\leq 0.5$$时，$$\alpha_m\geq 0$$，且$$\alpha_m$$随着$$e_m$$的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
4. 更新训练数据集的权值分布
$$D_{m+1}=(w_{m+1,1},w_{m+1,2},\cdots,w_{m+1,N})\\w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_m y_i G_m(x_i)),i=1,2,\cdots,N\\Z_m=\sum_{i=1}^N w_{mi}\exp(-\alpha_m y_i G_m(x_i))$$
当错误分类即$$y_i\neq G_m(x_i)$$时，权值被扩大，反之，权值被缩小。因此误分类样本在下一轮学习中起更大的作用。

3. 构建基本分类器的线性组合
$$G(x)=\sum_{m=1}^M \alpha_m G_m(x)$$
得到最终分类器
$$\begin{aligned}f(x)&=sign(G(x))\\&=sign\left(\sum_{m=1}^M \alpha_m G_m(x)\right)\end{aligned}$$
$$\alpha_m$$表示了基本分类器$$G_m(x)$$的重要性，这里$$\alpha_m$$之和并不为1。$$G(x)$$的符号决定实例x的类，$$G(x)$$的绝对值表示分类的确信度。

前向分步加法模型

1. 初始化$$f_0(x)=0$$；

2. 对$$m=1,2\cdots,M$$
1. 极小化损失函数
$$(\beta_m,\gamma_m)=\arg\min_{\beta,\gamma} \sum_{i=1}^N L\left(y_i,f_{m-1}(x_i)+\beta b(x;\gamma)\right)$$
2. 更新
$$f_m(x)=f_{m-1}(x_i)+\beta_m b(x;\gamma_m)$$

3. 得到加法模型
$$f(x)=f_M(x)=\sum_{m=1}^M\beta_m b(x;\gamma_m)$$

AdaBoost算法的推导

1. 先求解$$G^*_m(x)$$：
$$G^*_m(x)=\arg\min_{G}\sum_{i=1}^N{w}_{mi}I(y_i\neq G(x_i))$$
即$$G_m^*(x)$$为在$${w}_{mi}$$加权的数据集下分类误差率$$e_m$$最小的分类器。

2. 再解$$\alpha^*_m$$:
对$$\alpha$$求导，并令导数为0，求得
$$\alpha^*_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$$

3. 再观察样本权值的更新：
由$$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$$以及$$\={w}_{mi}=\exp[-y_if_{m-1}(x_i)]$$可得
$$\={w}_{m+1,i}=\={w}_{mi}\exp[-y_i\alpha_mG_m(x)]$$
对权重进行归一化处理，则得到AdaBoost算法中样本权重的更新法则
$$w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_m y_i G_m(x_i)),i=1,2,\cdots,N\\Z_m=\sum_{i=1}^N w_{mi}\exp(-\alpha_m y_i G_m(x_i))$$

AdaBoost多分类算法SAMME

• 多分类场景下的标签
在K分类任务下的标签y是一个K维向量$$\boldsymbol{y}=(y_1,y_2,\cdots,y_K)^T$$
$$y_k= \begin{cases}1, & \text { if } c=k \\ -\frac{1}{K-1}, & \text { if } c \neq k\end{cases}$$
相当于是把one-hot编码中所有的0全部替换为了$$-\frac{1}{K-1}$$，这样能保证$$y_1+y_2+\cdots+y_K=0$$
同样，对于多分类的学习器$$\boldsymbol{G}^{(m)}(x)$$，其输出也为K维向量$$(g_1(x),g_2(x),\cdots,g_K(x))^T$$，预测为k类，则$$g_k(x)=1，g_{l\neq k}(x)=-\frac{1}{K-1}$$

• 多分类场景下的指数损失函数
$$L(\boldsymbol{y}, \boldsymbol{f})=\exp \left(-\frac{1}{K}\left(y_1 f_1+y_2 f_2+\cdots+y_K f_K\right)\right)=\exp \left(-\frac{1}{K} \boldsymbol{y}^T \boldsymbol{f}\right)$$
其中 $$f_k$$ 表示模型第 k 个维度对应的输出结果，同时由于每个样本的预测结果有 K 维度，因此在计算损失的时候一般需要除以 K 。

• 前向分步算法
1. 初始化$$\boldsymbol{f}^{(0)}(x)=0$$
2. 每一轮的优化目标
$$\left(\alpha^{(m)}, \boldsymbol{G}^{(m)}\right)=\underset{\alpha, \boldsymbol{G}}{\arg \min } \sum_{i=1}^N L\left(\boldsymbol{y}_i, \boldsymbol{f}^{(m-1)}\left(x_i\right)+\alpha\boldsymbol{G}\left(x_i\right)\right)$$
3. 迭代更新
$$\boldsymbol{f}^{(m)}(x)=\boldsymbol{f}^{(m-1)}(x)+\alpha^{(m)} \boldsymbol{G}^{(m)}(x)$$
4. 最终集成模型
$$\boldsymbol{f}(x)=\sum_{m=1}^M \alpha^{(m)} \boldsymbol{G}^{(m)}(x)$$

• $$\alpha_m$$更新公式
$$\alpha_m=\frac{(K-1)^2}{K}\left(\log\frac{1-e_m}{e_m}+\log(K-1)\right)$$
其中$$\frac{(K-1)^2}{K}$$是常数，归一化后不影响最终的优化结果。

• 样本权重更新公式
$${w}_i^{(m+1)}=\frac{{w}_i^{(m)} \exp \left(\alpha_m I(c_i\neq G_i^{(m)})\right)}{Z_m}$$
$$I(c_i\neq G_i^{(m)})$$表示真实标签和预测标签是否不同，若不同则为1，相同则为0.

AdaBoost多分类SAMME算法推导

1. 先求解$$\boldsymbol{G}^{(m)}(x)$$：
$$\boldsymbol{G}^{(m)}(x)=\arg \min \sum_{i=1}^N w_i^{(m)} I\left(c_i \neq G^{(m)}_i\right)$$
即$$\boldsymbol{G}^{(m)}(x)$$为加权数据下分类误差率最小的分类器；

2. 再解$$\alpha_m$$:
对$$\alpha$$求导，并令导数为0，求得
$$\alpha_m=\frac{(K-1)^2}{K}\left(\log\frac{1-e_m}{e_m}+\log(K-1)\right)$$
其中$$\frac{(K-1)^2}{K}$$是常数，故并不影响最终的优化结果。

3. 再观察样本权值的更新:
由$$\boldsymbol{f}_m(x)=\boldsymbol{f}_{m-1}(x)+\alpha_m \boldsymbol{G}_m(x)$$以及$$\={w}_i^{(m)}=\exp \left(-\frac{1}{K} \boldsymbol{y}_i^T \boldsymbol{f}^{(m-1)}\left(x_i\right)\right)$$可得
$${w}_i^{(m+1)}=\frac{{w}_i^{(m)}}{Z_m}\exp \left(-\frac{\alpha_m}{K} \boldsymbol{y}_i^T \boldsymbol{G}^{(m)}\left(x_i\right)\right)$$
当$$c_i= G^{(m)}_i$$时，$${w}_i^{(m+1)}=\frac{{w}_i^{(m)}}{Z_m}\exp\left(-\frac{\alpha_m}{K-1}\right)$$
或$$c_i\neq G^{(m)}_i$$时，$${w}_i^{(m+1)}=\frac{{w}_i^{(m)}}{Z_m}\exp\left(\frac{K\alpha_m}{(K-1)^2}\right)\exp\left(-\frac{\alpha_m}{K-1}\right)$$
故可改写为$${w}_i^{(m+1)}=\frac{{w}_i^{(m)}}{Z_m}\exp\left(\frac{K\alpha_m}{(K-1)^2} I(c_i\neq G_i^{(m)})\right)$$
若不考虑$$\alpha_m$$更新公式中的常数系数$$\frac{(K-1)^2}{K}$$，则样本权重更新公式为
$${w}_i^{(m+1)}=\frac{{w}_i^{(m)} \exp \left(\alpha_m I(c_i\neq G_i^{(m)})\right)}{Z_m}$$

AdaBoost回归算法

1. 初始化样本权重
$$D_1=\left(w_{11},\cdots,w_{1i},\cdots,w_{1N}\right),w_{1i}=\frac{1}{N},i=1,2,\cdots,N$$

2. 对于$$m=1,2,\cdots,M$$
1. 使用具有权重$$D_m$$的样本集来训练数据，得到弱学习器$$G_m(x)$$
2. 计算训练集上的最大误差
$$E_m=\max \left|y_i-G_m\left(x_i\right)\right| i=1,2 \ldots N$$
3. 计算每个样本的相对误差：
• 若损失为绝对损失，则样本的相对误差为$$e_{m i}=\frac{\left|y_i-G_m\left(x_i\right)\right|}{E_m}$$
 
• 若损失为平方损失，则样本的相对误差为$$e_{m i}=\frac{\left(y_i-G_m\left(x_i\right)\right)^2}{E_m^2}$$
• 若损失为指数损失，则样本的相对误差为$$e_{m i}=1-\exp \left(\frac{-\left|y_i-G_m\left(x_i\right)\right|}{E_m}\right)$$
4. 计算弱学习器的回归误差率:
$$e_m=\sum_{i=1}^N w_{m i} e_{m i}$$
5. 计算弱学习器的系数
$$\alpha_m=\frac{e_m}{1-e_m}$$
6. 更新下一轮的样本权重
$$w_{m+1, i}=\frac{w_{m i}}{Z_m} \alpha_m^{1-e_{m i}}\\Z_m=\sum_{i=1}^N w_{m i} \alpha_m^{1-e_{m i}}$$

3. 构建最终强学习器
采用的是对加权的弱学习器取权重中位数对应的弱学习器作为强学习器的方法
$$f(x)=G_{m^*}(x)$$
其中，$$G_{m^*}(x)$$是所有$$\ln \frac{1}{\alpha_m}, m=1,2, \ldots M$$的中位数对应序号$$m^*$$的弱学习器。

AdaBoost的训练误差和泛化性能

• AdaBoost算法随着弱学习器数目的增加，泛化能力增强。

AdaBoost算法的正则化

AdaBoost的学习器类型

AdaBoost算法的优缺点

1. Adaboost作为分类器时，分类精度很高；

2. 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活；

3. 作为简单的二分类器时，构造简单，结果可理解；

4. 不容易发生过拟合。

• 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

集成学习之Adaboost算法原理小结 - 刘建平Pinard - 博客园

在集成学习原理小结中，我们讲到了集成学习按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，另一类是个体学习器之间不存在强依赖关系。前者的代表算法就是是boosting系列算法。在boosting系列算法中， Adaboost是最著名的算法之一。Adaboost既可

https://www.cnblogs.com/pinard/p/6133937.html