10.10 通过梯度提升进行数值最优化

通过与数值最优化的类比，可推导出对于任意可微损失准则求解式 10.29 的快速近似算法。用函数 $f(x)$ 来预测 $y$ 在训练集上的损失为：

目标是寻找可最小化 $L(f)$ 的 $f$，这里对 $f(x)$ 的约束为树模型的求和形式（式 10.28）。如果忽略这条约束，那么对式 10.33 的最小化可视为一个数值的最优化问题：

其中的最优化“参数” $\mathbf{f}\in\mathbb{R}^N$ 就是近似函数在 $N$ 个样本的每个数据点 $x_i$ 上的取值 $f(x_i)$：

数值最优化过程对式 10.34 求解是一些成分向量和的形式：

其中的 $\mathbf{f}_0=\mathbf{h}_0$ 为初始猜测值，每个后续的 $\mathbf{f}_m$ 是基于当前的参数向量 $\mathbf{f}_{m-1}$ 推导出的，而后者是之前所推导出的所有“更新”的和。不同的数值最优化方法会用不同的方法来计算每个增量向量 $\mathbf{h}_m$（“步”）。

10.10.1 最陡下降

最陡下降（steepest descent） 方法所选的增量向量为 $\mathbf{h}_m=-\rho_m\mathbf{g}_m$，其中 $\rho_m$ 为一个数值而 $\mathbf{g}_m\in\mathbb{R}^N$ 为函数 $L(\mathbf{f})$j 在 $\mathbf{f}=\mathbf{f}_{m-1}$ 处的梯度（gradient）。梯度 $\mathbf{g}_m$ 中的成分为：

步长（step length）$\rho_m$ 为下式的解：

那么就可以更新当前步骤的解：

并且在下一个循环中重复这个过程。最陡下降可视为一个非常贪婪的策略，因为 $-\mathbf{g}_m$ 是函数 $L(\mathbf{f})$ 在 $\mathbb{R}^N$ 空间中 $\mathbf{f}=\mathbf{f}_{m-1}$ 点处局部的下降最快的方向。

10.10.2 梯度提升方法

前向分段提升方法（算法 10.2）也是一个非常贪婪的策略。在每个步骤中的解是给定当前模型 $f_{m-1}$ 和其拟合值 $f_{m-1}(x_i)$ 后可最大程度地降低式 10.29 的树模型。因此，其中的树模型给出的预测 $T(x_i;\Theta_m)$ 就类比于负的式 10.35 中的梯度。两者之间主要的差别是树模型的更新 $\mathbf{t}_m=(T(x_1;\Theta_m),\dots,T(x_N;\Theta_m))$ 彼此不是独立的。它们是由同一个 $J_m$ 终节点决策树模型得出的预测值，而负梯度则是无约束的下降程度最大的方向。

分段方法中式 10.30 的解就类比于最陡下降中式 10.36 的线搜索（line search）。其区别在于式 10.30 是对 $\mathbf{t}_m$ 中对应着各个不同终节点区域的成分 $\{T(x_i;\Theta_m)\}_{x_i\in R_{jm}}$ 分别进行的线搜索。

如果唯一的目标是对训练集上的损失（式 10.33）进行最小化，则最陡下降方法是更好的策略。任意可微的损失函数 $L(y,f(x))$ 的梯度（式 10.35）都很容易计算，相较而言在使用第 10.6 节中介绍的稳健准则后求解式 10.29 比较困难。但如果最终的目标是将函数 $f_M(x)$ 泛化到训练集中没有的新数据上，那么最陡下降方法难以解决的是梯度（式 10.35）只在训练集中的点 $x_i$ 上可定义。

这个困难的一个可能解决方案是在第 m 次循环步骤中推导出一个尽可能好地接近负梯度的树模型 $T(x;\Theta_m)$。使用平方误差来描述近似程度，可得：

也就是用一个最小化平方误差的回归树模型来拟合负梯度值（式 10.35）¹。如在第 10.9 节所述，最小化平方误差的决策树模型存在快速的推导算法。尽管式 10.37 的最小值解中的区域 $\tilde{R}_{jm}$ 会与式 10.29 解中的 $R_{jm}$ 有所差别，但一般来说对求解的目的来说两者足够相似。毕竟在任意的场景中，前向分段提升算法和决策树模型自上而下的推导本身都是一种近似的方法。在构建了式 10.37 中的树模型后，可通过式 10.30 得出每个区域所对应的常数值。

表 10.2：常用损失函数的梯度。

表 10.2 概括了常用损失函数的梯度。对于平方误差损失，负梯度也就是普通的残差 $-g_{im}=y_i-f_{m-1}(x_i)$，因而式 10.37 本身就等价于标准的最小化平方误差的提升方法。对于绝对误差损失，负梯度为残差的符号，因而在每步循环中式 10.37 是最小化当前残差符号的平方所拟合的树模型。对于 Huber 损失的稳健回归（M-regression），负梯度是上述两者之间的一个折中（详见表）。

分类问题中，损失函数为多项分布偏差（式 10.22），并在每步循环中创建 $K$ 个最小化平方误差的树模型。每个树模型 $T_{km}$ 都是对各自的负梯度向量 $\mathbf{g}_{km}$ 的拟合：

其中的 $p_k(x)$ 的定义如式 10.21。尽管在每步循环中构建了 $K$ 个不同的树模型，但它们之间存在着式 10.21 所定义的关系。对于二分类问题（$K=2$），只需要构建一个树模型（练习 10.10）。

10.10.3 梯度提升方法的实现

算法 10.3 梯度树模型提升算法（Gradient Tree Boosting Algorithm）

1. 初始化 $f_0(x)=\arg\min_\gamma\sum_{i=1}^NL(y_i,\gamma)$。
2. 对从 $m=1$ 到 $m=M$：
   1. 对每个 $i=1,2,\dots,N$ 计算 $$r_{im} = - \left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} \right]_{f = f_{m-1}}$$
   2. 对目标变量 $r_{im}$ 拟合一个回归树模型，得出终节点区域 $R_{jm},j=1,2,\dots,J_m$。
   3. 对每个 $j=1,2,\dots,J_m$ 计算 $$\gamma_{jm} = \arg\min_\gamma \sum_{x_i \in R_{jm}} L(y_i, f_{m-1}(x_i) + \gamma)$$
   4. 更新函数 $$f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{jm} I(x \in R_{jm})$$
3. 输出结果 $\hat{f}(x) = f_M(x)$。

算法 10.3 给出了回归问题的通用的梯度树模型提升算法。在其中插入不同的损失函数 $L(y,f(x))$ 就可得到具体的算法。算法的第一行用最优常数模型进行初始化，即只有一个终节点的树模型。第（2.1）行中计算出负梯度中的元素，也被称为广义残差或伪残差（pseudo residual）$r$。常用损失函数的梯度见表格 10.2。

分类问题的算法与之类似。在每步 $m$ 循环中用式 10.38 对每个类别进行步骤（2.1）-（2.4），共重复进行 $K$ 次。步骤（3）中的结果是 $K$ 个不同的（匹配的）树模型展开式 $f_{kM}(x)$，$k=1,2,\dots,K$。这些可通过式 10.21 而得出分类概率，或者通过式 10.20 给出分类结果。更多细节可见练习 10.9。这里有两个基础的调节参数：循环的次数 $M$ 和每个成分树模型 $J_m,m=1,2,\dots,M$ 的大小。

这个算法原本的实现叫作“多重加性回归树模型”（multiple additive regression trees，MART），在本书的第一版中有所介绍。本章中的很多图都由 MART 所产生。而本节所描述的梯度提升方法在 R 中有可自由获取的实现，gbm 程序包（Ridgeway, 1999, Gradient Boosted Models）。第 10.14.2 节使用了 gbm 程序包，在第十五、十六章中也有大量的使用。另一个 R 中的提升方法实现是 mboost 程序包（Hothorn and Bühlmann, 2006）。Salform Systems 公司提供了一个称为“TreeNet”的梯度提升或 MART 方法的商业版实现。

本节练习

练习 10.9

Consider a K-class problem where the targets $y_{ik}$ are coded as 1 if observation i is in class k and zero otherwise. Using the multinomial deviance loss function (10.22) and the symmetric logistic transform, use the arguments leading to the gradient boosting Algorithm 10.3 to derive Algorithm 10.4. Hint: See exercise 10.8 for step 2(b)iii.

练习 10.10

Show that for K = 2 class classification, only one tree needs to be grown at each gradient-boosting iteration.