lightgbm介绍

2020-07-16

lightgbm介绍

lightgbm由微软开发的boosting工具包，顾明思议light，这个包计算速度更快，占用内存更少，而准确度和xgboost相当，也是一大神器。接下来就介绍一下。

1. 直方图算法

1.1 创建直方图

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

如[0,0.3)—>0，[0.3,0.7)—->1. 对于分类特征来说，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。

在节点分裂的时候，这时候就不需要按照预排序算法那样，对于每个特征都计算#data遍了，而是只需要计算#bins遍，这样就大大加快了训练速度

lgb直方图

1.2 直方图做差加速

一个叶子的直方图可以由它的父亲节点的直方图与它兄弟节点的直方图做差得到，提升一倍速度在histogram算法上一个trick是histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。利用这个方法，Lightgbm 可以在构造一个叶子（含有较少数据）的直方图后，可以用非常微小的代价得到它兄弟叶子（含有较多数据）的直方图。histogram算法与 pre-sorted算法对比

lgb直方图做差

1.3 和pre-sorted相比

优势
1. Pre-sorted 算法需要的内存约是训练数据的两倍(2 * #data * #features* 4Bytes)，它需要用32位浮点(4Bytes)来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位(4Bytes)的存储空间。因此是(2 * #data * #features* 4Bytes)。而对于 histogram 算法，则只需要(#data * #features * 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 bin value 用 1Bytes(256 bins) 的大小一般也就足够了。
2. 计算上的优势则是大幅减少了计算分割点增益的次数。对于每一个特征，pre-sorted 需要对每一个不同特征值都计算一次分割增益，代价是O(#feature#distinct_values_of_the_feature)；而 histogram 只需要计算#bins次，代价是(#feature#bins)。
3. 还有一个很重要的点是cache-miss。事实上，cache-miss对速度的影响是特别大的。预排序中有2个操作频繁的地方会造成cache miss，一是对梯度的访问，在计算gain的时候需要利用梯度，不同特征访问梯度的顺序都是不一样的，且是随机的，因此这部分会造成严重的cache-miss。二是对于索引表的访问，预排序使用了一个行号到叶子节点号的索引表（row_idx_to_tree_node_idx ），来防止数据切分时对所有的数据进行切分，即只对该叶子节点上的样本切分。在与level-wise进行结合的时候，每一个叶子节点都要切分数据，这也是随机的访问。这样会带来严重的系统性能下降。而直方图算法则是天然的cache friendly。在直方图算法的第3个for循环的时候，就已经统计好了每个bin的梯度，因此，在计算gain的时候，只需要对bin进行访问，造成的cache-miss问题会小很多。
4. 最后，在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用 histogram 进行通信。
  （数据并行的优化是Lightgbm的令一个亮点，这里不是特别理解，需要再深入研究）
劣势
histogram 算法不能找到很精确的分割点，训练误差没有 pre-sorted 好。但从实验结果来看， histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果，再加上boosting算法本身就是弱分类器的集成。

2. 建树过程的两种方法：Level-wise和Leaf-wise

lgbt树分裂

3. Gradient-based One Side Sampling (GOSS)

在每一次迭代前，利用了GBDT中的样本梯度和误差的关系，对训练样本进行采样: 对误差大（梯度绝对值大）的数据保留；对误差小的数据采样一个子集，但给这个子集的数据一个权重，让这个子集可以近似到误差小的数据的全集。这么采样出来的数据，既不损失误差大的样本，又在减少训练数据的同时不改变数据的分布，从而实现了在几乎不影响精度的情况下加速了训练。

在AdaBoost中，权重向量w很好的反应了样本的重要性。而在GBDT中，则没有这样的直接权重来反应样本的重要程度。但是梯度是一个很好的指标，如果一个样本的梯度很小，说明该样本的训练误差很小，或者说该样本已经得到了很好的训练(well-trained)。

要减少样本数，一个直接的想法是抛弃那些梯度很小的样本，但是这样训练集的分布会被改变，可能会使得模型准确率下降。LightGBM提出 Gradient-based One-Side Sampling (GOSS)来解决这个问题。

根据梯度的绝对值将样本进行降序排序
选择前a×100%a×100%的样本，这些样本称为A
剩下的数据(1−a)×100%(1−a)×100% 的数据中，随机抽取b×100%b×100%的数据，这些样本称为B
在计算增益的时候，放大样本B中的梯度(1−a)/b(1−a)/b 倍
关于g，在具体的实现中是一阶梯度和二阶梯度的乘积，见Github的实现（ LightGBM/src/boosting/goss.hpp）

4. Exclusive Feature Bundling (EFB)

一个有高维特征空间的数据往往是稀疏的，而稀疏的特征空间中，许多特征是互斥的。所谓互斥就是他们从来不会同时具有非0值（一个典型的例子是进行One-hot编码后的类别特征）。

LightGBM利用这一点提出Exclusive Feature Bundling（EFB）算法来进行互斥特征的合并，从而减少特征的数目。做法是先确定哪些互斥的特征可以合并（可以合并的特征放在一起，称为bundle），然后将各个bundle合并为一个特征。

5.其他

LightGBM的特征并行。每个worker保存所有数据集

每个worker在其特征子集上寻找最佳切分点
worker之间互相通信，找到全局最佳切分点
每个worker根据全局最佳切分点进行节点分裂

优点：避免广播instance indices，减小网络通信量。

缺点： split finding计算复杂度没有减小，且当数据量比较大时，单个worker存储所有数据代价高。

参考资料：博客1：https://www.hrwhisper.me/machine-learning-lightgbm/

博客2：https://blog.csdn.net/anshuai_aw1/java/article/details/83040541

一个很详细的PPT http://wepon.me/files/gbdt.pdf