我们来看下lightgbm的paper：《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》。
1.
GBDT是流行的机器学习算法，只有少量的高效实现，比如：XGBoost和pGBRT。尽管在这些实现中采用了许多工程优化，但当特征维度很高、数据size很大时，其效率和可扩展性仍不能令人满意。其中一个主要原因是，对于每个特征，他们需要扫描所有数据样本来估计所有可能划分点的信息增益（information gain），这是非常耗时的。为了解决该问题，我们提供了两个新技术：基于梯度的单边采样（GOSS: Gradient-based One-Side Sampling）、独有特征打包（EFB: Exclusive Feature Bundling）。有了GOSS，我们可以使用小梯度来排除大量的样本，只使用剩余部分来估计信息增益。我们通过证明，由于更大梯度的数据样本，通常在计算信息增益时扮演更重要角色，GOSS使用更小的data size即可以获得相当精准的关于信息增益的估计。有了EFB，我们可以将多个独有特征（比如：他们很少会同时采用非零值）进行打包，以减小特征数。我们证明了，发现最优的独有特征bundling是一个NP-hard问题，但一个贪心算法可以达到相当好的近似（这样可以有效减少特征数，同时不伤害split点决策的accuracy）。我们将这种带GOSS和EFB机制的GBDT称为LightGBM。我们的实现在多个公共数据集上做了实验，LightGBM可以加速常用的GBDT训练过程达20倍，而几乎保持相同的accuracy。
1.介绍
由于高效，精准，可解释性强，GBDT被广泛使用。GBDT在许多机器学习任务上都达到了state-of-art的效果。最近几年，随机大数据的出现，GBDT面临着新挑战，尤其是在accuracy和efficiency的权衡上。GBDT的常见实现，需要对每个特征进行扫描所有数据样本来估计所有可能划分点的信息增益。因此，他们的计算复杂度与特征数、以及样本数成比例。这使得这些实现在处理大数据时非常耗时。
为了解决该挑战，一个简单的想法是，减少数据样本数、以及特征数。然而，这被证明是非常有意义（non-trivial）的。例如，如何为GBDT执行数据采样是不明确的。有一些工作开展会根据它们的权重来采样数据，以加速boosting的训练过程[5,6,7]。但它们不能直接被应用在GBDT中，因为在GBDT中根本没有抽样权重(sample weight)。为此，我们提出了两种新技术。
GOSS。在GBDT中对于数据样本没有原始权重（native weight），我们注意到不同梯度的数据样本在计算信息增益时扮演着不同的角色。特别的，根据信息增益的定义，这些带着更大梯度的（例如：under-trained样本实例）样本实例会在计算信息增益时贡献更多。因此，当对这些数据样本做下采样(down-sampling)时，为了保持信息增益的accuracy，我们最好保留这些带有大梯度的样本（例如：比一个预定义阀值要更大，或者在top百分比间），并只随机drop掉那些小梯度的样本实例。我们证明了，这样的处理比均匀随机抽样（uniformly random sampling）可以产生更精准的增益估计，特别是当信息增益的值具有具有较大范围时。
EFB。在真实应用中，尽管具有大量特征数，但特征空间相当稀疏，这提供给我们一个设计一个几乎无损的方法的可能性，来减小有效特征数。特别的，在一个稀疏特征空间中，许多特征是（几乎）独有的，例如，他们很小同时采用非零值。这些样本包含了one-hot特征（例如：文本挖掘中的one-hot词表示）。我们可以很安全地对这些独有特征进行捆绑（bundle）。q我们设计了一个高效算法，它通过会将最优bundling问题缩减到一个图着色问题（graph coloring problem：通过将特征看成是顶点，如果每两个特征间相互排斥就添加一条边），通过一个常数近似率的贪心算法来解决该问题。
我们将这个带有GOSS和EFB的新GBDT算法称为LightGBM。
2.前提条件
2.1 GBDT和它的复杂度分析
GBDT是一个关于决策树的ensemble模型，它会顺序式进行训练。在每轮迭代中，GBDT会通过拟合负梯度（被称为：残差 residual errors）来学习决策树。
GBDT的主要开销在学习决策树中，学习决策树时最耗时的部分，是发现最佳的分割点（split points）。一种最流行的算法是，pre-sorted算法【8，9】，它会在pre-sorted特征值上枚举所有可能的分割点。另一种流行的算法是，histogram-based算法【10,11,12】，如算法1所示。histogram-based算法会将连续特征值进行分桶成(buckets)离散bins，并在训练期间使用这些bins来构建特征的histograms。由于histogram-based算法在内存消耗和训练速度上都更高效，我们基于它进行开发。
算法1､2:
如算法1所示，histogram-based算法会基于特征的histograms去发现最佳split points。它会花费O(#data x #feature)的时间复杂度来进行histogram building，以及花费O(#bin x #feature)来进行split point finding。由于#bin通常要比#data更小很多，histogram building会决定着计算复杂度。如果我们可以缩减#data数或者#feature数，我们将能够实质上加速GBDT的训练。
2.2 相关工作
在文献中有相当少的GBDT实现，包含XGBoost[13], pGBRT[14], scikit-learn[15], R的gbm[16]。sklearn和R-gbm实现使用的是presorted算法，而pGBRT实现了histogram-based算法。XGBoost支持两种实现（pre-sorted和histogram-based）。如[13]所示，XGBoost的效果要好于其它工作包。因而，我们使用XGBoost作为我们实验中的baseline。
为了缩减训练数据的size，常用的方法是对数据样本进行下采样。例如，在[5]中，如果数据样本的权重小于一个固定阀值，它们将会被过滤。SGB[20]会在每轮迭代中使用一个随机子集来训练弱学习器（weak learners）。在[6]中，抽样率在训练过程中会动态调整。然而，除了SGB外的所有其它工作都基于AdaBoost，不能直接应用于GBDT，因为它们对于在GBDT中的数据样本实例来说没有原始权重(native weights)。尽管SGB可以被用于GBDT，但它通常会降低accuracy，因而不是一个理想选择。
相同的，为了缩减特征数，很自然地会过滤弱特征[22,23,7,24]。这通常可以通过PCA或投影来完成。然而，这些方法高度依赖于：假设这些特征包含大量冗余，这在实践中并不总是成立（特征通常会根据它们的独特贡献被设计，移除任意之一都会在一定程序上影响训练的accuracy）。
在实际应用中的大规模数据集通常是相当稀疏的。GBDT会使用pre-sorted算法，通过忽略零值特征来缩减训练开销【13】。而histogram-based GBDT不会对稀疏优化解决方法有影响。原因是，histogram-based算法需要为每个数据样本检索特征的bin值（根据算法1），不管特征值是零或非零。我们更推荐histogram-based算法，它可以有效消除这样的稀疏特性。
为了解决之前的局限性，我们提出了两个新技术：GOSS、EFB。
3 GOSS
3.1 算法描述
在AdaBoost中，sample weight被当成是一个关于数据样本实例重要性的指示器（indicator）。然而，在GBDT中，不存在天然的sample weights，因而像AdaBoost提出的sampling方法不能直接用。幸运的是，我们注意到，对于在GBDT中的每个数据样本，它们的梯度可以为我们提供有用信息来进行数据抽样。也就是说，如果一个实例与一个小梯度有关，该样本的training error很小，并已经过良好训练。一个简单的想法是，抛弃这些小梯度的数据样本。然而，这样做可能会改变数据分布，进而伤害所学模型的accuracy。为了避免该问题，我们提出了一个新方法称为：GOSS。
GOSS会保留所有带大梯度的样本，并在小梯度样本上进行随机抽样。为了对数据分布的影响进行补偿，当计算信息增益时，GOSS会为带小梯度的数据样本引入一个常数乘子（见算法2）。特别的，GOSS首先会根据它们梯度的绝对值来对数据样本进行排序，接着选取top a x 100%的样本。接着它会从其余数据中随机抽样 b x 100%的样本。最后，当计算信息增益时，GOSS会通过一个常数\(\frac{1-a}{b}\)对小度数抽样数据进行放大。通过该方法，我们可以更关注under-trained样本实例，而不需要过多更改原始数据分布。
算法2:
3.2 理论分析
GBDT使用决策树来学习从输入空间\(X^s\)到梯度空间\(\mathcal{G}\)的函数。假设，我们具有一个训练集\({x_1,...,x_n}\)，n独立同分布(i.i.d.)，其中每个\(x_i\)是一个在空间\(X^s\)上的s维向量。在gradient boosting的每轮迭代中，关于loss函数的负梯度会根据模型的输出被表示为\({g_1, ..., g_n}\)。决策树模型会在最具信息量的特征上分割每个节点（使用最大信息增益）。对于GBDT，信息增益通常会通过在进行分割之后的variance来进行衡量，如下定义。
定义 3.1: 假设O是在决策树的一个确定节点上的训练数据集。在该节点上，分割特征j在点d中的variance gain，定义如下：
\[V_{j|O}(d) = \frac{1}{n_O}()\]其中，。
定理 3.2
4. EFB
在本部分，我们提出了一种新方法来有效缩减特征数。
算法3,4
高维数据通常非常稀疏。特征空间的稀疏性提供我们一个可能性来设计近科目无损的方法来缩减特征数。特别的，在一个稀疏特征空间中，许多特征相互排斥，例如，他们不会同时采用非零值。我们可以安全地将这些相互排斥的特征打包成单个特征（我们称之为一个“exclusive feature bundle”）。通过一个精心设计的特征扫描算法，我们可以从feature bundles中构建相同的feature histograms来作为从单个特征中计算的histograms。在这种方法中，histogram building的复杂度可以从O(#data x #feature)变为O(#data x #bundle)，其中，#bundle « #feature。接着，我们可以在对accuracy无伤的情况下极大加速GBDT的训练。接着，我们会详细展示是如何得到的。
有两个要点要解决。第一个是，决定哪些特征应一起进行加包。第二个是如何构建bundle。
定理 4.1：将特征划分为更小数目的exclusive bundles问题是一个NP-hard问题。
证明：我们会将图着色问题（graph coloring problem）应用到我们的问题上。由于图着色问题是NP-hard的，我们可以推导我们的推论。
给定关于图着色问题的任意样本 \(G = (V,E)\)。我们以如下方式构建一个样本实例。采用关联矩阵G的每一行作为一个feature，接着使用\(\mid V \mid\)个特征来获取一个instance。很容易看到，在我们的问题中，特征的一个exclusive bundle对应于相同颜色的一个顶点集，反之即然。
对于第1个要点，定理4.1证明了：发现最优的bundling策略是一个NP-hard问题。这意味着，在多项式时间内发现一个准确的解是不可能的。为了发现一个好的近似算法，我们首先将optimal bundling问题精减为图着色问题。通过将特征看成是顶点、如果两两特征不相互排斥则在上面添加边。我们使用一个贪心算法来为图着色生成bundles来生成合理的好结果（具有一个常数近似几率）。接着，我们注意到，通常有相当少的特征，尽管它们并不是100%相互排斥的，很少同时采用非零值。如果我们的算法可以允许一定比例的冲突，我们可以获得一个更小数目的feature bundles，并进一步提升计算效率。通过简单计算，随机污染一定比例的特征值会影响训练accuracy，最多达到\(O([(1-\gamma)n]^{-2/3})\)，其中\(\gamma\)是在每个bundle中的最大冲突然袭击。因此，如果我们选择一个相对小的\(\gamma\)，我们会在accuracy和efficiency上达到较好的平衡。
其于上述讨论，我们为exclusive feature bundling设计了一个算法来，如算法3所示。首先，我们使用一个带权重边来构建一个graph，它们有weights以应于特征间的总冲突。第二，我们通过在图中的度对特征进行降序排序。最后，我们在有序列表中确认每个特征，接着给它们分配一个已存在具有较小冲突的bundle（通过\(\gamma\)控制），或者创建一个新bundle。算法3的时间复杂度是\(O(#feature^2)\)，它在训练前仅会处理一次。当特征数不是非常大时，该复杂度是可接受的，但如果有数百万特征时仍会有问题。为了进一步提升效率，我们提出一种更有效的排序策略(ordering strategy)，无需构建graph：通过非零值的数目排序，这与通过degree的方式排序相似，因为更多非零值通常会产生更高的冲突率。由于我们只会更改算法3的排序策略，新算法的细节会被忽略以免重复。
对于第二个要点，我们需要一种好方法来将相同bundle中的features合并，以便能缩减相应训练复杂度。关键点是确认原始特征值可以从feature bundles中被确认。由于histogram-based算法会存储离散bins，而非特征的连续值，我们可以通过让排斥特征(exclusive features)落在不同的bins上。这可以通过添加offsets到特征的原始值中来完成。例如，假设我们在一个feature bundle中有两个features。最初，feature A的取值为[0, 10)，feature B的取值为[0, 20)。我们接着添加一个offsets为10到feature B中，以便重定义的features取值为[10,30)。这之后，可以安全地合并features A和B，并使用一个范围为[0,30)的feature bundle来替换原始的features A和B。详细情况见算法4.
EFB算法可以将多个排斥特征bundle到更少的dense features上，它可以有效避免不必要的零特征值计算。实际上，我们也可以优化最基本的histogram-based算法，通过为每个特征使用一个表来记录非零值数据来忽略零值。通过扫描该表的数据，对于一个特征，histogram building的开销会从O(#data)变更为O(#non zero data)。然而，该方法需要额外的内存和计算开销来维持这些在整个树增长过程中的per-feature tables。我们在LightGBM中将该优化实现作为一个基本功能。注意，该最优化不会与EFB冲突，因为在当bundles很稀疏时，我们仍可以使用它。
5.实验
本部分，我们会展示实验结果。我们使用了5个不同公共数据集。这些数据集如表1所示。其中，Microsoft Learning to Rank [LETOR]数据集包含了30K的网络搜索queries。该数据集所用的features大多数是dense numerical features。Allstate Insurance Claim数据集和Flight Delay数据集都包含了许多one-hot coding features。最后两个数据集来自于KDD CUP 2010和KDD CUP 2012. 我们直接使用来自NTU的获胜方案的features，它包含了dense和sparse features，这两个数据集都非常大。我们可以使用它们来直接测试算法。
表1
我们的实验环境是Linux server，它具有两个E5-2670 v3 CPUs(共24个核)以及256GB内存。所有实验都在多线程上运行，线程数固定在16个上。
5.1 总体比较
我们在下面提出了总的比较。XGBoost和没有GOSS和EFB的LightGBM(称为lgb_baseline)被用于baselines。对于XGBoost，我们使用两个版本，xgb_exa(pre-sorted算法)和xgb_his（histogram-based算法）。对于xgb_his，lgb_baseline，以及LightGBM，我们使用leaf-wise的树增长策略。对于xgb_exa，由于它只支持layer-wise的增长策略，我们为xgb_exa调整参数，以便让它像其它方法一样增长相似的树。接着，我们朝着在speed和accuracy间更好平衡的方向，为所有数据集调参。我们为Allstate，KDD10和KDD12设置a = 0.05, b=0.05, 为Flight Delay和LEFTOR设置a=0.1, b=0.5. 我们EFB中设置\(\gamma=0\)。所有算法会运行固定迭代次数，我们从该迭代中使用最好的score来获取accuracy结果。
表2
训练时间和测试accuracy在表2和表3中。从这些结果看，我们可以看到LightGBM是最快的，并且几乎与baselines维持着相同的accuracy。xgb_exa是基于pre-sorted算法的，它会比histogram-based算法要慢很多。通过比较lgb_baseline，LightGBM在AllState、Flight Delay、LETOR、KDD10和KDD12数据集上要快21x，6x，1.6x，14x和13x。由于xgb_his相当耗费内存，它在KDD10和KDD12数据集上不能成功运行，会out-of-memory。在其它数据集上，LightGBM会更快，直到在Allstate数据集上能达到9x加速。 加速的计算是通过每轮迭代的训练时间计算得到的，是由于所有算法会在相同迭代数上收敛。为了演示总的训练过程，我们展示各自在图1和图2上，基于wall clock time的训练曲线。
表3:
在所有数据集上，LightGBM可以达到几乎相同的test accuracy作为baselines。这意味着GOSS和EFB在带来大的加速时并不会伤害accuracy。这与第3.2节和第4节的理论分析相一致。
5.2 GOSS分析
首先，我们研究了GOSS的加速能力。从表2中LightGBM和EFB_only的比较来看，我们可以通过使用10%-20%的数据，看到GOSS可以带来接近2x的加速。GOSS可以只使用抽样数据就可以学到trees。然而，它会在整个数据集上保留一些计算，比如：指导预测和计算梯度。这样，我们就可以发现，整个加速与抽样数据的比例是非线性相关的。然而，由GOSS带来的加速仍非常大，该技术可以应用到不同数据集上。
第二，通过比较随机梯度增强（SGB：Stochastic Gradient Boosting），我们评估了GOSS的accuracy。不失一般性，我们使用LETOR数据集进行测试。我们通过选择在GOSS中不同的a和b来调参抽样比例，并为SGB使用相同的整体抽样比例。我们通过使用early stopping来运行这些settings直到收敛。结果如表4所示。我们可以看到，当使用相同的抽样比例（sampling ratio）时，GOSS的accuracy总是好于SGB。这些结果与在3.2节中讨论一致。所有实验演示了GOSS是一个比stochastic sampling更高效的sampling方法。
表4:
5.3 EFB分析
通过比较lgb_baseline和EFB_only，我们确认了EFB对于加速的贡献。结果如表2所示。这里，我们不允许在bundle finding process(例如：\(\gamma=0\))中有冲突。我们发现EFB可以帮助达到在这些大规模数据集上更大的加速。
注意，lgb_baseline对于稀疏特征有优化，EFB可以通过一个较大因子达到训练加速。由于EFB会将许多稀疏特征（one-hot features和隐式exclusive features）合并到更少的特征中。然而，EFB在维持非零数据表上，对于在树学习过程中的每个特征，不会有额外开销。再者，由于许多之前孤立的特征会捆绑到一起，它可以增加spatial locality，并极大提升cache hit rate。因此，在效率上的整体提升是显著的。有以上分析后，EFB是一个非常有效的算法，可以利用在histogram-based算法上的sparse特性，它可以为GBDT训练过程带来一个极大加速。
参考
https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf