起因
前面我们介绍了一些Qlib的基本入门用法，然后进一步深入，发现里面有很多的模型、算法等。那么今天就先以QuickStart的LightGBM入手，来详细了解一下吧。
代码：https://github.com/microsoft/LightGBM
LightGBM: 一种高效的梯度提升决策树算法
《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》 链接
作者：Guolin Ke¹, Qi Meng², Thomas Finley³, Taifeng Wang¹, Wei Chen¹, Weidong Ma¹, Qiwei Ye¹, Tie-Yan Liu¹
¹微软研究院，²北京大学，³微软雷德蒙研究院
会议：第31届神经信息处理系统大会（NIPS 2017），美国加州
摘要
梯度提升决策树Gradient Boosting Decision Tree（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 引言
梯度提升决策树（GBDT）因其高效性、准确性和可解释性而被广泛使用，在多分类、点击预测、排序等任务中表现出色。然而，随着大数据时代的到来（特征数和样本数都急剧增加），GBDT 面临新的挑战，尤其是在准确性与效率之间的权衡。
传统 GBDT 实现需要对每个特征扫描所有样本，以估计所有可能分裂点的信息增益，因此其计算复杂度与特征数和样本数成正比，导致在大数据场景下训练非常缓慢。
为应对这一挑战，我们提出以下两种新技术：
1.1 梯度单边采样（GOSS）
尽管 GBDT 中没有样本权重的概念，但我们注意到不同梯度的样本在信息增益计算中的作用不同。梯度较大的样本（即训练不足的样本）对信息增益贡献更大。因此，在降采样时，==我们应保留大梯度样本，仅随机丢弃小梯度样本，并通过权重调整保持数据分布的一致性==。
1.2 互斥特征捆绑（EFB）
==高维数据通常具有稀疏性，许多特征几乎不会同时取非零值（如 one-hot 编码特征）。我们可以将这些“互斥”特征捆绑为一个特征==，从而减少特征数量。我们证明该问题是 NP-难的，但贪心算法可在常数近似比下获得良好效果。
我们将集成这两种技术的 GBDT 实现称为 LightGBM，实验表明其训练速度提升显著，且精度几乎无损。
2 预备知识
2.1 GBDT 及其复杂度分析
GBDT 是一种集成模型，每轮训练一棵==拟合负梯度==（残差）的决策树。训练的主要开销在于寻找最优分裂点。常用的方法是预排序算法（精确但慢）和直方图算法（高效，内存友好）。我们基于后者进行优化。
直方图算法的复杂度为：
- 构建直方图：O(#data × #feature)
- 寻找分裂点：O(#bin × #feature)
由于 #bin ≪ #data，构建直方图是瓶颈。==若能减少 #data 或 #feature==，即可显著加速训练。
2.2 相关工作
- XGBoost：支持预排序和直方图算法，是目前最快的 GBDT 实现之一。
- SGB（随机梯度提升）：每轮随机采样样本，但会损失精度。
- 特征降维：如 PCA、特征选择，但可能损失信息。
3 梯度单边采样（GOSS）
3.1 算法描述
==GOSS 保留大梯度样本，对小梯度样本进行随机采样，并通过权重因子调整其贡献==，保持信息增益估计的准确性。
算法流程：
- 按梯度绝对值降序排序样本；
- 保留前 a×100% 的大梯度样本；
- 从剩余样本中随机采样 b×100%；
- 给小梯度样本赋予权重 (1−a)/b；
- 使用加权样本构建直方图并估计信息增益。
（==为了便于理解，博主注：==
把 GOSS 想象成“在线考试老师只改关键题”：
- 先给所有样本的“错题程度”打分（=梯度绝对值 |g_i|）。
- 梯度越大 → 错题越严重 → 越要保留。 把全班按 |g_i| 从高到低排队，前 a×100% 的“重灾区”学生全部留堂。
- 剩下的“几乎做对”的学生里，再随机抽 b×100% 出来，以免完全忽略他们。
- 为了让“抽样班”的成绩分布跟原来一样，给这些被抽到的“好学生”一个放大系数 weight = (1−a)/b。 直观理解：本来有 (1−a) 比例的好学生，现在只抽了 b 比例，所以每人要“代表” (1−a)/b 个自己。
- 用这套加权后的子样本去计算直方图、信息增益、分裂点——速度变快，但分布仍接近原班。
a、b 是什么？
- 用户可调的超参数，不是固定常数。
- 论文实验里给出的典型区间： – a ∈ [0.05, 0.2]（保留 5 %–20 % 的大梯度样本） – b ∈ [0.05, 0.2]（再从剩余里抽 5 %–20 %） – 合计采样率 ≈ a + b，常见 10 %–30 %。
- LightGBM 的默认设置：
–
top_rate(a) = 0.2 –other_rate(b) = 0.1 如果精度下降，优先增大 a（大梯度样本更关键）。 ） ### 3.2 理论分析
我们定义信息增益为分裂后方差减少量。GOSS 使用采样后的样本来估计信息增益，其误差上界为：
其中：
(对理论证明感兴趣的，可以去看看论文原文。)
结论：
- 当样本数 n 很大时，误差趋于 0；
- GOSS 优于随机采样（SGB），尤其在信息增益范围大时；
- 采样增加了基学习器的多样性，有助于泛化。
4 互斥特征捆绑（EFB）
4.1 算法描述
高维稀疏特征中，许多特征几乎不会同时非零（如 one-hot 特征）。我们将这些特征捆绑为一个“互斥特征 bundle”，从而减少特征数。
（==博主注：==
One-hot 特征（又称独热编码、一位有效编码）是把离散取值（类别）映射成二进制向量的最常用手段：
- 假设某特征有 N 个不同类别。
- 建立一个长度 = N 的全 0 向量。
- 样本属于第 i 类时，把向量的第 i 位置为 1，其余保持 0。
结果：每个类别对应唯一一个“1”位，所以叫 “one-hot”。
例子
特征“颜色”取值 {红, 绿, 蓝} → 3 维 one-hot 向量
- 红 → [1, 0, 0]
- 绿 → [0, 1, 0]
- 蓝 → [0, 0, 1]
）
两个关键问题：
- 哪些特征可以捆绑？ → 转化为图着色问题，特征是顶点，互斥关系是边；
- 如何合并特征？ → 为每个特征分配偏移量，使其值域不重叠，合并为一个新特征。
定理 4.1：寻找最优的互斥特征捆绑问题是 NP-难的。
贪心算法（算法 3）：
- 构建冲突图；
- 按度数降序排序特征；
- 遍历特征，尝试将其加入现有 bundle（冲突数 ≤ γ），否则新建 bundle。
合并算法（算法 4）：
- 为每个特征分配偏移量；
- 合并为一个新特征，保留原始特征值的可区分性。
复杂度：
- 捆绑阶段：O(#feature²)，仅执行一次；
- 合并后：直方图构建复杂度从 O(#data × #feature) 降为 O(#data × #bundle)，#bundle ≪ #feature。
（同样，对证明感兴趣的可以看原文。）
5 实验
5.1 数据集
| 数据集 | 样本数 | 特征数 | 类型 | 任务 | 指标 |
|---|---|---|---|---|---|
| Allstate | 12M | 4,228 | 稀疏 | 二分类 | AUC |
| Flight Delay | 10M | 700 | 稀疏 | 二分类 | AUC |
| LETOR | 2M | 136 | 稠密 | 排序 | NDCG@10 |
| KDD10 | 19M | 29M | 稀疏 | 二分类 | AUC |
| KDD12 | 119M | 54M | 稀疏 | 二分类 | AUC |
5.2 实验设置
- 对比方法：XGBoost（预排序 & 直方图）、lgb_baseline（无 GOSS/EFB）、SGB（随机采样）
- 参数：GOSS 采样率 a=0.05~ 0.1，b=0.05~0.1；EFB 冲突率 γ=0
- 线程数：16，迭代次数：固定，早停
5.3 结果
训练时间（每轮平均秒数）
| 数据集 | xgb_exa | xgb_his | lgb_baseline | EFB_only | LightGBM |
|---|---|---|---|---|---|
| Allstate | 10.85 | 2.63 | 6.07 | 0.71 | 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 | 2.85 |
| KDD12 | 191.99 | OOM | 168.26 | 20.23 | 12.67 |
- ==LightGBM 在所有数据集上均最快==，最高提速 21 倍（Allstate）
测试精度（AUC / NDCG@10）
| 数据集 | 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±8e-4 | 0.7846±4e-5 |
| LETOR | 0.4977 | 0.4982 | 0.5277 | 0.5239±6e-4 | 0.5275±5e-4 |
| KDD10 | 0.7796 | OOM | 0.78735 | 0.7759±3e-4 | 0.78732±1e-4 |
| KDD12 | 0.7029 | OOM | 0.7049 | 0.6989±8e-4 | 0.7051±5e-5 |
- LightGBM 精度==与最佳基线几乎一致==，无显著损失
5.4 GOSS 分析
- 提速：GOSS 单独带来约 2 倍提速；
- 精度：在相同采样率下，GOSS 精度 始终优于 SGB
5.5 EFB 分析
- 提速：EFB 在稀疏数据集上带来 显著提速（如 KDD10 上 6.3 倍）；
- 原因：减少特征数、避免零值计算、提升缓存命中率
6 结论
我们提出了 LightGBM，一种集成 GOSS 和 EFB 的高效 GBDT 实现。理论分析与实验结果表明：
- GOSS 能在减少样本的同时保持信息增益估计的准确性；
- EFB 能有效减少特征数，尤其适用于高维稀疏数据；
- LightGBM 在多个大规模数据集上实现了 最高 20 倍以上提速，且精度无损。
未来工作：
- 研究 GOSS 中 a、b 的最优选择策略；
- 进一步优化 EFB，使其适用于稠密特征场景。
Top comments (0)