梯度提升，亦稱作梯度增强，是一种用于回归和分类问题的机器学习技术。其产生的预测模型是弱预测模型的集成，如采用典型的决策树作为弱预测模型，这时则为梯度提升树（或）。像其他提升方法一样，它以分阶段的方式构建模型，但它通过允许对任意可微分损失函数进行优化作为对一般提升方法的推广。
梯度提升技術源自於於1997年時將提升方法用於优化算法的观察。随后於1999年時提出了显式回归梯度增强算法。Llew Mason、Jonathan Baxter、Peter Bartlett和Marcus Frean則針對梯度提升在一般的函数空间的運用進行研究，並於1999年在研討會發表之後，同年正式發表了论文。該论文介绍了将提升算法看作“函数空间上的梯度下降迭代”算法的观点。也就是将其视为通过迭代地选择指向负梯度方向的函数（弱预测模型），来优化函数空间上的成本函数的算法。这种将提升视为函数梯度的观点，导致了提升算法被運用於回归和分类之外的其他机器学习和统计领域的後續发展。
非正式介绍
（本节遵循Li对梯度增强的说明。）
与其他增强方法一样，梯度增强以迭代方式将弱的“学习器”组合为一个强学习器。最简单的解释是在最小二乘回归中，通过最小化均方误差 \tfrac{1}{n}\sum_i(\hat{y}_i - y_i)^2 ，“教”模型F预测实数值\hat{y} = F(x)。
在梯度提升的每个阶段 m, 1 \le m \le M, 假设已经有一个不太完美的模型 F_m (最开始时只是一个预测输出变量 均值的模型)。 梯度提升算法通过在当前模型 F_m 增加一个新的估计量 得到一个更好的模型: F_{m+1}(x) = F_m(x) + h(x). 为了求得 h, 梯度提升基于以下观察：一个完美的 可以完美预测当前不完美模型F_m的残差，即满足，
:
F_{m+1}(x) = F_m(x) + h(x) = y
或者，等效地有，
:
h(x) = y - F_m(x)
.
因此，梯度提升通过拟合残差 y - F_m(x)得到 。和其他提升方法的变体一样, F_{m+1} 通过纠正 F_m的误差变得更完美。 这个想法可以扩展到均方误差损失之外的任意损失函数，甚至扩展到分类与排序问题，只要观察到以下一点：模型的残差 y - F_m(x)就是均方损失函数\frac{1}{2}(y - F(x))^2关于F(x)的负梯度。因此，梯度提升其实是一种 梯度下降算法，可以代入除了均方损失之外的不同的损失函数，得到不同的梯度。
算法
在许多有监督学习问题中，一个输出变量和一个输入变量通过联合概率分布P(x,y)描述 。给定训练集\{ (x_1,y_1), \dots, (x_n,y_n) \} ，目的是在所有具有给定形式的函数F(x)中找到一个\hat{F}(x)使某些指定损失函数L(y, F(x))的期望值达到最小：
: \hat{F} = \underset{F}{\arg\min} \, \mathbb{E}_{x,y}[L(y, F(x))].
梯度提升方法通过某一类\mathcal{H}中弱学习器（或称基学习器）h_i (x)带权重和的形式来表示对实值变量做出估计的\hat{F}(x):
: \hat{F}(x) = \sum_{i=1}^M \gamma_i h_i(x) + \mbox{const}.
根据经验风险最小化原理，该方法试图找到一个近似\hat{F}(x)可以最大程度地减少训练集上损失函数的平均值，即，最小化经验风险。它是从一个由常数函数组成的模型F_0(x)开始 ，并以贪心的方式逐步扩展：
: F_0(x) = \underset{\gamma}{\arg\min} {\sum_{i=1}^n {L(y_i, \gamma)}},
: 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],
上式 h_m \in \mathcal{H} 是基学习器。
不幸的是，通常在每个步骤中为任意损失函数选择最佳函数是计算上不可行的优化问题。因此，我们将方法局限于问题的简化版本。
这个想法是对这个最小化问题（函数梯度下降）应用梯度下降步骤。如果我们考虑连续情况，即\mathcal{H} 是上的任意微分函数的集合 \R ，我们将根据以下方程式更新模型
: 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))},
: \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)}},
式子中，对于 i \in \{ 1,..,m \}是关于函数 F_i 求导，\gamma_m是步长。 但是在离散情况下，即\mathcal{H}如果是有限的，我们选择最接近梯度的候选函数 ，然后可以根据上述等式通过线搜索来计算系数。请注意，这种方法是一种启发式方法，因此不能给出给定问题的精确解决方案，而是一种近似方法。 在伪代码中，通用梯度增强方法是：
Input: training set \{(x_i, y_i)\}_{i=1}^n, a differentiable loss function L(y, F(x)), number of iterations .
Algorithm:
Initialize model with a constant value:
#: F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma).
For = 1 to :
Compute so-called pseudo-residuals:
##: 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.
Fit a base learner (or weak learner, e.g. tree) h_m(x) to pseudo-residuals, i.e. train it using the training set \{(x_i, r_{im})\}_{i=1}^n.
Compute multiplier \gamma_m by solving the following one-dimensional optimization problem:
##: \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).
Update the model:
##: F_m(x) = F_{m-1}(x) + \gamma_m h_m(x).
Output F_M(x).
梯度树增强
梯度提升通常与固定大小的决策树 （尤其是CART树）一起用作基础学习者。 对于这种特殊情况，Friedman提出了对梯度增强方法的改进，以提高每个基础学习者的适应质量。
第m步的通用梯度提升将适合决策树h_m(x)伪残留物。 让J_{m}是它的叶子数。 树将输入空间划分为J_{m}不相交的区域R_{1m}, \ldots, R_{J_{m}m}并预测每个区域的恒定值。 使用指标符号 ，输出h_m(x)输入x可以写为和：
: h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} \mathbf {1}_{R_{jm}}(x),
这里b_{jm}是该区域中预测的值R_{jm}{{Efn|Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient b_{jm} for the region R_{jm} is equal to just the value of output variable, averaged over all training instances in R_{jm}.}}。
然后系数b_{jm}乘以一些值\gamma_m ，使用线搜索进行选择，以最大程度地减少损失函数，并按以下方式更新模型：
:
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）建议修改此算法，以便选择一个单独的最佳值\gamma_{jm}每个树的区域，而不是单个\gamma_m为整棵树。 他称修改后的算法为“ TreeBoost”。 系数b_{jm}然后可以简单地丢弃树拟合过程中的数据，模型更新规则变为：
:
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).
树木大小
J （树中终端节点的数量）是该方法的参数，可以针对手头的数据集进行调整。 它控制模型中变量之间允许的最大交互级别。 用J = 2 （ 决策树桩 ），不允许变量之间进行交互。 用J = 3该模型可能包括多达两个变量之间的相互作用的影响，依此类推。
Hastie等人评论通常4 \leq J \leq 8对于提升效果很好，结果对选择J在这个范围内J = 2不足以用于许多应用程序，并且J > 10不太可能是必需的
叶子中的观察数
梯度树增强实现通常还通过限制树的终端节点中的最小观察次数来使用正则化（此参数在R gbm软件包中命名为n.minobsinnode 模型复杂度可以定义为学习树中叶子的比例。 损失和模型复杂性的联合优化对应于后修剪算法，该算法可删除未能将损失降低阈值的分支。 其他种类的正规化，例如\ell_2还可以添加对叶子值的惩罚以避免过度拟合 。
用法
梯度提升可以用于学习排名 。 商业网络搜索引擎Yahoo 和Yandex 在其机器学习的排名引擎中使用了梯度增强的变体。
名字
该方法有多种名称。弗里德曼（Friedman）将他的回归技术称为“梯度提升机”（GBM）。 ；Elith等。将这种方法描述为“增强回归树”（BRT）。
R的一种流行的开源实现将其称为“通用提升模型” Salford Systems的商业实现使用名称“ Multiple Additive Regression Trees”（MART）和TreeNet，两者均为商标。
[ 需要引用 ]
参见
- AdaBoost
- 随机森林
- XGBoost
- CatBoost
- 决策树学习
註解
参考文献
外部链接
评论 (0)