深入理解LightGBM

在Adaboost中通过分配给样本不同的权重从而体现出样本的重要性，但是在GBDT中没有依赖样本的权重进行模型的学习，无法做到根据样本的重要性进行样本的采样。但是，我们发现在GBDT模型的学习过程中，每个样本的梯度信息提供了有用的信息，梯度越大的样本点对减少损失更有帮助。因此，Light GBM在每一次迭代前，利用了GBDT中的每个样本梯度大小对训练样本进行采样。

• 首先GOSS方法依靠样本梯度的绝对值对样本进行从大到小排序；

• 然后根据阈值选择top a*100% 大梯度样本；

• 接着，针对剩下的小梯度样本随机采样top b*100%个，同时针对小梯度样本给予一个(1 - a) / b的常值权重。

• 这么采样出来的数据，既不损失梯度大的样本，又在减少训练数据的同时不改变数据的分布，从而实现了在几乎不影响精度的情况下加速了训练。

2. Exclusive Feature Bundling (EFB)

在特征维度很大的数据上，特征空间一般是稀疏的。利用这个算法，我们可以无损地降低GBDT算法中需要遍历的特征数量，更确切地说，是降低构造特征直方图（训练GBDT的主要时间消耗）需要遍历的特征数量。

EFB中文名叫独立特征合并，顾名思义它就是将若干个特征合并在一起。使用这个算法的原因是因为我们要解决数据稀疏的问题。在很多时候，数据通常都是几千万维的稀疏数据。因此我们对不同维度的数据合并一齐使得一个稀疏矩阵变成一个稠密矩阵。这里就有两个问题：

1. 如何确定哪些特征用于融合且效果为较好；

2. 如何将这些特征合并到一齐；

1）对于第一个问题，这是一个NP-hard问题。我们把feature看作是图中的点（V），feature之间的总冲突看作是图中的边（E）。而寻找寻找合并特征且使得合并的bundles个数最小，这是一个图着色问题。所以这个找出合并的特征且使得bundles个数最小的问题需要使用近似的贪心算法Algorithm3来完成。 它将问题一换成图着色算法去解决。

Algorithm3：

• 首先构建一个以feature为图中的点（V），以feature之间的总冲突为图中的边（E）这里说的冲突值应该是feature之间cos夹角值，因为我们是尽可能保证feature之间非0元素不在同一个row上；

• 然后按照度来对每个点（feature）做降序排序（度数越大与其他点的冲突越大）；

• 最后将特征合并到冲突数小于K的bundle或者新建另外一个bundle。算法的时间复杂度为O(#feature2)。

2）第二问题是将这些bundles中的特征合并起来Algorithm4。由于每一个bundle当中，features的range都是不一样，所以我们需要重新构建合并后bundle feature的range。在第一个for循环当中，我们记录每个feature与之前features累积totalRange。在第二个for循环当中，根据之前的binRanges重新计算出新的bin value（F[j]bin[i] + binRanges[j]）保证feature之间的值不会冲突。这是针对于稀疏矩阵进行优化。由于之前Greedy Bundling算法对features进行冲突检查确保bundle内特征冲突尽可能少，所以特征之间的非零元素不会有太多的冲突。如此一来，数据的shape就变成了#samples * #bundles，且#bundles << #features。EFB降低了数据特征规模提高了模型的训练速度。

3. 直方图算法

• Reduced cost of calculating the gain for each split

  • Pre-sort-based algorithms have time complexity O(#data)

  • Computing the histogram has time complexity O(#data), but this involves only a fast sum-up operation. Once the histogram is constructed, a histogram-based algorithm has time complexity O(#bins), and #bins is far smaller than #data.

• Use histogram subtraction for further speedup

  • To get one leaf’s histograms in a binary tree, use the histogram subtraction of its parent and its neighbor

  • So it needs to construct histograms for only one leaf (with smaller #data than its neighbor). It then can get histograms of its neighbor by histogram subtraction with small cost (O(#bins))

• Reduce memory usage

  • Replaces continuous values with discrete bins. If #bins is small, can use small data type, e.g. uint8_t, to store training data

  • No need to store additional information for pre-sorting feature values

• Reduce communication cost for parallel learning

把连续的浮点特征值离散化为K个整数，同时构造一个宽度为K的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

好处：

1. 减少了内存占用，比如离散为256bin时，只需要8bit；

2. 减少了split finding时计算增益的计算量，从O(#data)降到了O(#bins)

3. 直方图差加速

 一个叶子节点的直方图可以由它的父节点的直方图与它的兄弟结点的直方图做差得到，提升了一倍的速度。

直方图寻找分割点的算法：

1. 对于每个特征 f 首先建立一个直方图；

2. 遍历所有样本统计每个样本，累积bin[i]的梯度，以及bin[i]的样本数；

3. 对直方图的每个bin进行划分，计算左边的梯度值，和样本数，根据父节点的直方图做差获得由节点的梯度值和样本数，计算loss损失；

4. 基于叶子节点的生长

5. 并行优化