从参数空间到函数空间理解GBDT+XGBoost

内容摘要

泰勒公式
最优化方法
- 梯度下降法
- 牛顿法
从参数空间到函数空间
- 从Gradient descend到Gradient boosting
- 从Newton's method到Newton Boosting
Gradient boosting tree算法原理
Newton Boosting算法原理
LightGBM

泰勒公式

定义：是一个用函数在某点的信息，描述其附近取值的公式。
基本形式：

其中一阶泰勒展开式就是求一阶导，二阶展开式即求二阶导。x0为已知，公式表示f(x)在x0附近的展开。
GDBT或是xgb都是一个参数迭代的过程，因此这里表示一个迭代形式的泰勒函数：

假设

将f(x^t) 在x^(t-1)处进行展开：

梯度下降法（Gradient Descend Method）

机器学习中需要最小化损失函数L(θ),这个θ就是要求解的模型参数。GDM常用于求解无约束最优化问题，是一种迭代方法。初始话θ为θ^0，不断迭代来更新θ的值，进行损失函数的极小化。

迭代公式 θ^t = θ^(t-1)+△θ
进行一阶泰勒展开：

要使得L(θ^t) < L(θ^(t-1)),则可取：
其中解释一下为何△θ要取值为上式：首先明确，a的值为正，为了保证△θ恒为负数，则需要乘上L’(θ^t-1)先保证其为整数，再加上负号即可。
其实a就是我们常用的学习速率
a如何选取？
对于这个问题其实有很多方法可以使用，如果考虑使用full gradient较为笨但是精确的方法是line search，但是其复杂度过高，因此通常我们选取一个很小的值即可例如0.01-0.1之间。

牛顿法

牛顿法就是求取二阶泰勒展开：

假设我们要求的参数θ是一维，则记一阶导数为g，二阶导数为h，那么上式可表示为：

此时若求取L(θ^t) 的极小值，则令g△θ+h△θ^2/2极小，求取其一阶导数为0时的△θ即可：

如果参数θ是向量形式，那么可以向高维空间推广，此时的h为H（海森矩阵）。

以上介绍的梯度下降和牛顿法均为参数空间的优化算法
如何从参数空间推广到函数空间呢？即从Gradient descend到Gradient boosting；从Newton's method到Newton Boosting
下面介绍GBDT和xgb中使用的函数空间的优化算法，其基本原理还是梯度下降和牛顿法。
关系是这样的：
GBDT泛指一切梯度提升树，包括XGB。为了区分二者，可以利用其梯度下降的原理进行区分：

GBDT在函数空间中利用梯度下降进行优化
XGB在函数空间利用牛顿法进行优化

1. 梯度下降从参数空间到函数空间

其中对于函数空间，仅仅是将参数的拟合换为函数的拟合，每次仍然迭代的是一个负梯度，只是其最终得到的是增量函数的累加而不是增量参数累加。
GBDT里，迭代项ft(x)就是我们的决策树，最终将每棵决策树的预测值（函数）加起来。

2. 牛顿法从参数空间到函数空间

对于牛顿法的函数空间优化，其方法类似于梯度下降的函数空间优化

3. boosting算法小结
无论是梯度下降还是牛顿法，其函数空间上的boosting优化模型都看作是一类加法模型，相加的对象可以是一系列弱分类器或是回归树。

4. 牛顿法小结
牛顿法是梯度下降的进一步优化，梯度下降利用目标函数的一阶偏导信息，以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质；而牛顿法不仅使用目标函数的一阶偏导数，还进一步利用了目标函数的二阶偏导，这样就考虑了梯度变化的趋势，因而能更全面地确定合适的搜索方向以加快收敛。

GBDT原理分析

GBDT最早由Friedman提出，其核心是拟合前面迭代所留下来的残差，使其达到最小。

模型F定义为一个加法模型：

其中x为输入样本，h为分类回归树，w是分类回归树的参数，a是每棵树的权重。

通过最小化损失函数求解最优模型：
GBDT原是论文的算法伪代码：

算法的输入(xi,yi)分别是样本和lable，T为样本个数，L为损失函数

GBDT的学习过程是使得前面拟合的残差达到最小，那么首先计算残差，即算法中的2.1步，也称为响应。

接着学习第t棵树时就是寻找最新的残差的最小值。可以看到lable yi变成了前t-1棵树的残差值。
然后寻找合适的步长（通常情况，不使用line search，而是手动给一个很小的值）
最后将第t棵树与前t-1棵树加起来，更新模型即可。

XGBoost原理

模型的函数形式

xgb同样是一个加性模型，同样是在学习多棵树的结果并将其累加。f(x)就是每一棵树。其中q(x)表示将样本x分到了某个叶子节点上，w是叶子节点的分数，所以wq(x)就表示回归树对样本的预测值。

回归树的预测输出是一个实数的分数，因此可以用于回归和分类，以及排序等任务。

目标函数

首先回忆一下参数空间的目标函数：

实际上就是一个误差函数+正则化项

其中误差函数可以是平方误差或是对数误差等；正则化项可以是L1或L2

正则化项

wepon大神说道，正则化项的理解可以从贝叶斯先验角度去理解。也就是说，如果引入L2，那么就是假设模型参数服从正态分布（相当于对参数加上了分布约束），这样一来就将参数的取值进行一定的限制，同时可以知道，正态分布取0附近的概率最大，因此又将参数空间可能的范围进一步缩小，模型最终学习出来的参数取值都在0附近。

现在来看函数空间的目标函数

其中正则化项是对每一棵树的复杂度进行惩罚。
相比于GBDT，xgb目标函数就是多了一个正则化项。这样的做法使得模型不易过拟合。
既然是对复杂度做惩罚，那么树的什么特性可以反映复杂度？

树的深度、内部节点个数、叶子节点个数，叶节点分数
xgb中选用了叶子节点个数(T)，叶节点分数(w)来反映树的复杂度，其复杂度定义如下：

看完正则化项后再来关心一下目标函数中的误差函数

首先模型第t次迭代后将ft(x)与前t次的迭代结果进行相加，并代入目标函数，即式2，然后将误差项在yt-1处进行二阶展开，然后去掉常数项得到：

上面这个形式跟牛顿法的形式几乎一样，由于f在函数空间中是一个树的形式，则将f写为树的结构：

代入目标函数中得到：

虽然现在loss函数可以求最小值了，但是公式的两项并不统一，即：

如何将两项进行统一以方便求导呢？因为样本都会落在每一个节点上面，因此可以定义如下：

对每一个样本都相应有一个gi和hi。从最终的公式可以看到，由于是按照叶子节点进行累加，所以相当于每一个叶子节点均有一个误差函数，都要进行相应的误差计算。
根据转换后的损失函数，就可以求极小值了，前提是树结构确定：

相当于每一棵树的最小损失都可以计算了。

既然前提是需要树结构确定，那么如何确定树的结构？即如何确定树节点的分裂方法？

可以暴力枚举全部的树结构然后选择损失最小的结构即可。明显是一个NP问题。不现实！

贪心法：每次尝试分裂一个叶节点，计算前后增益，选择增益最大的保留。

那么增益如何计算？

xgb增益计算方法的演进：

初始版本：

这样的方法相当于去遍历所有可能分割的分割点，然后计算增益，最后选取最大的增益的分列方式去分割，明显负责度太高！！

近似算法：
对于每一个特征，只考虑分位点，以减少复杂度，分位点的选取粒度有两种：全局global和局部local。全局速度快但是经度降低。
解释一下：先将某特征的特征值从小到大排序，再选取分位点进行计算增益即可。

3. xgb中采用的树节点分裂方法（增益计算）

如何看权重分位点的选取呢？上图中前六个特征值的权重之和为0.6，7-8的权重和为0.6，最后一个为0.6，就这选取权重之和相同的点来进行分位点的选取，然后再计算增益。

内容参考wepon大神天池直播