人们很少会把Gradient Boosting翻译成中文名词,为了保持版面的整齐,还是使用了中文术语。目前,梯度提升是广泛使用的统计学习方法,其思想来源于数值优化中的最速下降法。梯度提升和最速下降法的主要区别就是:最速下降法中的梯度是基于参数空间的,然而梯度提升中的梯度基于假设空间。

函数估计

在机器学习任务中,在训练数据集上,我们通过最小化损失函数来选择假设空间中的假设

对于回归问题,常用的损失函数包括平方损失和绝对值损失;对于分类问题,常用的损失函数为负对数似然损失

通常我们将假设限制在某一类函数中,其中。在本文中,通过相加将多个单个假设集成

数值优化

通常,在假设空间固定之后,我们的训练过程也就是选择最佳的参数

其中,

那么损失最小的假设就是

如果我们采用数值优化的方法来训练模型,那么在每一步优化的过程中都会增加或减小参数的数值,那么就可以将最终的得到的参数视为初始参数和每一步参数增量的

最速下降

最速下降是非常简单的一种数值优化方法,每一步的参数增量定义如下。首先,当前的梯度的计算方法为

那么当前的参数增量就是

其中,

函数空间的数值优化

借鉴最速下降中的思想,我们可以尝试在函数空间(假设空间)中应用最速下降法,优化目标是最小化

类似参数空间中的数值优化,最终训练得到的假设为

对于每一步优化

其中

乘子的选择方法为

算法框架

通常来说,训练数据的数量是有限的,所以需要使用数据集的平均损失来近似损失的期望,又根据,梯度提升集成的优化目标就是

在梯度提升过程中,每一步使用贪心策略,因此对于

同时

按照,我们可以得到训练数据的梯度函数值,然而我们并不能直接得到梯度函数,所以需要考虑使用另外一个假设去拟合,损失函数为平方损失

得到拟合梯度的假设之后,应用到

然后更新集成假设

那么梯度提升的整体框架就是

  1. 对于

应用:增量模型

梯度提升算法框架可以采用一些常见的损失函数,形成具体的算法。

平方损失回归

平方损失函数,那么梯度就是

那么具体的算法就是

  1. 对于

绝对值损失回归

对于绝对值损失函数

那么算法框架中乘子搜索就变成了

其中,为带权中位数。

回归树

对于J个叶节点的回归树模型可以表示为

其中为指示函数,为叶节点在特征空间中对应的划分出的子空间,是对应的输出值。对于回归树来说,其集成假设的更新方式就是

引入,可以将写成

此时,最优参数的解就是

基于子空间不相交的特点,上式又可以写成

类似

因此,绝对值损失提升树算法为

  1. 对于

二元逻辑斯谛回归树

对于逻辑斯谛回归(分类)问题

其中等价于

对应的损失函数就是

在印象里,损失函数应该是

然而这里的损失函数却那么优美,如果将代回,就可以得到等价的公式。

那么损失函数关于的导数就是

这时乘子的搜索过程就是

对于回归树来说,我们可以在每个特征子空间内执行上述操作

上式不存在闭式解,使用牛顿法求解

最终的算法就是

  1. 对于

多元逻辑斯谛回归树

在多元分类的情况中,通常使用softmax函数来计算属于某一类的概率

对数似然损失就是

其中,将代入后关于求导

那么搜索乘子过程就变成了

同样需要采用牛顿法

具体算法为

  1. 对于
    1. 对于

编程实现

梯度提升决策树回归:GradientBoostingRegressor.jl

梯度提升决策树分类:GradientBoostingClassifier.jl

参考资料

  1. Greedy Function Approximation: A Gradient Boosting Machine
  2. A Gentle Introduction to Gradient Boosting