对GBDT, Xgboost 和 LightGbm 的理解

对于机器学习问题，我们寻找函数使得如下损失最小，

$\f^{*} = arg min_{f in H} L(y,f(x))$

其中，

$\L(y,f(x)) = sum_{i=1}^{n}l(y_i,f(x_i))$

Boosting方法假设为一系列基模型的加权和，

$\f_m=sum_{i=1}^{m}h(x;alpha_i)$

其中为基模型，为参数。采用向前迭代演算法求解 ,

$\alpha_m = arg min_{alpha}L(y,f_{m-1}(x)+ h(x;alpha))$

从而得到第步的模型：

$\f_m(x) = f_{m-1}(x)+h(x;alpha_m)$

1、GBDT

下面假设基模型为决策树（Decision Tree），并使用梯度下降法求解最优参数，这样的模型叫做Gradient Boosting Decision Tree(GBDT）。

让达到最小，只需让每一个样本的损失最小，于是沿著梯度方向搜索最优步长即可。从而得到：

$\h(x_i;alpha_m) =C frac{partial l(y_i,f_{m-1}(x_i))}{partial f_{m-1}(x_i)}$

由于的取值乘以一个常数不影响决策树叶子对应的区域(但影响取值），不妨认为

$\h(x_i;alpha_m) = frac{partial l(y_i,f_{m-1}(x_i))}{partial f_{m-1}(x_i)}$

这样我们得到了第个基模型在个样本上的取值，由于模型要适用于未知数据，因此需要有一个参数化的表达。我们需要求解参数，对于决策树，参数就是叶子节点对应的区域和取值，这并不是一个困难的问题。

刚刚提到了叶子节点对应的取值并不准确，因此还需要进一步求解这个值。对于每一个叶子节点上的样本，通过最小化节点上的样本的损失得到最优值。设第个基模型的第个叶子对应的区域为 $R_{jm}$ ，则这个区域上的取值 $gamma_{jm}$ 可以通过极小化下式得到：

$\gamma_{jm} = arg min_{gamma}sum_{x_i in R_{jm}}l(x_i,f_{m-1}(x_i)+gamma)$

这样就得到了第个基模型。在现实使用中，为了避免过拟合，通常可以乘以一个收缩系数，即：

$\f_m(x)=f_{m-1}(x)+gamma h(x;alpha_m)$

2、Xgboost 和 LightGbm

使用梯度下降法只得到了原损失函数的一阶近似，类似于梯度下降和牛顿法的关系，我们可以将损失函数进行二阶泰勒展开：

$l(y,f_{m-1}(x)+h(x;alpha_m))$

$=l(y,f_{m-1}(x))+frac{partial l(y,f_{m-1}(x))}{partial f_{m-1}(x)}h(x;alpha_m)+frac{1}{2}frac{partial^2 l(y,f_{m-1}(x))}{partial^2 f_{m-1}(x)}h^2(x;alpha_m)$

$=l(y,f_{m-1}(x))+g_{m-1}(x)h(x;alpha_m)+frac{1}{2}k_{m-1}(x)h^2(x;alpha_m)$

$=g_{m-1}(x)h(x;alpha_m)+frac{1}{2}k_{m-1}(x)h^2(x;alpha_m)+C ag1$

其中C不影响。

Xgboost同时考虑了如下正则项：

$\Omega(h(x;alpha_m))=frac{1}{2}lambda||gamma_m||^2+eta T$

其中为叶子节点上的取值，为叶子节点的数量。于是优化目标为：

$\L = sum_{i=1}^nl(y,f_{m-1}(x_i)+h(x_i;alpha_m)) +frac{1}{2}lambda||gamma_m||^2+eta T$

假设叶子节点的区域已经确定了，那么各个区域上的取值该怎么计算呢？（对于一个特定的区域，为常数）对于第j个区域，

$\gamma_{jm} = arg min_{gamma}(sum_{x_i in R_{jm}}g_{m-1}(x_i)gamma+frac{1}{2}k_{m-1}(x_i)gamma^2)+frac{1}{2}lambdagamma^2\ = arg min_{gamma}G_{m-1,j}gamma+frac{1}{2}(K_{m-1,j}+lambda)gamma^2\ =-frac{G_{m-1,j}}{K_{m-1,j}+lambda}$

且第个区域上的最小损失为：

$\L_j=-frac{1}{2}frac{G^2_{m-1,j}}{K_{m-1,j}+lambda}$

总的损失为，

$\L = sum_jL_j+eta T$

定义L的相反数为得分S，接下来最大化S。

然而现在的问题是，我们不知道每个区域长什么样。怎么办？办法是从头开始分裂。分裂前的得分为：

$\S_{before}=frac{G_{m-1}}{K_{m-1}+lambda}$

$G_{m-1}$ 是所有样本的一阶导数， $K_{m-1}$ 是所有样本的二阶导数。给定一个特征和阈值，分裂后的得分为：

$\S_{after}=frac{G_{m-1,L}}{K_{m-1,L}+lambda}+frac{G_{m-1,R}}{K_{m-1,R}+lambda}-eta$

$G_{m-1,L}$ 表示左边样本的一阶导数，其它同理。记录使得 $S_{after}$ 最大的特征和阈值，如果 $S_{after}>S_{before}$ ，则完成这次分裂，继续寻找下次分裂，否则停止分裂。

3、最佳分裂点

搜索最佳分裂点时一个特别耗时的过程。

对于连续特征，可以只搜索特定分位点，但这样并不是一种高效而稳健的方法。

对(1)配方，可以得到：

$\=frac{1}{2}k_{m-1}(x)(h(x;alpha_m)-frac{g_{m-1}(x)}{k_{m-1}(x)})^2+C$

$frac{1}{2}k_{m-1}(x)$ 可以看作样本损失的权重。于是，Xgboost的论文中以样本的二阶导数作为样本权重，提出了weigthed Quantile 方法，重新寻找分位点。 $k_{m-1}(x)$ 依赖于最新的模型，需要多次计算。

LightGbm则采用了直方图加速办法。先将特征离散为区间（bins），然后计算每个区间上的样本的一阶导数和二阶导数，最后搜索次数为区间数量，大大减小时间复杂度和空间复杂度。

对于类别变数，可以用Label对应的正样本的比例作为数值，对label进行排序。比如，颜色这个特征下有红、橙、黄、绿、青、蓝、紫7个取值，每个值对应的正样本的比例为红(0.7)、橙(0.2)、黄(0.8)、绿(0.3)、青(0.5)、蓝(0.4)、紫(0.6)。可以将颜色排序为黄、红、紫、青、蓝、绿、橙，这样只需要分裂6次，大大降低复杂度（原来需要分裂次），有文献证明这样的排序能达到cross entropy或 gini index的最优值。