AdaBoost提升方法

Boosting算法基于如下理论:

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

这意味着在学习中,如果已经发现了“弱学习算法”,那么可以提升(boost)为“强学习算法”。其中需要解决两个问题:

  1. 如何在每轮弱分类器的学习中改变训练数据的权值,即改变样本的概率分布;
  2. 如果将弱分类器组合成一个强分类器。

adaboost

adaboost(Adaptive Boosting)算法表述如下:

输入:训练数据集 $T={(x_1,y_1),\dots,(x_N,y_N)}$ ,其中 $x_i \in \mathcal{X} \subseteq \Re^n$ , $y_i \in \mathcal{Y} = {-1, 1}$ ; 输出:分类器 $G(x)$ 。

(1) 初始化训练数据的权值为等权值分布:

(2) 使用具有权值分布 $D_m$ 的训练数据集学习,其中, $m=1,\dots,M$ ,得到弱分类器:

计算 $G_m(x)$ 的训练错误率(error rate),即加和所有分类错误的权值:

其中, $w_{m,i}$ 表示第 $m$ 轮中第 $i$ 个实例的权值,且 $\sum_{i=1}^N w_{m,i} = 1$ 。

计算 $G_m(x)$ 的系数(该系数即用于调整每次迭代时训练样本分布的新权值):

以此系数更新训练样本的权值分布:

其中,单个样本的权重 $w_{m+1,i}$ ,根据样本是否被错分,计算如下:

这将使得正确分类的样本权重降低,而错误分类的样本权重升高,每次错误分类样本的权值将被放大 $e^{2\alpha_m} = e_m/(1-e_m)$ 倍。因此,错误分类的样本在下一轮学习中将发挥更大作用,adaboost总是基于错误来提升分类器性能。这里解决了第一个问题,即不改变训练数据,只是不断改变训练数据权值的分布,使得训练数据在弱分类器的学习中起不同的作用。

当错误分类数为0,或者错误率低于某个阈值,可以结束迭代,得到所有的弱分类器。

(3) 构建弱分类器的线性组合:

得到最终的强分类器:

其中, $y = \mathrm{sign}(x)$ 是符号判别函数, $x \in \Re, \, y \in {-1,1}$ 。

这里解决了第二个问题,即将弱分类器组合成一个强分类器。

小结:通常都认为adaboost和SVM是监督学习中最强大的两种方法。实际两者也有不少相似之处,并且原始的这两种算法都只能用于二元分类问题。如果我们把弱分类器想象成SVM的一个核函数,也可以按照最大化某个最小间隔的方法重写adaboost算法,而它们的不同也在于所定义的间隔计算方式有所不同,特别是在高维空间下更加明显。

具体实现

单层决策树 decision stump

参考

  • 统计学习方法, 李航, 8. 提升方法