英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
LightGBM:一种高效的梯度增强决策树
摘要
梯度增强决策树（GBDT）是一种流行的机器学习算法，具有很多有效的实现例如 XGBoost和pGBRT。尽管很多的工程优化算法已经应用于这些实现，但是当特征维度高，数据规模大时，效率和可扩展性仍然仍然不令人满意。为了解决这一个问题，我们提出了两种新技术：Gradient-based One-Side Sampling（基于梯度的单边采样GOSS）和Exclusive Feature Bundling（互斥的特征捆绑EFB）在GOSS中，我们排除了大量梯度较小的数据实例，只使用其余的数据估计信息增益。我们证明，由于梯度较大的数据实例在信息增益的计算中起着更重要的作用，所以GOSS可以在较小的数据量下获得相当准确的信息增益估计。使用EFB，我们将相互排斥的特性捆绑在一起（即，它们很少同时取非零值），以减少功能的数目。
我们证明了寻找互斥特征的最佳捆绑是NP-hard，，而贪心算法可以获得很好的近似比(从而可以有效地减少特征的数量，同时又不会对分割点的确定精度造成很大的影响)。我们称使用了GOSS和EFB的新的GBDT实现为LightGBM。我们在多个公共数据集上的实验表明，LightGBM可以将传统GBDT的训练速度提高20倍以上，同时达到几乎相同的精度。
1 简介
梯度增强决策树(Gradient decision tree, GBDT)是一种应用广泛的机器学习算法，具有效率高、精度高、可解释性强等优点。GBDT在许多机器学习任务中，如多类分类、点击率预测、排序学习等，都取得了最先进的性能。近年来，随着大数据的出现(包括特征数量和实例数量)，GBDT面临着新的挑战，尤其是在准确性和效率之间的权衡。传统的GBDT实现需要对每个特征扫描所有的数据实例来估计所有可能的分割点的信息增益。因此，它们的计算复杂性与特性的数量和实例的数量成正比。这使得这些实现在处理大数据时非常耗时。
为了解决这个问题，一个简单的想法是减少数据实例的数量和特性的数量。然而，这并不容易。例如，目前还不清楚如何对GBDT进行数据采样。虽然有一些工作是根据它们的权值对数据进行抽样，以加快boost的训练过程，但由于GBDT中根本没有样本权值，所以不能直接应用到GBDT中。在本文中，我们提出了两种实现这一目标的新技术，如下所述。
基于梯度的单边采样(GOSS)。虽然在GBDT中没有数据实例的固有权值，但是我们注意到不同梯度的数据实例在信息增益的计算中起着不同的作用。特别是根据信息增益的定义，梯度较大的实例(即(例如，训练不足的实例)将对信息获取做出更大的贡献。因此，在向下采样数据实例时，为了保持信息增益估计的准确性，我们最好保留那些梯度较大的实例(例如，大于一个预先定义的阈值，或者位于前百分位数之间)，只随机删除那些梯度较小的实例。我们证明了在目标采样率相同的情况下，这种处理比均匀随机采样的增益估计更准确，特别是在信息增益值有较大范围的情况下。
互斥的特征捆绑EFB。通常在实际应用中，虽然存在大量的特征，但特征空间十分稀疏，这为我们设计一种近乎无损的方法来减少有效特征的数量提供了可能。具体来说，在一个稀疏的特征空间中，许多特征(几乎)是互斥的，即它们很少同时取非零值。例子包括one-hot特征(例如，文本挖掘中的一个one-hot表示)。我们可以安全地将这些特征捆绑在一起。为此，我们设计了一个有效的算法，将最优的捆绑问题简化为一个图着色问题(将特征作为顶点，如果两个特征不是互斥的，则每两个特征加边)，并采用具有恒定近似比的贪婪算法求解。
我们称这种新的结合了GOSS和EFB的GBDT算法为LightGBM。我们在多个公共数据集上的实验表明，可以将训练过程加快20倍以上，同时达到几乎相同的精度。
本文的其余部分组织如下。首先，在第二节我们回顾了GBDT算法和相关工作。然后，在第三节和第四节分别详细介绍了GOSS和EFB。我们在公共数据集上的LightGBM实验在第5节中介绍。最后，我们在第6节对本文进行总结。
2 预备知识
2.1 GBDT及其复杂性分析
GBDT是一种按序列进行训练的决策树集成模型。在每次迭代中，GBDT通过拟合负梯度(也称为残差)来学习决策树。
GBDT的主要代价是学习决策树，而学习决策树最耗时的部分就是寻找最佳的分割点。最流行的分割点查找算法之一是预排序算法，它列举了预先排序的特征值上所有可能的分割点。该算法简单，可以找到最优的分割点，但在训练速度和内存消耗方面效率低下。另一种流行的算法是基于直方图的算法，如Alg.1所示。基于直方图的算法将连续的特征值放入离散的bin中，而不是在已排序的特征值上寻找分割点，并在训练过程中使用这些bin构造特征直方图。由于基于直方图的算法在内存消耗和训练速度方面都更高效，我们将在此基础上展开我们的工作。
如Alg.1所示，基于直方图的算法根据特征直方图找到最佳的分割点。它消耗O(#datatimes;#feature)用于直方图构建，O(#bintimes;#feature)用于分割点查找。由于#bin通常比#data小得多，因此直方图的构建将主导计算复杂度。如果我们能够减少#data或#feature，我们就能够大大加快GBDT的训练。
2.2 相关工作
在文献中已有不少GBDT的实现，包括XGBoost、pGBRT、scikit-learn、gbm in R。Scikit-learn和gbm in R实现了预排序算法，pGBRT实现了基于直方图的算法。XGBoost同时支持预排序算法和基于直方图的算法。如[13]所示，XGBoost的性能优于其他工具。因此，我们在实验部分使用XGBoost作为基线。
为了减少训练数据的大小，一种常见的方法是减少对数据实例的采样。例如，在[5]中，如果数据实例的权值小于固定阈值，则对其进行筛选。SGB在每次迭代中使用一个随机子集来训练弱学习器。在[6]中，采样率是在训练过程中动态调整的。但是，除了SGB，所有这些工作都是基于AdaBoost的，不能直接应用于GBDT，因为在GBDT中没有针对数据实例的本地权值。即使SGB可以应用于GBDT，但它通常会影响精度，因此不是一个理想的选择。
同样的，为了减少特征的数量，很自然的会对弱特征进行过滤。这通常是通过主成分分析或投影追踪来实现的。然而，这些方法高度依赖于特征包含大量冗余的假设，这在实践中可能并不总是正确的(特征通常以其独特的贡献进行设计，删除任何一个特征都可能在一定程度上影响训练的准确性)。
实际应用中使用的大规模数据集通常非常稀疏。使用预排序算法的GBDT可以通过忽略零值的特征来降低训练成本。然而，基于直方图算法的GBDT并没有有效的稀疏优化解。原因是，无论特征值是否为0，基于直方图的算法都需要检索每个数据实例的特征库值(参考Alg. 1)。使用基于直方图的算法的GBDT能够有效地利用这种稀疏性是非常可取的。
为了解决以往研究的局限性，我们提出了两种新的技术:基于梯度的单边采样(GOSS)和互斥特征绑定(EFB)。更多的细节将在下一节中介绍。
|
Algorithm 1: Histogram-based Algorithm |
|
|
Input: I: training data, d: max depth Input: m: feature dimension nodeSet larr; {0}▷tree nodes in current level rowSet larr; {{0, 1, 2, ...}}▷data indices in tree nodes for i = 1 to d do for node in nodeSet do usedRows larr; rowSet[node] for k = 1 to m do H larr; new Histogram() ▷ Build histogram for j in usedRows do bin larr; I.f[k][j].bin H[bin].y larr; H[bin].y I.y[j] H[bin].n larr; H[bin].n 1 Find the best split on histogram H. ... Update rowSet and nodeSet according to the best split points. ... |
|
|
Algorithm 2: Gradient-based One-Side Sampling |
|
|
Input: I: training data, d: iterations Input: a: sampling ratio of large gradient data Input: b: sampling ratio of small gradient data Input: loss: loss function, L: weak learner models larr; {}, fact larr; topN larr; a times; len(I) , randN larr; b times; len(I) for i = 1 to d do preds larr; models.predict(I) g larr; loss(I, preds), w larr; {1,1,...} sorted larr; GetSortedIndices(abs(g)) topSet larr; sorted[1:topN] randSet larr; RandomPick(sorted[topN:len(I)],randN) usedSet larr; topSet randSet w[randSet] times; = fact▷ Assign weight f act to the small gradient data. newModel larr; L(I[usedSet], －g[usedSet], w[usedSet]) models.append(newModel) |
|
3 基于梯度的单边采样
在本节中，我们提出了一种新的GBDT抽样方法，该方法可以在减少数据实例数量和保持学习决策树的准确性之间取得良好的平衡。
3.1 算法描述
在AdaBoost中，样例权值可以很好地指示数据实例的重要性。但是在GBDT中，没有本地的样本权值，所以针对AdaBoost提出的采样方法不能直接应用。幸运的是，我们注意到GBDT中每个数据实例的梯度为数据抽样提供了有用的信息。也就是说，如果一个实例与一个小的梯度相关联，那么这个实例的训练错误就很小，而且它已经经过了良好的训练。一个简单的想法是丢弃那些具有小梯度的数据实例。但是这样做会改变数据分布，从而影响学习模型的准确性。为了避免这一问题，我们提出了一种新的基于梯度的单边采样(GOSS)方法。
GOSS保留所有梯度较大的实例，并对梯度较小的实例进行随机抽样。为了补偿对数据分布的影响，在计算信息增益时，GOSS为梯度较小的数据实例引入了一个常数乘子(参见Alg. 2)。其中，GOSS首先根据梯度的绝对值对数据实例进行排序，并选择前atimes;100%实例。之后，GOSS在计算信息增益时，将小梯度采样数据放大一个常数。通过这样做，我们将更多的注意力放在训练不足的实例上，而不会对原始数据分布造成太大的影响。
3.2 理论分析
GBDT使用决策树来学习从输入空间Xs到梯度空间G的函数。假设我们有一个包含n个i.i.d实例的训练集{x1，...，xn}，其中每个xi都是空间Xs中维数为s的向量。在梯度增强的每次迭代中，损失函数相对于模型输出的负梯度记为{g1，...，gn}。决策树模型以最具信息特征(具有最大的信息增益)拆分每个节点。对于GBDT，通常用分割后的方差来衡量信息增益，定义如下:
定义3.1设O为决策树固定节点上的训练数据集。定义该节点在点d处分割特征j的方差增益为
，其中
， 和 .
对于特征j，决策树算法选择，计算最大增益
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238381]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
