引言
GBDT已经有了比较成熟的应用，例如XGBoost和pGBRT，但是在特征维度很高数据量很大的时候依然不够快。一个主要的原因是，对于每个特征，他们都需要遍历每一条数据，对每一个可能的分割点去计算信息增益。为了解决这个问题，本文提出了两个新技术：Gradient-based One-Side Sampling(GOSS)和Exclusive Feature Bundling(EFB)。
Histogram-based Algorithm
基于直方图的方法比基于预排序的方式要更加高效,这里对这个算法做一个简单的描述.算法的概要图如下所示:
直方图优化算法需要在训练前预先把特征值转化为bin value，也就是对每个特征的取值做个分段函数，将所有样本在该特征上的取值划分到某一段（bin）中,最终把特征取值从连续值转化成了离散值.直观的示例如下所示:
使用直方图算法有很多优点。首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值.然后在计算上的代价也大幅降低，XGBoost预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k可以认为是常数,为分段的个数),这样计算的时间复杂度量可以从O(data x feature) 降低到O(k x feature)。
当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。
Gradient-based One-Side Sampling
简而言之，GOSS保留了梯度较大的数据(这里有个理论,一般梯度比较大的数据是没有太训练好的,梯度小的数据是训练的差不多的)，而从梯度较小的数据中随机抽样。为了补偿对数据分布的影响，在计算信息增益时，为梯度较小的数据引入一个常数.其在实现的过程中首先对梯度进行排序,然后选取其中top a×100%的实例,然后从剩下的实例中随机抽出b×100%,然后，在计算信息增益的时候，GOSS会将梯度小的那部分数据乘上$\frac{1-a}{b}$,起到一定程度弥补的作用.这样处理的话,在训练的过程中就可以把主要的时间放在没有太训练好的数据上了。算法流程图如下所示:
Exclusive Feature Bundling
EFB主要的作用是减少特征的数量.高维度的数据通常是非常稀疏的，特征空间的稀疏性让我们可以设计一个几乎无损的方法去减少特征的数量。具体来说，在稀疏的特征空间中，许多特征是互斥的，它们从来不会同时取非零值。所以我们可以安全地将互斥特征捆绑到一个特征中（我们称之为exclusive feature bundle）。通过仔细地设计特征扫描算法，我们可以像独立特征一样给feat bundles建立feature histograms。这样做之后，histogram building的算法复杂度从O(data $\times$ feature)变为O(data $\times$ bundle), bundle << feature。这样，我们就可以在不降低acc的情况下显著地提高GBDT的训练速度.EFB主要有两个步骤,第一步是尽可能的将不怎么冲突的特征整合成一束;第二步是通过合并同一束中的特征来达到降低训练的时间复杂度的目的.
(1) 首先构建一个带权的图,边的权重指的是对应两个节点元素的冲突值(合并需要的代价),然后按照度降序的方式对特征进行排序.接着按照顺序遍历排序好的特征,对特征进行分配:要么在一个已经存在的feature bundle中,要么new一个feature bundle且该特征作为新feature bundle的第一个元素,算法流程如下所示:
(2) 这一步的关键要解决的问题是确保可以从合并之后的特征束中识别原始特征的值.使用基于直方图的的算法存储的是离散的值而不是连续的值,我们可以让独占特征驻留在不同的区间中来构建新的约束特征.可以通过添加offset的方式来实现这个想法.例如,我们有两个特征A以及B,特征A从[0,10]取值,B从[0,20]中取值,可以让B在原始取值的基础上加上一个10的偏移量,使得B从[10,30]中获取值.这样处理之后可以保证,A以及B合并的安全性.详细的流程如下所示:
扩展阅读:
(1) LightGBM的直方图做差加速
一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM可以在构造一个叶子的直方图后（父节点在上一轮就已经计算出来了），可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
(2) 带深度限制的Leaf-wise的叶子生长策略
Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
(3) 直接支持类别特征（即不需要做one-hot编码）
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化到多维的one-hot编码特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的one-hot编码展开。并在决策树算法上增加了类别特征的决策规则。在Expo数据集上的实验，相比0/1展开的方法，训练速度可以加速8倍，并且精度一致。
引用：
[1] https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf
[2] https://www.cnblogs.com/jiangxinyang/p/9337094.html
[3] https://www.jianshu.com/p/0d32a8bfa511
[4] https://blog.csdn.net/anshuai_aw1/article/details/83040541