LightGBM：一种高效的梯度提升决策树

这里介绍一种由微软团队开发的高效的梯度提升决策树 LightGBM。相关代码实现已开源至 github：

https://github.com/microsoft/LightGBM。

论文出处：

https://papers.nips.cc/paper_files/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf。

以下是论文翻译：

摘要

梯度提升决策树（GBDT）是一种流行的机器学习算法，已经有许多有效的实现，例如XGBoost和pGBRT。尽管这些实现中采用了许多工程优化，然而当特征维度高且数据量大时，其效率和可扩展性仍然不理想。

主要原因在于，对于每个特征，算法需要扫描所有数据实例来估算所有可能分割点的信息增益，这一过程非常耗时。为了解决这个问题，我们提出了两种新技术：基于梯度的单边采样（GOSS）和特征互斥捆绑（EFB）。在GOSS中，我们排除了大量梯度较小的数据实例，仅使用剩余的数据实例来估算信息增益。我们证明，由于具有较大梯度的数据实例在信息增益计算中起着更重要的作用，GOSS可以在使用更小的数据集时，获得较为准确的信息增益估计。在EFB中，我们将互斥特征捆绑在一起（即它们很少同时取非零值），以减少特征的数量。

我们证明，找到最优的互斥特征捆绑是NP-难问题，但贪心算法可以获得相当好的近似比率（从而有效地减少特征数量，同时不会大幅损害分割点判定的准确性）。我们将新的GBDT实现称为带有GOSS和EFB的LightGBM。我们在多个公开数据集上的实验表明，LightGBM加速了传统GBDT的训练过程，速度提升超过20倍，同时几乎保持相同的准确性。

引言

梯度提升决策树（GBDT）是一种广泛使用的机器学习算法，由于其在许多机器学习任务中的高效性、准确性和可解释性，GBDT在多类分类、点击预测和排序学习等任务中取得了最先进的性能。近年来，随着大数据的出现（特征数量和样本数都大幅增加），GBDT面临着新的挑战，特别是在准确性和效率之间的权衡问题。传统的GBDT实现需要为每个特征扫描所有数据实例，以估算所有可能的分割点的信息增益。因此，其计算复杂度将同时与特征数和样本数成正比。这使得在处理大数据时，这些实现非常耗时。

为了解决这一挑战，一个直接的想法是减少数据实例的数量和特征的数量。然而，这个问题非常复杂。例如，如何为GBDT执行数据采样仍然不清楚。虽然已有一些研究尝试根据样本的权重来进行数据采样，从而加速提升过程，但这些方法不能直接应用于GBDT，因为GBDT中根本没有样本权重。

我们提出了两种新技术来解决这一问题，具体如后文所述。

基于梯度的单边采样（GOSS）

尽管在GBDT中没有原生的数据实例权重，但我们注意到具有不同梯度的数据实例在信息增益的计算中扮演着不同的角色。具体来说，根据信息增益的定义，梯度较大的数据实例（即训练不足的实例）对信息增益的贡献较大。因此，在下采样数据实例时，为了保持信息增益估计的准确性，我们应该保留那些梯度较大的实例（例如，梯度大于预定义的阈值，或者位于梯度的前几个百分位），并随机丢弃那些梯度较小的实例。

我们证明，这种处理方法可以在目标采样率相同的情况下，获得比均匀随机采样更准确的信息增益估计，尤其是在信息增益的取值范围较大时。

特征互斥捆绑（EFB）

通常在实际应用中，尽管特征数量很多，但特征空间是相当稀疏的，这为我们设计一种近乎无损的方法来减少有效特征的数量提供了可能性。具体来说，在稀疏特征空间中，许多特征是（几乎）互斥的，即它们很少同时取非零值。

举例来说，包括单热编码特征（例如，文本挖掘中的单热词表示）。我们可以安全地将这些互斥特征捆绑在一起，通过减少最优捆绑问题的复杂度来实现。为此，我们将最优捆绑问题转化为图着色问题（通过将特征看作顶点，并在每两个不互斥的特征之间添加边），并通过贪心算法以常数近似比率来解决该问题。

我们将带有GOSS和EFB的新GBDT算法称为LightGBM。我们在多个公开数据集上的实验表明，LightGBM可以将训练过程加速至传统GBDT的20倍以上，同时实现几乎相同的准确性。

本文结构

本文结构安排如下：

• 第2节：回顾GBDT算法及相关工作；
• 第3节：v介绍GOSS的细节；
• 第4节：介绍EFB的细节；
• 第5节：实验结果展示LightGBM在公开数据集上的表现；
• 第6节：总结本文内容。

预备知识

GBDT及其复杂度分析

GBDT是一种决策树的集成模型，决策树是按序列训练的。在每次迭代中，GBDT通过拟合负梯度（也称为残差误差）来学习决策树。

GBDT的主要开销在于学习决策树，而学习决策树最耗时的部分是寻找最佳的分割点。最常用的寻找分割点的算法之一是预排序算法，该算法枚举了所有可能的分割点，基于预排序的特征值。这个算法简单且能够找到最优的分割点，但在训练速度和内存消耗上效率较低。

另一个常用算法是基于直方图的算法，如算法1所示。该算法通过将特征值划分到离散的区间中，使用这些区间来构建特征直方图，从而避免了在排序特征上的分割点查找。由于基于直方图的算法在内存消耗和训练速度上更高效，我们将在此基础上开展工作。

如算法1所示，基于直方图的算法根据特征直方图来寻找最佳分割点，构建直方图的复杂度为O(数据数 × 特征数)，而分割点查找的复杂度为 O(箱数 × 特征数)。由于箱数通常远小于数据数，因此在计算复杂度中，直方图构建的开销将占主导地位。如果我们能够减少数据数或特征数，则能够显著加速GBDT的训练过程。

相关工作

在文献中，已有不少GBDT的实现，包括XGBoost、pGBRT、scikit-learn和R中的gbm。Scikit-learn和R中的gbm实现了预排序算法，而pGBRT实现了基于直方图的算法。XGBoost支持这两种算法。

为减少训练数据的大小，一种常见的方法是对数据实例进行下采样。例如，在[5]中，当数据实例的权重小于某个固定阈值时，会对其进行过滤。SGB [20]在每次迭代中使用随机子集来训练弱学习器。在[6]中，采样率会根据训练进度动态调整。然而，除SGB [20]外，所有这些方法都是基于AdaBoost的[21]，而且不能直接应用于GBDT，因为GBDT没有数据实例的原生权重。尽管SGB可以应用于GBDT，但通常会损害准确性，因此它不是一个理想的选择。

为了减少特征数量，通常通过主成分分析（PCA）或投影追踪来过滤弱特征。然而，这些方法通常依赖于特征之间存在显著冗余的假设，而这一假设在实践中可能并不总是成立（特征通常是根据它们独特的贡献来设计的，去除其中任何一个可能会在某种程度上影响训练准确度）。

在实际应用中使用的大规模数据集通常是相当稀疏的。使用预排序算法的GBDT可以通过忽略零值特征来减少训练成本。然而，GBDT与基于直方图的算法并没有高效的稀疏优化解决方案。其原因在于基于直方图的算法需要为每个数据实例检索特征的bin值，无论特征值是否为零（参见算法1）。因此，非常希望GBDT能够有效地利用这些稀疏特性。

为了应对之前方法的局限性，我们提出了两种新技术，分别是梯度的单边采样（GOSS）和排他性特征捆绑（EFB）。更多细节将在接下来的章节中介绍。

基于梯度的单边采样

在本节中，我们提出了一种新的GBDT采样方法，能够在减少数据实例数量和保持所学决策树准确性之间取得良好的平衡。

算法描述

在AdaBoost中，样本权重是一个很好的数据实例重要性的指示器。然而，在GBDT中，并没有原生的样本权重，因此无法直接应用AdaBoost提出的采样方法。幸运的是，我们注意到GBDT中每个数据实例的梯度提供了有用的信息来进行数据采样。也就是说，如果一个实例与小梯度相关联，则该实例的训练误差很小，且它已经被很好地训练。一个直接的想法是丢弃那些具有小梯度的数据实例。然而，这样做会改变数据分布，从而影响所学模型的准确性。为了避免这个问题，我们提出了一种名为梯度基于单边采样（GOSS）的方法。

GOSS保留所有具有大梯度的实例，并对具有小梯度的实例执行随机采样。为了补偿对数据分布的影响，在计算信息增益时，GOSS为小梯度的数据实例引入了一个常数乘子（见算法2）。具体来说，GOSS首先根据其梯度的绝对值对数据实例进行排序，并选择前 $a \times 100$ 的实例。然后它从剩余的数据中随机采样 $b \times 100$ 的实例。之后，GOSS通过常数 $\frac{1-a}{b}$ 来放大这些小梯度数据的采样值，以计算信息增益。这样，我们能够在不改变原始数据分布的情况下，更加关注那些未被充分训练的实例。

理论分析

GBDT使用决策树从数据空间 $\mathcal{X}^s$ 学习函数到梯度空间 $\mathcal{G}$ [1]。假设我们有一个包含 $n$ 个独立同分布（i.i.d.）样本的数据集 ${x_1, \cdots, x_n}$，其中每个 $x_i$ 的维度为 $s$，即 $x_i \in \mathcal{X}^s$。在每次梯度提升的迭代中，模型参数的负梯度记为 ${g_1, \cdots, g_n}$。决策树模型在每个节点上分裂最具有信息增益的特征（信息增益最大）。对于GBDT，信息增益通常通过分裂后节点的方差来衡量，如下所定义。

定义 3.1。设 $O$ 为决策树固定节点 $d$ 的训练数据集，特征 $j$ 在点 $d$ 的方差增益定义为：

$$V_{j|O}(d) = \frac{1}{n_O} \left( \frac{\left( \sum_{x_i \in O : x_{ij} \leq d} g_i \right)^2}{n_{j|O}(d)} + \frac{\left( \sum_{x_i \in O : x_{ij} > d} g_i \right)^2}{n_{j|R}(d)} \right),$$

其中 $n_O = \sum I[x_i \in O]$，$n_{j|O}(d) = \sum I[x_i \in O : x_{ij} \leq d]$ 和 $n_{j|R}(d) = \sum I[x_i \in O : x_{ij} > d]$。

对于特征 $j$，决策树算法选择 $d_j^* = \arg \max_j V_j(d)$，并计算该特征的最大增益 $V_j(d^*)$。然后，数据根据特征 $j^*$ 在点 $d^*$ 上分裂成左右子节点。

在我们提出的GOSS方法中，首先，我们根据梯度的绝对值对训练实例进行排序；其次，我们保留前 $a \times 100$ 的梯度较大的实例；然后，对于其余的样本集 $A^c$（包含 $1-a \times 100$ 实例），我们进一步随机采样一个大小为 $B$ 的子集，其中 $B$ 为 $|A^c|$ 的向量大小；最后，我们根据合并子集 $A \cup B$ 上的估计方差增益 $V_j^*(d)$ 来分裂数据。

$$V_j^*(d) = \frac{1}{n} \left( \frac{\left( \sum_{x_i \in A_l : x_{ij} \leq d} g_i \right)^2}{n_j(d)} + \frac{\left( \sum_{x_i \in A_r : x_{ij} > d} g_i \right)^2}{n_r(d)} \right),$$

其中 $A_l = {x_i \in A : x_{ij} \leq d }$，$A_r = {x_i \in A : x_{ij} > d }$，$B_l = {x_i \in B : x_{ij} \leq d }$，$B_r = {x_i \in B : x_{ij} > d }$；并且系数 $\frac{1-a}{b}$ 用于将梯度总和归一化回到 $B$ 上。

因此，在GOSS中，我们使用 $V_j^*(d)$ 来代替 $V_j(d)$ 对所有实例进行分裂点的确定，计算成本得以大幅减少。更重要的是，理论证明表明，GOSS不会丧失太多训练精度，并且将优于随机采样。由于空间限制，我们将在附录中给出证明。

定义 3.2。我们将GOSS中的近似误差表示为 $\mathcal{E}(d) = | \hat{V}_j(d) - V_j(d) |$ 和 $\vec{g}*l(d) = \sum*{x_i \in (A \cup A_r)} |g_i| / n_j(d)$。

对于至少概率 $1 - \delta$，我们有：

$$\mathcal{E}(d) \leq C_{a,b} h \frac{1}{n_l(d)} \max \left\{ \frac{1}{n_l(d)}, \frac{1}{n_r(d)} \right\} + 2D C_{a,b} \sqrt{\frac{\ln \frac{1}{\delta}}{n}},$$

其中 $C_{a,b} = \frac{1-a}{\sqrt{b}} \max_{x_i \in A \cup A_r} |g_i|$，并且 $D = \max(\vec{g}_l(d), \vec{g}_r(d))$。

根据定理，我们得出以下讨论：

1. GOSS的渐进近似比率是 $O \left( \frac{1}{n_l(d)} + \frac{1}{n_r(d)} + \frac{1}{\sqrt{n}} \right)$。如果分裂不是特别不平衡（即，$n_l(d) \geq O(\sqrt{n})$ 和 $n_r(d) \geq O(\sqrt{n})$），则近似误差将主要由不等式（2）中的第二项支配。

   其次，随着数据量 $n$ 的增加，近似误差将趋于 $O(\sqrt{n})$，当 $n$ 足够大时，这意味着近似非常准确。

2. 随机采样是GOSS的一个特殊情形，当 $a = 0$ 时。在许多情况下，GOSS能够优于随机采样，在条件 $C_{0,\beta} > C_{a,\beta - a}$ 下，且等效于条件 $\frac{a}{\sqrt{b}} > \frac{1-a}{\beta - a}$，其中 $a = \max_{x_i \in A \cup A_r} |g_i| / \max_{x_i \in A^c} |g_i|$。

接下来，我们分析GOSS的泛化性能。我们考虑GOSS的泛化误差 $\mathcal{E}_{GOSS}(d) = | \hat{V}_j(d) - V^*(d) |$，这是由GOSS计算的方差增益与基础数据分布的真实方差增益之间的差距。我们有：

$$\mathcal{E}_{GOSS}^{gen}(d) \leq | \hat{V}_j(d) - V_j(d) | + | \hat{V}_j(d) - V^*(d) | \triangleq \mathcal{E}_{GOSS}(d) + \mathcal{E}^{gen}(d)。$$

因此，GOSS的泛化误差将接近于当使用所有数据实例时的误差，前提是GOSS的近似是准确的。另一方面，采样将增加基础学习者的泛化误差，进而可能有助于提高模型的泛化能力 [24]。

排他性特征捆绑

在本节中，我们提出了一种有效减少特征数量的新方法。

高维数据通常非常稀疏。特征空间的稀疏性为我们提供了减少特征数量的可能性。具体来说，在稀疏特征空间中，许多特征是相互排斥的，即它们从不同时取非零值。我们可以将排他性特征捆绑到一个单一特征中（我们称之为排他性特征捆绑）。通过精心设计的特征扫描算法，我们可以像构建单独特征的特征直方图一样，构建来自特征捆绑的相同特征直方图。通过这种方式，直方图构建的复杂度从 O(数据数 × 特征数) 改变为 O(数据数 × 箱数)，其中 箱数 << 特征数。这样我们可以显著加速 GBDT 的训练，而不会损害准确性。接下来，我们将详细介绍如何实现这一目标。

有两个问题需要解决。第一个是如何确定哪些特征应该被捆绑在一起。第二个是如何构建捆绑。

定理 4.1。 将特征划分为最小数量的排他性捆绑问题是 NP-难 的。

证明：我们将图着色问题[25]归约到我们的问题中。由于图着色问题是 NP-难 的，我们可以得出结论。

给定图着色问题 G=(V,E)。G = (V, E) 的任意实例，我们构造一个我们的实例。对于图的每一行作为特征，我们得到一个我们的实例问题，且容易看出，问题中的排他性特征捆绑对应于具有相同颜色的顶点集合，反之亦然。

对于第一个问题，我们在定理 4.1 中证明它是 NP-难 的，无法在多项式时间内找到最优捆绑策略，这表明不可能找到精确的解。为了找到一个良好的近似算法，我们首先将最优捆绑问题归约到图着色问题，将特征作为顶点，对于每两个特征如果它们不是互斥的，就在它们之间添加边，然后使用贪心算法可以产生合理的结果。

（具有常数近似比率的）图着色算法用于生成捆绑。此外，我们注意到，通常有一些特征，尽管不是 100% 互斥，但也很少同时取非零值。如果我们的算法允许一小部分冲突，我们可以得到更少的特征捆绑，并进一步提高计算效率。通过简单计算，随机污染特征值的少部分将影响训练准确度，最多约为 $O([(1 - \gamma)n]^{-2/3})$（见附录材料中的命题 2.1），其中 $\gamma$ 是每个捆绑中最大冲突率。因此，如果我们选择相对较小的 $\gamma$，我们将能够在准确性和效率之间取得良好的平衡。

基于上述讨论，我们设计了如算法 3 所示的排他性特征捆绑算法。首先，我们构建了一个加权图，其中边的权重表示特征之间的总冲突。然后，我们按图中每个特征的度数对特征进行降序排序。最后，检查每个特征并将其分配给现有捆绑中的一个（如果冲突较小，受 $\gamma$ 控制），或者创建一个新的捆绑。算法 3 的时间复杂度为 O(特征数)，并且在训练前仅处理一次。当特征数量不是非常大时，这个复杂度是可以接受的，但如果有数百万个特征，仍然可能会存在问题。为了提高效率，我们提出了一种无需构建图的更高效排序策略，通过按非零值的数量对特征进行排序，这类似于按度数对特征进行排序，因为更多非零值通常会导致更高的冲突概率。由于我们只是在重新排序策略方面进行调整，因此新算法的细节省略，以避免重复。

对于第二个问题，我们需要一种有效的方式来合并同一捆绑中的特征，以减少相应的训练复杂度。关键是确保原始特征的值可以通过特征捆绑来识别。由于基于直方图的算法存储特征的离散值，因此我们可以通过让排他性特征在不同的 bin 中进行排序，从而构造一个特征捆绑。这样就可以通过对原始特征的值添加偏移量来构造特征捆绑。例如，假设我们有两个特征在一个特征捆绑中。最初，特征 A 的值范围是 [0, 10]，特征 B 的值范围是 [0, 20]。然后，我们对特征 A 的值添加 10 的偏移量，使得 refined feature 的值范围变为 [10, 30]。此后，特征 A 和 B 可以安全地合并，并使用范围 [0, 30] 的特征捆绑来替代原始特征 A 和 B。详细的算法见算法 4。

EFB 算法可以将许多排他性特征捆绑成更少的稠密特征，从而有效避免对零特征值的无谓计算。实际上，我们还可以通过使用表格记录每个特征的非零值，优化基本的基于直方图的算法，忽略零特征值。通过扫描该表，特征的直方图构建成本将从 O(数据数) 变为 O(非零数据数)。然而，这种方法需要额外的内存和计算开销，以维护这些每个特征的表格以记录非零数据。我们在 LightGBM 中实现了此优化作为基本功能。请注意，此优化不会与 EFB 冲突，即使当捆绑稀疏时。

实验

在本节中，我们报告了关于我们提出的 LightGBM 算法的实验结果。我们使用了五个不同的公开数据集，这些数据集的详细信息列在表 1 中。其中，Microsoft Learning to Rank (LETOR) 数据集包含了 30K 个网页搜索查询。该数据集中使用的特征大多是密集的数值特征。Allstate Insurance Claim 和 Flight Delay 数据集都包含了大量的独热编码特征。最后两个数据集来自 KDD CUP 2010 和 KDD CUP 2012。我们直接使用了 NTU 获胜方案中使用的特征，这些特征包含了密集和稀疏特征，这两个数据集非常大。这些数据集既大又包含密集和稀疏特征，并覆盖了许多现实世界的任务。因此，我们可以使用它们来全面测试我们的算法。

我们的实验环境是一个 Linux 服务器，配备了两颗 E5-2670 v3 CPU（共 24 核心）和 256GB 内存。所有实验均采用多线程运行，线程数固定为 16。

总体比较

我们在本小节中展示了总体比较。

XGBoost [13] 和 LightGBM 没有使用 GOSS 和 EFB（称为 lgb_baseline）作为基准。对于 XGBoost，我们使用了两个版本，xgb_exa（预排序算法）和 xgb_his（基于直方图的算法）。对于 LightGBM，我们使用了叶子-wise 树生长策略 [32]。对于 xgb_exa，由于它只支持层次-wise 生长策略，我们调节了 xgb_exa 的参数，让它像其他算法一样生长树。

• 表1：实验中使用的数据集

名称	数据量	特征数量	描述	任务	指标
Allstate	12M	4228	稀疏	二分类	AUC
Flight Delay	10M	700	稀疏	二分类	AUC
LETOR	2M	136	密集	排序	NDCG@4
KDD10	19M	29M	稀疏	二分类	AUC
KDD12	119M	54M	稀疏	二分类	AUC

• 表2：总体训练时间成本比较。LightGBM 是 lgb_baseline 与 GOSS 和 EFB。EFB_only 是 lgb_baseline 与 EFB。表中的值是平均训练时间（秒）每次训练一次。

算法	xgb_exa	xgb_his	lgb_baseline	EFB_only	LightGBM
Allstate	10.85	2.63	6.07	0.61	0.28
Flight Delay	5.94	1.05	1.39	0.27	0.22
LETOR	5.55	0.63	0.49	0.46	0.31
KDD10	108.27 OOM	39.85	6.33	8.73	2.26
KDD12	191.99 OOM	168.26	20.23	12.67

• 表3：测试数据集上的总体准确率比较。用于分类任务的 AUC，排序任务使用 NDCG@10。SGB 是 lgb_baseline 与随机梯度提升，其采样策略与 LightGBM 相同。

算法	xgb_exa	xgb_his	lgb_baseline	SGB	LightGBM
Allstate	0.6070	0.6089	0.6093	0.6064 ± 7e-4	0.6093 ± 9e-5
Flight Delay	0.7601	0.7840	0.7847	0.7780 ± 4e-4	0.7846 ± 4e-5
LETOR	0.4977	0.4982	0.5277	0.5239 ± 6e-4	0.5275 ± 5e-4
KDD10	0.7796	0.7901	0.7873	0.7759 ± 3e-4	0.7873 ± 1e-4
KDD12	0.7029	0.7047	0.7084	0.6989 ± 8e-4	0.7051 ± 5e-5

我们还对所有数据集进行了参数调节，以便更好地平衡速度和准确性。

• 设置 α = 0.05，β = 0.05 对 Allstate，KDD10 和 KDD12 数据集；
• 设置 α = 0.1，β = 0.1 对 Flight Delay 和 LETOR；
• 设置 $\gamma=0$ 在 EFB 中。

所有算法都运行固定迭代次数，并且我们从最佳迭代中获取了准确率结果。

训练时间和测试准确度分别在表2和表3中总结。

从这些结果来看，LightGBM 是最快的，同时保持几乎相同的准确性。xgb_exa 基于预排序算法，与基于直方图的算法相比，在 Allstate、Flight Delay、LETOR、KDD10 和 KDD12 数据集上分别加速了 21 倍、6 倍、1.6 倍、14 倍和 13 倍。由于 xgb_his 很消耗内存，它无法在 KDD10 和 KDD12 数据集上成功运行，因为内存溢出。

在其余的数据集上，LightGBM 都更快，最高达 9 倍的加速。加速是基于每次迭代训练时间计算的。由于所有算法在相似数量的迭代中收敛，我们还展示了基于 Flight Delay 和 LETOR 数据集 墙时钟时间的训练曲线（见图1）6。

• 表4：在不同采样比下，GOSS 和 SGB 在LETOR 数据集上的准确度比较。我们通过使用大量迭代和早期停止来确保所有实验达到收敛点。不同设置下的标准差较小。GOSS 的参数 a 和 b 设置可以在附加材料中找到。

采样比	0.1	0.15	0.2	0.25	0.3	0.35	0.4
SGB	0.5182	0.5216	0.5239	0.5249	0.5252	0.5263	0.5267
GOSS	0.5224	0.5256	0.5275	0.5284	0.5289	0.5293	0.5296

为了节省空间，我们将其余数据集的训练曲线放在附加材料中。

在所有数据集上，LightGBM 可以达到与基准几乎相同的测试准确度。这表明 GOSS 和 EFB 不会影响准确度，同时带来显著的加速。这与我们在第 3.2 节和第 4 节中的理论分析一致。

LightGBM 在这些数据集上实现了完全不同的加速比。总体加速来自 GOSS 和 EFB 的结合，我们将在接下来的部分中详细讨论 GOSS 和 EFB 的贡献以及它们的有效性。

GOSS分析

首先，我们研究 GOSS 的加速能力。从 LightGBM 和 EFB_only（表2中的 LightGBM 未使用 GOSS）比较中可以看出，GOSS 自身可以通过使用 10% - 20% 的数据加速近 2 倍。GOSS 可以仅通过使用采样数据来学习树。然而，它仍然保留了一些在全数据集上的计算，比如进行预测和计算梯度。因此，我们可以发现整体加速与采样数据的比例并不完全相关，但 GOSS 带来的加速仍然是非常显著的，而且这种技术对不同数据集普遍适用。

其次，我们通过与随机梯度提升（SGB）[20] 比较来评估 GOSS 的准确性。在不失一般性的情况下，我们使用 LETOR 数据集进行测试。我们通过选择不同的 a 和 b 来调节采样比例，并为 SGB 使用相同的整体采样比例。我们在这些设置下运行，直到使用早期停止达到收敛。结果如表4所示。我们可以看到，在使用相同的采样比例时，GOSS 的准确性始终优于 SGB。这些结果与我们在第 3.2 节中的讨论一致。所有实验都表明，GOSS 是一种比随机采样更有效的采样方法。

EFB分析

我们通过将 lgb_baseline 与 EFB_only 进行比较，来检查 EFB 对加速的贡献。结果如表2所示。我们不允许在捆绑查找过程中出现冲突（即 $\gamma = 0$）。我们发现，EFB 可以帮助在这些大规模数据集上实现显著的加速。

请注意，lgb_baseline 已针对稀疏特征进行了优化，而 EFB 仍然能够加速训练过程。其原因在于 EFB 将许多稀疏特征（包括一热编码特征和隐式排他特征）合并为更少的特征。基本的稀疏特征优化已包含在捆绑过程中。另一方面，EFB 不需要在训练过程中为每个特征维护非零数据表。更重要的是，以前各自独立的特征现在被捆绑在一起，这有助于提高缓存命中率并显著提升效率。因此，整体的训练效率提升非常显著。通过进一步分析，EFB 是一种非常有效的算法，它能够在基于直方图的算法中利用稀疏特征，并且能在 GBDT 训练过程中带来显著加速。

结论

在本文中，我们提出了一种新型的 GBDT 算法，称为 LightGBM，该算法包含两种新技术：基于梯度的单边采样（Gradient-based One-Side Sampling）和排他性特征捆绑（Exclusive Feature Bundling），分别用于处理大规模数据实例和大规模特征。

我们在这两项技术上进行了理论分析和实验研究。实验结果与理论一致，表明在 GOSS 和 EFB 的帮助下，LightGBM 在计算速度和内存消耗方面显著超越了 XGBoost 和 SGB。未来的工作将研究基于梯度的单边采样中 a 和 b 的最优选择，并继续改进排他性特征捆绑的性能，以处理大量特征，无论这些特征是否稀疏。

支撑材料

在这里下载：https://papers.nips.cc/paper_files/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Supplemental.zip。

参考文献

1. Jerome H. Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189–1232, 2001.

2. Ping Li. Robust logitboost and adaptive base class (abc) logitboost. arXiv preprint arXiv:1203.3491, 2012.

3. Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: estimating the click-through rate for new ads. Proceedings of the 16th international conference on World Wide Web, pages 521–530. ACM, 2007.

4. Christopher JC Burges. From ranking to lambdamart: An overview. Learning, 11(23-581):81, 2010.

5. Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics, 28(2):337–407, 2000.

6. Charles Dubout and François Fleuret. Boosting with maximum adaptive sampling. In Advances in Neural Information Processing Systems, pages 1332–1340, 2011.

7. Ron Appel, Thomas J Fuchs, Piotr Dollár, and Pietro Perona. Quickly boosting decision trees-pruning underachieving features early. In ICML (3), pages 594–602, 2013.

8. Manish Mehta, Rakesh Agrawal, and Jorma Rissanen. Sliq: A fast scalable classifier for data mining. In International Conference on Extending Database Technology, pages 18–32. Springer, 1996.

9. John Shafer, Rakesh Agrawal, and Manish Mehta. Sprint: A scalable parallel classifier for data mining. In Proc. 1996 Int. Conf. Very Large Data Bases, pages 544–555. Citeseer, 1996.

10. Sanjay Ranka and V Singh. Clouds: A decision tree classifier for large datasets. In Proceedings of the 4th Knowledge Discovery and Data Mining Conference, pages 2–8, 1998.

11. Ruoming Jin and Gagan Agrawal. Communication and memory efficient parallel decision tree construction. In Proceedings of the 2003 SIAM International Conference on Data Mining, pages 119–129. SIAM, 2003.

12. Ping Li, Christopher JC Burges, Qiang Wu, JC Platt, D Koller, Y Singer, and S Roweis. Mcrank: Learning to rank using multiple classification and gradient boosting. In NIPS, volume 7, pages 845–852, 2007.

13. Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794. ACM, 2016.

14. Stephen Tyree, Kilian Q Weinberger, Lanul Agrawal, and Jennifer Paykin. Parallel boosted regression trees for web search ranking. In Proceedings of the 20th international conference on World wide web, pages 387–396. ACM, 2011.

15. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12(Oct):2825–2830, 2011.

16. Greg Ridgeway. Generalized boosted models: A guide to the gbm package. Update, 1(1):207, 2007.

17. Huan Zhang, Si Si, and Cho-Jui Hsieh. Gpu-acceleration for large-scale tree boosting. arXiv preprint arXiv:1706.08359, 2017.

18. Rory Mitchell and Eibe Frank. Accelerating the xgboost algorithm using gpu computing. PeerJ Preprints, 5:e2911v1, 2017.

19. Qi Meng, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, and Tieyan Liu. A communication-efficient parallel algorithm for decision tree. In Advances in Neural Information Processing Systems, pages 1271–1279, 2016.

20. Jerome H Friedman. Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4):367–378, 2002.

21. Michael Collins, Robert E Schapire, and Yoram Singer. Logistic regression, adaboost and bregman distances. Machine Learning, 48(1-3):253–285, 2002.

22. Ian Jolliffe. Principal component analysis. Wiley Online Library, 2002.

23. Luis O Jimenez and David A Landgrebe. Hyperspectral data analysis and supervised feature reduction via projection pursuit. IEEE Transactions on Geoscience and Remote Sensing, 37(6):2653–2667, 1999.

24. Zhi-Hua Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.

25. Tommy R Jensen and Bjarne Toft. Graph coloring problems, volume 39. John Wiley & Sons, 2011.

26. Tao Qin and Tie-Yan Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013.

27. Allstate claim data, https://www.kaggle.com/c/ClaimPredictionChallenge.

28. Flight delay data, https://github.com/szilard/benchm-ml#data.

29. Hsiang-Fu Yu, Hung-Yi Lo, Hsun-Ping Hsieh, Jing-Kai Lou, Todd G McKenzie, Jung-Wei Chou, Po-Han Chung, Chia-Hua Ho, Chun-Fu Chang, Yin-Hsuan Wei, et al. Feature engineering and classifier ensemble for kdd cup 2010. In KDD Cup, 2010.

30. Kuan-Wei Wu, Chun-Sung Ferng, Chia-Hua Ho, An-Chun Liang, Chun-Heng Huang, Wei-Yuan Shen, Jyun-Yu Jiang, Ming-Hao Yang, Ting-Wei Lin, Ching-Pei Lee, et al. A two-stage ensemble of diverse models for advertisement ranking in kdd cup 2012. In KDDCup, 2012.

31. Libsvm binary classification data, https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html.

32. Haijian Shi. Best-first decision tree learning. PhD thesis, The University of Waikato, 2007.