机器学习笔记 LightGBM：理解算法背后的数学原理

一、简述

在一次数据科学的比赛中，我有机会使用 LightGBM，这是一种最先进的机器学习算法，它极大地改变了我们处理预测建模任务的方式。我对它在数千个数据点上进行训练的速度感到着迷，同时保持了其他算法难以达到的准确性。LightGBM 是Light Gradient Boosting Machine的缩写，是 Microsoft 开发的开源、分布式、高性能梯度提升框架。

在数据科学和机器学习领域，准确执行预测是一项关键任务，可以显著影响业务运营和决策。传统方法通常难以应对现代数据的复杂性和数量，导致性能和可扩展性问题不理想。LightGBM 的优势就在于此，它提供了兼具速度、准确性和灵活性的强大解决方案。

二、什么是LightGBM？

LightGBM是微软开发的开源、分布式、高性能梯度提升框架。它旨在实现高效、可扩展和准确。该框架利用决策树来提高模型效率并最大限度地减少内存使用量。 LightGBM 的开发是为了克服传统梯度提升机 (GBM) 的计算效率低下问题，因为传统梯度提升机需要处理所有特征上的所有数据实例，从而产生大量计算。为了解决这个问题，LightGBM 引入了两项关键技术：基于梯度的单侧采样 (GOSS) 和独占特征捆绑 (EFB)。

1、基于梯度的单侧采样（GOSS）

基于梯度的单侧采样 (GOSS) 是一种通过选择性保留具有较大梯度的数据实例来提高 LightGBM 效率的技术。其背后的原理是梯度较大的实例对优化过程的贡献更大，而梯度较小的实例影响较小。 GOSS 利用梯度来获取有关每个实例的信息增益，从而解决计算问题。

梯度较小：表示算法在这个实例上已经训练得很好，所以误差较小。
大梯度：表示误差较大，也就是说，如果集中注意力，这个实例将提供更多的信息增益。

它会忽略梯度较小的实例，而集中精力处理梯度较大的实例。然而，这样做会改变数据分布，从而对模型的准确性产生负面影响。 GOSS 提供了一种基于梯度对数据进行采样同时保留数据分布的方法。运行机制

排序：数据实例根据其梯度的绝对值进行排序。
选择：选择具有最大梯度的顶部 $a \times 100\%$ 实例。
随机抽样：从剩余实例中，选择大小为 $b \times 100\%$ 的随机样本。
重新加权：在信息增益计算过程中，对小梯度的随机样本进行重新加权，其权重等于 $(1-a)/b$ 。

数学解释：

GOSS 最终确保模型在保持整体数据分布的同时，更加关注导致损失较大的实例（即训练不足的实例），从而不会显著影响学习到的模型的准确性。

2、独占特征捆绑 (EFB)

具有许多特征的数据集通常具有稀疏特征，这意味着有很多零值。这些稀疏特征通常是互斥的，这意味着它们不会同时具有非零值。

例如，在独热编码的文本数据中，只有表示特定单词的一列是非零的，而特定行中的所有其他列都是零。独占特征捆绑 (EFB) 是一种将这些互斥特征组合成单个特征的技术，可降低维数。EFB 使用贪婪算法将这些特征捆绑在一起。这种维数降低加快了梯度提升决策树 (GBDT) 的训练时间，而不会显著影响准确性，因为创建特征直方图的复杂性取决于捆绑的数量而不是特征的数量（并且捆绑的数量远少于特征的数量）。

EFB 面临的一个挑战是找到最佳捆绑包。微软的研究人员通过将捆绑问题转换为图形着色问题来解决此问题。在此问题中，特征表示为顶点，并在非互斥特征之间添加边。然后使用贪婪算法来创建捆绑包。该算法还允许捆绑很少同时具有非零值的特征，称为几乎互斥的特征。另一个挑战是以一种允许从捆绑特征中提取原始特征值的方式合并特征。例如，在三个特征的捆绑中，我们需要使用捆绑特征的值来识别这三个特征的值。

LightGBM 中基于直方图的算法为连续值创建了离散的箱体。为了有效地合并特征，将捆绑包中特征的独有值放置在不同的箱体中。这是通过向原始特征值添加偏移量来实现的，确保每个特征的值在捆绑包中仍然可以区分。

数学解释：

通过结合这两种技术，LightGBM 在效率和可扩展性方面都实现了显著的提升：

GOSS 确保在训练期间优先考虑最具信息量的实例，从而加快收敛速度并减少内存使用量。
EFB 通过捆绑互斥的特征来减少特征的数量，从而降低维数和计算成本。

三、节省分割样本的时间

在 LightGBM 中，最佳分割是根据最大化增益来定义的，增益可以衡量分割后损失函数的减少量。LightGBM 采用基于直方图的方法来有效地找到最佳分割。以下是 LightGBM 中如何定义和计算最佳分割的详细说明：

基于直方图的方法

1.分箱：将连续特征值离散化为固定数量的箱（直方图）。此步骤减少了可能的分割次数并加快了计算速度。

2.直方图构建：对于每个特征，构建一个直方图，其中每个箱包含落入该箱的样本的梯度与 Hessian 的总和。

3.分割查找：使用直方图而不是原始数据来评估潜在的分割。

增益计算 增益衡量了分割带来的损失函数的改善。其计算方法如下：

图示

直方图算法是将每列特征值转换成直方图，按照整数区间生成k个bin，然后将特征值放在对应区间的bin中，使得bins<<特征，从而减少内存占用和计算复杂度。

确定最佳分割的步骤

1. 初始化：计算当前节点的总梯度和（G）以及 Hessian 和（H）。

2. 对于每个特征：将特征值离散化到各个箱体中。构建梯度和 Hessian 直方图。对于每个可能的分割（箱），使用上述公式计算增益。

3. 选择最佳分割： 确定所有特征和箱体中增益最高的分割。此分割被选为当前节点的最佳分割。

四、如何形成树？

LightGBM 使用一种称为逐叶（或最佳优先）生长的独特方法来生长树，这与许多其他梯度提升框架使用的传统逐级（或广度优先）方法不同。

以下是 LightGBM 如何生长树的概述：在逐叶增长策略中，LightGBM 始终会拆分损失减少（增益）最高的叶子。这种方法可以生成更深的树，但叶子更少，但通常可以提高准确率。与 XGBoost 不同，LightGBM 是逐级增长的。

叶子生长的步骤：

1.从单个根节点开始：从单个根节点中的所有数据点开始。

2.计算潜在分割：对于每个特征，计算潜在的分割并评估其收益。增益被计算为分割时损失函数（例如均方误差）的减少。

3.选择最佳分割：选择提供最高增益的分割。这涉及评估所有特征的所有潜在分割并选择具有最大增益的分割。

4.通过分裂最好的叶子来种植树：分裂产生最高增益的叶子，从而产生两片新叶子。相应地更新树结构。

5.重复该过程：继续选择并分裂增益最高的叶子，直到满足停止标准（例如最大深度、叶子中的最小数据点数或指定数量的叶子）。 停止标准： 最大树深度、叶子中的最小数据点、最大叶子数量、最小分割增益

五、梯度提升方法

LightGBM 提供两种主要的增强技术：梯度增强决策树 (GBDT) 和 Dropouts 满足多元加性回归树 (DART)。

1、梯度提升决策树（GBDT）

GBDT 是 LightGBM 中使用的标准增强技术。它按顺序构建决策树集合，其中每棵树都经过训练以纠正先前树的错误。

主要特征：

•顺序训练：一棵树接一棵树地建立，每棵新树的目的都是为了减少先前所有树的组合残差误差。

•基于梯度的优化：该模型使用损失函数的梯度来识别最显著的错误并在后续树中纠正它们。

•加法模型：所有树的预测相加形成最终预测。

过程： 1.初始化：从初始预测开始（例如，回归的平均值）。

2.计算残差：对于每个数据点，计算残差（实际值与当前预测值之间的差值）。

3.训练一棵树：拟合一棵新的决策树来预测残差。

4.更新模型：通过添加新树的预测（按学习率缩放）来更新模型。

5.重复：继续添加树，直到达到指定的迭代次数或满足另一个停止标准。 数学解释：

2、Dropouts + 多元加性回归树 (DART)

DART是 GBDT 的扩展，旨在通过结合类似于神经网络中使用的 dropout 技术来缓解过度拟合。它在训练期间随机从集成中删除树，这有助于规范化模型。

主要特征：

随机丢弃：在每次迭代期间，会随机丢弃一部分树，并根据剩余的树来训练新树。

减少过度拟合：通过删除树，DART 可防止模型过度依赖任何特定的树，从而实现更好的泛化。

加法和 Dropout：结合加法建模（如 GBDT）和 Dropout 正则化（来自神经网络）的原理。

过程：

1.初始化：从初始预测开始。 2.计算残差：计算每个数据点的残差。 3.随机丢弃（Random Dropout）：从当前集合中随机丢弃一组树。 4.训练一棵树：用剩余集合的残差拟合一棵新的决策树。 5.更新模型：将新树的预测添加到当前模型中。 6.重复：继续该过程，在每次迭代中随机删除树，直到达到指定的迭代次数或满足另一个停止标准。

数学解释：

六、LightGBM 核心参数

LightGBM 核心参数是影响 LightGBM 模型在训练期间的行为和性能的重要设置。这些参数控制模型的各个方面，例如其结构、优化过程和目标函数。微调这些核心参数对于使模型适应特定的机器学习任务并实现最佳性能至关重要。关键参数包括学习率、叶子数、最大深度、正则化项和优化策略。

核心参数说明：

1. objective：指定训练期间要优化的损失函数。LightGBM 支持各种目标，例如回归、二元分类和多类分类。

2. task：定义要执行的任务，可以是“train”或“prediction”。默认值为“train”，但可以设置为“prediction”以进行模型推理。

3. num_leaves：确定每棵树中叶子的最大数量。较高的值允许模型捕获更复杂的模式，但可能会导致过度拟合。

4. learning_rate：控制梯度下降过程中每次迭代的步长。值越低，学习速度越慢，但可以提高泛化能力。

5. max_depth：设置每棵树的最大深度。较高的值使模型能够捕获更复杂的交互，但可能会导致过度拟合。

6. min_data_in_leaf：指定形成叶节点所需的最小数据点数。较高的值有助于防止过度拟合，但可能导致欠拟合。

7.num_iterations ：指定要执行的迭代次数（树）。默认值为 100 。

8. feature_fraction：控制构建每棵树时要考虑的特征比例。随机选择特征子集有助于提高模型多样性并减少过度拟合。

9. bagging_fraction：指定训练期间用于 bagging（有放回地采样数据点）的数据比例。它有助于提高模型的鲁棒性并减少方差。

10. lambda_l1 和lambda_l2：分别控制 L1 和 L2 正则化的正则化参数。这些参数会惩罚较大的系数以防止过度拟合。

11. min_split_gain：定义进一步分裂节点所需的最小增益。它有助于控制树的增长并防止不必要的分裂。

12. categorical_feature：指定用于训练模型的分类特征。

七、小结

LightGBM 在机器学习领域取得了显著的进步，特别是对于涉及大型数据集和复杂模型的任务。其创新的梯度提升方法利用基于梯度的单侧采样 (GOSS) 和独占特征捆绑 (EFB) 等技术，通过显著提高效率和可扩展性使其有别于传统算法。

LightGBM 的数学基础揭示了其稳健性和适应性。通过专注于逐叶树的生长、利用直方图进行分割查找以及采用高效的采样方法，LightGBM 实现了卓越的性能，同时降低了过度拟合的风险。这些数学技术确保 LightGBM 能够处理高维数据和复杂的模式，使其成为各个领域从业者的首选。了解 LightGBM 背后的数学原理不仅可以洞悉其内部工作原理，还可以帮助数据科学家和机器学习工程师微调模型以获得最佳性能。随着我们不断突破预测建模和数据分析的界限，LightGBM 等工具仍将成为我们工具包中不可或缺的一部分，推动创新并增强我们从数据中获取有意义见解的能力。