梯度提升

梯度提升

由提升树到梯度提升

在提升树模型中, 关键在于极小化损失函数:

$\left(\beta_{m}, \gamma_{m}\right)=\operatorname{argmin}_{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)$

得到参数$\beta_{m}$和$\gamma_{m}$, 从而得到第$m$步的基函数$b(x;\gamma_{m})$及加权参数$\beta_{m}$. 当损失函数$L(y, f(x))$是平方损失函数(回归任务)或指数损失函数(分类任务)时, 通过展开损失函数, 很容易得到优化的目标.

但对于一般的损失函数, 想要得到每一步的优化目标是很难得, 这样就限制了提升方法的使用范围和能力.

Friedman提出了梯度提升(Gradient boosting)方法来解决这个问题. 借鉴于梯度下降法, 根据当前模型损失函数的负梯度, 训练得到新的基函数, 然后将训练好的基函数以累加的形式结合到现有模型中.

梯度提升与梯度下降

在传统的梯度下降方法中, 最终求得的最优解$\theta^{*}$, 是从初始值$\theta_{0}$开始, 经过$T$次迭代之后得到的. 假设$\theta_{0} = -\frac{\delta L(\theta)}{\delta \theta_{0}}$, 那么有:

$\theta^{*}=\sum_{t=0}^{T} \alpha_{t} *\left[-\frac{\delta L(\theta)}{\delta \theta}\right]_{\theta=\theta_{t-1}}$

从初始值逐步迭代, 最终在参数空间中找到使损失函数最小的点.

在梯度提升算法中, 借鉴梯度下降的思路, 但此时我们不是搜索最优参数了, 而是直接在函数空间中搜索. 假设提升模型对应的函数为$F(x)$, 损失函数为$L(y,F(x))$, 为了最小化损失函数得到最优的函数$F^{*}(x)$, 也是从初始基函数$F_{0}(x)=f_{0}(x)$开始, 依次得到每个基函数$f_{t}(x)$:

$f_{t}(x)=-\alpha_{t} g_{t}(x)=-\alpha_{t} *\left[\frac{\delta L(y, F(x))}{\delta F(x)}\right]_{F(x)=F_{t-1}(x)}$

最终的提升模型为:

$F^{*}(x)=\sum_{t=0}^{T} f_{t}(x)$

为什么借鉴梯度下降

参考梯度下降法, 负梯度是损失函数在局部下降的最快方向. 使用负梯度拟合一个新的基函数, 这个基函数承担了函数空间中参数变化量$\Delta\theta$的角色, 使得提升模型$F(x)$在向最优函数$F^{*}(x)$以最快的方向迈进一步.

对比参数空间和函数空间:

• 以前梯度下降算法是在多维参数空间中的负梯度方向, 变量是参数

• 这里的变量是函数, 通过当前函数的负梯度方向来修正模型, 使模型更优, 最后累加的模型为近似最优(提升模型)函数

总结的说:

Gradient Boosting算法在每一轮迭代中, 首先计算出当前模型在所有样本上的负梯度, 然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重, 最终实现对模型的更新.

回顾提升树

对于回归提升树, 我们知道它的每个基函数拟合的是残差$r=y-f_{m-1}(x)$.

从梯度提升的角度看, 回归提升树使用的损失函数是平方误差函数$L(y,f(x))=\frac{1}{2} (y-f(x))^2$, 求它的负梯度$\left[\frac{\delta L(y, F(x))}{\delta F(x)}\right]_{F(x)=F_{t-1}(x)}=y-F_{t-1}(x)$, 正是上面的残差.

因此回归提升树只是损失函数为平方误差函数的特殊的梯度提升树.

参考资料

• 梯度提升（Gradient Boosting）算法