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

8.1 提升方法AdaBoost算法

8.1.1 提升方法的基本思路

提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。

在概率近似正确（probably approximately correct，PAC）学习框架中，

一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；
一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

提升方法就是从弱学习算法，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

对于提升方法来说，有两个问题需要回答：

在每一轮如何改变训练数据的权值或概率分布；
如何将弱分类器组合成一个强分类器。

关于第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。

至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

8.1.2 AdaBoost算法

算法 8.1（AdaBoost）

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$；弱学习算法；

输出：最终分类器$G(x)$。

（1）初始化训练数据的权值分布

$D_1 = (w_{11},...,w_{1i},...,w_{1N})\ \ \ w_{1i} = \frac{1}{N},\ \ \ i= 1,2,...,N$

（2）对$m=1,2,…,M$

（a）使用具有权值分布$D_m$的训练数据集学习，得到基本分类器。

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

（b）计算$G_m(x)$在训练数据集上的分类误差率

$e_m = \sum\limits_{i = 1}^{N}P(G_m(x_i) \neq y_i) = \sum\limits_{i = 1}^{N}w_{mi}I(G_m(x_i) \neq y_i)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.1)$

（c）计算$G_m(x)$的系数

$\alpha_m = \frac{1}{2}\log\frac{1 - e_m}{e_m}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.2)$

这里的对数是自然对数。

（d）更新训练数据集的权值分布

$D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.3)$ $w_{m+1,i} = \frac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i)), \ \ \ i= 1,2,...,N \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.4)$

这里，$Z_m$是规范化因子

$Z_m = \sum\limits_{i = 1}^{N} w_{mi}\exp(-\alpha_my_iG_m(x_i))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.5)$

它使$D_{m+1}$成为一个概率分布。

（3）构建基本分类器的线性组合（所有$\alpha_m$之和并不为1）

$f(x) =\sum\limits_{i = 1}^{N} \alpha_m G_m(x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.6)$

得到最终分类器

$G(x) = sign(f(x)) = sign(\sum\limits_{i = 1}^{N} \alpha_m G_m(x))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.7)$

AdaBoost的特点：

不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用；
利用基本分类器的线性组合构建最终分类器。

8.2 AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。

定理 8.1（AdaBoost的训练误差界） AdaBoost算法最终分类器的训练误差界为

$\frac{1}{N}\sum\limits_{i = 1}^{N}I(G(x_i) \neq y_i) \leq \frac{1}{N}\sum\limits_{i}\exp(-y_i f(x_i)) = \prod\limits_{m} Z_m\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.9)$

这里，$G(x),f(x)$和$Z_m$分别由式$(8.7)$、式$(8.6)$和式$(8.5)$给出。

这一定理说明，可以在每一轮选取适当的$G_m$使得$Z_m$最小，从而使训练误差下降最快。

定理 8.2（二类分类问题AdaBoost的训练误差界）

$\prod\limits_{m=1}^{M} Z_m = \prod\limits_{m=1}^{M} [2\sqrt{e_m(1-e_m)} ]$ $= \prod\limits_{m=1}^{M} \sqrt{(1-4\gamma^2_m)}$ $\ \ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq \exp(-1\sum\limits_{m=1}^{M} \gamma_m^2)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.10)$

这里，$\gamma_m = \frac{1}{2} - e_m$。

推论 8.1 如果存在$\gamma > 0$，对所有$m$有$\gamma_m \geq \gamma$，则

$\frac{1}{N}\sum\limits_{i=1}^{N}I(G(x_i) \neq y_i) \leq \exp(-2M\gamma^2)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.12)$

这表明在此条件下AdaBoost的训练误差是以指数速率下降的。

AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。

8.3 AdaBoost算法的解释

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

8.3.1 前向分步算法

考虑加法模型（additive model）

$f(x) = \sum\limits_{m=1}^{M}\beta_m b(x;\gamma_m)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.13)$

其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数。

在给定训练数据及损失函数$L(y,f(x))$的条件下，学习加法模型$f(x)$成为经验风险极小化即损失函数极小化问题：

$\min\limits_{\beta_m,\gamma_m} \sum\limits_{i=1}^{N} L(y_i,\sum\limits_{m=1}^{M}\beta_m b(x_i;\gamma_m))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.14)$

前向分步算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数$(8.14)$，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：

$\min\limits_{\beta,\gamma} \sum\limits_{i=1}^{N} L(y_i,\beta b(x_i;\gamma))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.15)$

算法 8.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$

（a）极小化损失函数

$(\beta_m,\gamma_m) = \arg\min\limits_{\beta,\gamma}\sum\limits_{i=1}^{N} L(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.16)$

得到参数$\beta_m,\gamma_m$。

（b）更新

$f_m(x) = f_{m-1}(x) + \beta_m b(x;\gamma_m)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.17)$

（3）得到加法模型

$f(x) = f_M(x) = \sum\limits_{m=1}^{M}\beta_m b(x;\gamma_m)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.18)$

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

8.3.2 前向分步算法与AdaBoost

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

8.4 提升树

提升树是以分类树或回归树为基本分类器的提升方法。

8.4.1 提升树模型

以决策树为基函数的提升方法称为提升树（booting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。

提升树模型可以表示为决策树的加法模型：

$f_M(x) = \sum\limits_{m=1}^{M}T(x;\Theta_m)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.24)$

其中，$T(x;\Theta_m)$表示决策树，$\Theta_m$为决策树的参数，$M$为树的个数。

8.4.2 提升树算法

提升树算法采用前向分步算法。首先确定初始提升树$f_0(x) = 0$，第$m$步的模型是

$f_m(x) = f_{m-1}(x) + T(x;\Theta_m)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.25)$

其中，$f_{m-1}(x)$为当前模型，通过经验风险极小化确定下一棵决策树的参数$\Theta_m$：

$\hat \Theta_m = \arg\min\limits_{i=1}^{N}L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.26)$

针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。

对于二分类问题，提升树算法只需将AdaBoost算法8.1中的基本分类器限制为二类分类树即可，可以说这时的提升树算法是AdaBoost算法的特殊情况。

已知一个训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n$，$\mathcal{X}$为输入空间，$ y \in Y \subseteq R$，$\mathcal{Y}$为输出空间。如果将输入空间$\mathcal{X}$划分为$J$个互不相交的区域$R_1,R_2,…,R_J$，并且在每个区域上确定输出的常量$c_j$，那么树可表示为

$T(x;\Theta) = \sum\limits_{j=1}^{J}c_jI(x \in R_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.27)$

其中，参数$\Theta = \{(R_1,c_1),(R_2,c_2),…,(R_J,c_J)\}$表示树的区域划分和各区域上的常数。$J$是回归树的复杂度即叶结点个数。

回归问题提升树使用以下前向分步算法：

$f_0(x) = 0$ $f_m(x) = f_{m-1}(x) + T(x;\Theta_m), \ \ \ m = 1,2,...,M$ $f_M(x) = \sum\limits_{m=1}^{M}T(x;\Theta_m)$

在前向分步算法的第$m$步，给定当前模型$f_{m-1}(x)$，需求解

$\hat \Theta_m = \arg\min\limits_{i=1}^{N}L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))$

得到$\hat \Theta_m$，即第$m$棵树的参数。

当采用平方误差损失函数时，

$L(y,f(x)) = (y-f(x))^2$

其损失变为

$L(y,f_{m-1}(x) + T(x;\Theta_m)) = [y- f_{m-1}(x)-T(x;\Theta_m)]^2$ $= [r-T(x;\Theta_m)]^2$

这里，

$r = y- f_{m-1}(x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.28)$

是更强模型拟合数据的残差（residual）。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。

算法 8.3（回归问题的提升树算法）

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，$x_i \in \chi = R^n$，$ y \in Y \subseteq R$；

输出：提升树$f_M(x)$。

（1）初始化$f_0(x) = 0$。

（2）对$m = 1,2,…,M$。

（a）按式$(8.28)$计算残差：

$r_{mi} = y_i- f_{m-1}(x_i), \ \ \ i=1,2,...,N$

（b）拟合残差$r_{mi}$学习一个回归树，得到$T(x;\Theta_m)$。

（c）更新$f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$。

（3）得到回归问题提升树

$f_M(x) = \sum\limits_{m=1}^{M}T(x;\Theta_m)$

8.4.3 梯度提升

对于一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值

$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

作为回归问题提升树算法中的残差近似值，拟合一个回归树。

算法 8.4（梯度提升算法）

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，$x_i \in \chi = R^n$，$ y \in Y \subseteq R$；

输出：提升树$\hat f(x)$。

（1）初始化

$f_0(x) = \arg\min\limits_{c}\sum\limits_{i=1}^{N}L(y_i,c)$

（2）对$m = 1,2,…,M$

（a）对$i=1,2,…,N$，计算

$r_{mi} = -[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

（b）对$r_{mi}$拟合一个回归树，得到第$m$棵树的叶结点区域$R_{mj},j=1,2,…,J$。

（c）对$j=1,2,…,J$，计算

$c_{mj} =\arg\min\limits_{c}\sum\limits_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i) + c)$

（d）更新$f_m(x) = f_{m-1}(x) + \sum\limits_{j=1}^{J}c_{mj}I(x \in R_{mj})$

（3）得到回归树

$\hat f(x) = f_M(x) = \sum\limits_{m=1}^{M}\sum\limits_{j=1}^{J}I(x \in R_{mj})$

算法第1步初始化，估计使损失函数极小化的常数值，它是只有一个根结点的树。
第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。
- 对于平方损失函数，它就是通常所说的残差；
- 对于一般损失函数他就是残差的近似值。
第2(b)步估计回归树叶结点区域，以拟合残差的近似值。
第2(c)步利用线性搜索估计叶结点区域的值，是损失函数极小化。
第2(d)步更新回归树。
第3步得到输出的最终模型$\hat f(x)$

Blog

第八章提升方法