LightGBM
上文中我们了解了一下XGBoost的原理，本文再来了解一下GBDT的另一个进化算法LightGBM，从原理上来说它和GBDT及XGBoost类似，都采用损失函数的负梯度作为当前决策树的残差近似值，去拟合新的决策树。
不了解LightGBM的人可能会有疑问，XGBoost已经在各大场景有很好的表现了，为什么还要用LightGBM呢？我们先来看一下LightGBM相对于XGBoost的优点，再来决定要不要了解一下这个算法。
LightGBM相对于XGBoost的优点：
- 更快的训练效率
- 低内存使用
- 更高的准确率
- 支持并行化学习
- 可以处理大规模数据
- 可以直接使用类别特征
WTF？这不就是传说中的更高、更快、更强吗，下面就让我们来看一下LightGBM究竟是怎么做的。
LightGBM的特点
- 基于Histogram的决策树算法
- 带深度限制的Leaf-wise的叶子生长策略
- 直方图做差加速
- 直接使用类别特征
- Cache命中率优化
- 基于直方图的稀疏特征优化
- 多线程优化
决策树算法
为了展示出LightGBM相对于XGBoost的优点，我们先给出XGBoost所使用的预排序算法，再和LightGBM所使用的算法来进行对比。
XGBoost
- 对所有的特征按照数值进行预排序；
- 找到最优的分割点，进行样本分割（假设数据量为n，则此过程消耗时间为O(n)）;
- 找到分割点，根据分割特征将数据分为左右两个子结点。
这个寻找特征的方式看上去没有什么问题，但是我们再深入去思考的话就会发现，当我们对所有的特征进行排序的时候，为了后续快速的计算分类点，我们不仅要保留特征还需要保留排序后的索引值，这也就意味着我们需要使用双倍的内存开销来保存这些东。同样在我们计算最优分割点的时候，需要从头遍历到尾，每一次都要进行增益的计算，时间和计算的开销也是巨大的。
由于XGBoost存在的这些不足，LightGBM考虑新的方法来进行最优分割点的寻找，让我们来了解一下。
LightGBM
LightGBM中使用的是直方图算法(histogram algorithm)，该算法所占用的内存更小，寻找分割点的复杂度也更低。其思想是将连续的浮点特征离散成k个离散值，并构造出一个宽度为k的直方图，然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
这么叙述起来显得比较抽象，也不利于理解，我们从下面的图出发，细致的来说明一下这个问题：
直方图算法的原理很简单，首先要做的就是把浮点型数据转化为bin数据（图中灰色到红色的过程），我们首先要确定对于每一个特征需要多少个桶（分割为多少个数据范围），然后均分，将属于该桶的样本数据更新为bin的值，最后用直方图来表示数据。这里所表达的意思就类似于上图中的Eg，如果数据属于[0,0.1)这个桶，就把数据的值更新为0。
直方图算法有几个我们需要注意的点：
- 使用bin替代原始数据相当于增加了正则化；
- 使用bin意味着很多数据的细节特征被放弃了，相似的数据可能被分到相同的桶中，这样数据之间的差异也就随之消失了；
- bin数量选择决定了正则化的程度，bin越少惩罚越严重，欠拟合的风险也就越高；
- 构建直方图的时候不需要对数据进行排序（比XGB的时间消耗少）；
- 直方图除了保存划分阈值和当前bin内样本数以外，还保存了当前bin内所有样本的一阶梯度和（一阶梯度和的平方的均值等价于均方损失）；
- 阈值的选取是按照直方图从小到大遍历，使用了上面的一阶梯度和，目的是得到划分之后△loss最大的特征及阈值。
Histogram 算法的优缺点：
- 由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
- 时间上的开销由原来的O ( d a t a ∗ f e a t u r e s ) O(data * features)O(data∗features)降到O ( k ∗ f e a t u r e s ) O(k * features)O(k∗features)。由于离散化，k远小于data，因此时间上有很大的提升。
Histogram加速：
一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅。速度提升了一倍。
决策树的生长策略
XGBoost采用的是按层生长level（depth）-wise生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
LightGBM采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
LightGBM原理
明白了LightGBM中树的生成，再让我们来了解一下LightGBM的原理，LightGBM主要包含GOSS和EFB算法，让我们来了解一下：
单边梯度采样（GOSS）
主要思想
GOSS算法的主要思想就在于梯度的大小对于信息增益的贡献上的差别，梯度大的样本点在信息增益的计算上扮演主要的作用，也就是说梯度大的样本点会贡献更多的信息增益，为了保持信息增益评估的精度，当我们对样本进行下采样的时候保留这些梯度大的样本点，而对于梯度小的样本点按比例进行随机采样即可。我们证明此措施在相同的采样率下比随机采样获得更准确的结果，尤其是在信息增益范围较大时。
算法描述
在AdaBoost算法中，我们在每次迭代时更加注重上一次错分的样本点，也就是上一次错分的样本点的权重增大，而在GBDT中并没有本地的权重来实现这样的过程，所以在AdaBoost中提出的采样模型不能应用在GBDT中。但是，每个样本的梯度对采样提供了非常有用的信息。也就是说，如果一个样本点的梯度小，那么该样本点的训练误差就小并且已经经过了很好的训练。一个直接的办法就是直接抛弃梯度小的样本点，但是这样做的话会改变数据的分布和损失学习的模型精度。GOSS的提出就是为了避免这两个问题的发生。我们来看一下对于GOSS的算法描述：
输入：训练数据，迭代步数d，大梯度数据的采样率a，小梯度数据的采样率b，损失函数和弱学习器的类型（一般为决策树）；
输出：训练好的强学习器；
- 根据样本点的梯度的绝对值对它们进行降序排序；
- 对排序后的结果选取前a*100%的样本生成一个大梯度样本点的子集；
- 对剩下的样本集合( 1 − a ) ∗ 100 (1-a)*100%(1−a)∗100的样本，随机的选取b ∗ ( 1 − a ) ∗ 100 b*(1-a)*100%b∗(1−a)∗100个样本点，生成一个小梯度样本点的集合；
- 将大梯度样本和采样的小梯度样本合并；
- 将小梯度样本乘上一个权重系数；
- 使用上述的采样的样本，学习一个新的弱学习器；
- 不断地重复（1）~（6）步骤直到达到规定的迭代次数或者收敛为止。
通过上面的算法可以在不改变数据分布的前提下不损失学习器精度的同时大大的减少模型学习的速率。
从上面的描述可知，当a=0时，GOSS算法退化为随机采样算法；当a=1时，GOSS算法变为采取整个样本的算法。在许多情况下，GOSS算法训练出的模型精确度要高于随机采样算法。另一方面，采样也将会增加弱学习器的多样性，从而潜在的提升了训练出的模型泛化能力。
GOSS算法的伪代码
互斥特征绑定（EFB）
主要思想
一个有高维特征空间的数据往往是稀疏的，而稀疏的特征空间中，许多特征是互斥的。所谓互斥就是他们从来不会同时具有非0值（一个典型的例子是进行One-hot编码后的类别特征）。
LightGBM利用这一点提出Exclusive Feature Bundling（EFB）算法来进行互斥特征的合并，从而减少特征的数目。做法是先确定哪些互斥的特征可以合并（可以合并的特征放在一起，称为bundle），然后将各个bundle合并为一个特征。(记住这里的bundle是什么)
这样建立直方图的时间将从O ( f e a t u r e ∗ d a t a ) O(feature*data)O(feature∗data)变为O ( b u n d l e ∗ d a t a ) O(bundle*data)O(bundle∗data)，而bundle<<feature，这样GBDT能在精度不损失的情况下进一步提高训练速度。
算法描述
- 将特征按照非零值的个数进行排序；
- 计算不同特征之间的冲突比率；
- 遍历每个特征并尝试合并特征，使冲突比率最小化。
根据这种思想，随之而来的是下面的两个问题：
- 怎么判定哪些特征应该绑定在一起？
- 怎么把特征绑定为一个？
哪些特征被绑定
由于将特征划分为更小的互斥绑定数量，这是一个NP-hard问题，即在多项式时间内不可能去找到准确的解决办法。所以这里使用的是一种近似的解决办法，即特征之间允许存在少数的样本点并不是互斥的（如存在某些对应的样本点之间不同时为非0值），允许小部分的冲突可以得到更小的特征绑定数量，更进一步的提高了计算的有效性。在理论上可以证明，通过允许小部分的冲突的话，使得模型的accuracy被影响
这里的是每个绑定的最大冲突率。所以，当我们选择很小的时，我们可以在精确度和效率上获得很好的权衡。
注意：这里构建图的方法是，图上的顶点代表特征，若两个特征不互斥，则在他们之间连一条边。
算法描述如下：
输入：特征F，最大冲突数K，图G；
输出：特征捆绑集合bundles；
- 建立一个图，每个边有权重，其权值对应于特征之间的总冲突。
- 按照降序排列图中的度数来排序特征。
- 按顺序对排好序的特征进行遍历，对于当前特征，查看是否能加入已有的bundle（冲突要小于k），若不行，则新建一个bundle。
建图的过程如下：
将每个特征视为图中的一个顶点。遍历每一个样本，如果在当前样本中特征i,j之间不互斥，则：
- 如果在图上i,j间不存在边，则连接一条边，权重为1；
- 如果存在边，权重加1。
算法的伪代码如下：
该算法的时间复杂度是O(feature^2) ,训练之前只处理一次，其时间复杂度在特征不是特别多的情况下是可以接受的，但难以应对百万维的特征。为了继续提高效率，我们提出了一个更加高效的无图的排序策略：将特征按照非零值个数排序，这和使用图节点的度排序相似，因为更多的非零值通常会导致冲突，新算法在该算法基础上改变了排序策略，我们再来看一下对该算法的优化。
合并互斥特征
Lightgbm关于互斥特征的合并用到了直方图（Histogram）算法。直方图算法的基本思想是先把连续的特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
由于基于直方图的算法存储的是离散的bins而不是连续的特征值，我们可以通过让互斥特征驻留在不同的bins中来构造feature bundle。这可以通过增加特征原始值的偏移量来实现。比如，假设我们有两个特征，特征A的取值范围是[0,10)，而特征B的取值范围是[0,20)，我们可以给特征B增加偏移量10，使得特征B的取值范围为[10, 30)，最后合并特征A和B，形成新的特征，取值范围为[0,30)来取代特征A和特征B。
当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；差一点的切分点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在Gradient Boosting的框架下没有太大的影响。
最终我们称使用GOSS算法和EFB算法的梯度提升树（GBDT）称之为LightGBM。
