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) 初始化训练数据的权值为等权值分布:

$$
D_1 = (w_{1,1},\dots,w_{1,N}), \, w_{1,i}=\frac{1}{N}, \, i=1,\dots,N
$$

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

$$
G_m(x): \mathcal{X} \to \{-1,+1\}
$$

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

$$
e_m = P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i) \neq y_i} w_{m,i}
$$

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

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

$$
\alpha_m = \frac{1}{2} \ln \frac{1-e_m}{e_m}
$$

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

$$
D_{m+1} = (w_{m+1,1},\dots,w_{m+1,N})
$$

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

$$
w_{m+1,i} = \left\{
\begin{array}{l l}
\frac{w_{m,i}}{\sum_{j=1}^N w_{m,j}} e^{-\alpha_m}, & \quad G_m(x_i) = y_i \\
\frac{w_{m,i}}{\sum_{j=1}^N w_{m,j}} e^{\alpha_m}, & \quad G_m(x_i) \neq y_i
\end{array}
\right.
$$

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

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

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

$$
f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)
$$

得到最终的强分类器:

$$
G(x) = {\rm sign}(f(x)) = {\rm sign} \left( \sum_{m=1}^M \alpha_m G_m(x) \right)
$$

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

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

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

具体实现

单层决策树 decision stump

参考

  • 统计学习方法, 李航, 8. 提升方法
2012-06-02 23:35
ml
status: part
comments powered by Disqus