论文解读：LightGBM——A Highly Efficient Gradient Boosting Decision Tree

摘要

GBDT是个非常流行的机器学习算法，有几个非常有效的应用实现，例如XGBoost合pGBRT。尽管这些应用算法应用来了很多工程优化技术，但是当特征维度特别大，数据量特别多时，这些算法还是不够高效。一个主要原因是：对于每一个特征，他们需要遍历所有数据去估计所有分裂点的信息增益，这会非常耗时。为了解决这个问题，我们提出了两种技术：GOSS(单边梯度采样)和EFB(互斥特征绑定)。对于GOSS，我们留下梯度较大的数据样本，而对梯度较小的样本进行随机采样，并加上权重补偿损失。论文也证明梯度较大的样本对计算信息增益上贡献较大。GOSS可以在较小的数据样本上获得对信息增益比较精确的估计。对于EFB，论文将互斥的特征绑定在一起(他们很少同时接受非零值)。我们证明找到最优绑定是一个NP-hard问题，所以我们找到了一个贪心算法，它可以完成非常好的近似.

1. Introduction

为了解决GBDT面临的挑战，一些研究曾经根据样本的权重来采样数据，但是在GBDT种没有样本权重。所以本文提出两种新技术：

GOSS：注意到，关于数据的梯度对信息增益的影响，于是对保留梯度较大的数据样本，并对梯度较小的样本进行随机采样。为了补偿丢到小梯度样本带来的损失，我们为小梯度样本增加了一个补偿常量

EFB：通常在真实的应用中，尽管数据的维度特别高，但是他们都很稀疏，因此我们设计了一个算法将互斥特征绑定在了一起。关于最优绑定问题，它是一个NP-hard问题，我们设计了一种近似算法将NP-hard问题转化成了图上色的问题(顶点代表特征，为两个不互斥(conflics)的特征添加边)

2. Preliminary

2.1 GBDT and Its Complexity Analysis

在GBDT算法中，时间复杂度最高的部分是寻找最佳的分裂点。最流行的算法就是预排序(pre-ordered)：就是枚举，显然这是非常低效的。还有一种算法是直方图算法(histogram-based algorithm)：它将连续型浮点特征分为离散的桶(bins)，然后用这些桶去构建直方图，累计统计量。本文将在直方图算法的基础上进行优化

2.2 Related Work

XGBoost既支持pre-ordered算法，也支持直方图算法。

使用pre-ordered算法的GBDT模型可以通过忽略值为0的特征来减少训练损失。然而使用直方图算法的GBDT并没有有效的对于稀疏数据的优化解决办法(这就是EFB算法引出的原因)。原因是直方图算法需要检索到桶中的所有特征，不论特征值是否是0或者非0。

3. Gradient-based One-Side Sampling（单边梯度采样）

使用方差增益指标来评估是否为好的分裂，使用单边梯度采样简化方差增益的计算。

公式推导：https://www.zhihu.com/question/386159856

4. Exclusive Feature Bundling

通过谨慎的构建一个特征扫描算法(feature scanning algorithm)，我们可以从特征包中构建与单个特征相同的特征直方图，这样就可以把算法的时间复杂度

这里有两个问题需要解决：

(1) 哪些特征应该绑在一起
找出最优的 bundle 组合数是一个 NP-hard 问题，LightGBM第一步将原问题转化为”图着色”问题，"图着色"问题也是一个NP-hard问题。所以第二步论文设计了一个贪心算法来用"图着色"问题解决互斥特征的绑定。另外，一些特征之间并不是100%的互斥，即有少量样本中不互斥，所以算法允许这些样本之间存在较小的冲突(conflicts)

通过上述讨论，论文设计了一个Greedy Bundling算法：
① 构建一个图，顶点表示特征，边表示特征之间的冲突
② 依据特征冲突的程度排序(降序)
③ 检查排序列表中的每个特征，考虑冲突阈值γ后将其特征放入一个已经存在的或者新建一个bundle
这个算法在特征数量不是特别多的时候时间复杂度可以被接受，为了更进一步提升效率，我们不构建图：通过特征非零值的数量进行排序(对应②)，因为
如果一个特征它的零值比较多的话那么它更容易和其他特征产生冲突

(2) 如何去构建bundle
该过程主要是关键在于原始特征值可以从bundle中区分出来，即绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值在bundle中能够被识别，考虑到直方图算法将连续的值保存为离散的bin，我们可以使得不同特征的值分到bundle中的不同bin中，这可以通过在特征值中加一个偏置常量来解决，比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间[0,10)，B特征的原始取值为区间[0,20），我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为[10,30），这样就可以放心的融合特征A和B了，因为在树模型中对于每一个特征都会计算分裂节点的，也就是通过将他们的取值范围限定在不同的bin中，在分裂时可以将不同特征很好的分裂到树的不同分支中去

5. 结论

LightGBM不论在时间复杂度还是内存消耗上都优于XGBoost

6. 参考算法