Light Gradient Boosting Machine。lightGBM 和 XGBoost一样，是对GBDT的优化实现，但比XGBoost更为优秀高效。GBDT 在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据一次性装进内存，会明显限制训练数据的大小。如果不装进内存，反复地读写训练数据又会消耗非常大的时间。XGboost中使用的精确贪心算法也同样存在这个问题。

参考资料（更加详细，有助于理解）：

https://github.com/ExpressGit/NLP_Study_Demo/blob/main/ML/LightGBM.ipynb

https://www.bilibili.com/video/BV1JK4y1L7ow/?spm_id_from=333.337.search-card.all.click&vd_source=514a3ed3ac370caf4facad7d6f4e1a2d

1. 核心思想

LightGBM是一种高效的梯度提升决策树（GBDT）实现，具有独特的优化策略以应对大规模数据和高维特征的挑战。其核心思想是通过引入基于直方图的决策树算法、梯度采样、特征捆绑等技术，优化模型的训练速度和内存使用，同时保持模型的准确性。

1.1 基于Histogram的决策树算法

LightGBM采用基于直方图的决策树算法，通过将连续特征值分桶（即构建直方图），极大地减少了寻找最佳分裂点时的计算量。同时，直方图算法的内存效率也显著提升，因为特征值只需要记录对应的分桶信息，而不必存储完整的特征值。

注意：

  • 使用分桶 bin 替代原始数据相当于增加了正则化。
  • 使用分桶 bin 意味着很多数据的细节特征丢失，相似的数据如果划分到相同的桶中，数据之间的差异就无法捕获了。
  • 分桶 bin 数量决定了正则化的程度，bin 越少惩罚越严重，欠拟合风险越高。
  • 因为预先设定了 bin 的范围，构建直方图时不需要对数据进行排序。
  • 直方图保存「划分阈值」、「当前 bin 内样本数」、「当前 bin 内所有样本的一阶梯度和」。
  • 阈值的选取是按照直方图从小到大遍历，使用了上面的一阶梯度和，目的是得到划分之后 损失函数 最大的特征及阈值。

1.2 单边梯度采样GOSS, Gradient-based One-Side Sampling (GOSS)

GOSS是一种采样策略，旨在通过保留梯度较大的样本（即模型难以拟合的样本）来提高梯度提升的效率。GOSS会对梯度较小的样本进行下采样，减少计算量，同时保证对整体数据分布的准确把握，从而加快模型的训练速度。

图1

1.3 互斥特征捆绑 Exclusive Feature Bundling

Exclusive Feature Bundling (EFB) 是一种特征压缩技术，用于减少特征的维度。LightGBM会将一些互斥的稀疏特征（即在同一个样本中不同时为非零的特征）捆绑成一个特征，极大地减少了特征维度的数量，而不会影响模型的精度。

算法步骤：

  • 将特征按照非零值的个数进行排序。
  • 计算不同特征之间的冲突比率。
  • 遍历每个特征并尝试合并特征，使冲突比率最小。

1.4 带深度限制的Leaf-wise的叶子生长策略

LightGBM采用叶子生长策略（Leaf-wise Growth），即在构建决策树时优先分裂增益最大的叶子节点，而不是逐层分裂。这种策略相比传统的逐层分裂方法（level-wise），能够更快地找到更优的分裂点，但也更容易出现过拟合。为此，LightGBM引入了深度限制，防止树结构过深。

1.5 直接支持类别特征

LightGBM直接支持类别特征，不需要对其进行独热编码（one-hot encoding）。通过对类别特征的分裂优化，LightGBM能够在高效处理类别特征的同时减少内存和计算的开销。

算法步骤：

  • 在枚举分割点之前，先把直方图按每个类别的均值进行排序。
  • 接着按照均值的结果依次枚举最优分割点。

1.6 支持高效并行

LightGBM支持特征并行和数据并行两种高效的并行计算方式。在特征并行中，多个特征的分裂点搜索可以并行进行；在数据并行中，使用分散规约把直方图合并的任务分摊到不同的机器上。

1.7 Cache命中率优化

LightGBM 所使用直方图算法对 Cache 天生友好：

首先，所有的特征都采用相同的方式获得梯度（区别于XGBoost的不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中率； 其次，因为不需要存储行索引到叶子索引的数组，降低了存储消耗，而且也不存在 Cache Miss的问题。

2. 算法步骤

LightGBM的基本算法流程如下：

  1. 初始化：初始化模型参数，将所有样本的预测值设定为常数值（如均值）。

  2. 构建决策树：根据残差更新样本的梯度信息，采用基于直方图的分裂方法，找到最佳分裂点。

  3. 更新预测值：根据新构建的树，更新所有样本的预测值。

  4. 迭代重复：根据更新后的预测值继续构建新树，重复该过程直到达到设定的迭代次数或满足早停条件。

3. 目标函数

LightGBM 的目标函数由损失函数和正则化项组成：

  • 损失函数：通常是平方误差（用于回归问题）或交叉熵损失（用于分类问题），用于衡量模型预测值与真实值的差异。

    \[ L(\theta) = \sum_i \ell(y_i, f(x_i)) \]

  • 正则化项：为了防止模型过拟合，LightGBM引入了树结构复杂度和叶子节点权重的正则化项：

    \[ \Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_j w_j^2 \]

各参数含义与XGboost中的相同。

4. 优点

速度快，占用内存少。

5. 缺点

LightGBM是基于偏差的算法，所以会对噪点较为敏感。在寻找最优解时，依据的是最优切分变量，没有将最优解是全部特征的综合这一理念考虑进去；