AI面试扩展之LightGBM = GOSS + histogram + EFB

“学习的同时记录，记录的同时分享，分享的同时交流，交流的同时学习。”

之前一直在用LightGBM模型，但是它的原理并不是非常的了解，与之前讲过的XGB的区别也不甚清楚，所以今日一鼓作气，好好整明白这个运行的原理。总的来说，XGB和LGB都是GBDT的优化。

AI面试题之XGBoost与手推二阶导

AI面试题之GBDT梯度提升树

从图中也可以看到，2014年提出的XGB,三年后提出了LGB，是一个更好更新的模型。

其实在上面的讲解GBDT的博客中提到了：GBDT中寻找分隔点分割特征是使用穷举法。穷举所有可能的情况然后比较哪一个最好。所以可以看的出来GBDT和XGBoost（这个也是类似的，不过后来支持了一种比穷举法更好的方法直方图法）这两个Boosting算法是针对小规模小维度的数据集的。

穷举法固然可以找到最优的分割点，但是对于现在动不动就几千万的数据集来说，难免过于消耗时间，所以LightGBM就是针对这种穷举耗费时间的问题作出了改善。

【LGB与XGB的区别】

1. GOSS：基于梯度的单边采样；
2. EFB：互斥特征捆绑。
3. histogram：直方图算法(后来XGB也支持了)
4. leaf-wise vs depth-wise
5. 不再one-hot

1. GOSS

• Gradient-based One-Side Sampling，基于梯度的单边采样。简单的说，因为数据太多了，所以从大量数据中采样出一些与原来数据分布、本质相同的数据，这样大数据变成小数据，可以提高速度，因为分布相同，所以精度减少的不会多。

先讲一下这个GOSS的流程吧，先上伪代码：

可以看到，流程就是：

1. 先根据模型计算出一个预测值preds；
2. 计算这个preds和真实值的损失，可能是均方误差或者是其他的，这个损失计算出来；
3. 然后对这个损失进行排序，这里需要注意的是，这个损失是一个数组，每一个样本的预测值和真实值都会有一个损失，并不是像是神经网络中的一个batch损失一样把多个样本的损失加和。假设有100个样本，那么就会有100个损失，对这个100个损失进行排序，排序后的数组叫做sorted；
4. 选取sorted中前面topN个样本，就是选取100个样本中预测效果最差的topN个样本，叫做大梯度数据（large gradient data）
5. 然后随机从剩下的预测比较准确的样本（小梯度数据）中选取一些，选取比率就是上面图片中提到的b。假设有100个样本，a为0.2，b为0.3，那么就会让损失最大的20个样本作为大梯度数据，然后在剩下的80个样本中随机选取30个样本作为小梯度数据；
6. 将小梯度的样本乘上一个权重系数（1-a）/b，
7. 然后用选出取来的大梯度数据和小梯度数据，还有这个权重，来训练一个新的弱学习器。
8. 最后把这个弱学习器加到models里面；然后再来一遍整个流程。这里可以看到，在第一步中 根据模型 得到预测值的这个模型，就是models，其实是当前已经训练的所有弱分类器共同得到的一个预测值。

扩展知识就是，当a=0时候，那么其实就只会采样出小梯度样本，其实就是从全部样本中进行比率b的随机采样，所以a=0的时候，GOSS算法就会退化成随机采样算法；而a=1的时候，GOSS算法就会变成用全部数据进行训练的算法。

总之，GOSS算法就是一个很简单的过程，既然数据太多，耗费时间太多，那么我就会少量数据来训练，但是我选取数据非常有技巧，我选取的数据训练出来的效果好。

2. 直方图算法

• Histogram optimization 之前提到的GBDT找分割的特征和阈值就是穷举，这个肯定非常的耗费时间，所以LightGBM使用Histogram optimization来寻找次优解的分割特征和阈值。

整个流程就是，要把数据的某一个特征转化成一个直方图，然后再直方图中的某一个bin作为分隔点，计算loss。

其实也是要穷举所有的特征，但是并不会穷举样本中该特征的所有可能的值作为分割点，而是将样本离散化成直方图，然后用直方图的bin作为分割点。假如总共有100个样本，在考虑特征A的时候，可能分割成10个bin，这样这个特征A就只会有10个分割点的可能性。

下面看运算的流程：

1. 首先是给每一个特征都会做一个直方图，每一个直方图都是由多个bin组成的，第一个bin可能是0-5，第二个bin是5-10……
2. 先遍历一遍所有的样本，然后把每一个样本分到对应的bin中，计算每一个bin中包含的样本数量，以及bin中所有样本的梯度和（梯度可以看成预测效果，梯度越大预测越差，距离真实值越远）
3. 然后遍历所有的bin作为分割点，计算这个分割点的loss（也可以理解为增益）。不难想象，一个分割bin会把整个直方图分成两部分，分割bin左边的bins和右边的bins。

这里要理解一下，分割bin会把一个直方图分成左右两部分，然后每一个部分又会找某一个特征的分割bin，形成一个树状的结构。

这里呢？可以发现一个等式：

所以，只用计算

就可以根据父辈节点的信息快速得到

,这样计算的就更快了。

相比：传统的方法，就是pre-sorted方法，优势在哪里呢？

1. 传统的方法排序的是连续值，而histogram是将连续值离散化，所以离散数据可以用更小的内存来存储。比方说，连续数据可能是4.234252131，但是改成离散值可能就是4.2;
2. 传统方法，需要计算多少次增益呢？特征值乘上样本数量。现在histogram只需要计算特征值乘上直方图bin的数量，一般会设置为一个常数。

可以看出来，histogram其实就是一个连续值离散化的方法。这也会让分割的精度下降，但是决策树本来就是一个弱分类器，所以精度下降的并不多，也能起到一定的防止过拟合的作用。

Histogram直方图法后来XGB也支持使用了，所以目前来说LGB和XGB都可以用这个方法。

3. EFB

• Exclusive Feature Bundling 互斥特征捆绑 LightGBM通过GOSS算法可以进行数据采样，他还可以进行特征抽样，让数据的规模进一步的减小。

思想很简单：就是在高纬度空间中数据，是使用稀疏编码的，比如one-hot，这样，在稀疏特征空间中，很少同时出现非0值。这样，就两个特征就可以安全的绑定在一起形成一个新的特征。

这个流程图就是在寻找哪两个特征可以捆绑。这里我在学习的时候产生了一个疑问，目前还没有解决，所以关于EFB就只能给出自己的看法和理解：

1. 直观理解就是因为对特征进行稀疏编码，所以两个特征同时是1的概率就会比较小，两个特征同时是非零值则认为发生冲突。如果冲突率较低，则两个特征可以绑定成一个特征。通过特征绑定，从而实现降低特征维度，从而提速。
2. 如何合并特征：一般都会给出这样的例子：

4 leaf-wise

lightGBM的树生长的过程也和xgboost不一样。xgboost的生长是level-wise的，即一层一层生长的，而lightgbm是leaf-wise即梯度优先的。如下图所示，即使左子树已经比右子树深很多，但只要左子树的梯度划分仍然比右子树占优，就继续在左子树进行划分。

从图中可以看到，depth-wise生长策略是决策树是否分裂到下一层，是每一个叶子节点都分类。leaf-wise是仅仅考虑某一个叶子是否继续分裂。

5 不再one-hot

这个是LGB首次提出来的。对于类别变量，XGB采用的方法就是常见的one-hot编码。但是LGB有着它自己独特的处理方案：

文中主要再说，one-hot不是一个好的解决方法，因为对于极多种类的类别特征，one-hot非常用以导致过拟合，也就是导致不平衡树。

【这一点个人理解是因为LGB采用的leaf-wise的方法，所以如果使用one-hot编码，那么就容易产生左右子树极度不平衡的情况，从而极易过拟合】

划分分类变量的基本思想就是将分类变量划分成两个类别,这样就会产生

个类别。比方说，有三类“a,b,c”，那么就会产生

个不同分类：“a|b,c”,“b|a,c”,“c|b,a”。

但是这样可能的划分太多了，所以LGB重新排序的类别，用

（类别对应的label的和与对应的label的数量的比值）来作为排序的指标，然后从小到大排序，然后就像按照连续变量的直方图方法划分一样，对其进行划分。比方说排序之后得到这样的顺序:“a,b,c”,那么就有两种分类方法“a|b,c”和“a,b|c”

相比one-hot方法，精度不减，但是速度提高了8倍（这是在一个数据集上的结果，具体可能有出入）。

- END -

喜欢的话，长按下面的二维码关注下【机器学习炼丹术】，成为炫酷的炼丹师吧！

目前在更：每天一两个AI面试干货知识点。