梯度提升技术

梯度提升，亦稱作梯度增强，是一种用于回归和分类问题的机器学习技术。其产生的预测模型是弱预测模型的集成，如采用典型的决策树作为弱预测模型，这时则为梯度提升树（GBT或GBDT）。像其他提升方法一样，它以分阶段的方式构建模型，但它通过允许对任意可微分损失函数进行优化作为对一般提升方法的推广。

梯度提升技術源自於Leo Breiman（英语：Leo Breiman）於1997年時將提升方法用於优化算法的观察^[1]。随后Jerome H. Friedman（英语：Jerome H. Friedman）於1999年時提出了显式回归梯度增强算法^[2][3]。Llew Mason、Jonathan Baxter、Peter Bartlett和Marcus Frean則針對梯度提升在一般的函数空间的運用進行研究，並於1999年在研討會發表之後^[4]，同年正式發表了论文^[5]。該论文介绍了将提升算法看作“函数空间上的梯度下降迭代”算法的观点。也就是将其视为通过迭代地选择指向负梯度方向的函数（弱预测模型），来优化函数空间上的成本函数的算法。这种将提升视为函数梯度的观点，导致了提升算法被運用於回归和分类之外的其他机器学习和统计领域的後續发展。

非正式介绍

（本节遵循Li对梯度增强的说明^[6]。）

与其他增强方法一样，梯度增强以迭代方式将弱的“学习器”组合为一个强学习器。最简单的解释是在最小二乘回归中，通过最小化均方误差 ${\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}}$  ，“教”模型${\displaystyle F}$ 预测实数值${\displaystyle {\hat {y}}=F(x)}$ 。

在梯度提升的每个阶段 ${\displaystyle m}$ , ${\displaystyle 1\leq m\leq M}$ , 假设已经有一个不太完美的模型 ${\displaystyle F_{m}}$  (最开始时只是一个预测输出变量 y 均值的模型)。 梯度提升算法通过在当前模型 ${\displaystyle F_{m}}$  增加一个新的估计量 h 得到一个更好的模型: ${\displaystyle F_{m+1}(x)=F_{m}(x)+h(x)}$ . 为了求得 ${\displaystyle h}$ , 梯度提升基于以下观察：一个完美的 h 可以完美预测当前不完美模型${\displaystyle F_{m}}$ 的残差，即满足，

${\displaystyle F_{m+1}(x)=F_{m}(x)+h(x)=y}$ 

或者，等效地有，

${\displaystyle h(x)=y-F_{m}(x)}$ .

因此，梯度提升通过拟合残差 ${\displaystyle y-F_{m}(x)}$ 得到 h 。和其他提升方法的变体一样, ${\displaystyle F_{m+1}}$  通过纠正 ${\displaystyle F_{m}}$ 的误差变得更完美。 这个想法可以扩展到均方误差损失之外的任意损失函数，甚至扩展到分类与排序问题，只要观察到以下一点：模型的残差 ${\displaystyle y-F_{m}(x)}$ 就是均方损失函数${\displaystyle {\frac {1}{2}}(y-F(x))^{2}}$ 关于${\displaystyle F(x)}$ 的负梯度。因此，梯度提升其实是一种 梯度下降算法，可以代入除了均方损失之外的不同的损失函数，得到不同的梯度。

算法

在许多有监督学习问题中，一个输出变量y和一个输入变量x通过联合概率分布${\displaystyle P(x,y)}$ 描述 。给定训练集${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ ，目的是在所有具有给定形式的函数${\displaystyle F(x)}$ 中找到一个${\displaystyle {\hat {F}}(x)}$ 使某些指定损失函数${\displaystyle L(y,F(x))}$ 的期望值达到最小：

${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$ .

梯度提升方法通过某一类${\displaystyle {\mathcal {H}}}$ 中弱学习器（或称基学习器）${\displaystyle h_{i}(x)}$ 带权重和的形式来表示对实值变量y做出估计的${\displaystyle {\hat {F}}(x)}$ :

${\displaystyle {\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const}}}$ .

根据经验风险最小化原理，该方法试图找到一个近似${\displaystyle {\hat {F}}(x)}$ 可以最大程度地减少训练集上损失函数的平均值，即，最小化经验风险。它是从一个由常数函数组成的模型${\displaystyle F_{0}(x)}$ 开始 ，并以贪心的方式逐步扩展：

${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$ ,

${\displaystyle F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]}$ ,

上式${\displaystyle h_{m}\in {\mathcal {H}}}$ 是基学习器。

不幸的是，通常在每个步骤中为任意损失函数L选择最佳函数h是计算上不可行的优化问题。因此，我们将方法局限于问题的简化版本。

这个想法是对这个最小化问题（函数梯度下降）应用梯度下降步骤。如果我们考虑连续情况，即${\displaystyle {\mathcal {H}}}$ 是上的任意微分函数的集合${\displaystyle \mathbb {R} }$  ，我们将根据以下方程式更新模型

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))},}$ 

${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},}$ 

式子中，对于${\displaystyle i\in \{1,..,m\}}$ 是关于函数${\displaystyle F_{i}}$ 求导，${\displaystyle \gamma _{m}}$ 是步长。 但是在离散情况下，即${\displaystyle {\mathcal {H}}}$ 如果是有限的，我们选择最接近L梯度的候选函数h ，然后可以根据上述等式通过线搜索来计算系数γ。请注意，这种方法是一种启发式方法，因此不能给出给定问题的精确解决方案，而是一种近似方法。 在伪代码中，通用梯度增强方法是^[2][7]：

Input: training set ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n},}$  a differentiable loss function ${\displaystyle L(y,F(x)),}$  number of iterations M.

Algorithm:

1. Initialize model with a constant value:

   ${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).}$ 

2. For m = 1 to M:
   1. Compute so-called pseudo-residuals:

      ${\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.}$ 

   2. Fit a base learner (or weak learner, e.g. tree) ${\displaystyle h_{m}(x)}$  to pseudo-residuals, i.e. train it using the training set ${\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}}$ .
   3. Compute multiplier ${\displaystyle \gamma _{m}}$  by solving the following one-dimensional optimization problem:

      ${\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).}$ 

   4. Update the model:

      ${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).}$ 

3. Output ${\displaystyle F_{M}(x).}$ 

梯度树增强

梯度提升通常与固定大小的决策树 （尤其是CART树）一起用作基础学习者。 对于这种特殊情况，Friedman提出了对梯度增强方法的改进，以提高每个基础学习者的适应质量。

第m步的通用梯度提升将适合决策树${\displaystyle h_{m}(x)}$ 伪残留物。 让${\displaystyle J_{m}}$ 是它的叶子数。 树将输入空间划分为${\displaystyle J_{m}}$ 不相交的区域${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$ 并预测每个区域的恒定值。 使用指标符号 ，输出${\displaystyle h_{m}(x)}$ 输入x可以写为和：

${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),}$ 

这里${\displaystyle b_{jm}}$ 是该区域中预测的值${\displaystyle R_{jm}}$ ^[a]。

然后系数${\displaystyle b_{jm}}$ 乘以一些值${\displaystyle \gamma _{m}}$  ，使用线搜索进行选择，以最大程度地减少损失函数，并按以下方式更新模型：

${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).}$ 

弗里德曼（Friedman）建议修改此算法，以便选择一个单独的最佳值${\displaystyle \gamma _{jm}}$ 每个树的区域，而不是单个${\displaystyle \gamma _{m}}$ 为整棵树。 他称修改后的算法为“ TreeBoost”。 系数${\displaystyle b_{jm}}$ 然后可以简单地丢弃树拟合过程中的数据，模型更新规则变为：

${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).}$ 

树木大小

${\displaystyle J}$  （树中终端节点的数量）是该方法的参数，可以针对手头的数据集进行调整。 它控制模型中变量之间允许的最大交互级别。 用${\displaystyle J=2}$  （ 决策树桩 ），不允许变量之间进行交互。 用${\displaystyle J=3}$ 该模型可能包括多达两个变量之间的相互作用的影响，依此类推。

Hastie等人评论通常${\displaystyle 4\leq J\leq 8}$ 对于提升效果很好，结果对选择${\displaystyle J}$ 在这个范围内${\displaystyle J=2}$ 不足以用于许多应用程序，并且${\displaystyle J>10}$ 不太可能是必需的^[7]。

正则化

过于紧密地拟合训练集可能导致模型的泛化能力下降。 几种所谓的正则化技术通过限制拟合过程来减少这种过度拟合的效果。

一个自然的正则化参数是梯度提升迭代的次数M（即，当基础学习者是决策树时，模型中的树的数量）。M的增加会减少训练集上的误差，但将其设置得过高可能会导致过度拟合。 通常通过监视单独的验证数据集上的预测误差来选择M的最佳值。 除了控制M外，还使用其他几种正则化技术。

另一个正则化参数是树的深度。 该值越高，模型越可能适合训练数据。

收缩率

梯度增强方法的一个重要部分是通过收缩进行正则化，它包括如下修改更新规则：

${\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,}$ 

哪里参数 ${\displaystyle \nu }$ 被称为“学习率”。

根据经验发现，使用较小的学习率 （例如${\displaystyle \nu <0.1}$  ）在不缩小（而不缩小）的情况下，极大地提高了模型的泛化能力${\displaystyle \nu =1}$  ）^[7]。然而，这是以在训练和查询期间增加计算时间为代价的：较低的学习率需要更多的迭代。

随机梯度增强

引入梯度增强后不久，Friedman在Breiman的bootstrap聚合 （“装袋”）方法的启发下 ，对该算法进行了较小的修改^[3]。具体来说，他提出在算法的每次迭代中，基础学习者都应适合随机抽取的训练集的子样本，而无需替换。^[b]弗里德曼（Friedman）观察到，通过这种修改，梯度增强的精度有了显着提高。

子样本大小是某个常数${\displaystyle f}$ 训练集的大小。 什么时候${\displaystyle f=1}$  ，该算法是确定性的，并且与上述算法相同。 较小的值${\displaystyle f}$ 将随机性引入算法中，并防止过度拟合 ，作为一种正则化 。 该算法也变得更快，因为回归树必须在每次迭代时都适合较小的数据集。弗里德曼^[3]获得了${\displaystyle 0.5\leq f\leq 0.8}$ 在中小型训练集上可获得良好的结果。 因此， ${\displaystyle f}$ 通常将其设置为0.5，这意味着训练集的一半用于构建每个基础学习者。

同样，像在装袋中一样，子采样允许通过评估那些在下一个基础学习者的构建中未使用的观察值的预测来定义预测性能改进的袋外误差 。 预算外的估计有助于避免需要独立的验证数据集，但通常会低估实际性能的提高和最佳迭代次数。 ^[8][9]

叶子中的观察数

梯度树增强实现通常还通过限制树的终端节点中的最小观察次数来使用正则化（此参数在R gbm软件包中命名为n.minobsinnode^[8]）。通过忽略导致导致节点包含少于此训练集实例数量的节点的任何拆分，在树构建过程中使用它。

施加此限制有助于减少叶子预测的差异。

惩罚树木的复杂性

用于梯度增强树的另一种有用的正则化技术是惩罚学习模型的模型复杂性。 ^[10] 模型复杂度可以定义为学习树中叶子的比例。 损失和模型复杂性的联合优化对应于后修剪算法，该算法可删除未能将损失降低阈值的分支。 其他种类的正规化，例如${\displaystyle \ell _{2}}$ 还可以添加对叶子值的惩罚以避免过度拟合 。

用法

梯度提升可以用于学习排名 。 商业网络搜索引擎Yahoo ^[11]和Yandex ^[12]在其机器学习的排名引擎中使用了梯度增强的变体。

名字

该方法有多种名称。弗里德曼（Friedman）将他的回归技术称为“梯度提升机”（GBM）。 ^[2] 梅森，巴克斯特等。将广义的算法抽象类描述为“功能梯度提升”^[4][5]。弗里德曼（Friedman）等人。将梯度提升模型的进展描述为多重可加回归树（MART）^[13]；Elith等。将这种方法描述为“增强回归树”（BRT）^[14]。

R的一种流行的开源实现将其称为“通用提升模型”^[8]。但是，使用BRT扩展这项工作的软件包。 ^[15] Salford Systems的商业实现使用名称“ Multiple Additive Regression Trees”（MART）和TreeNet，两者均为商标。   ^{[ 需要引用 ]}

参见

• AdaBoost
• 随机森林
• XGBoost
• CatBoost
• 决策树学习

註解

1. Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient ${\displaystyle b_{jm}}$  for the region ${\displaystyle R_{jm}}$  is equal to just the value of output variable, averaged over all training instances in ${\displaystyle R_{jm}}$ .
2. Note that this is different from bagging, which samples with replacement because it uses samples of the same size as the training set.

参考文献

1. Breiman, L. Arcing The Edge (PDF). Statistics Department, University of California, Berkeley. June 1997 [2019-11-12]. （原始内容 (PDF)于2020-05-09）. 
2. Friedman, J. H. Greedy Function Approximation: A Gradient Boosting Machine (PDF). February 1999 [2019-11-12]. （原始内容 (PDF)于2019-11-01）. 
3. Friedman, J. H. Stochastic Gradient Boosting (PDF). March 1999 [2019-11-12]. （原始内容 (PDF)于2014-08-01）. 
4. Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus. Boosting Algorithms as Gradient Descent (PDF). S.A. Solla and T.K. Leen and K. Müller (编). Advances in Neural Information Processing Systems 12. MIT Press: 512–518. 1999 [2022-09-10]. （原始内容 (PDF)于2019-12-22）. 
5. Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus. (PDF). May 1999 [2019-11-12]. （原始内容 (PDF)存档于2018-12-22）. 
6. Cheng Li. A Gentle Introduction to Gradient Boosting (PDF). [2019-11-12]. （原始内容 (PDF)于2018-10-24）. 
7. Hastie, T.; Tibshirani, R.; Friedman, J. H. 10. Boosting and Additive Trees. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd. New York: Springer. 2009: 337–384. ISBN 978-0-387-84857-0. （原始内容于2009-11-10）. 
8. Ridgeway, Greg. Generalized Boosted Models: A guide to the gbm package (PDF). 2007. （原始内容 (PDF)于2020-02-10）. 
9. Learn Gradient Boosting Algorithm for better predictions (with codes in R). [2019-11-12]. （原始内容于2019-08-13）. 
10. Tianqi Chen. Introduction to Boosted Trees （页面存档备份，存于互联网档案馆）
11. Cossock, David and Zhang, Tong (2008). Statistical Analysis of Bayes Optimal Subset Ranking 互联网档案馆的，存档日期2010-08-07., page 14.
12. Yandex corporate blog entry about new ranking model "Snezhinsk" （页面存档备份，存于互联网档案馆） (in Russian)
13. Friedman, Jerome. Multiple Additive Regression Trees with Application in Epidemiology. Statistics in Medicine. 2003, 22 (9): 1365–1381. PMID 12704603. doi:10.1002/sim.1501. 
14. Elith, Jane. A working guide to boosted regression trees. Journal of Animal Ecology. 2008, 77 (4): 802–813. PMID 18397250. doi:10.1111/j.1365-2656.2008.01390.x. 
15. Elith, Jane. Boosted Regression Trees for ecological modeling (PDF). CRAN. CRAN. [31 August 2018]. （原始内容 (PDF)于2020-07-25）. 

外部链接

• 如何解释梯度提升 （页面存档备份，存于互联网档案馆）
• 梯度增强回归树 （页面存档备份，存于互联网档案馆）