第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） 初始化训练数据的权值分布
（2） 对 $\(m = 1, 2, \cdots, M\)$
（a）使用具有权值分布 $\(D_m\)$ 的训练数据集学习，得到基本分类器
（b）计算 $\(G_m(x)\)$ 在训练数据集上的分类误差率
（c）计算 $\(G_m(x)\)$ 的系数
（d）更新训练数据集的权值分布
其中 $\(Z_m\)$ 是规范化因子
（3） 构建基本分类器的线性组合
得到最终分类器
说明：
步骤（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）可以写成：
由此可知，被基本分类器 $\(G_m(x)\)$ 误分类样本的权值得以扩大，而被正确分类样本的权值得以缩小。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用，这是AdaBoost的一个特点。步骤（3）中，线性组合 $\(f(x)\)$ 实现 $\(M\)$ 个基本分类器的加权表决。最终分类器 $\(G(x)\)$ 的符号决定实例 $\(x\)$ 的类别，$\(f(x)\)$ 的绝对值表示分类的确信度。
8.2 AdaBoost算法的训练误差分析
AdaBoost最基本的一个性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。
定理 8.1（AdaBoost的训练误差界） AdaBoost算法最终分类器的训练误差界为
其中 $\(G(x)\)\(、\)\(f(x)\)$ 和 $\(Z_m\)$ 由式（8.7）、式（8.6）和式（8.5）给出。
定理 8.2（二类分类问题AdaBoost的训练误差界）
其中 $\(\gamma_m = \frac{1}{2} - e_m\)$。
推论 8.1 如果存在 $\(\gamma > 0\)$，对所有 $\(m\)$ 有 $\(\gamma_m \geq \gamma\)$，则
这表明在此条件下AdaBoost的训练误差是以指数速率下降的。
8.3 加法模型与前向分步算法
8.3.1 前向分步算法
AdaBoost算法还有另一个解释，即可认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。
加法模型（additive model）考虑
其中 $\(b(x; \gamma_m)\)$ 为基函数，$\(\gamma_m\)$ 为基函数的参数，$\(\beta_m\)$ 为基函数的系数。显然，式（8.6）是一个加法模型。
在给定训练数据及损失函数 $\(L(y, f(x))\)$ 的条件下，学习加法模型 $\(f(x)\)$ 成为经验风险极小化即损失函数极小化问题：
前向分步算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式（8.14），那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
算法 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\)$
（b）更新
（3） 得到加法模型
8.3.2 前向分步算法与AdaBoost
定理 8.3 AdaBoost算法是前向分步加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。
证明：前向分步算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器
由基本分类器 $\(G_m(x)\)$ 及其系数 $\(\alpha_m\)$ 组成。损失函数是指数损失函数（exponential loss function）
假设经过 $\(m - 1\)$ 轮迭代前向分步算法已经得到 $\(f_{m-1}(x)\)$，在第 $\(m\)$ 轮学习 $\(\alpha_m\)\(、\)\(G_m(x)\)$ 和 $\(f_m(x)\)$，目标是使前向分步算法得到的 $\(\alpha_m\)$ 和 $\(G_m(x)\)$ 使 $\(f(x)\)$ 在训练数据集 $\(T\)$ 上的指数损失最小，即
求解可得
其中 $\(e_m\)$ 是分类误差率。这与AdaBoost算法第2（c）步的 $\(\alpha_m\)$ 完全一致。样本权值的更新也与AdaBoost算法第2（d）步的样本权值的更新等价。
8.4 AdaBoost与指数损失的关系
AdaBoost算法的一个重要解释是该算法实际是前向分步算法的一个实现。在这个方法里，模型是加法模型，损失函数是指数损失，算法是前向分步算法。
指数损失函数的形式为
对数几率函数与指数损失函数之间存在密切的关系。当使用指数损失函数时，分类问题的最优解可以通过不断拟合残差来逼近。AdaBoost通过指数损失函数建立了与加法模型的联系，使得前向分步算法能够有效地学习弱分类器的组合。
指数损失函数具有一个重要性质：它能够将对分类问题的求解转化为对重加权训练数据的分类问题。这正是AdaBoost算法通过改变训练数据的权值分布来逐步提升分类性能的理论基础。每一次迭代中，被前一轮弱分类器误分类的样本权值增加，而被正确分类的样本权值减小，这一机制与指数损失函数的数学性质密切相关。
8.5 提升树
提升树（boosting tree）是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学学习中性能最好的方法之一。
8.5.1 提升树模型
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型：
其中 $\(T(x; \Theta_m)\)$ 表示决策树，$\(\Theta_m\)$ 为决策树的参数，$\(M\)$ 为树的个数。
8.5.2 提升树算法
提升树算法采用前向分步算法。首先确定初始提升树 $\(f_0(x) = 0\)$，第 $\(m\)$ 步的模型是
其中 $\(f_{m-1}(x)\)$ 为当前模型，通过经验风险极小化确定下一棵决策树的参数 $\(\Theta_m\)$：
对于二类分类问题，提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，这是AdaBoost算法的特殊情况。对于回归问题的提升树，使用平方误差损失函数时，损失变简化为对残差的拟合。设
这是当前模型拟合数据的残差（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）计算残差：
（b）拟合残差 $\(r_{m,i}\)$ 学习一个回归树，得到 $\(T(x; \Theta_m)\)$
（c）更新 $\(f_m(x) = f_{m-1}(x) + T(x_i; \Theta_m)\)$
（3） 得到回归问题提升树
8.6 GBDT（梯度提升决策树）
提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
算法 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） 初始化
（2） 对 $\(m = 1, 2, \cdots, M\)$
（a）对 $\(i = 1, 2, \cdots, N\)$，计算
（b）对 $\(r_{m,i}\)$ 拟合一棵回归树，得到第 $\(m\)$ 棵树的叶结点区域 $\(R_{m,j}, \ j = 1, 2, \cdots, J_m\)$
（c）对 $\(j = 1, 2, \cdots, J_m\)$，计算
（d）更新 $\(f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J_m} c_{m,j} I(x \in R_{m,j})\)$
（3） 得到回归树
梯度提升算法中，第2（a）步计算损失函数的负梯度在当前模型的值，将其作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2（b）步估计回归树叶结点区域，以拟合残差的近似值。第2（c）步利用线性搜索估计叶结点区域的值，使损失函数极小化。
8.7 XGBoost原理
XGBoost（eXtreme Gradient Boosting）是对梯度提升决策树的进一步发展和改进，其核心在于对目标函数的正则化处理。XGBoost的目标函数由两部分组成：损失函数的和以及正则化项。
XGBoost的正则化目标函数为：
其中第一项 $\(\sum_{i=1}^{N} L(y_i, \hat{y}_i)\)$ 是经验损失，第二项 $\(\sum_{k=1}^{K} \Omega(f_k)\)$ 是正则化项，$\(K\)$ 是树的总个数。
树的复杂度定义为：
其中 $\(T\)$ 为叶结点的个数，$\(w_j\)$ 为第 $\(j\)$ 个叶结点的输出值，$\(\gamma\)$ 和 $\(\lambda\)$ 为正则化参数。
二阶导数近似：XGBoost使用损失函数的二阶泰勒展开来近似目标函数。设第 $\(t\)$ 步的预测为 $\(\hat{y}_i^{(t)}\)$，则目标函数在 $\(\hat{y}_i^{(t-1)}\)$ 处进行二阶展开：
其中 $\(g_i\)$ 为一阶导数：
$\(h_i\)$ 为二阶导数：
忽略常数项后，得到每个叶结点的最优权重：
对应的最优目标值为：
XGBoost通过Gain来评估分裂候选：
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\)$ |