XGBoost和LightGBM对GBDT的改进

首先需要了解什么是GBDT。简单来讲，GBDT就是将多个相关性很高的基分类器结合起来的模型。模型中每次新增的基分类器都要尽可能的拟合之前所有基分类器没能拟合的残差信息，也就是求解下面这个公式：
$\hat{\Theta}=\mathop{\arg\min}_{\Theta}\sum_{i=1}^N L(y_i,f_{m-1}(x_i)+T(x_i;\Theta))$ 通过求解这个式子得到 $\hat{\Theta}$ ，也即是新添加进来的基分类器的参数。 $y_i$ 是样本的label， $f_{m-1}(x_i)$ 是前m个基分类器的预测结果， $T(x_i;\Theta)$ 是当前基分类器的预测结果， $T(x_i;\Theta)$ 要尽可能地弥补 $f_{m-1}(x_i)$ 与 $y_i$ 之间的差距。一般而言，GBDT的基分类器是CART，CART每次进行节点分裂时都需要遍历一遍该节点中所有的特征及其对应的所有特征值，求解式子 $\mathop{\min}_{j,s}[\mathop{\min}_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\mathop{\min}_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$ 来得到最优切分变量j和切分点s，其实这个求解过程就是为了保证节点分裂后两个子节点中样本label的方差最小，这样两个子节点中的样本集相对来说才是最“纯”的。
而XGBoost对GBDT的改进我认为主要是2个方面：

损失函数的优化，XGBoost的损失函数如下： $\begin{align}L(\phi) & =\sum_i^n l(y_i,\hat{y_i})+\sum_k\Omega(f_k) \quad (1) \\ & =\sum_{i=1}^n l(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t) \quad (2) \\ & \approx \sum_{i=1}^n[l(y_i,\hat{y}^{(t-1)})+g_if_t(x_i)+\cfrac{1}{2}h_if_t^2(x_i)]+\Omega(f_t),其中g_i=\cfrac{\partial l(y_i,\hat{y}_i^{(t-1)})}{\partial\hat{y}_i^{(t-1)}},h_i=\cfrac{\partial^2 l(y_i,\hat{y_i^{(t-1)}})}{\partial (\hat{y}_i^{(t-1)})^2} \quad (3) \\ & =\sum_{i=1}^n[g_if_t(x_i)+\cfrac{1}{2}h_if_i^2(x_i)]+\gamma T+\cfrac{1}{2}\lambda \sum_{j=1}^Tw_j^2 \quad (4) \\ & =\sum_{j=1}^T[(\sum_{i\in I_j})w_j+\cfrac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2]+\lambda T \quad (5) \\ & =-\cfrac{1}{2}\sum_{j=1}^T\cfrac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda}+\lambda T \quad (6) \end{align}$ 损失函数具体解释：
1. (3)只需要用到2阶泰勒展开，因为损失函数是平方误差，展开到3阶就已经是0了；
2. 我们可以这样理解(4)为啥可以到(5)—— $f_t(x_i)$ 总会落在一个叶子节点上，所以直接统计每个叶子节点中的样本数量再乘上该叶子节点对应的权重 $w_j$ 就可以了。
求解(5)可得最优叶子权重为 $w_j^*=-\cfrac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda}$ 。此时就可以看出XGBoost的第一个改进——并不是直接将叶子节点中每个样本的残差求和得到该叶子节点的权重 $w$ ，而是利用了对每个样本的残差的1阶偏导信息和2阶偏导信息。
节点分裂策略的优化。首先说结论，XGBoost采用近似策略，通过特征的分布，按照一定条件确定一组候选分裂点遍历所有的候选分裂点来找到最佳分裂点。前面CART部分已经指出，节点每次分裂时都要对每个特征进行分析找到局部最优切分点，然后比较这些局部最优切分点得到最优切分变量和对应的最优切分点。这个过程是很耗费时间的，但是可以对其进行优化，优化点就在于局部最优切分点的寻找，其实并没有必要一个一个特征值的代入计算得到每个特征对应的最优切分点。如果把一个特征值看做一个桶，那么我们可以认为特征将数据集进行了桶分，分裂就是将这些桶分为两组，保证每个桶中loss都最小。想要减少计算量，就需要对桶进行合并，将桶的数量减少。XGBoost的做法就是将数据按照特征值进行排序，然后对桶进行合并，合并过程保证新的桶中数据的2阶损失信息之和 $\sum_i h_i$ 都差不多（个人对论文的理解：候选特征值最好能使得数据均匀分布，对(4)进行改写可得 $\sum_{i=1}^n\cfrac{1}{2}h_i(f_t()x_i-\cfrac{g_i}{h_i})^2+\Omega(f_t)+constant$ ，因此将 $h_i$ 视为样本 $i$ 的权重，确定候选分裂值的过程就是保证每个桶中的样本加权和相同）。下面我花了个草图来解释下合并的过程：

XGBoost候选节点选择策略.png

补充：XGBoost会对数据集进行预排序得到一个 $[feature\ number,data\ number]$ 的二维矩阵，其中每一行保存的是数据集按照该行feature值进行排序后的index向量。

个人认为上面提到的2点是XGBoost最大的2个改进，其他的改进还有：

shrinkage技术：在每次迭代中对基分类器的输出再乘上一个缩减权重。该操作是为了减少每个基分类器的影响力，留更多的空间给后面的基分类器来提升。2019.5.15号补充：XGBoost和LightGBM中的学习率就是指这个缩减参数，在XGBoost中shrinkage技术对应的是eta参数，在Light GBM中对应的是learning_rate参数。
采样技术：包括行采样和列采样。行采样就是每次只抽取部分样本进行训练；列采样分两种，一种是在生成基分类器之前就随机选好特征，一种是在每一层中随机选择参与训练的特征。
缺失值处理：将缺失值捆绑起来处理（将缺失值视为新的特征值），并将对应的样本分在左子节点或者右子节点，最后比较两者的收益大小来确定该节点分裂时是将缺失值对应样本分在左边还是右边。

最后总结下XGBoost与GBDT的不同：

XGBoost中基分类器可选择CART或者线性分类器
XGBoost训练时用到了2阶损失信息
XGBoost在损失函数中加入了正则项
XGBoost加入了shrinkage技术
XGBoost的采样技术加入了列采样
XGBoost可以自动学习缺失值的分裂方向
XGBoost支持并行。这里的并行不是tree粒度的并行，而是特征粒度的并行。每个基分类器的生成还是串行的，但是基分类器中每个特征的最优切分点的确定是并行的，每次节点分裂的时候各个特征的增益计算可以开多线程进行。

接下来讲讲LightGBM对GBDT的改进：主要还是对训练效率上的改进。GBDT的训练受到特征数量和数据量的双重影响，所以LightGBM就是从这2个方面入手来对GBDT进行改进。

针对样本数量，LightGBM提出了GOSS()算法，利用每个样本的梯度信息进行采样，保留梯度较大的样本，随机采样梯度较小的样本，同时对这部分采样样本会加上权重，抵消采样对样本分布带来的影响。GOSS算法伪代码如下：

GOSS算法.png
针对特征数量，LightGBM的做法是将一些特征融合成一个特征。在融合的同时对不同特征加上一个bias，保证不同特征对应值的区间没有重叠。不过具体是怎么融合的我暂时不了解，论文中只是将其定义为一个图着色问题，这里先挖个坑。

其他的改进还有：

LightGBM通过leaf-wise策略来生长树，每次选取具有最大 $\bigtriangledown loss$ 的节点来进行分裂（ $\bigtriangledown loss$ 最大说明这个节点对loss的贡献最大，最需要细分）。但是leaf-wise的策略在数据量较小的时候容易过拟合，因此需要限制树的深度来防止过拟合。
采用直方图来优化最优分割点寻找的过程。每次节点分裂时，先将特征值转换成bin值，建立直方图，直方图每个bin保存的是样本的~~label~~和该bin中的样本数。论文中直方图算法的伪代码如下：

LightGBM直方图算法.png

但是根据另外一张PPT来看，每个bin中似乎并没有保存label，而是保存的样本的梯度之和，该PPT如下：

基于直方图的最优分裂点寻找算法.png

个人认为还是下面PPT为准，也就是每个bin中，保存的是样本的梯度和和样本数量。
分裂过程中，LightGBM用了一个小trick，叫直方图做差。分裂时在统计好父节点的直方图后，只需要统计数据量较少的子节点的直方图，就可以通过直方图做差得到另一个节点的直方图。
补充1：我觉得建立直方图的作用主要是为了降低特征值的表示精度（ $float \rightarrow int$ ）和样本的合并。比如说特征值为[0.1,0.5)的都放到bin0中，那么此时表示精度就有float(0.1)变成int(0)，同时，特征值在[0.1,0.5)中的样本均装入bin0中，那么就可以用bin0来代替这些样本，分裂时样本遍历数也从feature_num次减少到bin_num次。
补充2：LightGBM不需要进行预先的排序，但是我觉得是因为装桶的过程就隐含了排序。
LightGBM的并行策略有三种。一种是特征并行，在特征维度上对数据集进行切分并放到不同机器上训练，适合数据量少，但是特征比较多的情况；一种是数据并行，在样本维度上对数据集进行切分并放到不同机器上训练，适合数据量大，但是特征比较少的情况；还有一种是投票并行，在特征维度和样本维度上都进行切分，适合数据量大且特征也多的情况。

XGBoost和LightGBM对GBDT的改进

推荐阅读更多精彩内容