监督学习(3) Ensemble: AdaBoost

发表于   |   分类于   |     |   阅读次数

导语

前面总结的SVM，决策树还有没有总结的神经网络等均是试图构建单一强大的学习器，通过选择不同细分的算法或调节参数应对不同的问题。而实际中我们自然希望“兼听则明”，将不同的分类器组合起来从而达到更好的效果。这种组合的思路被称作集成方法Ensemble Method。集成可以有多种形式：可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。 而本篇总结的AdaBoost则通过一系列弱学习器的组合达到很强的分类效果。

集成Ensemble

集成方法包括Bagging和Boosting，在介绍这两个概念之前先让我们了解下Boostrapping。

自举Bootstrapping

Bootstrapping名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法。它是一种有放回的抽样方法，允许抽取的样本集有重复元素，如下图所示。

屏幕快照 2016-12-18 08.48.53

自举汇聚Bagging

Bagging 是Bootstrap Aggregating的缩写。Bagging可分为三步：

  1. Boostrapping ：重抽样，从原始样本中抽出M个子集(可重复)
  2. Learning：对每个样本子集分别有一个分类器进行学习，得到M个结果
  3. Voting：对M个结果进行投票，最多的那个类别就是样本最终类别

bagging

可以看出Bagging的特点就是“平权” + “少数服从多数”。在样例选择上，Bagging 的训练集是随机选取的，每个分类器学习的样本集不同并且独立，其中的每个样例的权重相等。在进行分类(预测)时，每个预测函数的权重相等，并且可以并行计算。

好比一群学生想要得到一套考试题的答案，然后他们从这套考试题中随机抽出几道题组成N套考题。每个学生做其中一套得出被分配的题目的答案。最后这群学生将每道题目的答案汇总起来，选每道题得票最多的那个选项作为最终答案。这种方法很快，因为大家都在同时做，而且效果看起来也不错。

但是这种“少数服从多数”方法也有很大的缺陷。正如“正确答案往往掌握在少数学霸手中”，如果大部分学生(预测函数)对某一道题选(预测)错了那么投票后自然也还是错的。更致命的是大家都是独立做的，并不知道哪道题是”易错题”，因此就没有办法针对这种”错题”刻意训练提高准确率了。

提升Boosting

Boosing由Schapire在1989年提出。Bagging是并行学习，每个分类器相互独立；Boosting中的是串行学习，后一个分类器依赖于前一个分类器的结果，通过集中关注被已有分类器错分的那些数据来组合成新的分类器。

要了解Boosting，必须先了解什么是”弱可学习”(weakly learnable)和相对应的”强可学习”(strongly learnable)。

这两个概念是由Kearns和Valiant两个人提出来的，他们指出：

在概率近似正确(probably pproximately correct, PAC)学习的框架中：一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好 ，那么就称这个概念是弱可学习的

注意“强可学习” 和“弱可学习”对应的是概念本身，不是某个具体的算法，“弱学习器”和“强学习器”对应的才是具体算法。简单来说，强学习器就是”学霸“，回回考试考95+；而弱学习器就是“学渣”，每次考试勉强及格，英语听力考试戴不戴耳机无所谓的那种。常见的弱学习器的有决策树桩Decision Tree Stump和感知机Perceptron。

后来Schapire证明了强可学习与弱可学习是等价的。也就是说我们可以将弱学习器“提升”为强学习器，因为弱学习器容易发现并且有模型简单计算快等优点。提升方法就是从学渣出发(弱学习器)，反复学习，得到一系列学渣(弱学习器)，然后组合这些学渣构成一个学霸(强学习器)。 Boosting的算法有很多，大多数都是改变训练数据的权值分布，AdaBoost便是其中一种。

下面再用一个例子，解释Boosting的过程。

假设现在有3个弱学习器$H_1,H_2,H_3$依次进行学习一个二类训练集$T$

  1. 随机从$T$中抽出一部分子集组成$T_1$，训练弱学习器$H_1$
  2. 从T中选取另一部分子集$T_2$ ，$T_2$满足的条件是$H_1$在$T_2$上一半正确一半错误 ，用$T_2$训练弱学习器$H_2$
  3. 将$H_1$和$H_2$意见不同的数据集组成$T_3$ ，用$T_3$训练$H_3$
  4. 最终结果由$H_1,H_2,H_3$投票表决

屏幕快照 2016-12-19 08.30.31

AdaBoost

AdaBoost 是Adaptive Boosting的缩写。它的核心思路有两个：

  1. 在每一轮过后通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。(建立“错题本”，多关注错题，少关注做对的题)

  2. 通过加法模型将弱分类器进行线性组合，AdaBoost通过加权多数表决的方式，增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。即

    其中，$h_t(x)$ 表示预测函数(弱学习器)，$\alpha_t$表示该预测函数的权值

算法

屏幕快照 2016-12-18 14.48.05

输入：二类训练集$(x_1, y_1), \dots, (x_n, y_n)$， $y_i \in {+1, -1}$

  1. 初始化训练集权值分布$D_1(i) = \frac{1}{N}$
  2. 对$t = 1,2 \dots, T$
    • 对有$D_t$ 权值分配的训练集学习，得到分类器$h_t(x)$
    • 计算$ht(x)$在训练集上的误差率 $err_t = \sum{i =1}^N D_t(i) I(y_i \ne h_t)$
    • 计算$h_t(x)$ 系数 $\alpha_t = \frac{1}{2}ln \frac{1 - err_t}{err_t}$
    • 更新权值分布$D{t+1}(i) = \frac{D_t(i) exp(-\alpha_t y_i h_t(x_i))}{Z_t}$,其中$Z_t$ 是规范化因子$Z_t = \sum{i=1}^N D_t(i)exp(-\alpha_t y_i h_t(x_i))$
  3. 构建分类器的线性组合$f(x) = \sum{t =1}^T \alpha_t h_t(x)$ 得到最终分类器$H(x) = sign(\sum{t =1}^T \alpha_t h_t(x))$

举例

下面用一个例子说明上述AdaBoost权值更新算法。

屏幕快照 2016-12-19 09.09.21

如上图所示数据集有10个数据点，一半正类一半负类，现在我们用决策树桩作为基本分类器进行学习，决策桩在本例中是一条线。

屏幕快照 2016-12-19 09.13.39

初始化权值$D_1$：10个数据点，每个数据点权值为$\frac{1}{10}$

$h_1:$ 蓝色部分为$h_1$分的正类，粉色部分为负类。有三个正类被分错了，因此误差率$\epsilon_1 = 0.1\times 3 = 0.3$ ，计算$h_1$的系数$\alpha_1 = \frac{1}{2} \frac{1-0.3}{0.3} = 0.42$ 。更新数据权值，经计算后三个被分错的正类权值分别由0.1变为0.165，而其余7个分类正确的权值由0.1降为0.072。因此在数据集权值分布变为$D_2$ ,被分错的三个点形状变大了，正确的点变小了。

屏幕快照 2016-12-19 09.38.23

$h_2:$ 针对具有$D_2$ 权值分布的数据进行分类，将线画在了右侧。此时$h_2$分类误差率为$\epsilon_2 = 0.21$ ，$h_2$的系数$\alpha_2=0.65$。如最右所示，更新各数据点权值为$D_3$ ，此时最左侧两个正类和最右侧的两个负类两次均分类正确，权值近一步降低为0.046；第一次被分错的三个正类，这次被分对了，权值由$D_2$ 中 0.165降为0.104，仍比最初0.1高；三个被分错的负类权值由0.072升为0.167。

屏幕快照 2016-12-19 09.57.53

$h_3:$ 基于数据集权值分布$D_3$，得到$h_3$ 的误差率$\epsilon_3 = 0.14$ ，$h_3$ 的系数$\alpha_3 = 0.92$

屏幕快照 2016-12-19 10.01.49

最后组合$h1,h_2,h_3$，得到最终的分类函数$H{final}$ 。可以看出通过数据点权值的更改，仅将分类效果很弱的分类器组合起来也得到了不错的分类效果。

优缺点

优点

  • 简单，计算高效
  • 没有复杂的参数
  • 关注更难分类的数据
  • 不易过拟合(原因：margin增大，详见参考14)
  • 多样性-可以选不同的基本分类器

缺点

  • 对噪声敏感
  • 需要挑一个好的弱学习器

结语

AdaBoost 还有其他的解释，即可认为AdaBoost是加法模型，损失函数为指数函数的分类学习方法。更严谨深入的研究可以参考Reference 1,2,4; AdaBoost 的实现可参考Reference 3。期望本篇能对大家有所帮助，如有错误请在评论里指出;)

References

  1. Trevor Hastie, Robert Tibshirani, Jerome Friedman The Elements of Statistical Learning
  2. 李航 《统计学习方法》
  3. 《机器学习实战》
  4. Introduction to Boosting
  5. What is a weak learner?
  6. Rob Schapire Theory and Applications of Boosting
  7. 快速理解bootstrap,bagging,boosting-三个概念
  8. Weak Learning, Boosting, and the AdaBoost algorithm
  9. A Brief Introduction to Adaboost
  10. bootstrap, boosting, bagging 几种方法的联系
  11. Bagging和Boosting 概念及区别
  12. Ensamble methods: Bagging and Boosting
  13. Quick Introduction to Boosting Algorithms in Machine Learning
  14. CSE 151 Machine Learning