梯度提升算法 介绍

翻译维基百科介绍

梯度提升算法

梯度提升算法是一种解决回归和分类问题的机器学习技术，它通过对弱预测模型(比如决策树)的集成产生预测模型。它像其他提升方法一样以分步的方式构建模型，并且通过允许使用任意可微分的损失函数来推广它们。

非正式介绍

和其他boost方法一样，梯度提升方法也是通过迭代的方法联合弱”学习者”联合形成一个强学习者。很容易在最小二乘回归中解释算法的原理，最小二乘法回归的目的就是“教”模型F通过将平方误差$(\hat y-y)^2$最小化(平均训练集)来预测形如$\hat y=F(x)$的值。

在梯度提升的$1 \le m \le M$步中,假设已经有一些不完美的模型$F_m$(最初可以使用非常弱的模型，它只是预测输出训练集的平均值)。梯度提升算法不改变$F_m$，而是通过增加估计器$h$构建新的模型$F_{m+1}(x)=F_m(x)+h(x)$来提高整体模型的效果。那么问题来了，如何寻找$h$函数呢？梯度提升方法的解决办法是认为最好的$h$应该使得:

$$F_{m+1}(x)=F_m(x)+h(x) = y$$ 或者等价于: $$h(x) = y - F_{m}(x)$$ 因此，梯度提升算法将 $h$与残差$y-F_m(x)$拟合。与其他boosting算法的变体一样， $F_{m+1}$修正它的前身 $F_m$。我们观察到残差 $y-F_m(x)$是损失函数 ${1 \over 2}(y-F(x))^2$的负梯度方向，因此可以将其推广到其他不是平方误差(分类或是排序问题)的损失函数。也就是说，梯度提升算法是一种梯度下降算法，只需要更改损失函数和梯度就能将其推广。

算法

在许多监督学习问题中，都有一个输出变量$y$和一个输入向量$x$,通过联合概率$P(x,y)$可以将两者联系起来。使用一个训练集${( x 1 , y 1 ) , … , ( x n , y n ) }$已知$x$及对应的$y$。学习的目的就是通过最小化一些损失函数$L(y,F(x))$的期望值，找到$F^*(x)$的近似$\hat F(x)$。

$${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$$
梯度提升算法假设一个真值 $y$然后通过加权和形式的$h_i(x) \in \cal H$得到近似函数 $\hat F( x )$, $h_i(x)$被称为基学习器: $$\hat F(x)= \sum_{i=1}^n\gamma_ih_i(x)+const$$ 根据经验风险最小化原理， $\hat F(x)$可以通过对训练集样本平均损失求极小值得到。开始时，模型由一个常函数 $F_0(x)$组成，然后利用贪心策略增量扩展模型: $$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\in {\mathcal {H}}}{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+h(x_{i}))}$$
其中 $h_i(x) \in \cal H$是基学习器。
不幸的是，在任意损失函数L的每个步中选择最佳函数h，一般来说这是一个计算上不可行的优化问题。因此我们可以通过一些限制简化问题。简化的办法就是使用梯度下降法解决最小化问题。假设我们考虑连续的情况，比如 $\cal H$是一个定义在 ${\displaystyle \mathbb {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})),}$$ $${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})-\gamma {\frac {\partial L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})}}\right)}$$
其中导数是关于 $F_i i\in[1,2 .., m]$求导所得。然后在离散的情况下，比如函数集合 $\cal H$是有限的，我们将选择最接近损失函数 $L$梯度的候选函数$h$,其中 $\gamma$可以借助上式的线性搜索进行计算。注意，这是一个启发式的方法，因此不能得到精确解，但是得到的近似解已经足够精确了。
通用梯度提升方法的伪代码如下:

输入：训练集${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n}}$,可微损失函数$L(y,F(x))$，迭代次数M
算法如下:
1. 使用常量初始化模型：

$$F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma).$$
2. For m = 1 to M:
1.使用损失函数的负梯度在当前模型 $F_{m-1}(x)$上的值近似代替残差： $$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. 使用基学习器 $h_m(x)$拟合近似的残差值，即用训练集 ${\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}}$进行拟合
3. 解一维优化问题计算乘子 $\gamma_m$: $$\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.更新模型： $$F_{m}(x)=F_{{m-1}}(x)+\gamma _{m}h_{m}(x).$$
3.输出$F_M(x)$

梯度提升树

梯度提升算法通常用具有固定大小的决策树（特别是CART树）作为基学习器。对于这种特殊情况，Friedman提出了一种改进梯度提升的方法，提高了每个基学习期的质量。一般梯度提升算法在第m步使用$h_m(x)$拟合近似残差。另$J_m$为叶节点的数目。则模型树将空间分为$J_m$个不相交的区域${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$,每个区域的预测值为常量。利用指示函数$I$,对于输入$x$，输出$h_m(x)$可以有以下和的形式:

$$h_m(x)=\sum_{j=1}^{J_m}b_{jm}I(x \in R_{jm})$$ 其中， $b_{jm}$是区域 $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_{mj}$，而不是单个 $\gamma_m$。 他称修改后的算法为“TreeBoost”。 修改后可以简单地舍弃来自树拟合过程的系数 $b+{jm}$,并且模型更新规则变为： $${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}I(x\in R_{jm})\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等人评论认为， ${\displaystyle 4\leq J\leq 8}$时效果很好，预测结果对在这一范围内选择的J相当不敏感，J=2对于一般应用来说是不够的，但是也很少需要取$J \ge 10$.
（译注:由于译者水平有限，没有完全这段话含义，尤其是相互作用这几句话，希望得到大神指
点，现贴出原文）。
$J$, the number of terminal nodes in trees, is the method’s parameter which can be adjusted for a data set at hand. It controls the maximum allowed level of interaction between variables in the model. With$J=2$ (decision stumps), no interaction between variables is allowed. With$J=2$the model may include effects of the interaction between up to two variables, and so on.

Hastie et al.[7] comment that typically ${\displaystyle 4\leq J\leq 8}$ work well for boosting and results are fairly insensitive to the choice of J in this range, J = 2insufficient for many applications, and J > 10 is unlikely to be required.

正则化

拟合训练集太过于接近可能会降低模型的泛化能力。几种所谓的正则化技术通过约束拟合过程来减少这种过拟合效应。一个很自然的正则化参数是梯度提升的迭代次数M（即当基学习器是决策树时，模型中树的数目）。 增加M可减少训练误差，但将其设置得太高可能导致过拟合。 通常通过在单独的验证集上监测误差来选择M的最优值。 除了控制M之外，还可以使用其他一些正则化技术：

收缩

梯度提升算法的一个重要部分是收缩正则化，其中包括修改更新规则如下：

$$F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 < \nu \leq 1$$
其中参数 $\nu$称为学习率。经验表明，与使用较大的学习率（如 $\nu = 1$）相比，使用较小的学习率（比如 $\nu < 0.1$）能够显著的提高模型泛化能力。但是这也会使训练时间，迭代次数增加。

随机梯度提升

引入梯度提升方法不久之后，Friedman提出对该算法的微小修改，想法源于Breiman提出的bagging方法。具体来说，他提出在算法的每一次迭代中，基础学习器应该随机抽取训练集的子样本作为训练集拟合。Friedman观察到这种修改对梯度提升的精度有实质性改善。
子样本大小由常分数$f$决定，代表子样本大小与总样本大小的比值。当f = 1时，算法是确定性的，与前述相同。 较小的$f$则将随机性引入到算法中，作为正则化的一种形式有助于防止过度拟合。同时也能提高该算法的效率，因为在每次迭代时，回归树将拟合较小的数据集。 Friedman的观点认为，对于中小型训练集，${\displaystyle 0.5 \leq f \leq 0.8}$的效果很好。因此，f通常设置为0.5，这意味着训练集的一半用于构建每个基础学习器。
和bagging算法一样，子样本通过评价那些在构建下一个基学习器中没有使用的样本集，可以定义预测性能改进的包外误差（out-of-bag）。 包外估计可以避免需要独立的验证数据集，但往往低估实际性能的提升和最佳迭代次数。

叶节点中包含样本数

梯度提升树的实现中，还可以通过限制树叶节点中的最小样本数量来进行正则化（该参数在R gbm包中称为n.minobsinnode [10]）。 它忽略将导致叶节点包含少于某一阈值数量的训练集实例节点的分裂(译注：也就是预剪枝)。施加此限制有助于减少叶节点预测的方差。

树复杂度的罚项

梯度提升树的另一个有用的正则化技术是惩罚学习模型的模型复杂性。模型复杂度可以定义为树中叶子的比例数(译注：比例数？应该是指叶子总数与树数目的比值)。 损失函数加上模型复杂度的罚项对应于修剪后的算法，可以去除一些增加模型复杂度，但对损失函数的降低影响不大的分支。 还可以添加其他类型的正则化，例如${\displaystyle \ell_{2}}$ 正则化对叶节点值的惩罚，以避免过度拟合。