补课LightGBM算法原理

num_leaves = 427

这是近期在一个反欺诈联合建模的项目中，对方曾用LightGBM训练出的模型参数。当时的第一反应是，叶子为什么会设这么多，树建得太深不怕过拟合吗？因为在XGBoost的建模经验中，树深通常不超过4，意味着叶子数在16以内，而LGBM和XGB很像，都是二叉树，都属于GBDT框架，两者不能差这么多啊。
后面才知道，LGBM在树生长的策略上和XGB不一样，前者用的是Leaf-wise策略，后者用的是Level-wise，但是这种有400多个叶子的情况确实也不正常。不管怎么说，这对我也是个提醒，不能再以XGB的惯性思维来看LGBM了，这次咱就把LGBM的原理知识给补上。

1. LGBM算法起源
   LGBM是轻量级(Light)的梯度提升机器(GBM)，由微软的DMTK团队打造并于2017年在GitHub上作了开源。和XGB一样，是GBDT的一个进化版本，它延续了XGB的那一套集成学习的方式，但是相对于XGB，具有训练速度快和内存占用率低的特点。其原理介绍见论文‍《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》（百度学术可以下载）。
2. 从XGB的缺点到LGBM的优化
   在LGBM提出之前，最有名的GBDT工具就是XGB了。我们知道XGB采用了预排序和分位点近似等方式实现并行计算、减少计算压力，但是面对海量数据，训练速度依然是个问题。比如XGB在寻找特征最佳分裂点过程中，首先要对所有特征按照值大小进行预排序，然后通过遍历分割点找到特征上的最佳分割点，最后用该分割点将数据分裂成左右子节点；这样虽然能精确找出最佳分割点，但是对空间和时间的消耗都太大了：在空间方面，需要同时保存数据的特征值和特征排序后的索引，相当于消耗两倍内存；在时间方面，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗也不小。

除了上面提到的贪心算法，XGB还提供了分位点近似算法，这也是LGBM中直方图算法的思想，虽然也能减少遍历的分割点，不过效果有限，LGBM对此作了更好的运用。但不管是贪心算法还是近似算法，在节点分裂的过程中，分裂点数量、样本数量和特征数量这三点都是影响计算复杂度的重要因素，而LGBM在这三点上都做了很大的优化。LGBM的特点体现在：
基于Histogram的决策树算法：减少分裂点数量（离散化）
单边梯度采样(GOSS)：减少样本数量（采样）
互斥特征捆绑(EFB)：减少特征数量（降维）
Leaf-wise式生长策略：减少需要分裂的叶子数量（分裂源头）
支持类别特征
支持高效并行
Cache命中率优化

3. LGBM的优化细节
   本文中的示例图基本来自如下这篇文章，文章作者zhong_ddbb出的白话机器学习系列文章通俗易懂，值得大家读读：

直方图通常用来看数据的分布情况，比如看某客群在各个年龄段上的分布情况，首先要对年龄进行分段，其次对各个年龄段上的样本作统计，运用到LGBM上也是类似做法。

LGBM的直方图算法，也是先将连续的数值特征离散化为k个bins(bin值用连续的整数表示)，比如[20,30)->0、[30,40)->1、[40,60)->2，然后后续的各种统计都基于bin来算，待画出基于bin的直方图后，就可以在图上遍历寻找最优的分割点，从而替代XGB的预排序算法。与XGB中预排序只考虑非零值类似，LGBM只用非零特征构建直方图。

因为bin的数量远小于样本的水平数，遍历分裂点的个数也会少很多，计算量也就小了，而且bin的排序性和整数型特点使其天然可作为索引来使用，具体体现在：
内存消耗更低。XGB需要用32位的浮点数去存储特征值，并用32位的整型去存储索引，而LGBM不需要额外存储预排序的结果，只需要保存特征离散化后的值，这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。

计算代价更小。预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次，时间复杂度从O((特征值个数−1)∗特征数)降为O((k−1)∗特征数)。

除了以上最直接的优势之外，利用直方图的特性还可以在节点分裂上做差加速，显著提升计算速度，即直方图加速大法。一个叶子节点的直方图可以由父节点和兄弟节点的直方图做差得到，这样在构造直方图时，就不需要遍历叶子上的所有数据，只需遍历直方图的k个bin，速度可提升一倍。

既然每一次分裂之后都需要在分裂出的两个叶子上重新画出各个特征的直方图，那就可以挑样本量少的叶子先画啊，即先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就能用很小的代价得到它兄弟叶子的直方图。如下图x1为最佳切分特征：

但特征被这样离散化后，找到的并不是精确的分割点，不会影响算法的精度吗？在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些，原因在于决策树本身就是一个弱学习器，分割点是不是精确并不是太重要，直方图算法反而会起到正则化的效果，有效防止模型过拟合。

前面提到XGB的分位点近似算法对提升速度非常有限，这怎么理解？那个近似算法叫做Weight Quantile Sketch，考虑的是样本对loss的贡献，用样本在loss函数的二阶导数hi来表示，相当于基于hi的分布去找候选分割点，这样在每一层划分结束之后，下一次依然需要构建这样的直方图，毕竟样本被划分到了不同的节点中，二阶导分布也就变了。所以XGB在每一层都得动态构建直方图，因为它这个直方图算法不是针对某个特定的特征的，而是所有特征共享一个直方图（每个样本的二阶导）。而LGBM对每个特征都有一个直方图，这样构建一次就好，而且还能通过直方图作差加速分裂。因此XGB的直方图算法不如LGBM来的快。

2）单边梯度抽样算法(GOSS)
在AdaBoost中，会给每个样本一个权重，每一轮之后再调大错误样本的权重，让后面的模型更加关注前面分错的样本，这时候样本权重就体现了数据的重要程度。到了GBDT中，没有像Adaboost这样的样本权重，但是GBDT中每个数据都会有不同的梯度值，而梯度小的样本，训练误差也比较小，说明数据已经被模型学习的很好了，LGBM就基于梯度的这个特点对样本进行采样，剔除部分梯度小的样本，让模型更加关注那些梯度大的样本。
这里解释下梯度小的样本对模型学习帮助不大的原因。GBDT聚焦于残差学习，以残差的平方函数为例，一阶求导后可得到如下残差和梯度的关系，可以看到如果新的模型要想降低残差的效果好，那样本的梯度就应该越大越好。

不过只是通过简单剔除梯度小的样本，用剩下的样本来训练模型，势必会改变数据的分布，模型精度也会受到影响。GOSS(Gradient-based One-Side Sampling)算法对此作了特殊处理，它保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了补偿数据分布改变带来的影响，在计算信息增益时为梯度小的样本引入一个常数进行平衡。

假设样本个数=500，GOSS首先将这些样本按照梯度值的绝对值进行排序，然后选取值最大的a500个数据，在剩下的较小梯度样本中随机选择b500个数据，再给这b500个数据乘以一个常数(1− a)/b，这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布（a+(1-a)/bb=1）。

示例如上，在选出了两个梯度大的和两个梯度小的样本之后，在小梯度样本前面乘以一个常数作为新的权重。在这样得到的样本上画出的直方图中，样本总个数依然是8个，虽然6个梯度小的样本中去掉了4个，留下了两个。但是这两个样本在梯度上和个数上都进行了3倍的放大，因此可防止采样对原数数据分布造成太大的影响。GOSS正是通过这样的方式，在不降低太多精度的同时，减少了样本数量，加快了训练速度。

3）互斥特征捆绑算法(EFB)

高维度的数据往往是稀疏的，这种特点启发我们在信息尽量无损的情况下进行特征降维，EFB(Exclusive Feature Bundling)算法就是通过捆绑特征来降低特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息，但EFB可以接受两个不完全互斥的特征（部分情况下两个特征都是非零值），我们用冲突比率来衡量特征不互斥的程度，当这个值较小时，EFB也可以对其进行捆绑，而不会对精度造成较大影响。这样计算的时间复杂度就会从O(#data#feature)，降低为O(#data#bundle)。

那么EFB算法是怎么判定哪些特征应该绑在一起，绑定之后的特征值应该如何确定呢。先看第一个问题，EFB会利用特征和特征间的关系构造一个加权无向图：
将所有特征看成图的各个顶点，将有冲突的特征用边连起来，边的权重就是相连特征的总冲突值（即相连特征同时不为0的样本个数）。
按照节点的度对特征降序排序，度越大，说明与其他特征的冲突越大。
对于每一个特征，遍历已有的特征簇，如果在设定的冲突阈值之内，则将特征加入到簇中，如果所有簇都加不进去，就新建一个簇，把自己放进去。

这样就获得了可以捆绑的特征簇，但是这里既要遍历特征，又要对每个特征遍历簇，当特征很多的时候，算力就是个问题了。为了对此进行优化，可直接将特征按照非零值样本个数进行排序，因为更多非零值的特征会导致更多的冲突，这样就不用构建图，排序后即可进行第三步的分簇了。
接着看第二个问题，捆绑后的特征该如何取值，这里关键在于原始特征需要能从捆绑后的特征中分离出来。处理起来也比较简单，在特征值中加入一个偏置常量就可以解决，通过特征值作区分。比如，将特征A和B绑定到了同一个bundle里面，A的原始取值区间[0,10), B为[0,20), 就可以在特征B的取值上加一个常量10转换为[10,30)，这样绑定好的特征取值就是[0,30)，就可以放心的融合了。

图中用bin来解释可能不妥，
我们将bin理解为特征的原始值就好

4）Leaf-wise生长策略
除了使用前面提到的三大算法对寻找最优分裂点的过程进行优化，LGBM在树的生成过程中也进行了优化，它抛弃了XGB的按层生长(level-wise)策略，而采用了带有深度限制的按叶子生长(leaf-wise)策略。在Level-wise中，遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，但这其实是一种低效的策略，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂，因此带来了很多没必要的计算开销。

而Leaf-wise生长策略更为高效，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后在该叶子上进行分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。不过Leaf-wise可能会长出比较深的决策树，产生过拟合，对此除了叶子数量，LGBM在Leaf-wise上还增加了最大深度的限制，这样在提高计算效率的同时，也能抑制过拟合。

5）LGBM的工程优化
这块内容不在开头提到的论文中，而体现在Qi Meng等相关作者写的另一篇论文《A communication-efficient parallel algorithm for decision tree》中。关于工程上的优化方案主要有类别特征支持、高效并行和Cache命中率优化这三部分。
支持类别特征
大多数模型都无法直接支持类别特征，一般需要把类别特征先通过one-hot编码转化到多维的0/1特征。但对于决策树来说，这种方式弊端也很明显，尤其在特征类别很多的情况，体现在：
a. 样本切分不平衡，切分增益会非常小。如居住城市切分后，会产生是否北京，是否南通等系列特征，这些特征上只有少量样本为1，大量为0。这样拆分出来的较小的样本集，占总样本的比例也很小，无论增益多大，乘以该比例之后几乎可以忽略；而较大的样本集几乎就是原始的样本集，增益几乎为零，这种不平衡的切分带来的效果几乎和不切分是一样的。
b. 影响决策树学习。决策树依赖的是数据的统计信息，而one-hot会把数据切分到零散的小空间上，在这些小空间上统计信息不准确的，学习效果就会变差。

对此，LGBM采用many-vs-many的切分方式将类别特征分为两个子集，如下图右通过if x in (‘A’,’B’)的方式切分出来左右样本集对应的样本量要均衡些，更有利于模型学习，这也使得LGBM称为第一个直接支持类别特征的GBDT工具。在算力这块，假设某个特征有k个类别，则有 种中切分组合（类似将班级里k个同学分成两组的组合问题），时间复杂度为 ，LGBM基于Fisher的《On Grouping For Maximum Homogeneity》论文实现了 的时间复杂度。

左边基于one-hot分裂，右边基于many-vs-many
这种切分思路在于，先把直方图按照每个类别对应的label均值进行排序，然后再按照排序的结果依次枚举最优分割点，其实和风控建模时用特征各个水平对应的坏账率来替代特征值的处理思路是一样的。当然了，这里用到了label信息很容易产生过拟合，LGBM为此在这个方法上增加了很多约束条件。实验结果证明，相对于one-hot，many-vs-many可以在精度不变的情况下，使训练速度加速8倍。

支持高效并行

在通过并行方式提升速度方面，LGBM可支持特征并行、数据并行和投票并行这三种方式。
a.特征并行(Attribute-parallel)。XGB使用的正是这种并行方法，通过垂直划分数据集到多个机器中，每个机器在不同的特征集上分别寻找最优的分割点，然后在机器间同步最优的分割点。因为要把划分结果通信告知到每台机器，因此会增加额外的复杂度。而LGBM会在每台机器上都会保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

b.数据并行(Data-parallel)。这类方法一般通过水平划分数据，让不同的机器先在本地构造直方图，然后进行全局合并，最后在合并的直方图上面寻找最优分割点。这种方式往往带来的通讯开销很大，比如使用点对点通信，一台机器的通讯开销大约为O(#machine×#feature×#bin)。而LGBM在数据并行中使用分散规约(Reduce scatter)把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步将通信量减半。

c.投票并行(Parallel Voting Decision Tree)。一般先在本地找出Top K个特征，并基于投票筛选出可能是最优分割点的特征，然后合并时只合并每个机器选出来的特征。这种方式其实是对数据并行的进一步优化，使通信代价变成常数级别，特别是在数据量很大的时候，通过只合并部分特征的直方图可以有效达到降低通信量，得到非常好的加速效果。

Cache命中率优化

XGB对cache优化不友好，在预排序后特征对梯度的访问是随机的，不同的特征访问的顺序也不一样，无法对cache进行优化。而且在每一层树生长的过程，需要随机访问一个行索引到叶子索引的数组，不同特征访问的顺序也不一样，也会造成较大的cache miss。为了解决缓存命中率低的问题，XGB提出了缓存访问算法进行改进。

而LGBM所用的直方图算法对Cache天生友好。首先，所有特征都采用相同的方式获得梯度（区别于XGB的不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，极大提高了缓存命中率；其次，因为不需要存储行索引到叶子索引的数组，降低了存储消耗，也不存在Cache Miss的问题。
这部分内容我也没理解透，先放在这里作个了解。

4. 最后总结

LGBM提出的初衷就是解决工程上的问题，也就是在面对海量数据时如何做到又快又准，为此在XGB的基础上做了很多的优化，我们从内存和速度两个角度来总结下：
a. 内存更小

使用直方图算法将特征值转变为bin值，且不需要记录特征到样本的索引，将分裂过程的空间复杂度从XGB的O(2*#data)降低为O(#bin)，极大降低了内存消耗
直方图算法将存储特征值转变为存储bin值，降低了内存消耗
互斥特征捆绑算法减少了特征数量，降低了内存消耗

b. 速度更快

采用直方图算法将遍历样本转变为遍历直方图，极大降低了时间复杂度
单边梯度算法过滤掉梯度小的样本，减少了大量计算
基于Leaf-wise的生成策略构建树，减少了很多不必要的计算量
采用优化后的特征并行、数据并行方法加速计算
对缓存进行了优化，增加了Cache的命中率

5. 参考文献
   白话机器学习算法理论+实战番外篇之LightGBM：https://blog.csdn.net/wuzhongqiang/article/details/105350579?tdsourcetag=s_pctim_aiomsg
   LGBM论文原文：《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》