浅谈对AdaBoost的理解

最近在学习目标检测和追踪方面的东西，看了一些论文，其中有很多涉及到AdaBoost算法及其变种。本人刚刚接触机器学习，所以查阅了一些这方面的资料，现在将自己的一些理解记录如下。

注：文中的多处图表和文字引用自周志华教授的著作《机器学习》

集成学习

首先看一下周志华的《机器学习》中对集成学习的定义：

集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统(multi-classifier system) 、基于委员会的学习(committee-based learning) 等。

也就是说，我们需要先产生一组“个体学习器”（又叫“基学习器”），然后通过某种组合策略（比如说所有“个体学习器”的输出结果进行投票或者取平均值）将其组合起来，形成一个“组合学习器”，如下图所示：

浅谈对AdaBoost的理解

其中，“个体学习器”一般是用结构简单的学习器。其学习效果有限，一般只比随即猜测好一点，所以，我们称之为弱学习器（week learner）。对应到分类问题，就叫做弱分类器。众多弱学习器可以是同一类型的，也可以是不同类型的。“组合学习器”一般具有很好的学习效果，我们称之为强学习器（strong learner）。对应到分类问题，就叫做强分类器。

正所谓“三个臭皮匠，顶个诸葛亮”，弱学习器通过组合之后的效果要好于每一个弱学习器的效果。但想要实现这样的效果，各个弱学习器需要满足两个要求：

单个弱学习器的性能要够好（要比随即猜测好，即正确率>50%）
不同的弱学习器要具有多样性（直观想象一下：如果所有的弱分类器都一样，那跟一个弱分类器就没有区别，就起不到“集中智慧，集体决策”的效果了）。

至于为什么要满足这两个要求，可以参见《机器学习》的集成学习章节，里面有一个例子可以帮助理解。

Boosting

既然集成学习是将多个“个体学习器”组合起来从而产生效果的，那么问题来了：我们如何选取这一系列的“个体学习器”呢？这些“个体学习器”之间究竟按照什么规则组合起来呢？对于这些问题，人们提出了很多的解决方案，这些解决方案一般被划分为两大类，下面是《机器学习》中的表述：

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类?即个体学习器问存在强依赖关系、必须串行生成的序列化方法?以及个体学习器间不存在强依赖关系、可同时生成的并行化方法;前者的代表是Boosting ，后者的代表是Bagging 和”随机森林” (Random Forest).

下面我们一起来了解一下Boosting方法。同样，先看一下《机器学习》中的表述：

先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器;如此重复进行，直至基学习器数目达到事先指定的值T ，最终将这T 个基学习器进行加权结合。

从上面的表述可以看出，Boosting其实一种算法思想，而不是具体的实现。而且从以上的表述可以看出，在根据Boosting的思想设计一种具体算法时有这么几个具体的问题需要解决：

如何根据前一个弱学习器的分类结果调整样本的分布，使得分类错误的样本得到更多的关注
如何确定各个弱分类器的权值
选用什么类型的弱学习器
如何使用样本训练每一个弱学习器（依赖于3）
迭代次数T（弱分类器个数T）如何选择

对这几个问题的不同解决方案，往往就代表着不同的具体算法。而在目前众多的基于Boosting思想的算法当中，最为著名的莫过于AdaBoost算法了。

AdaBoost

AdaBoost算法是Boosting思想的一种具体实现。AdaBoost算法规定了在学习过程中如何重新调整样本分布以及如何确定各弱分类器权值，即解决了上述的第1、2个问题。

先看一下AdaBoost的伪代码：

浅谈对AdaBoost的理解

简单的解释一下伪代码：

输入：
- 训练样本 $D$
- 弱分类器学习算法（未指定）
- 训练轮数 $T$ （未指定）
过程：
- 1.起初，假设样本是均匀分布的，所有的m个样本的权重都为 $1 / m$
- 2.进行 $T$ 次循环（生成 $T$ 个弱分类器）
- 3.采用某种学习算法，根据样本数据 $D$ 和对应的当前的权重 $D t$ ，学习出一个弱分类器。学习的目标是减少当前弱分类器的错误率 $ε t$
- 4.计算当前若分类器的错误率 $ε t$ 。这个错误率不仅仅与分类错误的样本个数有关，而且跟样本的权重有关（可以看作是错误样本的权重相加）。权重大的样本则会对错误率产生更大的影响。而步骤3又是以最小化错误率为目标，因此权重大的样本会更受重视（为了减小本轮的错误率，应尽可能的将权重大的样本分正确）。而样本的权重又是根据上一轮的分类结果产生的（上一轮的步骤7）。这样做的实质就是使上一轮分错的样本在本轮尽量分对。
- 5.检查当前弱分类器是否是“足够好的”，即错误率是否大于0.5
- 6.计算得到该分类器的权重 $α t$ ，错误率越小的分类器，权重越高
- 7.根据分类结果，更新样本的权重，更新后的权重为 $D t + 1$ ，使得被当前弱分类器分类错误的样本权重增加，分类正确的样本权重减小，更新后的权重供下一轮学习使用
输出：
- 强分类器，就是 $T$ 个若分类器的加权和

不过，AdaBoost算法并没有规定弱分类器的类型、训练弱分类器使用的学习算法以及训练的轮数（弱分类器的个数）。这些都可以根据实际的问题来确定。例如，在使用Haar-like特征+AdaBoost的经典人脸检测框架中，使用的弱分类器是深度为1的决策树，而 $T$ 是根据最终的人脸检测准确率来确定的。笔者最近也在看这方面的论文，后面想写一篇博客详细的记录一下自己的收获。

至此，我们已经对AdaBoost算法的思想和具体的实现过程有了初步的了解。根据笔者自身的经历，现在已经可以去阅读相关的论文、然后做一些基础的实践应用了。但机器学习作为一个比较重视理论基础的领域，进一步的了解算法背后的数学原理往往是开展进一步工作的关键（至少笔者目前是这么认为的）。而且，怀着一颗求知的心，我们也很想知道伪代码中那些公式是如何得出来的，不是吗？那么，期待我的下一篇博客吧! Y(^_^)Y

浅谈对AdaBoost的理解

集成学习

Boosting

AdaBoost

相关推荐