集成学习之Adaboost算法原理

Posted by Qing on May 29, 2018

集成学习

集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务,有时也被称为多分类器。

下图显示出集成学习的一般结构:先产生一组“个体学习器”,再用某种策略将它们结合起来。 个体学习器通常由一个现有的学习算法从训练数据产生,例如决策树算法、BP神经网络算法等等。
若个体学习器都属于同一类别,例如都是决策树或都是神经网络,则称该集成为同质的(homogeneous);若个体学习器包含多种类型的学习算法,例如既有决策树又有神经网络,则称该集成为异质的(heterogenous)。

同质集成:个体学习器称为“基学习器”(base learner),对应的学习算法为“基学习算法”(base learning algorithm)。
异质集成:个体学习器称为“组件学习器”(component learner)或直称为“个体学习器”。 集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”尤为明显,因此集成学习的很多理论研究都是针对弱学习器进行的,而基学习器又被称为弱学习器。但需要注意的是,虽然从理论上来说使用弱学习器集成足以获得好的性能,但在实践中出于种种考虑,例如希望使用较少的个体学习器,或是重用关于常见学习器的一些经验等,人们往往会使用比较强的学习器。

上面我们已经提到要让集成起来的泛化性能比单个学习器都要好,虽说团结力量大但也有木桶短板理论调皮捣蛋,那如何做到呢?这就引出了集成学习的两个重要概念:准确性(accuracy)和多样性(diversity)。准确性指的是个体学习器不能太差,要有一定的准确度;多样性则是个体学习器之间的输出要具有差异性。通过下面的这三个例子可以很容易看出这一点,准确度较高,差异度也较高,可以较好地提升集成性能。

我们做个简单分析。考虑二分类问题和真实函数,假定基分类器的错误率为,即对每个基分类器 假设集成通过简单投票法结合T个基分类器,若有超过半数的基分类器正确,则集成分类就正确:

假设基分类器的错误率互相独立,则由 Hoeffding 不等式可知,集成的错误率为:

上式显示出,随着集成个体数目T的增大,集成的错误率将指数级下降,最终趋向于零。
但是上面的分析有一个关键假设:基学习器的误差相互独立。在现实任务中,个体学习器是为解决同一个问题训练出来的,它们显然不可能互相独立!事实上,个体学习器的“准确性”和“多样性”本身就存在冲突。一般,准确性很高之后,要增加多样性就需牺牲准确性。事实上,如何产生并结合“好而不同”的个体学习器,恰是集成学习研究的核心。
根据个体学习器的生成方式,目前的集成学习方法大致分为两大类:

  1. 个人学习器之间存在强依赖关系、必须串行生成的序列化方法。代表算法是Boosting;
  2. 以及个体学习器间不存在强依赖关系,可同时生成的并行化方法。代表算法是Bagging和“随机森林”。

提升方法与AdaBoost算法

提升方法(Boosting)是一族可将所分类器提升为强学习器的算法,这族算法的工作机制类似:

  • 先从初始训练集训练一个基学习器。
  • 再根据基学习器的表现对训练样本分布进行重调,使得先前基学习器做错的样本在后续受到更多的关注
  • 然后,基于调整后的样本分布来训练下一个基学习器
  • 一直重复上述步骤,直到基学习器的个数达到train前的指定数T,然后将这T个基学习器进行加权

对提升方法来说,有两个问题需要回答:一是在每一轮如何改变训练数据的权值或概率分布;二是如何将弱分类器组合成一个强分类器。关于这两个问题,Boosting族算法中最著名AdaBoost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。至于第二个问题,即弱分类器的组合,AdaBoost算法采用加权多数表决的方法。具体地,加大分类错误率小的弱分类器的权值,使其在决定中起较大的作用,减少分类误差率大的弱分类器的权值,使其在表决中起较小的作用。下面介绍AdaBoost算法的基本思路。

Adaboost算法的基本思路

现在叙述AdaBoost算法。假设给定一个二类分类的训练数据集

其中,每个样本点由实例与标记组成。实例,标记, AdaBoost算法利用下列算法,从训练数据集中学习一系列弱分类器或基分类器,并将这些弱分类器线性组合成为一个强分类器。

输入:训练集 ,训练轮数T,和一个基学习算法

输出:最终分类器

  1. 初始化训练数据的权值分布:

    1. 使用具有权值分布的训练数据集学习,得到基本分类器

    2. 计算在训练数据集上的分类误差率

    3. 计算的系数

    4. 更新训练数据集的权值分布 这里,是规范化因子 它使得成为一个概率分布。

  2. 构建基本分类器的线性组合 得到最终分类器

这里说明以下3个方面:

  • 计算基本分类器的系数表示在最终分类器中的重要性。当时,,并且随机的减小而增大,所以分类误差越小的基本分类器在最终分类器中的作用越大。
  • 可以写成: 由此可知,被基本分类器误分类样本的权值得以扩大,而被正确分类样本的权值却得以缩小。因此,误分类样本在下一轮学习中起更大的作用,不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基本分类器的学习中起不同的作用。
  • 最终分类器的生成是M个基分类器的加权表决。系数表示了基本分类器的重要性,这里,所有的之和并不为1。

Adaboost算法的推导

Adaboost算法有多种推导方式,比较容易理解的是基于“加性模型”,即基学习器的线性组合 来最小化指数损失函数

其中是样本的实际类别,是预测的类别,样本的权重服从分布,代表求期望。

损失函数的定义

那么损失函数为什么这样定义呢?下面证明: 若能使损失函数最小化,那我们考虑上式对的偏导为零:

令上式为零,得:

因此,有

时,时,

这样的分类规则正是我们所需要的,若指数函数最小化,则分类错误率也最小,它们俩是一致的。所以我们的损失函数可以这样定义。

基分类器权重系数 的求取

接下来,我们看一下基类器 和系数 的求取。

在Adaboost算法中,第一个分类器是直接将基学习算法用于初始数据分布求得,之后不断迭代,生成 。当第m个基分类器产生后,我们应该使得其在数据集第m轮样本权重基础上的指数损失最小,即:

考虑指数损失函数的导数为零

可解得

这恰是分类器权重更新公式

如何更新样本权重D?

这一部分比较长,在周志华老师《机器学习》P175有详细的推导,感兴趣的读者可以自行查阅。这里直接给出 的迭代公式。

其中 ,是一个常数。

AdaBoost算法的误差

随着集成学习中个体分类器数目的增加,其集成的错误率将成指数级下降,最终趋向于零。
李航老师《统计学习方法》有详细的证明。这里就不再赘述了。

总结

这里对AdaBoost算法的优缺点做一个总结。

AdaBoost的主要优点有:

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

AdaBoost的主要缺点有:

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

参考文档

机器学习-周志华
统计学习方法-李航
集成学习之Adaboost算法原理小结