boosting系列之LightGBM算法详解

LightGBM简介

LightGBM是由微软团队基于xgboost的缺点新的实现,主要思想还是基于GBDT算法,在细节上进行了优化,在效率和精度方面都超过了xgboost的实现。并且支持分布式并行,包括特征并行,数据并行以及GPU并行计算。下面就对该算法的原理和细节进行详细说明。

LightGBM主要针对xgboostgbdt中特征分裂进行了优化,xgb和其他gbdt的实现中都采用了pre-sort,这种方式对内存消耗和训练速度上效率都非常低,还有另外一种实现就是通过直方图算法(histogram-based algorithm)因此,LightGBM采用histogram算法来对每个特征的分裂进行优化。

另外,为了减小训练数据集,一般是通过下采用,或者通过阈值的方式来过滤掉权重较小的数据。同样,可以通过过滤掉弱特征来减少特征量,从而在每次训练弱分类器的过程中提升模型的训练效率。但是GBDT中并没有样本权重的指标,下面就基于LightGBM论文中提出的点进行详细描述。

算法过程

主要对LigthGBM中的直方图算法,GOSS算法以及EFB进行详细的说明和算法过程描述,这三个点是该算法中最核心的优化和细节实现。并对这三个点的作用进行说明。

histogram算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数,同时构造一个宽度为k的直方图。在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。下面是histogram的过程:

1563269661109

从上面的直方图算法流程中可以看出,主要对特征进行离散化,转化为bin value。通过分段函数将特征取值划分到某个bin中。上面的流程中,第二个for循环开始,是遍历node集合,即创建的每个树模型;第三个for循环开始遍历所有的特征(m个特征),为每个特征创建一个Histogram对象;在第四个for循环开始遍历所有的样本,来构建直方图,在这里主要做了2个操作,一个是统计每个bin下样本的个数,不断更新每个bin下的样本数,另外一个操作就是不断更新每个bin下梯度和,计算每个bin中样本的梯度和。后面开始基于bin来找最佳分裂。

Gradient-based One-Side Sampling (GOSS)

AdaBoost中,样本权重是数据样本的重要性指标,但是在GBDT中并没有样本权重,不能通过权重来对样本进行采样。不过在GBDT中存在每个数据不同的梯度值,而这个信息对采用非常有用,即实例的梯度小,实例训练误差也就较小,已经被学习得很好了,直接想法就是丢掉这部分梯度小的数据,但是直接这样做会导致数据的分布被改变,从而影响训练模型的精度,而GOSS即是解决该问题而提出。

GOSS简单的描述就是保留梯度较大的样本,在梯度较小的实例上进行随机采样。为了抵消对数据分布的影响,计算信息增益的时候,GOSS对小梯度的数据引入常量乘数。GOSS首先根据数据的梯度绝对值排序,选取top a个实例。然后在剩余的数据中随机采样b个实例。在计算信息增益时为采样出的小梯度样本乘以$\frac {1-a} {b}$的权重,这样在训练过程中模型会更关注训练不足的实例,而不会过多改变原数据集的分布。具体过程如下:

1563331674809

在迭代(每个迭代就是一个弱分类器)的过程中,使用模型预测训练集的目标值,再计算Loss的梯度值,并更新每个样本的梯度g和每个样本的权重w,再对所有样本的梯度值进行排序,选取梯度值大的TOP N。在剩下的样本中在随机抽取TOP N个样本,组合为新的训练集。并再来更新新的样本权重(小梯度样本乘以frac),再训练模型。

Exclusive Feature Bundling (EFB)

上面的GOSS主要是减少样本数量来提升效率。而EFB主要可以理解为互斥特征绑定,即减少特征的数量,从而来提升训练效率。一般在建模过程中,高纬度的数据是稀疏的,既然是稀疏的,那么能通过一种方式来减少特征维度么?在高维和稀疏的特征空间中,很多特征是互斥的,即不同时为非0值。那么,就提出了一种将互斥特征进行绑定为一个单一的特征,来减少特征维度。微软研究团队设计了一种将互斥特征捆绑后的特征构建与单个特征相同的直方图,这样构建直方图的复杂度从O(#data*#feature)变为O(#data*#bundle),这样提升了效率,而不降低模型精度。但是在这个过程中,存在2个关键的问题:

  1. 如何判断哪些特征应该绑定在一起呢?(上面时候进行绑定)
  2. 怎么将特征绑定在一起呢?(如何绑定)

特征绑定(bundle)

LightGBM算法中采用了”图着色”一类问题进行解决,首先创建一个图G(v, e),其中v就是特征,为图中的节点,e为G中的边,将不是相互独立的特征用一条边连接起来,边的权重就是两个相连接的特征的总冲突值,这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点(特征)。具体算法过程如下:

1563334789846

特征合并(merging feature)

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

1563335082001

参考指南

  1. LightGBM中文文档
  2. 官方论文地址
  3. LightGBM原理-LightGBM: A Highly Efficient Gradient Boosting Decision Tree
  4. Lightgbm源论文解析:LightGBM: A Highly Efficient Gradient Boosting Decision Tree
  5. LightGBM模型中的改进细节
  6. Lightgbm 直方图优化算法深入理解
  7. LightGbm之直方图优化理解