LightGBM 直方图优化算法

给出下面这个广泛使用 直方图优化算法的ppt，本文是对该张ppt的解释。

直方图优化算法需要在训练前预先把特征值转化为bin，也就是对每个特征的取值做个分段函数，将所有样本在该特征上的取值划分到某一段（bin）中。最终把特征取值从连续值转化成了离散值。

下面是训练过程中利用直方图寻找最佳分割点的算法。（不需要像预排序一样，把特征的所有取值进行排序）

     首先，对于当前模型的每个叶子节点，需要遍历所有的特征，来找到增益最大的特征及其划分值，以此来分裂该叶子节点。

    然后，（在第二个for循环中）

1. 对于每个特征，首先为其创建一个直方图，这个直方图存储了两类信息，分别是每个bin中样本的梯度之和（），还有就是每个bin中样本数量（）；
2. 然后，遍历所有样本，累积上述的两类统计值到样本所属的bin中；
3. 接着，遍历所有bin，分别以当前bin作为分割点，累加其左边的bin至当前bin的梯度和（SL）以及样本数量（nL），并与父节点上的总梯度和（Sp）以及总样本数量（np）相减，得到右边所有bin的梯度和（SR）以及样本数量（nR），带入公式，计算出增益，在遍历过程中取最大的增益，以此时的特征和bin的特征值作为分裂节点的特征和分裂特征取值。

上面第三步中涉及到了lightgbm的一个优化——Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM 可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。 

    下面是整理的直方图算法的优缺点（对比pre-sorted预排序）。

优点：

1.  首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的1/8。  
2.  然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#样本数*#特征数)优化到O(k*#特征数)。  

缺点：

1. 预处理能够忽略零值特征，减少训练代价；而直方图不能对稀疏进行优化，只是计算累加值（累加梯度和样本数）。但是，LightGBM对稀疏进行了优化：只用非零特征构建直方图。

最后一点是比较关键的一点，LightGBM为何使用直方图这种比较粗的分割节点方法，还能达到比较好的效果？

    虽然分割的精度变差了，但是对最后结果的影响不是很大，主要由于决策树是弱模型， 分割点是不是精确并不是太重要 ；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。