查看“︁梯度提升技术”︁的源代码

{{noteTA|G1=IT|G2=Math}}

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

梯度提升技術源自於{{link-en|Leo Breiman}}於1997年時將[[AdaBoost|提升方法]]用於优化算法的观察<ref name="Breiman1997">{{Cite journal|title=Arcing The Edge|url=https://statistics.berkeley.edu/sites/default/files/tech-reports/486.pdf|last=Breiman|first=L.|date=June 1997|publisher=Statistics Department, University of California, Berkeley|journal=|access-date=2019-11-12|archive-date=2020-05-09|archive-url=https://web.archive.org/web/20200509042129/https://statistics.berkeley.edu/sites/default/files/tech-reports/486.pdf|dead-url=no}}</ref>。随后{{link-en|Jerome H. Friedman}}於1999年時提出了显式回归梯度增强算法<ref name="Friedman1999a">{{Cite journal|title=Greedy Function Approximation: A Gradient Boosting Machine|url=https://statweb.stanford.edu/~jhf/ftp/trebst.pdf|last=Friedman|first=J. H.|date=February 1999|journal=|access-date=2019-11-12|archive-date=2019-11-01|archive-url=https://web.archive.org/web/20191101082737/http://statweb.stanford.edu/~jhf/ftp/trebst.pdf|dead-url=no}}</ref><ref name="Friedman1999b">{{Cite journal|title=Stochastic Gradient Boosting|url=https://statweb.stanford.edu/~jhf/ftp/stobst.pdf|last=Friedman|first=J. H.|date=March 1999|journal=|access-date=2019-11-12|archive-date=2014-08-01|archive-url=https://web.archive.org/web/20140801033113/http://statweb.stanford.edu/~jhf/ftp/stobst.pdf|dead-url=no}}</ref>。Llew Mason、Jonathan Baxter、Peter Bartlett和Marcus Frean則針對梯度提升在一般的函数空间的運用進行研究，並於1999年在研討會發表之後<ref name="MasonBaxterBartlettFrean1999a">{{Cite conference |url=http://papers.nips.cc/paper/1766-boosting-algorithms-as-gradient-descent.pdf |title=Boosting Algorithms as Gradient Descent |last1=Mason |first1=L. |last2=Baxter |first2=J. |last3=Bartlett |first3=P. L. |last4=Frean |first4=Marcus |book-title=Advances in Neural Information Processing Systems 12 |editor=S.A. Solla and T.K. Leen and K. Müller |publisher=MIT Press |page=512–518 |year=1999 |access-date=2022-09-10 |archive-date=2019-12-22 |archive-url=https://web.archive.org/web/20191222000742/http://papers.nips.cc/paper/1766-boosting-algorithms-as-gradient-descent.pdf |dead-url=no }}</ref>，同年正式發表了论文<ref name="MasonBaxterBartlettFrean1999b">{{Cite journal|title=Boosting Algorithms as Gradient Descent in Function Space|url=https://www.maths.dur.ac.uk/~dma6kp/pdf/face_recognition/Boosting/Mason99AnyboostLong.pdf|last=Mason|first=L.|last2=Baxter|first2=J.|date=May 1999|last3=Bartlett|first3=P. L.|last4=Frean|first4=Marcus|journal=|author=|access-date=2019-11-12|archive-url=https://web.archive.org/web/20181222170928/http://maths.dur.ac.uk/~dma6kp/pdf/face_recognition/Boosting/Mason99AnyboostLong.pdf|archive-date=2018-12-22|dead-url=yes}}</ref>。該论文介绍了将提升算法看作“函数空间上的梯度下降迭代”算法的观点。也就是将其视为通过迭代地选择指向负梯度方向的函数（弱预测模型），来优化函数空间上的成本函数的算法。这种将提升视为函数梯度的观点，导致了提升算法被運用於回归和分类之外的其他机器学习和统计领域的後續发展。

== 非正式介绍 ==
（本节遵循Li对梯度增强的说明<ref>{{Cite web|title=A Gentle Introduction to Gradient Boosting|url=http://www.chengli.io/tutorials/gradient_boosting.pdf|author=Cheng Li|accessdate=2019-11-12|archive-date=2018-10-24|archive-url=https://web.archive.org/web/20181024221908/http://www.chengli.io/tutorials/gradient_boosting.pdf|dead-url=no}}</ref>。）

与其他增强方法一样，梯度增强以迭代方式将弱的“学习器”组合为一个强学习器。最简单的解释是在最小二乘[[迴歸分析|回归]]中，通过最小化[[均方误差]] <math>\tfrac{1}{n}\sum_i(\hat{y}_i - y_i)^2</math> ，“教”模型<math>F</math>预测实数值<math>\hat{y} = F(x)</math>。

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

: <math>
F_{m+1}(x) = F_m(x) + h(x) = y
</math>

或者，等效地有，

: <math>
h(x) = y - F_m(x)
</math>.

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

== 算法 ==
在许多有[[監督式學習|监督学习]]问题中，一个输出变量{{Mvar|y}}和一个输入变量{{Mvar|x}}通过[[联合分布|联合概率分布]]<math>P(x,y)</math>描述 。给定训练集<math>\{ (x_1,y_1), \dots, (x_n,y_n) \} </math>，目的是在所有具有给定形式的函数<math>F(x)</math>中找到一个<math>\hat{F}(x)</math>使某些指定[[损失函数|损失函数<math>L(y, F(x))</math>]]的期望值达到最小：

: <math>\hat{F} = \underset{F}{\arg\min} \, \mathbb{E}_{x,y}[L(y, F(x))]</math>.

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

: <math>\hat{F}(x) = \sum_{i=1}^M \gamma_i h_i(x) + \mbox{const}</math>.

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

: <math>F_0(x) = \underset{\gamma}{\arg\min} {\sum_{i=1}^n {L(y_i, \gamma)}}</math>,
: <math>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]</math>,

上式<math> h_m \in \mathcal{H} </math>是基学习器。

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

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

: <math>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))},</math>
: <math>\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)}},</math>
式子中，对于<math> i \in \{ 1,..,m \}</math>是关于函数<math> F_i </math>求导，<math>\gamma_m</math>是步长。 但是在离散情况下，即<math>\mathcal{H}</math>如果是有限的，我们选择最接近{{Mvar|L}}梯度的候选函数{{Mvar|h}} ，然后可以根据上述等式通过[[线搜索]]来计算系数{{Mvar|&gamma;}}。请注意，这种方法是一种启发式方法，因此不能给出给定问题的精确解决方案，而是一种近似方法。 在伪代码中，通用梯度增强方法是<ref name="Friedman1999a" /><ref name="hastie">{{Cite book|url=https://hastie.su.domains/ElemStatLearn/|title=The Elements of Statistical Learning: Data Mining, Inference, and Prediction.|last=Hastie|first=T.|last2=Tibshirani|first2=R.|last3=Friedman|first3=J. H.|chapter=10. Boosting and Additive Trees|edition=2nd|publisher=Springer|location=New York|pages=337-384|year=2009|isbn=978-0-387-84857-0|archiveurl=https://web.archive.org/web/20091110212529/http://www-stat.stanford.edu/~tibs/ElemStatLearn/|archivedate=2009-11-10|dead-url=no}}</ref>： {{彩色框 头部|blue}}
Input: training set <math>\{(x_i, y_i)\}_{i=1}^n,</math> a differentiable loss function <math>L(y, F(x)),</math> number of iterations {{Mvar|M}}.

Algorithm:

# Initialize model with a constant value:
#: <math>F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma).</math>
# For {{Mvar|m}} = 1 to {{Mvar|M}}:
## Compute so-called ''pseudo-residuals'':
##: <math>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.</math>
## Fit a base learner (or weak learner, e.g. tree) <math>h_m(x)</math> to pseudo-residuals, i.e. train it using the training set <math>\{(x_i, r_{im})\}_{i=1}^n</math>.
## Compute multiplier <math>\gamma_m</math> by solving the following [[线搜索|one-dimensional optimization]] problem:
##: <math>\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).</math>
## Update the model:
##: <math>F_m(x) = F_{m-1}(x) + \gamma_m h_m(x).</math>
# Output <math>F_M(x).</math>
{{彩色框 底部}}

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

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

: <math>h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} \mathbf {1}_{R_{jm}}(x),</math>

这里<math>b_{jm}</math>是该区域中预测的值<math>R_{jm}</math>{{Efn|Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient <math>b_{jm}</math> for the region <math>R_{jm}</math> is equal to just the value of output variable, averaged over all training instances in <math>R_{jm}</math>.}}。

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

: <math>
  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)).
 </math>

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

: <math>
  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).
 </math>

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

Hastie等人评论通常<math>4 \leq J \leq 8</math>对于提升效果很好，结果对选择<math>J</math>在这个范围内<math>J = 2</math>不足以用于许多应用程序，并且<math>J > 10</math>不太可能是必需的<ref name="hastie" />。

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

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

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

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

: <math>F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 < \nu \leq 1,</math>

哪里参数 <math>\nu</math>被称为“学习率”。 

根据经验发现，使用较小的学习率 （例如<math>\nu < 0.1</math> ）在不缩小（而不缩小）的情况下，极大地提高了模型的泛化能力<math>\nu = 1</math> ）<ref name="hastie" />。然而，这是以在训练和[[信息檢索|查询]]期间增加[[时间复杂度|计算时间]]为代价的：较低的学习率需要更多的迭代。 

=== 随机梯度增强 ===
引入梯度增强后不久，Friedman在Breiman的[[Bagging算法|bootstrap聚合]] （“装袋”）方法的启发下 ，对该算法进行了较小的修改<ref name="Friedman1999b" />。具体来说，他提出在算法的每次迭代中，基础学习者都应适合随机抽取的训练集的子样本，而无需替换。{{Efn|Note that this is different from bagging, which samples with replacement because it uses samples of the same size as the training set.}}弗里德曼（Friedman）观察到，通过这种修改，梯度增强的精度有了显着提高。 

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

同样，像在装袋中一样，子采样允许通过评估那些在下一个基础学习者的构建中未使用的观察值的预测来定义预测性能改进的袋外误差 。 预算外的估计有助于避免需要独立的验证数据集，但通常会低估实际性能的提高和最佳迭代次数。 <ref name="gbm-vignette">{{Cite web |url=https://cran.r-project.org/web/packages/gbm/gbm.pdf |title=Generalized Boosted Models: A guide to the gbm package |author=Ridgeway, Greg |year=2007 |archive-url=https://web.archive.org/web/20200210081401/https://cran.r-project.org/web/packages/gbm/gbm.pdf |archive-date=2020-02-10 |dead-url=no}}</ref><ref>{{Cite web |url=https://www.analyticsvidhya.com/blog/2015/09/complete-guide-boosting-methods/ |title=Learn Gradient Boosting Algorithm for better predictions (with codes in R) |accessdate=2019-11-12 |archive-date=2019-08-13 |archive-url=https://web.archive.org/web/20190813212727/https://www.analyticsvidhya.com/blog/2015/09/complete-guide-boosting-methods/ |dead-url=no }}</ref> 

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

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

=== 惩罚树木的复杂性 ===
用于梯度增强[[决策树|树的]]另一种有用的正则化技术是惩罚学习模型的模型复杂性。 <ref>Tianqi Chen. [http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf Introduction to Boosted Trees] {{Wayback|url=http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf |date=20191105181311 }}</ref> 模型复杂度可以定义为学习树中叶子的比例。 损失和模型复杂性的联合优化对应于后修剪算法，该算法可删除未能将损失降低阈值的分支。 其他种类的正规化，例如<math>\ell_2</math>还可以添加对叶子值的惩罚以避免[[過適|过度拟合]] 。 

== 用法 ==
梯度提升可以用于学习排名 。 商业网络搜索引擎[[雅虎|Yahoo]] <ref>Cossock, David and Zhang, Tong (2008). [http://www.stat.rutgers.edu/~tzhang/papers/it08-ranking.pdf Statistical Analysis of Bayes Optimal Subset Ranking] {{Webarchive|url=https://web.archive.org/web/20100807162855/http://www.stat.rutgers.edu/~tzhang/papers/it08-ranking.pdf|date=2010-08-07}}, page 14.</ref>和[[Yandex]] <ref name="snezhinsk">[http://webmaster.ya.ru/replies.xml?item_no=5707&ncrnd=5118 Yandex corporate blog entry about new ranking model "Snezhinsk"] {{Wayback|url=http://webmaster.ya.ru/replies.xml?item_no=5707&ncrnd=5118 |date=20120301165959 }} (in Russian)</ref>在其机器学习的排名引擎中使用了梯度增强的变体。 

== 名字 ==
该方法有多种名称。弗里德曼（Friedman）将他的回归技术称为“梯度提升机”（GBM）。 <ref name="Friedman1999a" /> 梅森，巴克斯特等。将广义的算法抽象类描述为“功能梯度提升”<ref name="MasonBaxterBartlettFrean1999a" /><ref name="MasonBaxterBartlettFrean1999b" />。弗里德曼（Friedman）等人。将梯度提升模型的进展描述为多重可加回归树（MART）<ref>{{Cite journal|title=Multiple Additive Regression Trees with Application in Epidemiology|last=Friedman|first=Jerome|journal=Statistics in Medicine|issue=9|doi=10.1002/sim.1501|year=2003|volume=22|pages=1365–1381|pmid=12704603}}</ref>；Elith等。将这种方法描述为“增强回归树”（BRT）<ref>{{Cite journal|title=A working guide to boosted regression trees|url=https://archive.org/details/sim_journal-of-animal-ecology_2008-07_77_4/page/802|last=Elith|first=Jane|journal=Journal of Animal Ecology|issue=4|doi=10.1111/j.1365-2656.2008.01390.x|year=2008|volume=77|pages=802–813|pmid=18397250|ref=Elith2008}}</ref>。

[[R语言|R的]]一种流行的开源实现将其称为“通用提升模型”<ref name="gbm-vignette" />。但是，使用BRT扩展这项工作的软件包。 <ref>{{Cite web|title=Boosted Regression Trees for ecological modeling|url=https://cran.r-project.org/web/packages/dismo/vignettes/brt.pdf|accessdate=31 August 2018|author=Elith|first=Jane|work=CRAN|publisher=CRAN|archive-date=2020-07-25|archive-url=https://web.archive.org/web/20200725061155/https://cran.r-project.org/web/packages/dismo/vignettes/brt.pdf|dead-url=no}}</ref> Salford Systems的商业实现使用名称“ Multiple Additive Regression Trees”（MART）和TreeNet，两者均为商标。     
<sup class="noprint Inline-Template Template-Fact" data-ve-ignore="true">&#x5B; ''[[Wikipedia:来源请求|<span title="This claim needs references to reliable sources. (August 2018)">需要引用</span>]]'' &#x5D;</sup>

== 参见 ==
* [[AdaBoost]]
* [[随机森林]]
* [[XGBoost]]
* [[CatBoost]]
* [[决策树学习]]

== 註解 ==
{{Notelist}}

== 参考文献 ==
{{Reflist}}

== 外部链接 ==

* [http://explained.ai/gradient-boosting/index.html 如何解释梯度提升] {{Wayback|url=http://explained.ai/gradient-boosting/index.html |date=20200426194916 }} 
* [https://blog.datarobot.com/gradient-boosted-regression-trees 梯度增强回归树] {{Wayback|url=https://blog.datarobot.com/gradient-boosted-regression-trees |date=20190530091114 }} 
[[Category:决策树]]
[[Category:分類演算法]]