LightGBM GOSS/EFB

LightGBM 用三项机制加速大样本高维训练。(1) 直方图算法: 每个连续特征离散化为 $k$ 个桶 (bin), 分裂只在桶边界上找切分点 — 分裂复杂度从预排序的 $O(n \cdot d)$ 降为 $O(k \cdot d)$, 内存从 $O(n \cdot d)$ 降到 $O(k \cdot d)$, 且父子节点的直方图可增量复用。(2) GOSS (Gradient-based One-Side Sampling, 单边梯度采样): 计算分裂增益时, 按样本梯度绝对值 $|g_i|$ 降序排列, 前 $a \times 100\%$ 的大梯度样本全部保留; 在剩余 $(1 - a) \times 100\%$ 的小梯度样本中随机采样 $b \times 100\%$, 并把被采样的小梯度样本权重放大 $\frac{1 - a}{b}$ 倍 — 增益用加权统计量估计, 期望与全量一致 (无偏), 计算量只剩 $(a + b)$ 比例 (如 $a = 0.2, b = 0.1$ 时只用约 30% 样本)。直觉: 梯度绝对值大 = 伪残差大 = 拟合不足的样本, 携带主要学习信号; 若等概率随机采样, 这些关键样本大概率被丢掉。(3) EFB (Exclusive Feature Bundling, 互斥特征捆绑): 稀疏数据里很多特征 (尤其 one-hot 编码) 互斥 — 几乎不同时取非零值; 把互斥特征捆成一个复合特征 (用图着色近似求解最小 bundles, 冲突度小于阈值即可捆绑), 特征数从 $d$ 降到 bundle 数, 直方图构建从 $O(\text{data} \times d)$ 降到 $O(\text{data} \times \text{bundles})$。另外 LightGBM 用 Leaf-wise 生长: 每次分裂当前增益最大的叶子 (配 max_depth 限制) — 比 Level-wise 逐层同步分裂收敛更快、误差更低, 但样本少时更易过拟合; 原生支持类别特征 (免 one-hot)。

“GOSS 与 EFB 原理”“Leaf-wise vs Level-wise”“直方图 vs 预排序”是高频追问; 工程上用于 CTR 预估、大规模排序等海量稀疏特征场景, 与 XGBoost 并列两大 GBDT 引擎。

XGBoost 精确贪心对每个特征预排序 ($O(n \log n)$ 每列) 且 Level-wise 全量遍历, 在样本与特征同时巨大时太慢 — GOSS 用约 30% 样本达到近似全量精度 (训练加速通常 5–10 倍且精度几乎不降); EFB 把特征数从 $d$ 压到 bundles (稀疏 one-hot 场景通常降 3–8 倍); 直方图把内存从 $O(n \cdot d)$ 降到 $O(k \cdot d)$ — 三项叠加构成 LightGBM 相对 XGBoost 的核心速度优势。

GOSS 原理与增益估计: 大梯度样本全保留 + 小梯度样本随机采样, 为什么小梯度样本权重要乘 $\frac{1-a}{b}$ 放大? (无偏估计)

为什么大梯度样本携带更多信息? 梯度 $g_i$ 与 GBDT 伪残差的关系

EFB 互斥特征捆绑: 什么是互斥特征? 冲突度如何度量? 特征数从 $d$ 降到 bundles 后复杂度下降多少?

Leaf-wise 与 Level-wise 生长策略对比: 为什么 Leaf-wise 更高效但更容易过拟合? 如何缓解 (max_depth)?

直方图算法 vs 预排序: 复杂度从 $O(n \cdot d)$ 到 $O(k \cdot d)$ 的内存与精度权衡; LightGBM vs XGBoost 总体对比