Adaboost (Adaptive Boosting) 是一个通过逐步聚焦于基学习器犯错的样本、减少集成偏差的方法,其利用多个弱学习器的线性组合来达到一个强分类器的效果。Adaboost 的思想是:在算法中会对每一个样本赋予一个权重,在后续的训练中会提高前一轮被误分类的样本权重,而降低被正确分类的样本权重。既可以处理分类,也可以处理回归任务。对于弱学习器的分类任务,结合策略可以利用加权多数表决的方法,对于回归任务可以采用加权平均。

  简言之,AdaBoost 算法三个部分是:

  • 模型为加法模型
  • 损失函数为指数损失函数:$\underset{ \alpha , G }{ \arg \min } \sum _ { i = 1 } ^ { m } \exp \left( - y _ { i } f _ { k } ( x_i ) \right)$
  • 学习算法为前向分步算法

0. 费曼学习法提问环节

0.1 Adaboost 主要解决什么类型问题?

  主要解决二分类问题,多分类时,还需要进一步整理。

0.2 掌握 Adaboost 的关键几点是什么?

  在复述时有几点会卡住:

  1. 样本权重怎么更新?如何推导得到样本权重?
  2. 为什么定义的 $w\prime$?
  3. 怎么做到增大正确分类样本的概率?
  4. 损失函数推导会卡住,怎么忽略其中 $\alpha$ 的影响?
  5. 怎么证明在损失函数中先不考虑 $\alpha$,只考虑最小化的 $G(x)$,后面再单独通过分类误差率来计算 $\alpha$?而不是在优化损失函数时也将 $\alpha$ 作为参数优化出来?
  6. 如何推导更新 $\alpha$?

1. Adaboost 分类算法

1.1 Adaboost 二分类算法

  首先做一些基本假设,数据集记作:

  假设有 $T$ 个弱学习器,对于每一个学习器 $G_k(x)$ 来说,样本的权重(初始化时)为:

  当所有的基学习器训练好后,以加法模型的形式得到一个集成的最终学习器,由若干个基学习器加权多数表决(二分类任务加权平均后用一个符号函数得到类别)结果:

  其中 $\alpha _ { t } $ 是每一个弱学习器的权重,最终模型在预测时的决策函数为:

  如果是二分类的话,每一个弱分类器的结果是 $\{+1, -1\}$,最终的决策函数通过综合所有弱分类器结果得出合适的 $\{+1, -1\}$ 结果。

  知道所有的弱学习器是如何合作决策后,那么我们现在来搞清楚如何在训练时更新这些弱学习器的权重,以及更新每一个弱学习器下的样本权重 $D(k)$。

  Adaboost 的算法学习方法是采用前向分步学习算法,我们记第 $k-1$ 轮的强学习器为:

  而第 $k$ 轮的强学习器为:

  则有:

  至此,我们知道了最终决策函数的表达方式,以及每一轮强学习器的更新方式,对于一个完备的模型来讲还差一个衡量训练后的函数好坏的指标——损失函数,Adaboost 用的是指数损失函数

  至于为什么 Adaboost 用指数损失函数,ESL 上介绍说有两个原因:

  • 其有良好的可计算性;
  • 在更新权重时有比较简单的形式。

  利用上面介绍的前向分布学习算法的关系,我们可以将指数损失函数改写成:

  我们可以尝试将指数部分的加法部分提前面并拆开分成已有的强学习器和当前弱学习器对训练样本的指数损失函数,我们可以令:

  其表示第 $i$ 个样本在前一个已有的强学习器 $f _ { k - 1 } ( x )$ 上的指数损失函数值,这个部分只依赖于前面训练得到的强学习器 $f _ { k - 1 } ( x )$,跟当前的弱学习器 $G$ 和弱学习器权重 $\alpha$ 没有关系,不影响最小化,于是我们可以将其看作是第 $i$ 个样本的权值。那么据此可以进一步改写损失函数:

  具体的损失函数变换推导如下式,我们要求 $G_k(x)$,可以把 $\alpha$ 看成常数,损失函数可理解为求弱分类器 $G_k(x)$ 使得其误分类样本的数量尽可能的少。

  如此得到了选择当前学习器的式子:

  在上述指数损失函数的基础上,我们可以按照 $y_i \neq G(x_i)$ 成立与否将指数损失函数继续改写:

  求该式的极值,对 $\alpha$ 求导,使其等于 $0$,得到:

  将上式分数部分定义为分类误差率 $e_k$,取名很直接,因为是 $y _ { i } \neq G$ 占所有的比率:

  因为所有样本权值加和我们会归一化,即 $\sum _ { i = 1 } ^ { m } w _ { k i } ^ { \prime }=1$,所以 $w _ { k i }$ 和 $w _ { k i } ^ { \prime } $ 都可以看成是样本权值。将 $e_k$ 代入上述等式易得弱学习器权重的更新公式:

  最后看样本权重的更新,利用 $f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x)$ 和 $w_{ki}^{’} = e^{-y_if_{k-1}(x)}$,即可得:

  当然,在具体更新样本权重时,会将样本权重归一化,即在权值更新公式上除以一个规范化因子 $Z_k$,使得得到所有样本权值加和为 1。

  其中

  基于上面的推导,我们已经知道了所有的重要信息,从初始的样本权重开始,训练一个弱学习器,然后得到这个学习器下所有样本的权重,那么可以计算分类误差率,进而计算当前弱学习器的权重,由此又可以计算下一个弱学习器的权重分布,继续后续的弱学习器训练,周而复始,直到所有弱学习器都搞定。

AdaBoost算法流程

输入:训练数据集 $T = \{ \left( x_1, y_1 \right), \left( x_2, y_2 \right), \cdots, \left( x_N, y_N \right) \}$,其中 $x_i \in \mathcal{X} \subseteq R^{n}$, $y_{i} \in \mathcal{Y} = \{ +1, -1 \}$, $i = 1, 2, \cdots, N$;

输出:分类器 $G\left(x\right)$

  1. 初始化训练数据的权值分布
  1. 对 $m=1,2,\cdots,M $   2.1 使用具有权值分布 $D_{m}$ 的训练数据集学习,得到基本分类器

  2.2 计算 $G_{m}\left(x\right)$ 在训练数据集上的分类误差率

  2.3 计算 $G_{m} \left(x\right)$ 的系数

  2.4 更新训练数据集的权值分布

  其中, $Z_{m}$ 是规范化因子

  1. 构建基本分类器的线性组合

  得到最终分类器

1.2 Adaboost 多元分类算法

  对于 Adaboost 多元分类算法,其实原理和二元分类类似,最主要区别在弱分类器的系数上。比如 Adaboost SAMME 算法,它的弱分类器的系数:

  其中 $R$ 为类别数。从上式可以看出,如果是二元分类, $R=2$,则上式和我们的二元分类算法中的弱分类器的系数一致。

2. Adaboost 回归算法

  Adaboost 回归算法有很多变种,需要做更细致的分析,对于 Adaboost R2 的方式可以参考刘建平的博客

3. Adaboost 应用

  • 弱学习器要怎么选?需要能够对样本加权值的模型?
  • 弱学习器数量要怎么选?
  • 调参怎么调?
  • 为什么常用的弱学习器不用不同模型,而选择同一种模型

3.1 基学习器

  对于基学习器的选择,理论上来说不一定非要“弱学习器”,你甚至可以选神经网络作为弱分类器。但是,基学习器最好是选择那些能够避免 overfitting 且能够控制模型复杂度的弱学习器。原因是 Boosting 一般会随着迭代的进行不可避免的增加 variance,如果基学习器就有较高的 variance(例如神经网络),那么训练好的最终模型很容易 overfitting 进而复杂度过高。一般来说,使用最广泛的 Adaboost 弱学习器是决策树和神经网络。对于决策树,Adaboost 分类用了 CART 分类树,而 Adaboost 回归用了 CART 回归树。

3.2 Adaboost 归一化

  为了防止 Adaboost 过拟合,我们通常会加入正则化项,其实是添加了一个学习率可以来控制算法迭代。在弱学习器的迭代中,我们在当前弱学习器上加上学习率 $\nu$:

  其中 $\nu$ 的取值范围是 $0 < \nu \leq 1$,较小的 $\nu$ 意味着我们需要更多的弱学习器的迭代次数,一般我们可以通过学习率和最大迭代次数来控制算法的拟合效果。

3.3 调参神学

  一般来说常用 Sklearn 里面集成好的 sklearn.ensemble.AdaBoostClassifier,可以通过这个接口很直接地看到需要注意的参数:

class sklearn.ensemble.AdaBoostClassifier(base_estimator=None, n_estimators=50, learning_rate=1.0, algorithm=SAMME.R, random_state=None)

  学习率、最大迭代次数是非常需要调节的参数,当然还有到底用多少个弱学习器也是可以调节的参数。

1) base_estimator:基学习器

  我们常用的一般是 CART 决策树或者神经网络 MLP,默认是决策树。需要注意的是,如果参数 algorithm 选择的是 SAMME.R,则我们的弱分类学习器还需要支持概率预测。

2) n_estimators: 弱学习器的最大个数

  n_estimators 太小,容易欠拟合,n_estimators 太大,又容易过拟合,一般选择一个适中的数值,默认是 50。在实际调参的过程中,我们常常将 n_estimators 和参数 learning_rate 一起考虑。

3) learning_rate:每个弱学习器的权重缩减系数

  为了防止 Adaboost 过拟合,我们通常也会加入正则化项,这个正则化项我们通常称为步长 (learning rate)。定义为 $\nu$,对于前面的弱学习器的迭代 $f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x)$ 加上了正则化项,则有

  $\nu$ 的取值范围为 $0 < \nu \leq 1$。对于同样的训练集学习效果,较小的 $\nu$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果,所以 n_estimators 和 learning_rate 要一起调参。

4) algorithm:实现分类 Adaboost 的两种算法 SAMME 和 SAMME.R

  两者的主要区别是基学习器权重的度量,SAMME 使用对样本集分类效果作为弱学习器权重 (原理中即为SAMME),而 SAMME.R 使用对样本集分类的预测概率大小来作为弱学习器权重。

  SAMME.R 迭代一般比 SAMME 快,一般使用默认的 SAMME.R 就够了。但是假如SAMME.R,则基学习器参数 base_estimator 必须使用支持概率预测的分类器。

  假如我们选取的基学习器为决策树,那么调参经常用到的还包括决策树的参数:

  • max_features
  • max_depth
  • min_samples_split
  • min_samples_leaf
  • min_weight_fraction_leaf
  • max_leaf_nodes 等

4. 总结

Adaboost 优点

  • Adaboost 作为分类器时,精度很高。
  • 在 Adaboost 的框架下,可以使用各种回归分类模型来构建学习器,非常灵活
  • 作为简单的二元分类器时,构造简单,结果可理解
  • 不容易发生过拟合

Adaboost 缺点

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

4.1 应用

  AdaBoost 算法最成功的应用之一是机器视觉里的目标检测问题,如人脸检测和行人检测。车辆检测。在深度卷积神经网络用于此问题之前,AdaBoost 算法在视觉目标检测领域的实际应用上一直处于主导地位。

Gradient Descent 角度理解 Adaboost 推导?

References

  1. ML Lecture 22: Ensemble
  2. 第06章:深入浅出ML之Boosting家族
  3. 集成模型之Adaboost算法(三)
  4. 集成学习之Adaboost算法原理小结
  5. AdaBoost Fits an Additive Model
  6. AdaBoost算法
  7. AdaBoost
  8. 前向分步算法 && AdaBoost算法 && 提升树(GBDT)算法 && XGBoost算法
  9. 理解AdaBoost算法