更快更准的LightGBM

GBDT对于每一个特征的每一个分裂点,都需要遍历全部数据来计算信息增益。因此,其计算复杂度将受到特征数量和数据量双重影响,如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存,反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据,普通的GBDT算法很难满足其需求。
LightGBM是Microsoft开发的一个GBDT算法框架,具有更快的训练速度、 更低的内存消耗 、更好的准确率和分布式支持,在传统的GBDT算法上进行了如下优化：

基于Histogram的决策树算法

直方图算法的基本思想：
数值特征离散化／分组：一个bin为一组,根据特征所在的bin值作为索引,遍历寻找最优的分割点

histogram算法的优点:

• 相比于pre-sorted（如xgboost中的exact 算法）, histogram 在内存消耗和计算代价上优势明显：
  • Pre-sorted 算法：需要的内存约是训练数据的两倍(2 N D 4Bytes), 其中N为样本数目,D为特征维数。它需要用32位浮点来保存特征 值,并且对每一列特征,需要一个额外的排好序的索引（需要32 位的存储空间）。
  • histogram 算法：只需要N D 1Bytes)的内存,仅为pre-sorted算 法的1/8。因为histogram 算法仅需要存储特征离散化后的数值, 不需要原始的特征值,也不用排序,而bin索引用8个bit(256个bin) 一般也足够了。
• histogram算法可大幅减少计算分割点增益的次数
  • 对于一个特征,pre-sorted 需要对每一个不同特征值都 计算一次分割增益,而histogram 只需要计算bin 次。
• 使用bin替代原始数据相当于增加了正则化,bin数量越少惩罚越严重
• 构建直方图时不需要对数据进行排序（比XGBoost快）,因为预先设定了bin的范围
• 直方图做差加速 一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到,在速度上可以提升一倍。通常构造直方图时,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。在实际构建树的过程中,LightGBM还可以先计算直方图小的叶子节点,然后利用直方图做差来获得直方图大的叶子节点,这样就可以用非常微小的代价得到它兄弟叶子的直方图。
• XGBoost的Weighted Quantile Sketch分布式加权直方图算法基于样本对应的二阶导Hi去找候选bin的分割点，当前层所有特征共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图，而LightGBM中对每个特征都有一个直方图，所以构建一次直方图就够了。

直方图除了保存划分阈值和当前bin内样本数以外还保存了当前bin内所有样本的一阶梯度和（一阶梯度和的平方的均值等价于均方损失),阈值的选取是按照直方图从小到大遍历,使用了上面的一阶梯度和,目的是得到划分之后△loss最大的特征及阈值。

带深度限制的Leaf-wise的叶子生长策略

level-wise过一次数据可以同时分裂同一层的叶子,容易进行多线程优化,不容易过拟合。但level-wise不加区分的对待同一层的叶子,带来了很多没必要的开销, 比较低效（很多叶子的分裂增益较低,没必要进行搜索和分裂） leaf-wise每次从当前所有叶子中,找到分裂增益最大(一般也是数据 量最大)的一个叶子进行分裂。同level-wise 相比,在分裂次数相同 的情况下,leaf-wise 可以降低更多的误差,得到更好的精度。 leaf-wise 的缺点是可能会长出比较深的决策树,产生过拟合。因此 LightGBM在leaf-wise 之上增加了一个最大深度的限制,在保证高 效率的同时防止过拟合。

直接支持类别特征(Categorical Feature)

树模型来说并不推荐使用 one-hot 编码,尤其当类别特征中类别个数很多的情况下,会存在以下问题：

• 会产生样本切分不平衡问题,导致切分增益非常小（即浪费了这个特征）。使用 one-hot编码,意味着在每一个决策节点上只能使用one vs rest（例如是不是狗,是不是猫等）的切分方式。例如,动物类别切分后,会产生是否狗,是否猫等一系列特征,这一系列特征上只有少量样本为 1,大量样本为 0,这时候切分样本会产生不平衡,这意味着切分增益也会很小。较小的那个切分样本集,它占总样本的比例太小,无论增益多大,乘以该比例之后几乎可以忽略；较大的那个拆分样本集,它几乎就是原始的样本集,增益几乎为零。比较直观的理解就是不平衡的切分和不切分没有区别。
• 会影响决策树的学习。因为就算可以对这个类别特征进行切分,独热编码也会把数据切分到很多零散的小空间上,如下图左边所示。而决策树学习时利用的是统计信息,在这些数据量小的空间上,统计信息不准确,学习效果会变差。但如果使用下图右边的切分方法,数据会被切分到两个比较大的空间,进一步的学习也会更好。下图右边叶子节点的含义是X=A或者X=C放到左子节点,其余放到右子节点。

LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。LightGBM采用 many-vs-many 的切分方式将类别特征分为两个子集,实现类别特征的最优切分。假设某维特征有 k 个类别,则有种可能性,时间复杂度为,LightGBM 基于 Fisher的《On Grouping For Maximum Homogeneity》论文实现了的时间复杂度。算法流程如下图所示,在枚举分割点之前,先把直方图按照每个类别对应的label(标签)均值进行排序；然后按照排序的结果依次枚举最优分割点。从下图可以看到, 为类别的均值。当然,这个方法很容易过拟合,所以LightGBM里面还增加了很多对于这个方法的约束和正则化。

Cache命中率优化

计算下一个分裂点循环每一个特征的时候,每个样本的梯度在本轮是固定不变的,可缓存提升训练速度。
LightGBM 所使用直方图算法使所有的特征都采用相同的方式获得梯度（区别于XGBoost的不同特征通过不同的索引获得梯度）,只需要对梯度进行排序并可实现连续访问,大大提高了缓存命中率；不需要存储行索引到叶子索引的数组,降低了存储消耗,而且也不存在 Cache Miss的问题。

互斥特征捆绑算法 (Exclusive Feature Bundling)

通过特征捆绑的方式减少特征维度,通常被捆绑的两个或者多个特征都是互斥的（即特征不会同时为非零值,像one-hot）,如果特征间并不是完全互斥（部分情况下所有特征都是非零值）,可以用一个指标对特征不互斥程度进行衡量,称之为冲突比率,当这个值较小时,我们可以选择把不完全互斥的特征捆绑,而不影响最后的精度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定,则可以降低特征数量。这样在构建直方图时的时间复杂度从O(#data #feature)降到O(#data #bundle),由于#bundle << # feature,我们能够极大地加速GBDT的训练过程而且不损失精度。

怎么判定哪些特征应该绑在一起（build bundled）?

将特征分割为较小量的互斥特征群是NP难的,LightGBM的EFB算法将这个问题转化为图着色的问题来求解,将所有的特征视为图的各个顶点,将不是相互独立的特征用一条边连接起来,边的权重就是两个相连接的特征的总冲突值,这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外,我们注意到通常有很多特征,尽管不是100％相互排斥,但也很少同时取非零值。 如果我们的算法可以允许一小部分的冲突,我们可以得到更少的特征包,进一步提高计算效率。经过简单的计算,随机污染小部分特征值将影响精度最多 O([(1–γ)n]−2/3),γ是每个绑定中的最大冲突比率,当其相对较小时,能够完成精度和效率之间的平衡。当其相对较小时,能够完成精度和效率之间的平衡。具体步骤可以总结如下：

1. 构造一个加权无向图,顶点是特征,边有权重,其权重与两个特征间冲突相关；
2. 根据节点的度进行降序排序,度越大,与其它特征的冲突越大；
3. 遍历每个特征,将它分配给现有特征包,或者新建一个特征包,使得总体冲突最小。

算法允许两两特征并不完全互斥来增加特征捆绑的数量,通过设置最大冲突比率 来平衡算法的精度和效率。EFB 算法的伪代码如下所示：
算法3的时间复杂度是O(feature2),训练之前只处理一次,其时间复杂度在特征不是特别多的情况下是可以接受的,但难以应对百万维的特征。为了继续提高效率,改变排序策略：将特征按照非零值个数排序,其他还是保持一样

怎么把特征绑为一个（merge feature）?

如何合并同一个bundle的特征来降低训练时间复杂度。关键在于原始特征值可以从bundle中区分出来。鉴于直方图算法存储离散值而不是连续特征值,我们通过将互斥特征放在不同的箱中来构建bundle。这可以通过将偏移量添加到特征原始值中实现,例如,假设bundle中有两个特征,原始特征A取值[0, 10],B取值[0, 20]。我们添加偏移量10到B中,因此B取值[10, 30]。通过这种做法,就可以安全地将A、B特征合并,使用一个取值[0, 30]的特征取代AB。

单边梯度采样 Gradient-based One-Side Sampling(GOSS)

GOSS是一个样本的采样算法,目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的。根据计算信息增益的定义,梯度大的样本对信息增益有更大的影响。因此,GOSS在进行数据采样的时候只保留了梯度较大的数据,但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布。所以,GOSS首先将要进行分裂的特征的所有取值按照绝对值大小降序排序（XGBoost一样也进行了排序,但是LightGBM不用保存排序后的结果）。选取top a个实例。然后在剩余的数据中随机采样b个实例。接着计算信息增益时为采样出的小梯度数据乘以(1-a)/b,这样算法就会更关注训练不足的实例,而不会过多改变原数据集的分布。

支持高效并行

特征并行

特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点,然后在机器间同步最优的分割点。XGBoost使用的就是这种特征并行方法。这种特征并行方法有个很大的缺点：就是对数据进行垂直划分,每台机器所含数据不同,然后使用不同机器找到不同特征的最优分裂点,划分结果需要通过通信告知每台机器,增加了额外的复杂度。
LightGBM 则不进行数据垂直划分,而是在每台机器上保存全部训练数据,在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。具体过程如下图所示。

数据并行

传统的数据并行策略主要为水平划分数据,让不同的机器先在本地构造直方图,然后进行全局的合并,最后在合并的直方图上面寻找最优分割点。这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信,一台机器的通讯开销大约为 O(#machine#feature#bin)；如果使用集成的通信,则通讯开销为 O(2#feature#bin)；
LightGBM在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器,合并不同worker的无交叉的不同特征的直方图,降低通信和计算,并利用直方图做差,先计算样本量少的节点的样本索引，在通信的过程中可以只传输某一叶节点的直方图，而对于其邻居可通过直接相减得到子节点的样本索引,进一步减少了一半的通信量。具体过程如图所示。

投票并行

基于投票的数据并行则进一步优化数据并行中的通信代价,使通信代价变成常数级别。在数据量很大的时候,使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的,可以得到非常好的加速效果。具体过程如下图所示。
大致步骤为两步：

1. 本地找出 Top K 特征,并基于投票筛选出可能是最优分割点的特征；

2. 合并时只合并每个机器选出来的特征。

   总结

3. 内存更小

   • XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 O(2*#data) 降低为 O(#bin) ，极大的减少了内存消耗；
   • LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
   • LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
4. 速度更快
   • LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
   • LightGBM 采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
   • LightGBM 采用基于 Leaf-wise 算法的增长策略构建树，减少很多不必要的计算量；
   • LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
   • LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。

参考链接

lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf
深入理解LightGBM
深入理解LightGBM
XGBoost 和 Lightgbm 笔记
RF,GBDT,XGBOOST, LightGBM之间的爱恨情仇