gbm
一、 前言
最近在做Kaggle比赛的时候，看到别人的Kenels中都用到了lightgbm，自己也试图用了一下，发现效果很好，最重要的是它相对于XGBoost算法，大大的降低了运行的速度。所以就对Lightgbm的原理探了个究竟，这里就对Lightgbm论文的理解以及对官网上对Lightgbm的介绍做一个学习笔记。
传统的boosting算法（如GBDT和XGBoost）已经有相当好的效率，但是在如今的大样本和高维度的环境下，传统的boosting似乎在效率和可扩展性上不能满足现在的需求了，主要的原因就是传统的boosting算法需要对每一个特征都要扫描所有的样本点来选择最好的切分点，这是非常的耗时。为了解决这种在大样本高纬度数据的环境下耗时的问题，Lightgbm使用了如下两种解决办法：一是GOSS（Gradient-based One-Side Sampling, 基于梯度的单边采样），不是使用所用的样本点来计算梯度，而是对样本进行采样来计算梯度；二是EFB（Exclusive Feature Bundling， 互斥特征捆绑） ，这里不是使用所有的特征来进行扫描获得最佳的切分点，而是将某些特征进行捆绑在一起来降低特征的维度，是寻找最佳切分点的消耗减少。这样大大的降低的处理样本的时间复杂度，但在精度上，通过大量的实验证明，在某些数据集上使用Lightgbm并不损失精度，甚至有时还会提升精度。下面就主要介绍这两种方法。
本文的主要内容，首先介绍GOSS和EFB方法，然后再根据Lightgbm官网的介绍，谈一谈Lightgbm的特性以及调参。
二、Gradient-based One-Side Sampling（GOSS）介绍
GOSS（基于梯度的单边采样）方法的主要思想就是，梯度大的样本点在信息增益的计算上扮演着主要的作用，也就是说这些梯度大的样本点会贡献更多的信息增益，因此为了保持信息增益评估的精度，当我们对样本进行下采样的时候保留这些梯度大的样本点，而对于梯度小的样本点按比例进行随机采样即可。
2.1 GOSS算法
在AdaBoost算法中，我们在每次迭代时更加注重上一次错分的样本点，也就是上一次错分的样本点的权重增大，而在GBDT中并没有本地的权重来实现这样的过程，所以在AdaBoost中提出的采样模型不能应用在GBDT中。但是，每个样本的梯度对采样提供了非常有用的信息。也就是说，如果一个样本点的梯度小，那么该样本点的训练误差就小并且已经经过了很好的训练。一个直接的办法就是直接抛弃梯度小的样本点，但是这样做的话会改变数据的分布和损失学习的模型精度。GOSS的提出就是为了避免这两个问题的发生。下面就是GOSS算法的伪代码：
下面将对上述算法进行描述。
2.2 GOSS算法描述
输入：训练数据，迭代步数d，大梯度数据的采样率a，小梯度数据的采样率b，损失函数和若学习器的类型（一般为决策树）；
输出：训练好的强学习器；
（1）根据样本点的梯度的绝对值对它们进行降序排序；
（2）对排序后的结果选取前a*100%的样本生成一个大梯度样本点的子集；
（3）对剩下的样本集合（1-a）*100%的样本，随机的选取b*（1-a）*100%个样本点，生成一个小梯度样本点的集合；
（4）将大梯度样本和采样的小梯度样本合并；
（5）将小梯度样本乘上一个权重系数
；
（6）使用上述的采样的样本，学习一个新的弱学习器；
（7）不断地重复（1）~（6）步骤直到达到规定的迭代次数或者收敛为止。
通过上面的算法可以在不改变数据分布的前提下不损失学习器精度的同时大大的减少模型学习的速率。
从上面的描述可知，当a=0时，GOSS算法退化为随机采样算法；当a=1时，GOSS算法变为采取整个样本的算法。在许多情况下，GOSS算法训练出的模型精确度要高于随机采样算法。另一方面，采样也将会增加若学习器的多样性，从而潜在的提升了训练出的模型泛化能力。
三、Exclusive Feature Bundling（EFB）介绍
Lightgbm实现中不仅进行了数据采样，也进行了特征抽样，使得模型的训练速度进一步的减少。但是该特征抽样又与一般的特征抽样有所不同，是将互斥特征绑定在一起从而减少特征维度。主要思想就是，通常在实际应用中高纬度的数据往往都是稀疏数据（如one-hot编码），这使我们有可能设计一种几乎无损的方法来减少有效特征的数量。尤其，在稀疏特征空间中许多特征都是互斥的（例如，很少同时出现非0值）。这就使我们可以安全的将互斥特征绑定在一起形成一个特征，从而减少特征维度。但是怎样的将互斥特征绑定在一起了？Lightgbm作者使用的是基于直方图（histograms）的方法。
3.1 EFB算法
由于将特征划分为更小的互斥绑定数量，这是一个NP-hard问题，即在多项式时间内不可能去找到准确的解决办法。所以这里使用的是一种近似的解决办法，即特征之间允许存在少数的样本点并不是互斥的（如存在某些对应的样本点之间不同时为非0值），允许小部分的冲突可以得到更小的特征绑定数量，更进一步的提高了计算的有效性。在理论上可以证明，通过允许小部分的冲突的话，使得模型的accuracy被影响，这里的是每个绑定的最大冲突率。所以，当我们选择很小的时，我们可以在精确度和效率上获得很好的权衡。下面就是互斥特征绑定（Exclusive Feature Bundling）的算法：
下面将对上述算法进行描述。
3.2 EFB算法描述
输入：特征F，最大冲突数K，图G；
输出：特征捆绑集合bundles；
（1）构造一个边带有权重的图，其权值对应于特征之间的总冲突；
（2）通过特征在图中的度来降序排序特征；
（3）检查有序列表中的每个特征，并将其分配给具有小冲突的现有bundling（由控制），或创建新bundling。
上述算法的时间复杂度为并且在模型训练之前仅仅被处理一次即可。在特征维度不是很大时，这样的复杂度是可以接受的。但是当样本维度较高时，这种方法就会特别的低效。所以对于此，作者又提出的另外一种更加高效的算法：按非零值计数排序，这类似于按度数排序，因为更多的非零值通常会导致更高的冲突概率。 这仅仅改变了上述算法的排序策略，所以只是针对上述算法将按度数排序改为按非0值数量排序，其他不变。
3.3 合并互斥特征
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的框架下没有太大的影响。
Histogram算法有如下的一些优点：
（1）减少分割增益的计算量：xgboost中默认使用的是pre-sorted算法，需要次的计算，而Histogram算法只需要计算次，并且远小于；
（2）通过直方图相减来进一步的加速模型的训练：在二叉树中可以通过利用叶节点的父节点和相邻节点的直方图的相减来获得该叶节点的直方图。所以仅仅需要为一个叶节点建立直方图 (其小于它的相邻节点)就可以通过直方图的相减来获得相邻节点的直方图，而这花费的代价（）很小。
（3）减少内存的使用：可以将连续的值替换为离散的bins。 如果较小, 可以利用较小的数据类型来存储训练数据并且无需为 pre-sorting 特征值存储额外的信息。
（4）减少并行学习的通信代价。
我们称使用GOSS算法和EFB算法的梯度提升树（GBDT）称之为LightGBM。
四、Lightgbm的一些其它特性
4.1 Leaf-wise的决策树生长策略
大部分决策树的学习算法通过 level-wise 策略生长树，记一次分裂同一层的叶子，不加区分的对待同一层的叶子，而实际上很多叶子的分裂增益较低没必要进行分裂，带来了没必要的开销。如下图：
LightGBM 通过 leaf-wise 策略来生长树。每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。但是，当样本量较小的时候，leaf-wise 可能会造成过拟合。 所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合。
4.2 类别特征值的最优分割
对于类别型的数据，我们通常将类别特征转化为one-hot/哑变量编码。 然而，对于学习树来说这不是个好的解决方案。 原因是，对于一个基数较大的类别特征，学习树会生长的非常不平衡，并且需要非常深的深度才能来达到较好的准确率。
事实上，最好的解决方案是将类别特征划分为两个子集，总共有种可能的切分。比如有一个颜色特征，每个样本的颜色特征是{红、黄、蓝、绿}四种类别中的一种，如果使用ne-hot/哑变量编码很好理解这里不再叙述，但是如果使用LightGBM的切分策略，就是将红、黄、蓝、绿对应的四类样本分为两类的所有可能策略，比如：红黄一类，蓝绿一类。那么就会有 种策略，这样才能充分的挖掘该维特征所包含的信息，找到最优的分割策略。 但是这样寻找最优分割策略的时间复杂度就会很大。对于回归树有个有效的解决方案。为了寻找最优的划分需要大约 。基本的思想是根据训练目标的相关性对类别进行重排序。 更具体的说，根据累加值()重新对（类别特征的）直方图进行排序，然后在排好序的直方图中寻找最好的分割点。
4.3 Lightgbm中的并行学习
4.3.1 特征并行
1、传统算法的的特征并行
传统的特征并行算法旨在于在并行化决策树中的寻找最佳切分点，主要流程如下：
（1）垂直切分数据（不同的Worker有不同的特征集）；
（2）在本地特征集寻找最佳切分点 {特征, 阈值}；
（3）在各个机器之间进行通信，拿出自己的最佳切分点，然后从所有的最佳切分点中推举出一个最好的切分点，作为全局的切分点；
（4）以最佳划分方法对数据进行划分，并将数据划分结果传递给其他Worker；
（5）其他Worker对接受到的数据进一步划分。
2、传统的特征并行方法主要不足:
（1）存在计算上的局限，传统特征并行无法加速特征切分（时间复杂度为 ）。 因此，当数据量很大的时候，难以加速。
（2）需要对划分的结果进行通信整合，其额外的时间复杂度约为。（一个数据一个字节）
3、LightGBM 中的特征并行
在数据量很大时，传统并行方法无法有效地对特征进行并行，LightGBM 做了一些改变：不再垂直划分数据，即每个Worker都持有全部数据。 因此，LighetGBM中没有数据划分结果之间通信的开销，各个Worker都知道如何划分数据。 而且，样本量也不会变得更大，所以，使每个机器都持有全部数据是合理的。
LightGBM 中特征并行的流程如下：
（1）每个Worker都在本地特征集上寻找最佳划分点｛特征， 阈值｝；
（2）本地进行各个划分的通信整合并得到最佳划分；
（3）执行最佳划分。
然而，该特征并行算法在数据量很大时仍然存在计算上的局限。因此，建议在数据量很大时使用数据并行。
4.3.2 数据并行
1、传统的数据并行算法
数据并行目的是并行化整个决策学习过程。数据并行的主要流程如下：
（1）水平划分数据；
（2）Worker以本地数据构建本地直方图；
（3）将所有Worker的本地直方图整合成全局整合图；
（4）在全局直方图中寻找最佳切分，然后执行此切分。
2、传统数据并行的不足：
高通讯开销。 如果使用点对点的通讯算法，一个Worker的通讯开销大约为。 如果使用集体通讯算法（例如， “All Reduce”等），通讯开销大约为。
3、LightGBM中的数据并行
LightGBM 中通过减少数据并行过程中的通讯开销，来减少数据并行的开销：
（1）不同于传统数据并行算法中的，整合所有本地直方图以形成全局直方图的方式，LightGBM 使用Reduce scatter的方式对不同Worker的不同特征（不重叠的）进行整合。 然后Worker从本地整合直方图中寻找最佳划分并同步到全局的最佳划分中。
（2）如上面提到的，LightGBM 通过直方图做差法加速训练。 基于此，我们可以进行单叶子的直方图通讯，并且在相邻直方图上使用做差法。
通过上述方法，LightGBM 将数据并行中的通讯开销减少到。
4.3.3 投票并行
投票并行进一步的减少数据并行的的通信消耗为常数级别。它使用两阶段的投票来减少特征直方图的通信消耗。
五、LightGBM中的主要调节的参数
5.1 针对 Leaf-wise（Best-first）树的参数优化
（1）num_leaves这是控制树模型复杂度的主要参数。理论上, 借鉴 depth-wise 树, 我们可以设置 num_leaves= 但是, 这种简单的转化在实际应用中表现不佳. 这是因为, 当叶子数目相同时, leaf-wise 树要比 depth-wise 树深得多, 这就有可能导致过拟合. 因此, 当我们试着调整 num_leaves 的取值时, 应该让其小于 max_depth=7时，depth-wise 树可以达到较高的准确率.但是如果设置 num_leaves 为 128 时, 有可能会导致过拟合, 而将其设置为 70 或 80 时可能会得到比 depth-wise 树更高的准确率. 其实, depth 的概念在 leaf-wise 树中并没有多大作用, 因为并不存在一个从 leaves 到 depth 的合理映射。
（2）min_data_in_leaf. 这是处理 leaf-wise 树的过拟合问题中一个非常重要的参数. 它的值取决于训练数据的样本个树和 num_leaves. 将其设置的较大可以避免生成一个过深的树, 但有可能导致欠拟合. 实际应用中, 对于大数据集, 设置其为几百或几千就足够了。
（3）max_depth（默认不限制，一般设置该值为5—10即可） 你也可以利用 max_depth 来显式地限制树的深度。
5.2 针对更快的训练速度
（1）通过设置 bagging_fraction 和 bagging_freq 参数来使用 bagging 方法；
（2）通过设置 feature_fraction 参数来使用特征的子抽样；
（3）使用较小的 max_bin；
（4）使用 save_binary 在以后的学习过程对数据进行加速加载。
5.3 针对更好的准确率
（1）使用较大的 max_bin （学习速度可能变慢）；
（2）使用较小的 learning_rate 和较大的 num_iterations；
（3）使用较大的 num_leaves （可能导致过拟合）；
（4）使用更大的训练数据；
（5）尝试 dart（一种在多元Additive回归树种使用dropouts的算法）.
5.4 处理过拟合
（1）使用较小的 max_bin（默认为255）
（2）使用较小的 num_leaves（默认为31）
（3）使用 min_data_in_leaf（默认为20） 和 min_sum_hessian_in_leaf（默认为）
（4）通过设置 bagging_fraction （默认为1.0）和 bagging_freq （默认为0，意味着禁用bagging，k表示每k次迭代执行一个bagging）来使用 bagging
（5）通过设置 feature_fraction（默认为1.0） 来使用特征子抽样
（6）使用更大的训练数据
（7）使用 lambda_l1（默认为0）, lambda_l2 （默认为0）和 min_split_gain（默认为0，表示执行切分的最小增益） 来使用正则
（8）尝试 max_depth 来避免生成过深的树
六、参考文献
（1）LightGBM: A Highly Efficient Gradient Boosting Decision Tree 论文
（2）LightGBM官网