XGBoost 是一种强大且高效的梯度提升框架。它将正则化技术直接引入目标函数,并进行了稀疏感知和并行处理等系统级优化,这标志着相对于传统梯度提升机(GBM)的重大进步。对于许多问题,XGBoost在预测准确性和计算性能之间提供了出色的平衡。然而,随着数据集在实例数量($N$)和特征数量($M$)两方面的持续增长,即使是像XGBoost这样经过优化的算法,也可能遇到显著的计算瓶颈。主要困难通常源于树构建过程中寻找最佳分裂点的过程。考虑XGBoost默认的精确贪婪算法。为了在特定节点上为一个特征找到最优分裂,算法通常需要:根据特征值对实例进行排序。遍历该特征的所有可能分裂点(通常在每个唯一的排序值之间有一个)。计算每个潜在分裂的质量得分(例如,基于正则化目标函数的增益)。对所有特征重复此过程。在每个节点上对所有实例和所有特征进行这种穷举搜索会变得计算量巨大。其成本大致与非缺失条目数量成比例,在密集情况下,每次分裂的成本可近似为$O(N \times M)$。尽管存在优化措施(如预排序和缓存,或使用直方图的近似算法),但扫描大量数据或特征值的基本需求依然存在。这种计算成本主要体现在两个方面:训练时间: 对于拥有数百万或数十亿行,或数万个特征的数据集,为每棵树重复遍历数据点和特征会显著增加总训练时间。内存占用: 存储中间结果,例如每个实例的排序特征值或梯度统计信息,可能需要大量内存,甚至可能超出单台机器的可用资源。XGBoost的近似算法可以减少这一点,但构建和存储直方图仍然会带来内存开销。这些局限性在现代机器学习中常见的场景中变得尤为明显:网络规模数据集、高维基因组数据,或涉及大量工程化或稀疏特征的问题。对一种梯度提升算法的需求,这种算法既能保持高准确度,又能大幅提高训练速度和减少内存使用,促成了LightGBM的开发。LightGBM从一开始就以高效率为首要目标进行设计。它引入了几种新颖技术,专门用于减轻在大数据集上训练时产生的计算和内存成本。这些技术包括:基于梯度的单边采样(GOSS): 减少分裂计算中需要考虑的数据实例数量。互斥特征捆绑(EFB): 通过捆绑稀疏的、互斥的特征来减少需要扫描的有效特征数量。基于直方图的算法: 使用离散化的特征值(直方图)来加速分裂点查找并减少内存使用,这类似于XGBoost的近似算法,但进行了进一步的优化。叶子生长策略: 一种不同的树构建策略,通常收敛速度更快,但需要注意控制复杂度。理解以往算法面临的这些具体计算障碍,为理解LightGBM中实现的设计选择和优化提供了背景,我们将在本章中详细审视这些内容。