LightGBM总结

前言

  • 对LightGBM的亮点总结

简介

Lightgbm里面的直方图算法就是为了减少分裂点的数量, Lightgbm里面的单边梯度抽样算法就是为了减少样本的数量, 而Lightgbm里面的互斥特征捆绑算法就是为了减少特征的数量。 并且后面两个是Lightgbm的亮点所在

直方图算法

LightGBM的直方图算法是代替Xgboost的预排序算法的,虽然直方图的算法思路不算是Lightgbm的亮点,毕竟xgboost里面的近似算法也是用的这种思想,但是这种思路对于xgboost的预排序本身也是一种优化,所以Lightgbm本着快的原则,也采用了这种直方图的思想。那么直方图究竟在做什么事情呢?

直方图算法说白了就是把连续的浮点特征离散化为k个整数(也就是分桶bins的思想), 比如[0, 0.1) ->0, [0.1, 0.3)->1。 并根据特征所在的bin对其进行梯度累加和个数统计,在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。 拿出某一个连续特征来看看如何分桶的:

这样在遍历到该特征的时候,只需要根据直方图的离散值,遍历寻找最优的分割点即可,由于bins的数量是远小于样本不同取值的数量的,所以分桶之后要遍历的分裂点的个数会少了很多,这样就可以减少计算量

XGBoost 在进行预排序时只考虑非零值进行加速,而 LightGBM 也采用类似策略:只用非零特征构建直方图。这种离散化分桶思路其实有很多优点的, 首先最明显就是内存消耗的降低,xgboost需要用32位的浮点数去存储特征值, 并用32位的整型去存储索引,而Lightgbm的直方图算法不仅不需要额外存储预排序的结果,而且可以只保存特征离散化后的值,而这个值一般用8位整型存储就足够了,内存消耗可以降低为原来的1/8
在计算上的代价也大幅降低,预排序算法每遍历一个特征值就需要计算一次分裂的增益,而Lightgbm直方图算法只需要计算k次(k可以认为是常数,为bin的个数)

Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下,构造Histogram需要遍历该叶子上的所有数据,通过该方法,只需要遍历Histogram的k个桶。速度提升了一倍。再说一下这个细节, 到底这是啥意思

Histogram算法并不是完美的。由于特征被离散化后,找到的并不是很精确的分割点,所以会对结果产生影响。但在实际的数据集上表明,离散化的分裂点对最终的精度影响并不大,甚至会好一些。原因在于decision tree本身就是一个弱学习器,分割点是不是精确并不是太重要,采用Histogram算法会起到正则化的效果,有效地防止模型的过拟合bin数量决定了正则化的程度,bin越少惩罚越严重,欠拟合风险越高)。 直方图算法可以起到的作用就是可以减小分割点的数量, 加快计算。

xgboost不是后面的近似分割算法也进行了分桶吗? 为啥会比lightgbm的直方图算法慢这么多呢? xgboost那里的分桶是基于什么? 那个算法叫做Weight Quantile Sketch算法,考虑的是对loss的影响权值,用的每个样本的 $h_i $ 来表示的,相当于基于 $ h_i $ 的分布去找候选分割点,这样带来的一个问题就是每一层划分完了之后,下一次依然需要构建这样的直方图,毕竟样本被划分到了不同的节点中,二阶导分布也就变了。 所以xgboost在每一层都得动态构建直方图, 因为它这个直方图算法不是针对某个特定的feature的,而是所有feature共享一个直方图(每个样本权重的二阶导)

而lightgbm对每个特征都有一个直方图,这样构建一次就OK, 并且分裂的时候还能通过直方图作差进行加速。 故xgboost的直方图算法是不如lightgbm的直方图算法快的

单边梯度抽样算法(GOSS)

单边梯度抽样算法(Gradient-based One-Side Sampling)是从减少样本的角度出发, 排除大部分权重小的样本,仅用剩下的样本计算信息增益,它是一种在减少数据和保证精度上平衡的算法。

众所周知,GBDT中没有原始样本的权重,既然Lightgbm是GBDT的变种,应该也没有原始样本的权重,你这里怎么排除大部分权重小的样本? 我们知道在AdaBoost中,会给每个样本一个权重,然后每一轮之后调大错误样本的权重,让后面的模型更加关注前面错误区分的样本,这时候样本权重是数据重要性的标志,到了GBDT中, 确实没有一个像Adaboost里面这样的样本权重,理论上说是不能应用权重进行采样的, But, 我们发现啊, GBDT中每个数据都会有不同的梯度值, 这个对采样是十分有用的, 即梯度小的样本,训练误差也比较小,说明数据已经被模型学习的很好了,因为GBDT不是聚焦残差吗? 在训练新模型的过程中,梯度比较小的样本对于降低残差的作用效果不是太大,所以我们可以关注梯度高的样本,这样不就减少计算量了吗? 当然这里你可能没有明白为啥梯度小的样本对降低残差效果不大, 那咱可以看看GBDT的这个残差到底是个什么东西。 把xgboost里面的一个图截过来:

但是要是盲目的直接去掉这些梯度小的数据,这样就会改变数据的分布,Lightgbm才提出了单边梯度抽样算法,根据样本的权重信息对样本进行抽样,减少了大量梯度小的样本,但是还能不会过多的改变数据集的分布,这就比较牛了。 怎么做的呢?

GOSS 算法保留了梯度大的样本,并对梯度小的样本进行随机抽样,为了不改变样本的数据分布,在计算增益时为梯度小的样本引入一个常数进行平衡。

首先将要进行分裂的特征的所有取值按照绝对值大小降序排序(xgboost也进行了排序,但是LightGBM不用保存排序后的结果),然后拿到前 a % 的梯度大的样本,和剩下样本的 b %,在计算增益时,后面的 b%通过乘上 $ \frac{1-a}{b} $来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上,另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

这个地方要注意一下,如果看论文,这个前 a % 的样本和剩下样本的 b% 其实是这样算的, 前 a% 就是选出 a×#samples 个样本作为梯度大的, b%就是在剩下的样本中选出 b×#samples 个样本作为梯度小但是保留下来的样本

通过上面,我们就通过采样的方式,选出了我们的样本,两个梯度大的6号和7号,然后又从剩下的样本里面随机选了2个梯度小的,4号和2号,这时候我们重点看看基于采样样本的估计直方图长什么样子,毕竟我们从8个里面选出了四个,如果直接把另外四个给删掉的话,这时候会改变数据的分布,但应该怎么做呢?

梯度小的样本乘上相应的权重之后,我们在基于采样样本的估计直方图中可以发现Ni的总个数依然是8个, 虽然6个梯度小的样本中去掉了4个,留下了两个。 但是这2个样本在梯度上和个数上都进行了3倍的放大,所以可以防止采样对原数数据分布造成太大的影响, 这也就是论文里面说的将更多的注意力放在训练不足的样本上的原因

Lightgbm正是通过这样的方式,在不降低太多精度的同时,减少了样本数量,使得训练速度加快

互斥特征捆绑算法(EFB)

高维度的数据往往是稀疏的,这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的(即特征不会同时为非零值,像one-hot),这样两个特征捆绑起来才不会丢失信息。果两个特征并不是完全互斥(部分情况下两个特征都是非零值),可以用一个指标对特征不互斥程度进行衡量,称之为冲突比率,当这个值较小时,我们可以选择把不完全互斥的两个特征捆绑,而不影响最后的精度,举例如下:

  • 怎么判定哪些特征应该绑在一起?
    • 首先将所有的特征看成图的各个顶点,将不相互独立的特征用一条边连起来,边的权重就是两个相连接的特征的总冲突值(也就是这两个特征上同时不为0的样本个数)
    • 然后按照节点的度对特征降序排序, 度越大,说明与其他特征的冲突越大
    • 对于每一个特征, 遍历已有的特征簇,如果发现该特征加入到特征簇中的矛盾数不超过某一个阈值,则将该特征加入到该簇中。 如果该特征不能加入任何一个已有的特征簇,则新建一个簇,将该特征加入到新建的簇中

  • 特征绑在一起之后,特征值应该如何确定呢?
    • 关键就是原始特征能从合并的特征中分离出来, 这是什么意思? 绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle里面进行识别,考虑到直方图算法将连续的值保存为离散的bins,我们可以使得不同特征的值分到簇中的不同bins里面去,这可以通过在特征值中加入一个偏置常量来解决。
    • 比如,我们把特征A和B绑定到了同一个bundle里面, A特征的原始取值区间[0,10), B特征原始取值区间[0,20), 这样如果直接绑定,那么会发现我从bundle里面取出一个值5, 就分不出这个5到底是来自特征A还是特征B了。 所以我们可以再B特征的取值上加一个常量10转换为[10, 30),这样绑定好的特征取值就是[0,30), 我如果再从bundle里面取出5, 就一下子知道这个是来自特征A的。 这样就可以放心的融合特征A和特征B了。 看下图:

LightGBM的生长策略(Leaf-wise)

lightgbm除了在寻找最优分裂点过程中进行了优化,其实在树的生成过程中也进行了优化, 它抛弃了xgboost里面的按层生长(level-wise), 而是使用了带有深度限制的按叶子生长(leaf-wise)。

这两种生长方式是怎么回事, XGBoost 在树的生成过程中采用 Level-wise 的增长策略,该策略遍历一次数据可以同时分裂同一层的叶子,容易进行多线程优化,也好控制模型复杂度,不容易过拟合。但实际上Level-wise是一种低效的算法,因为它不加区分的对待同一层的叶子,实际上很多叶子的分裂增益较低,没必要进行搜索和分裂,因此带来了很多没必要的计算开销(一层一层的走,不管它效果到底好不好)

Leaf-wise 则是一种更为高效的策略,每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环。因此同 Level-wise 相比,在分裂次数相同的情况下,Leaf-wise 可以降低更多的误差,得到更好的精度。Leaf-wise 的缺点是可能会长出比较深的决策树,产生过拟合。因此 LightGBM 在 Leaf-wise 之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合

Level-wise的做法会产生一些低信息增益的节点,浪费运算资源,但个对于防止过拟合挺有用。 而Leaf-wise能够追求更好的精度,降低误差,但是会带来过拟合问题。 那你可能问,那为啥还要用Leaf-wise呢? 过拟合这个问题挺严重鸭! 但是人家能提高精度啊,作者也使用了max_depth来控制树的高度。 其实敢用Leaf-wise还有一个原因就是Lightgbm在做数据合并,直方图和GOSS等各个操作的时候,其实都有天然正则化的作用,所以作者感觉在这里使用Leaf-wise追求高精度是一个不错的选择

LightGBM的工程优化

支持类别特征
  • LightGBM是第一个直接支持类别特征的GBDT工具。我们知道大多数机器学习工具都无法直接支持类别特征,一般需要把类别特征,通过one-hot 编码,转化到多维的0/1特征,降低了空间和时间的效率。但对于决策树来说,其实并不推荐使用独热编码,尤其是特征中类别很多,会存在以下问题:

    • 产生样本切分不平衡问题,切分增益会非常小。如,国籍切分后,会产生是否中国,是否美国等一系列特征,这一系列特征上只有少量样本为 1,大量样本为 0。这种划分的增益非常小:较小的那个拆分样本集,它占总样本的比例太小。无论增益多大,乘以该比例之后几乎可以忽略;较大的那个拆分样本集,它几乎就是原始的样本集,增益几乎为零;
    • 影响决策树学习:决策树依赖的是数据的统计信息,而独热码编码会把数据切分到零散的小空间上。在这些零散的小空间上统计信息不准确的,学习效果变差。本质是因为独热码编码之后的特征的表达能力较差的,特征的预测能力被人为的拆分成多份,每一份与其他特征竞争最优划分点都失败,最终该特征得到的重要性会比实际值低。
  • 对于类别型的特征,传统的机器学习模型是需要先利用one-hot编码,而在LightGBM中只需要提前将类别映射到非负整数即可(integer-encoded categorical features),例如,进行如下编码mapping{'特朗普': 1, '傻蛋': 2, '其他': 0},在官方文档中也建议使用从0开始的连续的数值进行编码,当训练集中的某个类别型的特征取值个数超大,可以将其看做是连续特征看待,或者进行embedding编码。

    • 关于LightGBM的类别型编码,经常和one-hot编码相比,one-hot编码是一种one-vs-other来划分数据,如假设某个类别型特征 $x_n$ 的取值只有[A, B ,C, D], 那么在节点分裂时一共有4种分法,每次分裂的时候,依次进行遍历,当取值为A时,计算增益,取值为B时,计算增益…在LightGBM中,利用参数max_cat_to_onehot来设定是否开启one-hot编码,当训练集中的某个类别特征取值个数小于等于4时,默认利用one-hot对类别特征编码。
    • 与之相对的编码方式就是 many-vs-many, 还是以上述特征为例,分裂时的判断条件可能为:$ x_n$ 取值为A或者B,取值为A或者C,差异如下:
      • one-vs-other: A|[B, C, D], B|[A, C, D], C|[A, B, D], D|[A, B, C]
      • many-vs-many: [A, C] | [B, D], [A, B, C] | [D] , …;

    通过比较发现,onehot编码需要更深的不平衡(一个取值上样本太少)的树才能得到很好的结果,而many-vs-many在一次分裂时可以结合多个取值,树的深度将减少

  • 在LighGBM中是如何实现many-vs-many的呢,以一个类别特征为例:

    • 统计该特征中的各取值上的样本数,按照从样本数从大到小排序,去除样本占比小于1%的类别值(所以大家遇到特别稀疏的特征时,最好先进行尾部取值合并,要不然会被算法自动抹去);
    • 对于剩余的特征值(可以理解为一个特征值对应一个桶),统计各个特征值对应的样本的一阶梯度之和,二阶梯度之和,根据正则化系数,算得各个桶的统计量: 一阶梯度之和 / (二阶梯度之和 + 正则化系数)
    • 根据该统计量对各个桶进行从大到小排序;
    • 在排序好的桶上,进行最佳切点查找,这一步就会得到上述many-vs-many的结果,而且通过参数max_cat_threshold, 默认一个组(包含多个特征取值,所以叫many)中最多可以存在32个不同的特征取值。而且,LightGBM中用了比较粗的粒度来解决查找,先从左到右,再从右到左,满足特征取值个数不超过max_cat_threshold, 增益最大即可(与连续特征一样的计算公式);
支持高效并行
  • 特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点,然后在机器间同步最优的分割点。XGBoost使用的就是这种特征并行方法。这种特征并行方法有个很大的缺点:就是对数据进行垂直划分,每台机器所含数据不同,然后使用不同机器找到不同特征的最优分裂点,划分结果需要通过通信告知每台机器,增加了额外的复杂度。
  • LightGBM 则不进行数据垂直划分,而是在每台机器上保存全部训练数据,在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

调参

  • 首先选择较高的学习率,大概0.1附近,这样是为了加快收敛的速度。这对于调参是很有必要的。
  • 对决策树基本参数调参
  • 正则化参数调参
  • 最后降低学习率,这里是为了最后提高准确率

问题

  • id类的特征,怎么处理放进lgb合适?调用接口转成数值型的类别特征,类别例如:1,2,3等
    • 有区分度就行
    • 如果你的id是有其他含义的,比如id越短越有钱,相似的id代表两人相似之类的;那最好用能保留原始信息的映射
    • 如果你这个特征特别强,直接放进去最好
  • 连续的统计特征,类似:gid_download_times 某游戏总共的下载次数,这种特征看网上直接放进去也可,做个离散化分桶也可,所以哪种更合适呢?
    • 最好是分桶吧,有利于引入非线性
      • 按热度分几个桶?
-------------The End-------------
谢谢大锅请我喝杯阔乐~