LightGBM: A Highly Efficient Gradient Boosting Decision Tree 论文解析

本文记录了LGB论文中一些技术点，主要由论文内容和个人理解组成，欢迎一起探讨

（一）介绍

GBDT由于其高效性准确性和可解释性近几年来被广泛使用，但是随着大数据时代的发展，传统的GBDT也面临着新的挑战。大数据之所以大，一方面是因为样本的数量多，另一方面是因为特征维度高。而传统的GBDT实现中，对于每次最佳分裂节点的选择算法中，一般有两个for循环，第一个循环遍历所有特征，第二个循环遍历所有样本，计算以某特征某的某个值为分裂点前后的信息增益，所以计算代价将会随着数据量和特征维度的增加而成比例的增加。
直观上，解决上述问题最直接的方法那就减少样本的数量和特征的维度，但是如何在不损失精度的情况下减少样本和特征就是个关键问题了。下面两个算法可以解决这个问题。
Gradient-based One-Side Sampling (GOSS)：对样本进行采样，一个经验做法就是根据样本的权重来选择样本，比如adaboost模型中每一轮训练后都为更新样本的权重，这样在后续的训练中，预测误差大的样本就会被得到更大的关注。基于这一思想，我们也可以利用权重来采样样本。在xgboost的打分函数中我们可以看到，每个样本的训练误差表达式经过配方后，前面有个二阶导系数作为权重，权重越大的损失函数越大，也就是说该样本是训练不足的（under-trained instances），在计算信息增益的时候也将会产生更多的贡献。所以我们可以按照如下的方法来采样：保留梯度（二阶导数）较大的样本，对于梯度较小的样本进行随机采样。经证明，我们将下采样的样本通过一个系数进行放缩后让采样后的样本分布于采样前的样本分布相同，我们就可以在减少样本的情况下得到相同的训练精度。
Exclusive Feature Bundling (EFB):在实际的应用场景中，虽然样本的特征维度很高，但是样本空间都是很稀疏的（比如特征进行one-hot以后），我们可以将这些稀疏的特征合并成较为稠密的特征以减少特征的维度。我们考虑将互斥特征（exclusive features）绑定到一起，互斥特征就是不同时取非零的特征（比如判端一个人是否有老婆、是否有老公这两个特征），并通过图着色算法的贪心解来求得较优的绑定方法。
我们将实现了GOSS和EFB算法的GBDT称作lightGBM。

(二) LGB论文发表前GBDT的发展总结

GBDT是一个决策树的集成模型，在每一轮（即新的树）生成的过程中，GBDT都是沿着前n-1轮训练好的集成模型的梯度来进行拟合的，即拟合前面模型的残差。
在GBDT的每一棵决策树的生成中，最耗时的部分就是树的最佳分割点的选择。最佳分割点的选择一般有两种方法：

• 预排序算法（pre-sorted algorithm ），这是最基本的算法，该算法先将模特先的所有样本按照特征值进行排序，并计算每个样本的一阶和二阶导数，以及所有样本的一阶二阶导数和（这样是为了做差加速），然后逐一枚举所有的分割点。因为是有序的，所以再次遍历一遍所有样本，就能出所有样本的信息增益从而选择出最佳的分割点。这个方法虽然简单有效但是涉及排序，是个非常消耗内存的操作。
• 直方图算法 （histogram-based algorithm），该算法将样本的特征值映射到对应的区间上（被称为桶），这样的好处主要有两点，一个是不用排序了（因为区间都是有序的），第二个是节省了存储内存，比如1.23455这个浮点数被映射到桶1上，我们对该浮点数的存储只要保存int类型的1即可。直方图算法的伪代码形式如下
  

伪代码*四个for循环，第一个for遍历树深度（即每一层），第二个for遍历节点（每一层的每个节点），第三个for 遍历特征，第四个for遍历每个样本。

• $\operatorname{bin} \leftarrow I . \mathrm{f}[\mathrm{k}][j] . \mathrm{bin}$bin←I.f[k][j].bin:找到样本对应的桶
• $H[\text { bin }] . \mathrm{y} \leftarrow H[\mathrm{bin}] . \mathrm{y}+\mathrm{I.y}[\mathrm{j}]$H[ bin ].y←H[bin].y+I.y[j]:这个理解是根据样本的label值算出每个桶中的一阶导和二阶导数的和
• 注：这里的直方图法时直接将连续的特征映射到桶中形成一个直方，很多资料上写xgboost 也用了直方图算法，xgboost的直方并不是将特征映射到桶中形成直方，而是将加权后的二阶导的值分段后形成直方，要注意区分。在xgboost论文发表后的一年，Tianqi Chen 借鉴了lgb的直方图算法，改进了xgboost,githubIssue

(三）Gradient-based One-Side Sampling

采样算法描述

在AdaBoost 中，样本的权重作为样本重要性的标志。但是GBDT样本是没有权重的，所以AdaBoost的采样方法不能被GBDT直接使用，但是GBDT中每个样本都是有梯度的，这个损失函数式子来源于xgboost 论文：
$\sum_{i=1}^{n} \frac{1}{2} h_{i}\left(f_{t}\left(\mathbf{x}_{i}\right)+g_{i} / h_{i}\right)^{2}+\Omega\left(f_{t}\right)+constant$i=1∑n​21​hi​(ft​(xi​)+gi​/hi​)2+Ω(ft​)+constant
可以观察到，梯度越小的样本对应的损失函越小，也就是该样本被训练的很好，那么后续可以减少对该样本的训练。一个最直接的方法就是将这些小梯度的样本丢弃掉，但是这样做的坏处就是会破坏样本的分布，用GOSS算法来解决这个问题，算法的伪代码如下：

GOSS 算法保留了梯度较大的样本，对梯度较小的样本进行下采样 ，为了弥补下采样导致的样本分布问题，我们在下采样的样本上加了个放大的系数$\frac{1-a}{b}$b1−a​,也就下采样后的样本成上这个系数以后 ，在计算信息增益的时候，他们可以以少量的样本来代替所有低梯度的样本。其中top $a*100\%$a∗100%的样本被我们定义成大梯度样本剩下的样本被称为小梯度样本，在小梯度样本中我们采样 $b*100\%$b∗100%的样本。

分裂点的选择

定义分裂后的信息增益如下：

• $n_{O}=\sum I\left[x_{i} \in O\right]$nO​=∑I[xi​∈O] ：表示所有样本
• $n_{l|O}^{j}(d)=\sum I\left[x_{i} \in O : x_{i j} \leq d\right]$nl∣Oj​(d)=∑I[xi​∈O:xij​≤d] ：表示按照feature[j]的值d作为分裂点后左子树的样本
• 我们要遍历所有的d值来找到最佳的分割点

按照GOSS算法的采样后信息增益的表达式就可以写成：

• $A_{l}=\left\{x_{i} \in A : x_{i j} \leq d\right\}$Al​={xi​∈A:xij​≤d}
• $A_{r}=\left\{x_{i} \in A : x_{i j}>d\right\}$Ar​={xi​∈A:xij​>d}
• $B_{l}=\left\{x_{i} \in B : x_{i j} \leq d\right\}$Bl​={xi​∈B:xij​≤d}
• $B_{r}=\left\{x_{i} \in B : x_{i j} > d\right\}$Br​={xi​∈B:xij​>d}
• $\frac{1-a}{b}$b1−a​为了将采样后的小梯度样本的梯度和恢复复到原来小梯度样本的梯度总和上

通过下采样大大减少了样本的数量， 原来是统一划分，现在分成两拨，大梯度样本群和小梯度样本群，在里面分别找到划分点d计算梯度和。
论文中后续没有提到采样后是否在再进行分桶，个人觉得应该还是会进行分桶的，分桶的样本数量大大减少，建立直方图需要o(N)的时间复杂度，现在只需要O(n)(N为所有样本数，n为下采样后的样本数）
这种采样方式的在精确性上的理论保证这里就不展示了，有兴趣的翻阅原论文

(四）Exclusive Feature Bundling

高维的特征通常是稀疏的，特征的稀疏性提供了减少特征数的可能性。我们首先定义互斥特征的概念：如果两个特征不同时取非零值，那么我们称他俩为互斥特征，同时取非零值则称为特征之间有冲突。这是严格的定义，如果允许误差的存在，存在少量冲突的特征我们也可以把他们当做互斥特征。
如果我们将所有的特征根据互斥性分成一个个互斥的特征束，每个特征束内部的特征都是相互互斥的，再将特征束中的特征进行合并，那么合并后的特征总数就变成了特征束的数量，从而大大减少了特征的数量。
所以现在就存在两个问题，一是如何将所有特征划分到特征束中 ，二是每个特征束中的特征们如何合并成一个特征。

如何划分特征束

这是一个NP-hard问题，可以把这个问题类比到图着色问题上，什么是图着色问题可以参考百度百科-图着色问题，没有最佳解，只能找到近似解。
我们构造一个关联组织G(V，E),每个定点V表示一个特征，如果两个特征之间不是互斥（即冲突）的，那么在他们之间添加一条边（即两个点不同着相同的颜色，即不能被划分到同一个特征束中）,边的权重表示这两个特征的总冲突。
这里特征互斥可以放宽限度，可以存在一定的冲突，如果我们允许一个特征束中的冲突率为$\gamma$γ，那么将对训练的精度造成$\mathcal{O}\left([(1-\gamma) n]^{-2 / 3}\right)$O([(1−γ)n]−2/3)的影响，具体证明可以看原论文中的补充材料。所以我们可以在保证准确性的情况下适当的保留些冲突率使得特征束变得更少。
生成特征束的伪代码如下：

我们将所有的特征点根据度进行降序排列，特征的度越大说明跟他冲突的特征越多。

• 第一个for循环遍历所有特征定点
• 第二个for循环遍历当前所有的特征束，计算当前特征加入特征束[j]后特征束[j]的总冲突，如果小于阈值，则将当前特征加入第j个特征束
• 如果找不到可以加入的特征束，则当前特征形成一个新的特征束

这个算法的时间复杂度是$O(features^{2})$O(features2)(sortBydegree的过程），因为要将求每个特征的度，也就是某个特征和剩所有特征进行比较。当特征维度非常大的时候，这个时间开销也是很难接受的。我们可以近似特征非零的个数带代替其degree,因为非零特征值越多，和别的特征的冲突率基本上也就越大。

如何合并特征束

上面的算法已经划分好了特征束，现在要将一个特征束中的特征进行合并成一个特征。我们按照原先不同的特征尽量分到不同的桶的原则，比如AB特征在一个特征束中，A的取值范围为[0,10）,B的取值范围为[0,20），为了合并后能够区分这个两个特征，我们可以给B加一个offset = 10，使其取值范围变为[10,30），这样AB特征就不会出现重叠了。
算法伪代码如下