AdaBoost 简介【译】

原文:AdaBoost 简介

目前的集成学习(Ensemble Learning)方法大致可分为两类:一是个体学习器之间存在强依赖关系、必须串行生成的序列化方法,代表算法是Boosting;二是个体学习器之间不存在强依赖关系,可同时生成的并行方法,代表算法是 Bagging 和 “随机森林(Random Forest)”。

首先要知道 AdaBoost(adaptive boosting) 算法Boosting算法族中的一员。Boosting算法可将弱学习器提升为强学习器。所谓的弱学习器就是泛化性能略高于随机猜测的学习器,而强学习器很显然就是指泛化能力较高的学习器了。Boosting算法原理图:

Boosting

AdaBoost算法中有一个很重要的环节。每一个训练样本都被赋予权值,并且随着训练过程样本权值不断更新。更新的原则是:误分类样本被赋予更高的权值,而正确分类样本的权值被相应降低。通过这种方式能够将重点放在不能正确分类的样本上,新选出来的分类器能够发挥原有分类器没有的作用,提高整体的分类效果。

一、算法目标

如果你正在处理一个二分类模式识别问题,并且现在提供了一系列分类器,你可以从中选择使用哪些分类器(我们这里称之为小能手)。现在你想从中选出最优的几个小能手参加“超级碗”比赛。因此,你要选出一个十一人梦之队。假设给定的数据 $x_i$ 和每个分类器(小能手) $k_j$ 可以发表一个观点 $k_j(x_i) \in{\{-1,1\}}$,并且根据这些观点最终得出的决定是 sign(C(x_i)),这个 sign函数是所有小能手提出的观点的带权之和:

这里的 $k_1,k_2,…,k_11$ 表示这十一个小能手代表的时哪一种分类器。然后前面的常数 $a_1,a_2,…,a_11$ 是我们给定的每个小能手的权重。此外,小能手 $K_j$ 只能回答 “yes(+1)” 或者 “no(-1)” 来对问题分类。这里的 sign 函数是一个非线性决策,它是由这一些列线性分类器组合而成。

二、寻找合适的分类器

如果你也想参加我们这个分类器比赛,你要做的是:1)找到适合的队员,2)召集他们,3)根据他们的贡献给他们分配权重值。

寻找合适队员的工作是通过使用分类器训练数据集 N 中的一部分 T 来完成,N中得数据就是一个多维数据点 $x_i$。对于每一个 $x_i$ ,它们都有一个相对应的标签 $y_i = 1$ 或者 $y_i=-1$。如果分类器判断错误,我们就给这个分类器减去一个值 $e^{\beta}$,如果分类器判断正确,我们就给这个分类器减去一个值 $e^{-\beta}$,这样对所有的分类器进行测试和排序。这里的 $\beta > 0$,所以会保证判断错误的惩罚值会比判断正确地要高。不过也许你会奇怪,为什么判断正确还要给一个惩罚值,但其实只要判断正确的惩罚值小于判断错误的惩罚值($e^{-\beta}<e^{\beta}$),那就是没有问题的。这类错误函数和常用的欧式距离不同,它是一种指数损失函数。AdaBoost就是使用的指数损失函数作为错误惩罚函数。

在测试这些分类器的时候,对于某一个分类器 L,我们构建一个矩阵 S,S 用1记录判断错误,用0记录判断正确。矩阵的列代表着每个数据点 $x_i$,列代表着第 j 个分类器:

分类器

在上面这个例子里,我们可以看到第一个分类器对第1,2和N这三个点得判断正确,对第3个点的判断错误。其他的分类器对数据点的判断结果也显而易见。

AdaBoost算法的主要思想就是通过自动迭代挑选出分类器。每次迭代的当前相关性(或者叫重要性)决定了数据集中得元素的权重。一开始,所有元素都分配的时相同的权重(1或者1/N,保持权重之和为1)。随着挑选的过程,越难判别的元素就会让它们的权重越高。这个挑选的过程就是选出对这些难判别元素分类效果较好地分类器。如果每次挑选的分类器只适用于那些已经可以正确判断的元素,那这个挑选的过程就没有意义了。如果想两次都挑选一个分类器,那直接复制它的权重即可。最好的“队员”就是能为团队提供新视野的人。挑选的分类器一定要最佳互补。“并不是每个人都能做四分卫的”。

三、征集分类器

每次迭代我们都要对所有分类器排序,然后选出最佳分类器。假设在第 m 次迭代时,我们已经筛选出了 m-1 个分类器,现在要选择下一个了。当前筛选出的 m-1 个分类器的线性组合如下:

所以扩展到第 m 个分类器时,线性组合表示为:

在第一次迭代的时候 m=1,C_{m-1} 是 0 。我们为第 m 个线性组合定义了总的代价或者总的错误作为指数损失为:

这里的 $a_m$ 和 $k_m$ 要通过优化方式得到。既然我们目标是要得到 $k_m$,这里重写一下上面的公式3.3:

注意这里的上标 m 不是幂,而是第 m 个;下标 m-1 也是代表第 m-1 个。i=1,….,N。

在第一次迭代中, $w_i^{(1)}=1,i=1,…,N$。而后面的迭代中,向量 $w^{(m)}$ 代表着第 m 次迭代分配给数据点的权重。我们可以把上面的公式3.4拆分成两个和:

公式3.5很重要,它表示总的代价就是判断正确的代价之和加上判断错误的代价之和(之前已经说过判断对错都要给一个代价)。把第一个代价和(判断正确代价和)表示为 $W_ce^{-a_m}$ ,然后第二个代价和(判断错误代价和)表示为 $W_ee^{a_m}$,所以公式3.5就可以表示为如下:

由于分类器 $k_m$ 的选择和 $a_m(a_m>0)$ 的具体值没有关系,所以对于一个固定的 $a_m$ 值来说,最小化代价函数 E 就等价于最小化 $e^{a_m}E$,同时因为公式3.6左右两边同时乘以 $e^{a_m}$ 得。

又因为 $e^{2a_m}>1$,所以公式3.7又可以变为:

这里的($W_c+W_e$) 就是总的代价 $W$,对于当前迭代来说它可以看做一个常量,它就是所有数据点的权重和。在第 m 个迭代时,如果我们选择了一个分类器使得错误判断的代价 $W_e$ 达到最小,那么等式3.7的右侧也就是当前迭代里的最小值了。正因为有了最小的代价,所以很显然这就保证我们选出的下一个分类器 $k_m$ 带有最小的惩罚值。

四、加权

之前的挑选分类器的时候都是直接假定权重值 $a_m$ 是一个常数,现在把它看做一个未知数,我们要来确定它的具体的值了。看公式3.6直接对 $a_m$ 求导得:

直接令公式3.9等于0,再乘以 $e^{a_m}$ 可以得到:

可以得到最优的 $a_m$ 就是:

而 $W$ 又是所有数据点权重之和,可以重写公式4.3得:

这里的 $e_m=W_e/W$,就是给定权重下,数据集的分类错误率。

五、伪代码

假设有一个数据集 T 里面的数据点为 $x_i$,这些数据点的标签 $y_i$ 是(+1,-1) 中的一个,假设所有数据点的权重初始值 $w_i^{(1)}=1$。我们想要从一系列分类器中选出 M 个分类器。执行 M 次迭代。每次迭代时,所有数据点的权重之和为 $W$,所有分类错误的数据点的权重和为 $W_e$。

AadBoost算法伪代码:

For m=1 to M
1.从一系列分类器中选出一个分类器错误分类权重和最小,也就是满足如下情况:

2.将分类器的权重值 $a_m$ 设置为:

这里的 $e_m=W_e/W$

3.为下一次迭代更新所有分类器的权重值。如果 $k_m(x_i)$ 分类错误,则设置:

否则设置:

以上就是 AdaBoost的伪代码。

第一步里面的那一系列分类器可以是一个分类器族,这里面有一个分类器可使当前权重情况下的损失函数达到最小值。分类器池不必提前给出,只要是这个分类器存在的即可。如果已经给出了有限个分类器,我们只要每次测试一个即可。而这个搜索矩阵 S 可以在每次迭代的时候重复使用,只要乘以权重值 $w^{(m)}$ 所对应矩阵的转置即可,这是为了每次都能得出误分类权重 $W_e$。

至于这些权重值,其实是表示了权重的变化步骤,因此只有误分类才会导致权重的变化。

值得注意的是权重向量 $w^{(m)}$ 是迭代构造的。每次迭代可能都会导致它全部重新计算,但是还算高效也简单易实现。

另外,那些弱分类器的权重值会是0。如果有一个完美的分类器($e_m=W_e/W=0$),那它的权重是无穷大,并且我们就只需要这一个分类器就好了。而一个劣质的分类器($e_m=W_e/W=1$)的权重很显然是负无穷大,其实这样也好,我们可以每次直接对它的分类结果取反,同样我们也只需要这一个分类器即可。

六、问题

  1. 假设我们为误分类分配了一个代价值 a,为正确分类分配了一个代价值 b,且 a>b>0,我们可以将这个代价值变形为 $a=c^d,b=c^{-d}$。这样指数损失函数 $e^{a_m},e^{-a_m}$也不影响它的通用性了。

参考:

[1] Y. Freund, and R. Shapire, “A decision-theoretic generalization of on-line
learning and an application to boosting”, Proceedings of the Second European
Conference on Computational Learning Theory, 1995, pp. 23–37.

[2] Paul A. Viola, Michael J. Jones, “Robust Real-Time Face Detection”, ICCV
2001, Vol. 2, pp. 747.

[3] T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning,
Springer-Verlag, New York, 2001.


THE END.

评论