提升方法

提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本集样本的权重,学习多个分类器,并将这些分类器进行线性组合,提升分类性能。

提升方法的基本思路

提升方法基于这样一种思想: 对于一个复杂的任务来说,将多个专家判断进行适当的综合所得出的判断要比其中任何一个专家单独判断好, 实际上就是“三个臭皮匠顶一个诸葛亮”的道理。 历史上, Kearns和Valiant首先提出了“强可学习(strongly learnable)”和“弱可学习(weakly learnable)”的概念。指出:在概率近似正确(probably approximately correct, PAC)学习框架中,一个概念(一个类), 如果存在一个多项式的学习的算法能够学习它,学习的正确率仅比随机猜测的略好,那么就称这个概念是弱可学习的;一个概念,如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么这个概念是强可学习的。 非常有趣的是Schapire后来证明强可学习与弱可学习是等价的,也就是说,在PAC学习框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

这样一来,问题便成为,在学习中,如果已经发现了“弱可学习”算法,那么能够将它提升(boost)为“强可学习”算法。大家知道,发现弱可学习算法要比发现强可学习算法容易的多。那么如何具体实施提升,便成为开发提升方法时所要解决的问题。关于提升方法的研究很多,有很多算法被提出。最具代表性的是AdaBoost算法(AdaBoost Algorithm)。

对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要求比精确的分类规则(强分类器)容易的多。提升方法就是从弱分类器学习算法出发,反复学习,得到一系列弱分类器(又称为基分类器),然后组合这些弱分类器,构成一个强分类器。大多数提升算法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

这样对提升算法来说,有两个问题需要回答: 一是在每一轮如何改变训练数据的权值活概率分布;二是如何将弱分类器组合成一个强分类器。关于第1个问题,AdaBoost的做法是提高那些被前一轮拖分类器错误分类的样本权值。这样一来,那些没有得到正确分类的数据,由于其权值加大而受到后一轮分类器的更大关注。于是分类问题被一系列弱分类器“分而治之”。至于第2个问题,即弱分类器的组合,AdaBoost采取加权多数表决的方法。具体地,加大分类误差率小的弱分类器的权值,使其在表决中起到较大作用,减小分类误差率大的弱分类器的权值,使其在表决中起到较小的作用。

AdaBoost

AdaBoost算法

现在叙述AdaBoost算法。假设给定一个二分类的训练数据集\[T=\{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}\]其中,每个样本点由实例与标记组成。实例\(x_i \in \mathcal{X} \subseteq R^n\), 标记\(y_i \in \mathcal{Y} = \{-1, +1\}\), \(\mathcal{X}\) 是实例空间, \(\mathcal{Y}\) 是标记集合。AdaBoost利用一下算法,从训练数据中学习一系列弱分类器,并将这些弱分类器线性组合成一个强分类器。

算法1 (AdaBoost)

  • 输入: 训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}\),其中\(x_i \in \mathcal{X} \subseteq R^n\)\(y_i \in \mathcal{Y} = \{-1, +1\}\);弱学习算法;
  • 输出: 最终分类器\(G(x)\)
  • 1 初始化训练数据的权值分布\[D_1 = (w_{11}, ..., w_{1i}, ..., w_{1n}) \quad , w_{1i} = \frac {1} {N} \quad, i = 1, 2, ..., N\]
  • 2 对\(m = 1, 2, ..., M\)
  • 2.a 使用具有权值分布\(D_m\)的训练数据集学习, 得到基本分类器\[G_m(x):\mathcal{X} \rightarrow {-1, +1}\]
  • 2.b 计算\(G_m(x)\)在训练数据集上的分类误差率\[e_m = \sum_{i = 1} ^N P(G_m(x_i) \neq y_i) = \sum _{i=1} ^N w_{mi}I(G_m(x_i) \neq y_i) \tag{1}\]
  • 2.c 计算\(G_m(x)\)的系数\[\alpha_m = \frac {1} {2} \log \frac {1 - e_m} {e_m} \tag{2}\]这里的对数是自然对数
  • 2.d 更新训练数据集的权值分布\[D_{m+1} = (w_{m+1,1}, ...,w_{m+1,i}, w_{m+1,N})\] \[w_{m+1,i} = \frac {w_{mi}} {Z_{m}} exp(-\alpha_m y_i G_m(x_i)), \quad i=1,2,...,N \tag{3}\] 这里,\(Z_m\)是规范化因子\[Z_m = \sum _{i=1} ^N w_{mi} exp(-\alpha_m y_i G_m(x_i))\] 它使\(D_{m+1}\)成为一个概率分布
  • 3 构建基本分类器的线性组合\[f(x) = \sum _{m=1} ^M \alpha _m G_m(x) \tag{4}\]得到最终分类器\[G(x) = sign(f(x)) = sign(\sum _{m=1} ^M \alpha _m G_m(x))\]

对AdaBoost算法做如下说明:

步骤1 假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类的讯息中作用相同,这一假设保证第1步能够在原始数据上学习基本分类器\(G_1(x)\)

步骤2 AdaBoost反复不学习基本分类器, 在每一轮m=1,2,…, m顺次执行下列操作:

a 使用当前分布\(D_m\)加权的训练数据集,学习基本分类器\(G_m(x)\) b 计算基本分类器\(G_m(x)\)在加权训练数据集上的分类误差率: \[e_m = \sum_{i = 1} ^N P(G_m(x_i) \neq y_i) = \sum _{G_m(x_i) \neq y_i} w_{mi}\]这里,\(w_{mi}\)表示第\(m\)轮中第\(i\)个实例的权值,\(\sum_{i=1} ^N w_{mi} = 1\)。 这表明, \(G_m(x)\)在加权的训练数据集上的分类误差率是被\(G_m(x)\)误分类样本的权值之和,由此可以看出数据权值分布\(Dm\)与基本分类器\(G_m(x)\)的分类误差率的关系。 c 计算基本分类器\(G_m(x)\)的的系数\(\alpha_m\)\(\alpha_m\)表示\(G_m(x)\)在最终分类器中的重要程度。由式3可知,当\(e_m <= \frac {1} {2}\)\(\alpha_m >= 0\),并且\(\alpha_m\)随着\(e_m\)的减小二增大,所以误差率越小的基本分类器在最终分类器中作用越大。 d 更新训练数据的权值分布为下一轮做准备,式3可以写成:\[w_{m+1,i} = \begin {cases} \frac {w_{mi}} {Z_m} e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac {w_{mi}} {Z_m} e^{\alpha_m}, & G_m(x_i) \neq y_i \end{cases}\]由此可知,被基分类器\(G_m(x)\)误分类样本的权值得以扩大,而被正确分类样本的权值得以缩小,两相比较,由式2可知误分类样本的权值被放大\(e^{2\alpha_m}=\frac{1-e_m} {e_m}\)倍。因此误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据,而不断改变数据权值的分布,使得训练数据在基本分类器的学习过程中起不同的作用,这是AdaBoost的一个特点。

步骤3 线性组合\(f(x)\)实现\(M\)个基本分类器的加权表决,系数\(\alpha_m\)表示了基本分类器\(G_m(x)\)的重要性,这里所有\(\alpha_m\)之和并不为1.\(f(x)\)的符号决定实例\(x\)的分类,\(f(x)\)的绝对值表示分类的确信度,利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。

AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差,即在训练数据集上的分类误差率,关于这个问题有下面定理:

定理1 (AdaBoost的训练误差界) AdaBoost算法最终分类器的训练误差界为\[\frac {1} {N} \sum _{i=1} ^N I(G(x_i) \neq y_i) <= \frac {1} {N} \sum _i exp(-y_i f(x_i)) = \prod _m Z_m\]这里,\(G(x)\),\(f(x)\)\(Z_m\)的定义都如前文给出。

证明 (略)

这一定理说明,可以在每一轮选取适当的\(G_m\)使得\(Z_m\)最小,从而使训练误差下降最快,对二分分类问题,有如下结果:

定理2 (二分类问题AdaBoost的训练误差界) \[\prod _{m=1} ^M Z_m = \prod_{m=1} ^M [2\sqrt{e_m(1-e_m)}] = \prod _{m=1} ^M \sqrt {(1-4 \gamma_m^2)} <= exp(-2 \sum _{m-1} ^M \gamma_m ^2)\]这里\(\gamma_m = \frac {1} {2} - e_m\)

证明 (略)

推论1 如果存在\(\gamma > 0\),对所有\(m\)\(\gamma_m >= \gamma\),则\[\frac {1} {N} \sum _{i=1} ^N I(G(x_i) \neq y_i) <= exp(-2M \gamma^2)\]

这表明在此条件下AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。

注意,AdaBoost算法不需要知道算法下界\(\gamma\),这正是Freund与Schapire设计AdaBoost时所考虑的。与一些早期的提升方法不同,AdaBoost具有适应性,即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来,Ada是Adaptive的简写。

AdaBoost算法的解释

AdaBoost算法还有另一种解释,即可以认为AdaBoost算法是模型为加法模型,损失函数为指数函数,学习算法为向前分步算法时的二类分类学习方法。

前向分步算法

考虑加法模型(additive model)\[f(x) = \sum _{m=1} ^M \beta _m b(x; \gamma _m)\] 其中, \(b(x; \gamma _m)\)为基函数, \(\gamma _m\)为基函数的参数, \(\beta _m\)为基函数的系数。显然,式4是一个加法模型。

在给定训练数据及损失函数\(L(y, f(x))\)的条件下,学习加法模型\(f(x)\)成为经验风险极小化即损失函数极小化问题:\[\min _{\beta _m, \gamma _m} \sum _{i=1} ^N L \left( y_i , \sum _{m=1} ^M \beta _m b(x_i; \gamma _m) \right) \tag{5}\]

通常这是一个复杂的优化问题。前向分步算法(forward stagewise algorithm)求解这一优化问题的想法是:因为学习的是加法模型,如果能从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数式5,那么就可以简化优化的复杂度。具体地,每步只需优化如下损失函数:\[\min _{\beta,\gamma} \sum _{i=1} ^N L(y_i, \beta b(x_i; \gamma))\]

给定训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}, \quad x_i \in \mathcal{X} \subseteq R^n, \quad y_i \in \mathcal{Y} = \{-1, +1\}\), 损失函数\(L(y, f(x))\)和基函数的集合\(\{b(x;\gamma)\}\),学习加法模型\(f(x)\)的前向分布算法如下:

算法2 (前向分步算法)

  • 输入: 训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}\); 损失函数\(L(y, f(x))\); 基函数集\(\{b(x;\gamma)\}\)
  • 输出: 加法模型\(f(x)\)

  • 1 初始化\(f_0(x) = 0\)
  • 2 对\(m=1,2, ..., M\)
  • 2.a 极小化损失函数\[(\beta_m, \gamma_m) = arg \min _{\beta, \gamma} \sum _{i=1} ^{N} L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma))\]得到参数\(\beta_m\), \(\gamma_m\)
  • 2.b 更新\[f(x) = f_{m-1}(x) + \beta_m b(x; \gamma _m)\]
  • 3 得到加法模型 \[f(x) = f_M(x) = \sum _{m=1} ^M \beta_m b(x; \gamma _m)\]

这样,前向分步算法将同时求解\(m=1\)\(M\)所有参数\(\beta_m\)\(\gamma_m\)的优化问题简化为逐次求解各个\(\beta_m\)\(\gamma_m\)的优化问题。

前向分布算法与AdaBoost

由前向分布算法可以推导出AdaBoost,用定理叙述这一关系。

定理 3 AdaBoost算法是向前分步加法算法的特例。这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。

证明: 前向分步算法学习的是加法模型,当基函数为基本分类器时,该加法模型等价于AdaBoost的最终分类器\[f(x) = \sum _{m=1} ^M \alpha_m G_m(x)\]由基本分类器\(G_m(x)\)及其系数\(\alpha_m\)组成, \(m=1,2,...,M\)。前向分步算法逐一学习基函数,这一过程与AdaBoost算法逐一学习基本分类器的过程一致,下面证明前向分步算法的损失函数是指数损失函数(exponential loss function) \[L(y, f(x)) = exp(-yf(x))\]时, 其学习的具体操作等价于AdaBoost算法学习的具体操作。

具体推导(略)。