第8章：提升方法

8.1 提升方法 AdaBoost算法

提升方法（boosting）是统计学习中非常重要的一类方法，其核心思想是：将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。历史上，Kearns和Valiant首先提出了"强可学习"（strongly learnable）和"弱可学习"（weakly learnable）的概念。在概率近似正确（PAC）学习的框架下，一个概念如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

提升方法基于这样的思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

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

算法 8.1（AdaBoost）

输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)，其中 \(x_i \in \mathcal{X} \subseteq \mathbb{R}^n\)，\(y_i \in \mathcal{Y} = \{-1, +1\}\)；弱学习算法。

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

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

\[ D_1 = (w_{1,1}, w_{1,2}, \cdots, w_{1,N}), \quad w_{1,i} = \frac{1}{N}, \quad i = 1, 2, \cdots, N \]

（2） 对 \(m = 1, 2, \cdots, M\)

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

\[ G_m(x) : \mathcal{X} \rightarrow \{-1, +1\} \]

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

\[ e_m = \sum_{i=1}^{N} w_{m,i} I(G_m(x_i) \neq y_i) \qquad(8.1) \]

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

\[ \alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m} \qquad(8.2) \]

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

\[ D_{m+1} = (w_{m+1,1}, w_{m+1,2}, \cdots, w_{m+1,N}) \qquad(8.3) \]

\[ w_{m+1,i} = \frac{w_{m,i} \exp(-\alpha_m y_i G_m(x_i))}{Z_m}, \quad i = 1, 2, \cdots, N \qquad(8.4) \]

其中 \(Z_m\) 是规范化因子

\[ Z_m = \sum_{i=1}^{N} w_{m,i} \exp(-\alpha_m y_i G_m(x_i)) \qquad(8.5) \]

（3） 构建基本分类器的线性组合

\[ f(x) = \sum_{m=1}^{M} \alpha_m G_m(x) \qquad(8.6) \]

得到最终分类器

\[ G(x) = \text{sign}(f(x)) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right) \qquad(8.7) \]

说明：

步骤（1）假设训练数据具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同。步骤（2）中，AdaBoost反复学习基本分类器，在每一轮 \(m = 1, 2, \cdots, M\) 依次执行操作。步骤（2）（b）中，基本分类器 \(G_m(x)\) 在加权的训练数据集上的分类误差率是被 \(G_m(x)\) 误分类样本的权值之和。步骤（2）（c）中，由式（8.2）可知，当 \(e_m < \frac{1}{2}\) 时，\(\alpha_m > 0\)，并且 \(\alpha_m\) 随着 \(e_m\) 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。步骤（2）（d）中更新训练数据的权值分布为下一轮作准备。式（8.4）可以写成：

\[ w_{m+1,i} = \begin{cases} \frac{w_{m,i}}{Z_m} e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac{w_{m,i}}{Z_m} e^{\alpha_m}, & G_m(x_i) \neq y_i \end{cases} \]

由此可知，被基本分类器 \(G_m(x)\) 误分类样本的权值得以扩大，而被正确分类样本的权值得以缩小。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用，这是AdaBoost的一个特点。步骤（3）中，线性组合 \(f(x)\) 实现 \(M\) 个基本分类器的加权表决。最终分类器 \(G(x)\) 的符号决定实例 \(x\) 的类别，\(f(x)\) 的绝对值表示分类的确信度。

---

8.2 AdaBoost算法的训练误差分析

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

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

\[ \frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^{N} \exp(-y_i f(x_i)) = \prod_{m=1}^{M} Z_m \qquad(8.9) \]

其中 \(G(x)\)、\(f(x)\) 和 \(Z_m\) 由式（8.7）、式（8.6）和式（8.5）给出。

定理 8.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\left(-2\sum_{m=1}^{M} \gamma_m^2\right) \qquad(8.10) \]

其中 \(\gamma_m = \frac{1}{2} - e_m\)。

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

\[ \frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) < \exp(-2M\gamma^2) \qquad(8.12) \]

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

---

8.3 加法模型与前向分步算法

8.3.1 前向分步算法

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

加法模型（additive model）考虑

\[ f(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m) \qquad(8.13) \]

其中 \(b(x; \gamma_m)\) 为基函数，\(\gamma_m\) 为基函数的参数，\(\beta_m\) 为基函数的系数。显然，式（8.6）是一个加法模型。

在给定训练数据及损失函数 \(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) \qquad(8.14) \]

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

\[ \min_{\beta, \gamma} \sum_{i=1}^{N} L(y_i, \beta b(x_i; \gamma)) \qquad(8.15) \]

算法 8.2（前向分步算法）

输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)，\(x_i \in \mathcal{X} \subseteq \mathbb{R}^n\)，\(y_i \in \mathcal{Y}\)；损失函数 \(L(y, f(x))\)；基函数集 \(\{b(x; \gamma)\}\)。

输出：加法模型 \(f(x)\)。

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

（2） 对 \(m = 1, 2, \cdots, M\)

（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)) \qquad(8.16) \]

得到参数 \(\beta_m, \gamma_m\)

（b）更新

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

（3） 得到加法模型

\[ f(x) = f_M(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m) \qquad(8.18) \]

8.3.2 前向分步算法与AdaBoost

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

证明：前向分步算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器

\[ f(x) = \sum_{m=1}^{M} \alpha_m G_m(x) \qquad(8.19) \]

由基本分类器 \(G_m(x)\) 及其系数 \(\alpha_m\) 组成。损失函数是指数损失函数（exponential loss function）

\[ L(y, f(x)) = \exp[-y f(x)] \qquad(8.20) \]

假设经过 \(m - 1\) 轮迭代前向分步算法已经得到 \(f_{m-1}(x)\)，在第 \(m\) 轮学习 \(\alpha_m\)、\(G_m(x)\) 和 \(f_m(x)\)，目标是使前向分步算法得到的 \(\alpha_m\) 和 \(G_m(x)\) 使 \(f(x)\) 在训练数据集 \(T\) 上的指数损失最小，即

\[ (\alpha_m, G_m(x)) = \arg \min_{\alpha, G} \sum_{i=1}^{N} \exp[-y_i(f_{m-1}(x_i) + \alpha G(x_i))] \qquad(8.21) \]

求解可得

\[ \alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m} \qquad(8.22) \]

其中 \(e_m\) 是分类误差率。这与AdaBoost算法第2（c）步的 \(\alpha_m\) 完全一致。样本权值的更新也与AdaBoost算法第2（d）步的样本权值的更新等价。

---

8.4 AdaBoost与指数损失的关系

AdaBoost算法的一个重要解释是该算法实际是前向分步算法的一个实现。在这个方法里，模型是加法模型，损失函数是指数损失，算法是前向分步算法。

指数损失函数的形式为

\[ L(y, f(x)) = \exp[-y f(x)] \qquad(8.23) \]

对数几率函数与指数损失函数之间存在密切的关系。当使用指数损失函数时，分类问题的最优解可以通过不断拟合残差来逼近。AdaBoost通过指数损失函数建立了与加法模型的联系，使得前向分步算法能够有效地学习弱分类器的组合。

指数损失函数具有一个重要性质：它能够将对分类问题的求解转化为对重加权训练数据的分类问题。这正是AdaBoost算法通过改变训练数据的权值分布来逐步提升分类性能的理论基础。每一次迭代中，被前一轮弱分类器误分类的样本权值增加，而被正确分类的样本权值减小，这一机制与指数损失函数的数学性质密切相关。

---

8.5 提升树

提升树（boosting tree）是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学学习中性能最好的方法之一。

8.5.1 提升树模型

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型：

\[ f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m) \qquad(8.24) \]

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

8.5.2 提升树算法

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

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

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

\[ \Theta_m = \arg \min_{\Theta} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i; \Theta)) \qquad(8.26) \]

对于二类分类问题，提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，这是AdaBoost算法的特殊情况。对于回归问题的提升树，使用平方误差损失函数时，损失变简化为对残差的拟合。设

\[ r = y - f_{m-1}(x) \qquad(8.28) \]

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

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

输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)，\(x_i \in \mathcal{X} \subseteq \mathbb{R}^n\)，\(y_i \in \mathcal{Y} \subseteq \mathbb{R}\)；

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

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

（2） 对 \(m = 1, 2, \cdots, M\)

（a）按式（8.27）计算残差：

\[ r_{m,i} = y_i - f_{m-1}(x_i), \quad i = 1, 2, \cdots, N \]

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

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

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

\[ f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m) \qquad(8.29) \]

---

8.6 GBDT（梯度提升决策树）

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值

\[ r_{m,i} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x) = f_{m-1}(x)} \qquad(8.30) \]

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

算法 8.4（梯度提升算法）

输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)，\(x_i \in \mathcal{X} \subseteq \mathbb{R}^n\)，\(y_i \in \mathcal{Y} \subseteq \mathbb{R}\)；损失函数 \(L(y, f(x))\)。

输出：回归树 \(f(x)\)。

（1） 初始化

\[ f_0(x) = \arg \min_c \sum_{i=1}^{N} L(y_i, c) \qquad(8.31) \]

（2） 对 \(m = 1, 2, \cdots, M\)

（a）对 \(i = 1, 2, \cdots, N\)，计算

\[ r_{m,i} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x) = f_{m-1}(x)} \qquad(8.32) \]

（b）对 \(r_{m,i}\) 拟合一棵回归树，得到第 \(m\) 棵树的叶结点区域 \(R_{m,j}, \ j = 1, 2, \cdots, J_m\)

（c）对 \(j = 1, 2, \cdots, J_m\)，计算

\[ c_{m,j} = \arg \min_c \sum_{x_i \in R_{m,j}} L(y_i, f_{m-1}(x_i) + c) \qquad(8.33) \]

（d）更新

\[ f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J_m} c_{m,j} I(x \in R_{m,j}) \]

（3） 得到回归树

\[ f(x) = f_M(x) \qquad(8.34) \]

梯度提升算法中，第2（a）步计算损失函数的负梯度在当前模型的值，将其作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2（b）步估计回归树叶结点区域，以拟合残差的近似值。第2（c）步利用线性搜索估计叶结点区域的值，使损失函数极小化。

---

8.7 XGBoost原理

XGBoost（eXtreme Gradient Boosting）是对梯度提升决策树的进一步发展和改进，其核心在于对目标函数的正则化处理。XGBoost的目标函数由两部分组成：损失函数的和以及正则化项。

XGBoost的正则化目标函数为：

\[ \text{obj} = \sum_{i=1}^{N} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k) \qquad(8.35) \]

其中第一项 \(\sum_{i=1}^{N} L(y_i, \hat{y}_i)\) 是经验损失，第二项 \(\sum_{k=1}^{K} \Omega(f_k)\) 是正则化项，\(K\) 是树的总个数。

树的复杂度定义为：

\[ \Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \qquad(8.36) \]

其中 \(T\) 为叶结点的个数，\(w_j\) 为第 \(j\) 个叶结点的输出值，\(\gamma\) 和 \(\lambda\) 为正则化参数。

二阶导数近似：XGBoost使用损失函数的二阶泰勒展开来近似目标函数。设第 \(t\) 步的预测为 \(\hat{y}_i^{(t)}\)，则目标函数在 \(\hat{y}_i^{(t-1)}\) 处进行二阶展开：

\[ \text{obj}^{(t)} \approx \sum_{i=1}^{N} \left[L(y_i, \hat{y}_i^{(t-1)}) + g_i w_q(x_i) + \frac{1}{2} h_i w_q(x_i)^2\right] + \Omega(f_t) \qquad(8.37) \]

其中 \(g_i\) 为一阶导数：

\[ g_i = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} \qquad(8.38) \]

\(h_i\) 为二阶导数：

\[ h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2} \qquad(8.39) \]

忽略常数项后，得到每个叶结点的最优权重：

\[ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \qquad(8.40) \]

对应的最优目标值为：

\[ \text{obj}^* = -\frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T \qquad(8.41) \]

XGBoost通过Gain来评估分裂候选：

\[ \text{Gain} = \frac{1}{2} \left[\frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda}\right] - \gamma \qquad(8.42) \]

XGBoost的主要特点包括：使用二阶导数信息、加入正则化项防止过拟合、支持并行计算、缺失值自动处理。这些改进使得XGBoost在各种机器学习竞赛和实际应用中取得了卓越的效果。

---

公式汇总表

编号	公式名称	公式内容
(8.1)	分类误差率	\(e_m = \sum_{i=1}^{N} w_{m,i} I(G_m(x_i) \neq y_i)\)
(8.2)	系数计算	\(\alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m}\)
(8.4)	权值更新	\(w_{m+1,i} = \frac{w_{m,i} \exp(-\alpha_m y_i G_m(x_i))}{Z_m}\)
(8.5)	规范化因子	\(Z_m = \sum_{i=1}^{N} w_{m,i} \exp(-\alpha_m y_i G_m(x_i))\)
(8.6)	加法组合	\(f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)\)
(8.9)	训练误差界	\(\frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) \leq \prod_{m=1}^{M} Z_m\)
(8.10)	二类误差界	\(\prod_{m=1}^{M} Z_m = \prod_{m=1}^{M} 2\sqrt{e_m(1 - e_m)}\)
(8.13)	加法模型	\(f(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m)\)
(8.16)	前向分步极小化	\((\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))\)
(8.24)	提升树模型	\(f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m)\)
(8.28)	残差	\(r = y - f_{m-1}(x)\)
(8.30)	负梯度（残差近似）	\(r_{m,i} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x) = f_{m-1}(x)}\)
(8.35)	XGBoost目标函数	\(\text{obj} = \sum_{i=1}^{N} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k)\)
(8.36)	树复杂度	\(\Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2\)
(8.38)	一阶导数	\(g_i = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}\)
(8.39)	二阶导数	\(h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}\)
(8.40)	叶结点最优权重	\(w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}\)
(8.42)	分裂Gain	\(\text{Gain} = \frac{1}{2} \left[\frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda}\right] - \gamma\)