集成学习（2）Adaboost

一、Adaboost (Boosting)

AdaBoost（Adaptive Boosting，自适应增强），其自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

1.1 思想

Adaboost 迭代算法有三步：

• 初始化训练样本的权值分布，每个样本具有相同权重；
• 训练弱分类器，如果样本分类正确，则在构造下一个训练集中，它的权值就会被降低；反之提高。用更新过的样本集去训练下一个分类器；
• 将所有弱分类组合成强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。

1.2 细节

1.2.1 损失函数

Adaboost 模型是加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

加法模型：最终的强分类器是由若干个弱分类器加权平均得到的。

前向分布学习算法：算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。第 k 轮的强学习器为： \[ F_{k}(x)=\sum_{i=1}^{k} \alpha_{i} f_{i}(x)=F_{k-1}(x)+\alpha_{k} f_{k}(x) \]

定义损失函数为 \(\mathbf{n}\) 个样本的指数损失函数： \[ L(y, F)=\sum_{i=1}^n \exp \left(-y_i F_k\left(x_i\right)\right) \] 利用前向分布学习算法的关系可以得到： \[ \begin{aligned} L(y, F) & =\sum_{i=1}^m \exp \left[\left(-y_i\right)\left(F_{k-1}\left(x_i\right)+\alpha_k f_k\left(x_i\right)\right)\right] \\ & =\sum_{i=1}^m \exp \left[-y_i F_{k-1}\left(x_i\right)-y_i \alpha_k f_k\left(x_i\right)\right] \\ & =\sum_{i=1}^m \exp \left[-y_i F_{k-1}\left(x_i\right)\right] \exp \left[-y_i \alpha_k f_k\left(x_i\right)\right] \end{aligned} \] 因为 \(F_{k-1}(x)\) 已知, 所以令 \(w_{k, i}=\exp \left(-y_i F_{k-1}\left(x_i\right)\right)\) ，随着每一轮迭代而将这个式子带入损失函数, 损失函数转 化为: \[ L(y, F(x))=\sum_{i=1}^m w_{k, i} \exp \left[-y_i \alpha_k f_k\left(x_i\right)\right] \] 我们求 \(f_k(x)\) ，可以得到: \[ f_k(x)=\operatorname{argmin} \sum_{i=1}^m w_{k, i} I\left(y_i \neq f_k\left(x_i\right)\right) \] 将 \(f_k(x)\) 带入损失函数, 并对 \(\alpha\) 求导, 使其等于 0，则就得到了: \[ \alpha_k=\frac{1}{2} \log \frac{1-e_k}{e_k} \] 其中, \(e_k\) 即为我们前面的分类误差率。 \[ e_k=\frac{\sum_{i=1}^m w_{k i}^{\prime} I\left(y_i \neq f_k\left(x_i\right)\right)}{\sum_{i=1}^m w_{k i}^{\prime}}=\sum_{i=1}^m w_{k i} I\left(y_i \neq f_k\left(x_i\right)\right) \] 最后看样本权重的更新。利用 \(F_k(x)=F_{k-1}(x)+\alpha_k f_k(x)\) 和 \(w_{k+1, i}=w_{k, i} e x p\left[-y_i \alpha_k f_k(x, i)\right]\), 即可得: \[ w_{k+1, i}=w_{k i} \exp \left[-y_i \alpha_k f_k\left(x_i\right)\right] \] 这样就得到了样本权重更新公式。

1.2.2 正则化

为了防止 Adaboost 过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长（learning rate) 。 对于前面的弱学习器的迭代,加上正则化项 \(\mu\) 我们有: \[ F_k(x)=F_{k-1}(x)+\mu \alpha_k f_k(x) \] \(\mu\) 的取值范围为 \(0<\mu \leq 1\) 。对于同样的训练集学习效果, 较小的 \(\mu\) 意味着我们需要更多的弱学习器的迭代次 数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

1.3 优缺点

1.3.1 优点

1. 分类精度高；
2. 可以用各种回归分类模型来构建弱学习器，非常灵活；
3. 不容易发生过拟合。

1.3.2 缺点

1. 对异常点敏感，异常点会获得较高权重。