7.1 概述与核心创新
LightGBM(Light Gradient Boosting Machine)是由 微软亚洲研究院(Microsoft Research Asia) 的 Guolin Ke(柯国霖)等人与北京大学合作,于 2017 年在 NIPS 会议(NIPS 2017,即现在的 NeurIPS)上发表的高效梯度提升决策树系统(论文 LightGBM: A Highly Efficient Gradient Boosting Decision Tree)。作为 XGBoost 之后的又一里程碑式工作,LightGBM 不仅在训练速度上实现了数量级的提升,还在内存效率、高维稀疏数据处理、大规模数据场景等方面展现出卓越优势。
LightGBM 的四大核心技术构成了其高效性的基石:
- 直方图决策树(Histogram-based Decision Tree):将连续特征离散化为有限个 bin,在直方图上进行统计和分裂查找,把每个特征的分裂点查找从 $O(\#\text{data})$ 降到 $O(\#\text{bin})$(直方图构建本身仍是 $O(\#\text{data})$)。直方图算法并非 LightGBM 首创,它是 LightGBM 的基础,后面三项才是论文的新贡献。
- Leaf-wise(叶子优先)生长策略:每次选择分裂增益最大的叶子进行分裂,而非按层级均匀分裂。相同分裂次数下能达到更低的训练损失,收敛更快。
- GOSS(Gradient-based One-Side Sampling):基于梯度大小进行样本采样,保留所有大梯度样本,仅随机采样小梯度样本,并对小梯度样本乘以常数权重来补偿数据分布的变化,在大幅减少样本量的同时基本保持精度(论文给出了近似误差上界)。
- EFB(Exclusive Feature Bundling):识别高维稀疏数据中互斥的特征,将其捆绑为单一特征,显著减少特征维度,加速直方图构建和分裂查找。
核心洞察:LightGBM 并非简单地在 XGBoost 基础上做工程优化,而是从算法层面重新设计了树学习的基本流程——直方图替代预排序、Leaf-wise 替代 Level-wise、GOSS 和 EFB 分别从减少样本数和减少特征数两个方向降低直方图构建这一主要开销。这些创新使其在大规模数据(千万级样本、万级特征)上依然保持高效。
7.2 直方图决策树(Histogram-based Decision Tree)
7.2.1 核心思想:特征离散化到 k 个 bin
传统 GBDT 和 XGBoost 的精确贪心算法需要对每个特征的每个可能分割点进行排序遍历。当数据量达到百万级时,这一预排序过程成为主要瓶颈。LightGBM 的直方图算法从根本上改变了这一范式:将连续特征离散化为最多 $k$ 个 bin(参数 max_bin,默认 255),在离散后的 bin 上构建直方图进行统计,将分裂点查找的复杂度从 $O(\#\text{data})$ 降低到 $O(\#\text{bin})$。
具体来说,直方图算法分为两个阶段:
阶段一:直方图构建(Binning)
- 对每个连续特征,将取值范围划分为 $k$ 个离散区间(bin)。
- 使用子样本(参数
bin_construct_sample_cnt,默认 200,000 个样本)确定 bin 的边界(大致按等频/分位数划分)。 - 将原始浮点特征值映射为 bin 索引(整数)。LightGBM 会按
max_bin自动选择存储类型,例如max_bin=255时用uint8_t存储。
阶段二:直方图遍历(Split Finding)
- 对每个叶子节点,为每个特征构建直方图。
- 每个 bin 统计梯度之和 $\sum g_i$、Hessian 之和 $\sum h_i$ 和样本数(论文算法 1 只写了梯度和与样本数,实现中同时累加 Hessian)。
- 遍历所有 bin 计算分裂增益,找出最优分裂点。
7.2.2 算法流程
LightGBM 直方图算法的完整流程如下:
- 特征离散化:对于每个连续特征,基于训练数据的分位数将其划分为 $k$ 个 bin。
- 样本映射:将每个样本的原始特征值替换为对应的 bin 索引。
- 直方图构建:对于当前节点的每个特征,初始化一个长度为 $k$ 的直方图数组。
- 统计聚合:遍历节点中的所有样本,根据样本的 bin 索引,将 $g_i$、$h_i$ 累加到对应 bin 中。
- 分裂查找:遍历直方图的每个 bin 边界作为候选分裂点,计算增益,选择最优分裂。
- 递归分裂:对子节点重复步骤 3-5,直到满足停止条件。
7.2.3 复杂度分析(与预排序算法对比)
| 阶段 | 预排序算法(XGBoost exact) | 直方图算法(LightGBM) | 优势说明 |
|---|---|---|---|
| 数据预处理 | $O(\#\text{data} \times \#\text{feature} \times \log \#\text{data})$ | 分桶:对采样数据确定边界后线性映射 | 无需对全量数据排序 |
| 直方图构建(每节点) | 无此步骤 | $O(\#\text{data} \times \#\text{feature})$ | 只是简单累加,但仍是主要开销 |
| 分裂点查找(每节点) | $O(\#\text{data} \times \#\text{feature})$ | $O(\#\text{bin} \times \#\text{feature})$ | $\#\text{bin} \ll \#\text{data}$(默认255 vs 百万) |
| 内存占用 | 原始浮点值 + 预排序索引 | 只存 bin 索引(如 uint8_t),无需预排序信息 | 内存大幅降低 |
| 缓存友好性 | 差(随机访问梯度统计量) | 优(顺序访问直方图数组) | 提升缓存命中率 |
| GPU 加速 | 复杂 | 天然适合 | 直方图聚合适合并行化 |
由于 $\#\text{bin}$(默认 255)远小于 $\#\text{data}$(通常百万级),分裂点查找这一步的开销几乎可以忽略:在 1000 万样本的数据集上,预排序需要逐个检查约 1000 万个候选点,而直方图只需扫描 255 个 bin 边界。但整体训练并不会因此快上万倍,因为构建直方图仍要遍历节点内的每个样本,复杂度为 $O(\#\text{data} \times \#\text{feature})$。论文指出这一步主导了总开销,所以 LightGBM 又分别用 GOSS 减少样本数($\#\text{data}$)、用 EFB 减少特征数($\#\text{feature}$)。
7.2.4 直方图做差加速(Histogram Subtraction)
LightGBM 利用二叉树的结构特性,提出直方图做差加速技术。在二叉树中,父节点直方图等于左右子节点直方图之和:
$$ \mathrm{Hist}_{\text{parent}} = \mathrm{Hist}_{\text{left}} + \mathrm{Hist}_{\text{right}} $$(这里用 $\mathrm{Hist}$ 表示直方图,以免与 Hessian 之和 $H$ 混淆;等式对每个 bin 的梯度和、Hessian 和、样本数逐项成立。)因此,对于每次分裂,只需构建数据量较小的一侧子节点的直方图,另一侧通过父节点直方图减去已构建子节点直方图得到:
$$ \mathrm{Hist}_{\text{sibling}} = \mathrm{Hist}_{\text{parent}} - \mathrm{Hist}_{\text{node}} $$优势分析:
- 传统方法:每次分裂要为两个子节点各遍历一次样本来构建直方图,工作量与父节点样本数成正比。
- 做差加速:只遍历样本较少的那个子节点,工作量不超过父节点样本数的一半,另一侧通过减法获得,直方图构建的样本遍历量至少节省一半。
- 减法复杂度仅 $O(\#\text{bin} \times \#\text{feature})$,与样本数无关,远低于重新构建直方图。
这一优化在 Leaf-wise 生长策略下同样适用:每次分裂一个叶子后,只需为两个新叶子中样本较少的那个构建直方图。
7.2.5 离散化的正则化效果
直方图离散化不仅加速计算,还具有意想不到的正则化效果:
- 减少过拟合:将连续值压缩到有限 bin,相当于对特征进行了量化,减少了模型对训练数据中微小波动的敏感度。
- 量化噪声(直观理解):离散化会让分裂点不那么精确;但每棵树只是集成中的一个弱学习器,粗糙一些的分裂点对最终精度的影响通常有限,有时还能减少对训练数据细微波动的拟合。
- 官方文档的说法:
max_bin较小可能降低训练集精度,但可能提升泛化能力(缓解过拟合)。是否真能提升要看数据,需通过验证集确认。
7.3 Leaf-wise(叶子优先)生长策略
7.3.1 与 Level-wise(层级优先)的详细对比
传统树提升算法(包括 XGBoost 默认的 grow_policy='depthwise')采用 Level-wise(层级优先) 生长策略:树按层级生长,每一层的所有节点同时分裂。LightGBM 采用 Leaf-wise(叶子优先,也称 best-first) 策略:每次从所有当前叶子中选择分裂增益(损失下降)最大的叶子进行分裂。这一策略源自 best-first 决策树(Shi, 2007),XGBoost 的 hist / approx 方法也可通过 grow_policy='lossguide' 使用。
graph TD
subgraph LevelWise["Level-wise: 按层生长,同层所有节点同时分裂"]
A1["Root"] --> B1["Level 1"]
A1 --> B2["Level 1"]
B1 --> C1["Level 2"]
B1 --> C2["Level 2"]
B2 --> C3["Level 2"]
B2 --> C4["Level 2"]
end
subgraph LeafWise["Leaf-wise: 每次只分裂增益最大的叶子"]
A2["Root"] --> B3["Gain=0.8"]
A2 --> B4["Gain=0.3"]
B3 --> C5["Gain=0.6"]
B3 --> C6["Gain=0.5"]
B4 --> C7["..."]
B4 --> C8["..."]
end
style A1 fill:#f9f,stroke:#333
style A2 fill:#f9f,stroke:#333
| 维度 | Level-wise(层级优先) | Leaf-wise(叶子优先) |
|---|---|---|
| 生长方式 | 按层分裂,同层所有节点同时分裂 | 每次只分裂增益最大的叶子 |
| 树结构 | 平衡树,各层节点均匀 | 非平衡树,某分支可能很深 |
| 收敛速度 | 较慢,存在无效分裂(增益很小的节点也被强制分裂) | 更快,专注高增益分裂,每次分裂带来最大损失降低 |
| 过拟合风险 | 较低(树的深度可控) | 较高(需配合 max_depth 或 num_leaves 限制) |
| 相同叶子数下的训练损失 | 较高 | 通常更低(官方文档:固定 #leaf 时 Leaf-wise 往往得到更低的损失) |
| 代表实现 | XGBoost(默认 depthwise)、sklearn GradientBoosting* | LightGBM、XGBoost(lossguide)、sklearn HistGradientBoosting* |
| 适用场景 | 小规模数据、需要平衡树结构 | 大规模数据、追求训练效率 |
7.3.2 分裂增益公式
Leaf-wise 策略下的分裂增益与 XGBoost 的增益(XGBoost 6.3.6)本质相同,都来自二阶近似。LightGBM 源码中叶子的得分写作 $\frac{G^2}{H+\lambda}$,没有 $\frac{1}{2}$ 因子,分裂增益为:
$$ \mathrm{Gain} = \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} $$只有当 $\mathrm{Gain}$ 大于 min_gain_to_split(默认 0)时才分裂。其中 $G_L, G_R$ 为左右子节点梯度之和,$H_L, H_R$ 为 Hessian 之和,$\lambda$ 对应参数 lambda_l2(默认 0,而 XGBoost 的 lambda 默认为 1)。设置 lambda_l1 时,与 XGBoost 一样把 $G$ 换成软阈值 $\operatorname{sign}(G)\max(\lvert G \rvert - \lambda_1, 0)$。
因为少了 $\frac{1}{2}$,同样的分裂在 LightGBM 中算出的增益是 XGBoost 方括号部分的 2 倍,所以
min_gain_to_split与 XGBoost 的gamma数值上不能直接互换。
Leaf-wise 的核心是:在所有候选叶子中,选择使上式增益最大的叶子进行分裂。这与 Level-wise 的"平均主义"形成鲜明对比——Level-wise 不加区分地分裂同层所有节点,即使某些节点的分裂增益很小。
7.3.3 为什么更快但需要控制深度
更快的根本原因:
- 资源集中:Level-wise 是平均主义,即使某些节点分裂增益很小(如增益接近0)也会被强制分裂,造成计算浪费。Leaf-wise 将计算资源集中在最有潜力的叶子节点,每次分裂都带来最大损失降低。
- 相同分裂次数下损失更低:在相同分裂次数(即相同计算量)下,Leaf-wise 通常能达到更低的训练损失,因为它优先处理"最需要分裂"的区域。
- 高效利用直方图:Leaf-wise 与直方图做差加速天然契合,因为每次只分裂一个叶子,直方图只需为该叶子及其子节点构建。
过拟合风险与控制:
- Leaf-wise 可能产生深度极不平衡的树,某些分支很深(对小数据区域过拟合),而另一些分支很浅。
- 如果不加控制,Leaf-wise 可能产生仅包含几个样本的深叶子,导致对小数据集的过拟合。
LightGBM 通过以下参数控制过拟合:
| 参数 | 默认值 | 作用 |
|---|---|---|
max_depth | -1(无限制) | 树的最大深度,限制树的生长深度 |
num_leaves | 31 | 最大叶子数,Leaf-wise的主要复杂度控制参数 |
min_data_in_leaf | 20 | 叶子最小样本数,防止叶子过于稀疏 |
min_sum_hessian_in_leaf | 0.001 | 叶子最小Hessian和,控制叶子置信度 |
经验法则:深度为 $d$ 的二叉树最多有 $2^d$ 个叶子,所以同时设置两者时应满足 num_leaves <= 2^max_depth。例如,当 max_depth = 7 时,num_leaves 超过 128 就没有意义。官方调参文档建议实际取值明显小于 $2^{\text{max\_depth}}$。注意即使设置了 max_depth,树仍按 Leaf-wise 方式生长,max_depth 只是额外的上限。
7.4 GOSS(Gradient-based One-Side Sampling)
7.4.1 核心思想:梯度大的样本贡献更大
GOSS 的核心洞察来源于对梯度分布的观察:在 Gradient Boosting 的每一轮迭代中,样本的梯度绝对值大小反映了模型对该样本的拟合程度。梯度绝对值大的样本是模型"还没学好"的样本(under-trained),而小梯度样本已被较好拟合。因此,大梯度样本对信息增益计算的贡献更大。
GOSS 的采样策略:
- 保留所有大梯度样本(梯度绝对值最大的 $a \times 100\%$ 样本)。
- 随机采样小梯度样本(从剩余样本中随机选取 $b \times 100\%$)。
- 通过常数乘子修正小梯度样本的权重,保持信息增益估计的无偏性。
这一策略使得 GOSS 每轮只用约 $(a + b) \times 100\%$ 的样本建树。LightGBM 中 $a$、$b$ 分别对应参数 top_rate(默认 0.2)和 other_rate(默认 0.1),即默认每轮使用 30% 的样本;论文实验中用的是 $a=b=0.05$ 或 $a=b=0.1$,精度与全数据训练几乎相同。
7.4.2 算法流程(伪代码)
flowchart TD
A["输入: 训练集 I, 参数 a, b"] --> B["计算所有样本的梯度 g_i"]
B --> C["按梯度绝对值降序排序"]
C --> D["topSet = 前 a * len(I) 个样本"]
C --> E["剩余样本中随机选 b * len(I) 个"]
D --> F["usedSet = topSet + randSet"]
E --> F
F --> G["给randSet样本乘权重修正因子 (1-a)/b"]
G --> H["在usedSet上构建树"]
H --> I{"满足停止条件?"}
I -->|否| B
I -->|是| J["输出最终模型"]
伪代码:
- 输入:训练数据 $I$,大梯度采样比例 $a$,小梯度采样比例 $b$
- 计算权重修正因子:$fact \leftarrow (1-a)/b$
- 计算大梯度样本数:$topN \leftarrow a \times |I|$
- 计算随机采样数:$\mathit{randN} \leftarrow b \times \lvert I \rvert$
- 对于每次迭代:
- 计算所有样本的梯度 $g_i$
- 按梯度绝对值降序排序,得到索引数组 $\mathit{sorted}$
- $\mathit{topSet} \leftarrow \mathit{sorted}[1:\mathit{topN}]$ // 保留大梯度样本
- $\mathit{randSet} \leftarrow \operatorname{RandomPick}(\mathit{sorted}[\mathit{topN}+1:\mathit{end}],\ \mathit{randN})$ // 随机采样小梯度
- $\mathit{usedSet} \leftarrow \mathit{topSet} \cup \mathit{randSet}$
- 初始化权重 $w_i \leftarrow 1$(对所有样本)
- 对于 $\mathit{randSet}$ 中的每个样本:$w_i \leftarrow w_i \times \mathit{fact}$ // 修正小梯度样本权重
- 使用加权样本 $(\mathit{usedSet}, -g_{\mathit{usedSet}}, w_{\mathit{usedSet}})$ 构建树
- 输出最终模型
实现细节(LightGBM 源码
src/boosting/goss.hpp)
- 排序依据是 $\lvert g_i h_i \rvert$ 而不是单纯的 $\lvert g_i \rvert$;对平方损失($h_i$ 为常数)两者等价。
- 修正因子 $\frac{1-a}{b}$ 同时乘在被采样小梯度样本的梯度和 Hessian 上。
- 前 $\lfloor 1/\text{learning\_rate} \rfloor$ 轮不做 GOSS 采样(例如学习率 0.1 时前 10 轮用全部数据),因为训练初期梯度普遍较大,采样意义不大。
- 4.0 版起 GOSS 通过
data_sample_strategy='goss'启用;旧写法boosting='goss'仍兼容,但会给出警告并被解释为boosting='gbdt'+data_sample_strategy='goss'。
7.4.3 信息增益修正公式
GOSS 对采样后的样本集合估计信息增益,引入常数 $\frac{1-a}{b}$ 把 $B$ 上的梯度和放大回整个小梯度集合 $A^c$ 的规模,使估计近似无偏。
论文用方差增益衡量分裂质量。在某个节点的样本集合 $O$ 上,以特征 $j$ 的阈值 $d$ 分裂时:
$$ V_{j\mid O}(d) = \frac{1}{n_O}\left[\frac{\left(\sum_{\{x_i \in O:\, x_{ij} \le d\}} g_i\right)^2}{n_{l\mid O}^j(d)} + \frac{\left(\sum_{\{x_i \in O:\, x_{ij} > d\}} g_i\right)^2}{n_{r\mid O}^j(d)}\right] $$其中 $n_O$ 为节点样本数,$n_{l\mid O}^j(d)$、$n_{r\mid O}^j(d)$ 为左右两侧样本数。它相当于把 XGBoost 中的 $\frac{G^2}{H+\lambda}$ 取 $h_i = 1$、$\lambda = 0$。
设 $A$ 为大梯度样本集合(保留全部,比例 $a$),$A^c$ 为其余样本,$B$ 为从 $A^c$ 中随机采样的子集(大小为 $b \times n$)。$A_l = \{x_i \in A \mid x_{ij} \leq d\}$,$A_r = \{x_i \in A \mid x_{ij} > d\}$ 为 $A$ 在分裂点 $d$ 左右的分裂。类似定义 $B_l, B_r$。
GOSS 的信息增益估计为:
$$ \tilde{V}_j(d) = \frac{1}{n}\left[ \frac{\left(\sum_{x_i \in A_l} g_i + \frac{1-a}{b} \sum_{x_i \in B_l} g_i\right)^2}{n_l^j(d)} + \frac{\left(\sum_{x_i \in A_r} g_i + \frac{1-a}{b} \sum_{x_i \in B_r} g_i\right)^2}{n_r^j(d)} \right] $$符号表:
| 符号 | 含义 |
|---|---|
| $A$ | 大梯度样本集合(保留全部,比例 $a$) |
| $B$ | 从小梯度样本中随机采样的子集(比例 $b$) |
| $A_l, A_r$ | 大梯度样本在分裂点左右的分裂 |
| $B_l, B_r$ | 小梯度采样样本在分裂点左右的分裂 |
| $\frac{1-a}{b}$ | 权重补偿因子:$B$ 中样本数是 $bn$,而它代表的 $A^c$ 有 $(1-a)n$ 个样本,放大后梯度和的期望与 $A^c$ 上的真实梯度和一致 |
| $n_l^j(d), n_r^j(d)$ | 分裂点 $d$ 左右两侧的样本数 |
理论保证:原始论文定理 3.2 证明,GOSS 的近似误差以至少 $1-\delta$ 概率满足:
$$ \mathcal{E}(d) \leq C_{a,b}^2 \ln\frac{1}{\delta} \cdot \max\left\{\frac{1}{n_l^j(d)}, \frac{1}{n_r^j(d)}\right\} + 2DC_{a,b}\sqrt{\frac{\ln(1/\delta)}{n}} $$其中近似误差 $\mathcal{E}(d) = \left\lvert \tilde{V}_j(d) - V_j(d) \right\rvert$,$C_{a,b} = \frac{1-a}{\sqrt{b}} \max_{x_i \in A^c} \lvert g_i \rvert$,$D = \max\left(\bar{g}_l^j(d), \bar{g}_r^j(d)\right)$,$\bar{g}_l^j(d)$、$\bar{g}_r^j(d)$ 分别为左右两侧梯度绝对值的平均。
关键结论:误差的渐近阶为 $O\left(\frac{1}{n_l^j(d)} + \frac{1}{n_r^j(d)} + \frac{1}{\sqrt{n}}\right)$。只要分裂不过于不平衡($n_l^j(d)$、$n_r^j(d) \ge O(\sqrt{n})$),误差主要由第二项决定,并随 $n$ 增大以 $O(1/\sqrt{n})$ 的速度趋于 0,也就是说数据量很大时 GOSS 的近似相当准确。论文还说明,随机采样是 $a=0$ 时的特例,在很多情况下 GOSS 的误差更小。
7.4.4 与 AdaBoost 采样策略的对比
| 特性 | AdaBoost 采样 | GOSS |
|---|---|---|
| 权重基础 | 样本权重(前序分类器错误率决定) | 梯度绝对值(当前模型拟合残差决定) |
| 采样策略 | 直接按权重加权训练(reweighting),或按权重有放回重采样(resampling) | 保留大梯度样本,随机采样小梯度样本 |
| 适用算法 | AdaBoost / 加权 Boosting | GBDT / LightGBM(用梯度大小近似识别更有信息量的样本) |
| 修正机制 | 无显式修正(权重自然归一化) | 显式常数乘子 $(1-a)/b$ 修正信息增益 |
| 理论保证 | 训练误差随轮数指数下降的上界 | 方差增益估计的近似误差上界(定理 3.2) |
| 核心思想 | 关注被错分的困难样本 | 关注模型未充分拟合的样本(大梯度) |
AdaBoost 的样本权重直接反映错分累积程度;GBDT 虽然也可以接收外部样本权重,但每轮“哪些样本最需要被关注”通常由当前损失的梯度体现。GOSS 利用梯度绝对值作为信息量大小的近似指标,既保留了“关注困难样本”的直觉,又适配了 GBDT 的梯度优化框架。
7.5 EFB(Exclusive Feature Bundling)
7.5.1 核心思想:互斥特征捆绑
EFB 解决的是高维稀疏数据中的特征冗余问题。现实数据中,尤其是经过 one-hot 编码或词袋表示后的数据,特征维度极高但极其稀疏。许多特征是互斥(mutually exclusive)的——即很少在同一行同时取非零值。例如:
- One-hot 编码后的类别特征:每行只有一个值为 1,其余为 0。
- 文本挖掘中的词袋表示:每篇文档只包含少量词汇。
EFB 将互斥特征捆绑成单一特征,在不损失信息的前提下减少特征维度,从而加速直方图构建和分裂查找。
7.5.2 冲突图 + 贪心 Bundling 算法
原始论文证明(定理 4.1):将特征划分为最少数量的互斥捆绑问题是 NP-hard。证明思路是将图着色问题归约到该问题:对任意图 $G=(V,E)$,为每个顶点构造一个特征,有边相连的两个特征会在某些样本上同时非零(即冲突),于是同一种颜色的顶点集合恰好对应一个互斥捆绑。
由于精确解难求,LightGBM 采用贪心近似算法:
flowchart TD
A["输入: 特征集合 F"] --> B["构建冲突图 G=(V,E)"]
B --> C["按度数降序排序特征"]
C --> D["初始化 bundles 为空列表"]
D --> E{"还有未分配特征?"}
E -->|是| F["取下一个特征 f"]
F --> G["寻找冲突最小的 bundle"]
G --> H{"冲突是否不超过阈值?"}
H -->|是| I["将 f 加入该 bundle"]
H -->|否| J["新建 bundle 包含 f"]
I --> E
J --> E
E -->|否| K["输出 bundles"]
伪代码:
- 输入:特征集合 $F$,最大冲突数 $K$(论文正文用每个 bundle 的最大冲突率 $\gamma$ 描述允许的冲突程度,并说明随机污染少量特征值对训练精度的影响至多为 $O\left([(1-\gamma)n]^{-2/3}\right)$,所以 $\gamma$ 较小时可以较好地兼顾精度与效率)
- 构建冲突图 $G = (V, E)$:
- 每个特征对应一个顶点
- 如果特征 $i$ 和 $j$ 在某些行同时非零,则添加边 $(i,j)$,边权为冲突次数
- 按顶点在图中的度数降序排序特征
- 初始化:$\mathit{bundles} \leftarrow []$,以及每个 bundle 的累计冲突数
- 对于排序后的每个特征 $f$:
- 依次检查已有的每个 bundle:若 $f$ 与该 bundle 的冲突数加上该 bundle 已有的冲突数 $\le K$,就把 $f$ 加入这个 bundle,并停止检查
- 如果没有任何 bundle 能容纳 $f$:新建一个只含 $f$ 的 bundle
- 输出:$\mathit{bundles}$
论文中这一步是“放进第一个满足条件的 bundle”(first-fit),不是在所有 bundle 中找冲突最小的。
复杂度分析:
- 贪心捆绑(论文算法 3)的时间复杂度为 $O(\#\text{feature}^2)$,只在训练前执行一次。
- 特征数达到百万级时这仍然很慢,论文因此给出更快的变体:不建图,直接按特征的非零值个数降序排序(非零值越多,越可能发生冲突,效果与按度数排序类似)。
- 论文主实验取 $\gamma = 0$,即不允许冲突。LightGBM 4.x 中 EFB 由
enable_bundle(默认true)开关控制,没有对外暴露冲突率参数(在 4.7.0 中设置max_conflict_rate会提示 Unknown parameter)。
7.5.3 为什么类别特征 One-Hot 编码后天然互斥
One-hot 编码将 $K$ 个类别的特征转换为 $K$ 个二元特征:
- 对于任意样本,$K$ 个特征中恰好一个为 1,其余为 0。
- 因此 $K$ 个特征两两完全互斥(冲突率为 0)。
- EFB 可将 $K$ 个特征捆绑为一个,特征数从 $K$ 减少到 1。
论文实验表明,在包含大量 one-hot 或其他稀疏特征的数据集(如 KDD Cup 2010/2012)上,EFB 可带来显著加速。除 one-hot 特征外,EFB 也能捆绑那些“隐式互斥”的稀疏特征。
7.5.4 特征偏移(Offset)技术
将多个特征捆绑为一个后,需要区分不同原始特征的值。LightGBM 使用 Offset(偏移) 方法解决这一问题。
假设捆绑两个特征:
- 特征 A:取值范围 $[0, 10)$
- 特征 B:取值范围 $[0, 20)$
给特征 B 添加偏移量 10,使其取值范围变为 $[10, 30)$。合并后捆绑特征取值范围为 $[0, 30)$(论文中写作 $[0, 30]$),直方图可清楚区分每个值来自哪个原始特征。
一般化公式:
$$ \text{newBin}[i] = \begin{cases} F[j].\text{bin}[i] + \text{binRanges}[j] & \text{if } F[j].\text{bin}[i] \neq 0 \\ 0 & \text{if } F[j].\text{bin}[i] = 0 \text{ for all } j \end{cases} $$其中累积偏移量 $\text{binRanges}$ 由各特征的 bin 数依次累加得到:
$$ \text{binRanges} = \left[0,\ \#\text{bin}(F_1),\ \#\text{bin}(F_1)+\#\text{bin}(F_2),\ \dots\right] $$由于 bundle 内的特征互斥,每个样本至多有一个特征非零,所以 $\text{newBin}[i]$ 是唯一确定的(论文算法 4;有少量冲突时,后处理的特征会覆盖先前的值)。所有特征的 0 值共用捆绑特征的 0 号 bin。
示例(假设 0 号 bin 表示零值,各特征的非零 bin 依次排在后面):
| 原始特征 | 非零取值的 bin | 偏移量 | 捆绑后对应的 bin |
|---|---|---|---|
| F1 | $1 \sim 2$ | 0 | $1 \sim 2$ |
| F2 | $1 \sim 3$ | 2 | $3 \sim 5$ |
| F3 | $1 \sim 4$ | 5 | $6 \sim 9$ |
捆绑特征共有 $1 + 2 + 3 + 4 = 10$ 个 bin(共用的 0 号 bin 加上三个特征各自的非零 bin),三个特征的取值区间互不重叠。
7.5.5 实际效果
原始论文实验(表 2,单轮迭代平均耗时)表明:
- 只加 EFB 时(EFB_only 对比 lgb_baseline),稀疏的大数据集上加速明显:Allstate 约 $8.5\times$(每轮从 6.07 s 降到 0.71 s),KDD10 约 $6.3\times$,KDD12 约 $8.3\times$,Flight Delay 约 $5.1\times$;稠密的 LETOR 数据集几乎没有变化(从 0.49 s 到 0.46 s)。这些数据集的特征维度从 136(LETOR)到 5400 万(KDD12)不等。
- 再加上 GOSS(即完整的 LightGBM),使用 10%–20% 的数据时,GOSS 自身又带来接近 $2\times$ 的加速。
- EFB 不需要在建树时为每个稀疏特征额外维护非零数据表,节省了内存。
- 原本分散的特征被捆绑在一起,提高了空间局部性,显著改善缓存命中率。
7.6 类别特征处理
LightGBM 对类别特征提供了原生支持,无需手动进行 one-hot 编码。这一设计在高基数类别特征(如用户ID、商品ID)场景下尤为重要,因为 one-hot 编码会产生高维稀疏特征,既不高效也易造成过拟合。
核心处理机制
类别值需编码为非负整数:通过
categorical_feature指定类别特征。LightGBM 核心库要求类别取值为整数(会被转成int32,负值视为缺失,最好是从 0 开始的连续整数),不会自动把字符串映射成整数。Python 包中若输入是 pandas DataFrame 且列为category类型,会自动提取其整数编码,此时可直接使用categorical_feature='auto'(默认;最新文档说明只自动识别无序的 category 列,有序的会按数值处理)。预测时遇到训练中没见过的类别会按缺失值处理。基于统计的分裂:对于类别特征,LightGBM 不寻找单个数值分裂点,而是把类别集合划分为两个子集。$k$ 个类别共有 $2^{k-1}-1$ 种二划分,逐一枚举不可行;但对回归树存在高效解法(Fisher, 1958),约 $O(k \log k)$ 即可找到最优划分。具体来说:
- 在当前节点上,统计每个类别的梯度和 $G_c$ 与 Hessian 和 $H_c$。
- 按 $\frac{G_c}{H_c + \text{cat\_smooth}}$ 对类别排序(官方文档描述为按
sum_gradient / sum_hessian排序,实现中分母加了平滑项cat_smooth)。 - 在排序后的类别序列上像连续特征一样从两端扫描切分点,找出最优的两子集划分。
- 类别数不超过
max_cat_to_onehot(默认 4)时改用 one-vs-rest 分裂(一个类别对其余类别)。
与类别分裂相关的正则化参数:
cat_smooth(默认 10,减小小类别的噪声)、cat_l2(默认 10,类别分裂时额外的 L2 正则)、max_cat_threshold(默认 32,限制类别分裂时考虑的切分点数量)、min_data_per_group(默认 100,每个类别组的最少样本数)。官方文档建议,样本少或类别数多时用min_data_per_group、cat_smooth抑制过拟合;对类别数非常多的特征,直接把整数编码当作数值特征处理往往效果更好。避免 one-hot 的高维灾难:对于高基数类别特征(如百万级用户ID),one-hot 编码会产生百万维稀疏矩阵。LightGBM 将其作为单一特征处理,直方图 bin 数等于类别数(或受限的最大 bin 数),内存和计算效率远高于 one-hot 方案。
使用方式:
| |
7.7 并行学习与内存优化
以下内容依据 LightGBM 官方文档 Features 中的 “Optimization in Distributed Learning” 一节。并行方式由参数 tree_learner 选择:serial(默认,单机)、feature、data、voting。
7.7.1 特征并行(Feature Parallel,tree_learner='feature')
传统特征并行:数据按列(特征)切分到不同 worker。各 worker 在自己的特征子集上找局部最优分裂,相互通信得到全局最优分裂;持有该特征的 worker 执行分裂,再把“每个样本去左还是去右”的划分结果发给其他 worker。缺点有两个:分裂操作本身是 $O(\#\text{data})$,无法被并行加速;划分结果的通信量约为 $O(\#\text{data}/8)$(每个样本 1 bit)。
LightGBM 的特征并行:每个 worker 都持有完整数据,只是各自负责搜索不同的特征子集:
- 各 worker 在本地负责的特征上寻找最优分裂点 {feature, threshold}。
- 相互通信,得到全局最优分裂。
- 每个 worker 都在本地执行这个分裂(因为都有完整数据,不需要传输划分结果)。
由于分裂操作仍是 $O(\#\text{data})$,样本数很大时特征并行加速有限,此时应使用数据并行。
7.7.2 数据并行(Data Parallel,tree_learner='data')
传统数据并行:数据按行切分,各 worker 用本地数据构建本地直方图,合并成全局直方图后寻找最优分裂。缺点是通信量大:点对点通信时每台机器约为 $O(\#\text{machine} \times \#\text{feature} \times \#\text{bin})$,用 All Reduce 等集合通信约为 $O(2 \times \#\text{feature} \times \#\text{bin})$。
LightGBM 的数据并行优化:
- Reduce Scatter 代替全量合并:不同 worker 负责合并不同(互不重叠)特征的直方图,各自在合并后的直方图上找局部最优分裂,再同步得到全局最优分裂。
- 结合直方图做差:每次分裂只需通信样本较少的那个子节点的直方图,另一个子节点用减法得到。
- 综合起来,通信代价约为 $O(0.5 \times \#\text{feature} \times \#\text{bin})$。
7.7.3 投票并行(Voting Parallel,tree_learner='voting')
投票并行进一步把数据并行的通信量降到与特征数无关的常数级别。它来自 PV-Tree(Meng et al., NIPS 2016),采用两阶段投票:
- 局部投票:每个 worker 根据本地数据选出增益最高的 top-$k$ 个特征(参数
top_k,默认 20)。 - 全局投票:汇总各 worker 的投票,按得票数选出全局 top-$2k$ 个候选特征。
- 只收集这 $2k$ 个特征的完整直方图,合并后确定最优分裂。
top_k 越大结果越准确,但训练越慢。官方并行学习指南(Distributed Learning Guide)给出的选择建议:样本少时用特征并行;样本多、特征少时用数据并行;样本和特征都多时用投票并行。
7.7.4 内存优化总结
| 优化技术 | 机制 | 效果 |
|---|---|---|
| 直方图存储 | 用 uint8 存储 bin 索引 | 相比 float32 存储原始值,内存降低 75% |
| 直方图做差 | 父节点直方图减子节点直方图 | 直方图构建的样本遍历量至少减半 |
| EFB | 捆绑互斥特征 | 特征维度降低,直方图构建次数减少 |
| GOSS | 采样小梯度样本 | 每轮建树只用约 $(a+b)$ 比例的样本(默认 $0.2+0.1$,即减少 70%) |
| 类别特征原生支持 | 避免 one-hot 高维稀疏 | 高基数类别场景内存大幅降低 |
7.8 LightGBM在Kaggle和实际应用中的表现
LightGBM 自 2017 年发布以来,迅速成为 Kaggle 竞赛和工业界的主流工具之一。
Kaggle 竞赛表现:
- 在大量结构化数据竞赛中,LightGBM 与 XGBoost 并列为首选基线模型。
- 由于训练速度更快,在需要快速迭代和大量模型实验的竞赛中优势明显。
- 在内存受限的环境(如 Kaggle Notebook)中,LightGBM 的内存效率使其能处理更大规模数据。
工业界应用:
- 广告点击率预测(CTR):处理大规模、高维稀疏的广告特征正是 GOSS 和 EFB 的设计目标,LightGBM 常用于 CTR 预估。
- 推荐系统:作为特征交互模型,处理用户-商品高维稀疏特征。
- 金融风控:信用评分、欺诈检测等场景,LightGBM 训练高效,并可配合特征重要性、SHAP 值(
predict(..., pred_contrib=True))解释模型,是常用方案之一。 - 时间序列预测:结合适当的特征工程,LightGBM 在多种时间序列竞赛中表现出色。
与 XGBoost 的对比选择(经验性的粗略参考,样本量阈值并无严格界限,详细对比见 算法对比与选择决策):
- 数据量较小(< 10,000 样本)时,两者差异不大;XGBoost 的精确贪心可能略优。
- 数据量中等(10,000 - 100,000)时,LightGBM 的速度优势开始显现。
- 数据量较大(> 100,000 或高维稀疏)时,LightGBM 通常训练更快、内存更省,是首选。
- 对模型精度有极致要求的场景,两者可分别调参后做模型融合(Stacking)。
7.9 Python API与关键参数详解
LightGBM 提供两种 Python 接口:原生 lgb.train 接口和 scikit-learn 兼容接口。
原生接口(lgb.train)
| |
Scikit-Learn兼容接口
| |
在 LightGBM 4.7.0 中,sklearn 接口
fit()的eval_set参数会给出弃用警告,新写法是关键字参数eval_X=..., eval_y=...;更早的版本只支持eval_set,所以本文代码仍用eval_set,两种写法目前都能运行。另外,sklearn 接口在早停后predict/predict_proba会自动使用best_iteration_。
关键参数详解
| 参数 | 含义 | 默认值 | 调参建议 |
|---|---|---|---|
num_leaves | 最大叶子数 | 31 | Leaf-wise核心参数,控制模型复杂度。若记 max_depth 为 $d$,不应超过 $2^d$,实践中通常明显小于 $2^d$。 |
max_depth | 树最大深度 | -1 | 限制过拟合,$\le 0$ 表示无限制。通常设为 5-10。 |
learning_rate | 学习率 | 0.1 | 典型值 0.01-0.3。较小的值配合更多的 n_estimators。 |
min_data_in_leaf | 叶子最小样本数 | 20 | 防止过拟合,大数据集可增大,小数据集可减小。sklearn 接口中名为 min_child_samples。 |
feature_fraction | 列采样比例 | 1.0 | 每棵树随机选取的特征比例,防止过拟合,典型值 0.8。sklearn 接口中名为 colsample_bytree;按节点采样用 feature_fraction_bynode。 |
bagging_fraction | 行采样比例 | 1.0 | 不放回地随机选取的样本比例,需配合 bagging_freq > 0 才生效。sklearn 接口中名为 subsample。 |
bagging_freq | 行采样频率 | 0 | 每多少轮重新采样一次,0 表示不执行 bagging。sklearn 接口中名为 subsample_freq。 |
lambda_l1 / reg_alpha | L1正则化 | 0.0 | 产生稀疏权重,类似 Lasso。 |
lambda_l2 / reg_lambda | L2正则化 | 0.0 | 惩罚大权重,防止过拟合。典型值 0.1-10。 |
cat_smooth | 类别特征平滑 | 10 | 处理类别特征的平滑参数,防止低频次类别过拟合。 |
max_bin | 最大直方图 bin 数 | 255 | 增大可提升精度但增加计算量,减少可正则化。 |
min_gain_to_split | 最小分裂增益 | 0.0 | 增益低于此值不分裂(含义类似 XGBoost 的 gamma,但数值尺度不同,见 7.3.2)。 |
data_sample_strategy | 样本采样策略 | bagging | bagging(随机行采样)或 goss;4.0 版新增。top_rate(默认 0.2)、other_rate(默认 0.1)为 GOSS 的 $a$、$b$。 |
boosting_type | 提升类型 | gbdt | gbdt(标准梯度提升)、dart(Dropouts meet Multiple Additive Regression Trees)、rf(随机森林)。旧版的 goss 选项已改为 data_sample_strategy='goss'。 |
7.10 伪代码与实现细节
LightGBM 整体训练流程
伪代码:
- 输入:训练集 $D = \{(x_i, y_i)\}_{i=1}^n$,迭代轮数 $T$,参数集合 $\Theta$
- 特征预处理:
- 对于每个连续特征:基于分位数划分为 $k$ 个 bin
- 将样本特征值映射为 bin 索引(按
max_bin选择存储类型,如uint8_t) - 如果启用 EFB:贪心捆绑互斥特征,计算偏移量
- 初始化:$\hat{y}_i \leftarrow b_0$,对所有 $i$(
boost_from_average=true时,回归、二分类等任务的 $b_0$ 取与标签均值对应的常数,否则为 0) - 对于 $t = 1, 2, \dots, T$:
- 计算梯度与 Hessian:$g_i \leftarrow \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}_i}$,$h_i \leftarrow \frac{\partial^2 L(y_i, \hat{y}_i)}{\partial \hat{y}_i^2}$,对所有 $i$
- 如果启用 GOSS:
- 按 $\lvert g_i \rvert$(实现中为 $\lvert g_i h_i \rvert$)降序排序样本
- $\mathit{topSet} \leftarrow$ 前 $a \times n$ 个大梯度样本
- $\mathit{randSet} \leftarrow$ 从剩余样本中随机选 $b \times n$ 个
- $\mathit{usedSet} \leftarrow \mathit{topSet} \cup \mathit{randSet}$
- 对 $\mathit{randSet}$ 中样本的 $g_i$、$h_i$ 乘以 $\frac{1-a}{b}$
- 在 $\mathit{usedSet}$ 上构建树
- 否则(标准 GBDT):在全部样本(或 bagging 采样后的样本)上构建树
- 构建第 t 棵树(Leaf-wise):
- 在根节点上构建直方图,求出根节点的最优分裂及其增益
- 重复至多 $L_{\max} - 1$ 次,其中 $L_{\max}$ 表示
num_leaves:- 在所有当前叶子中选出最优分裂增益最大的叶子
- 如果该增益 $\le$
min_gain_to_split(或所有叶子都不满足min_data_in_leaf、max_depth等约束),停止建树 - 执行分裂,得到两个新叶子
- 利用直方图做差:对样本较少的子节点遍历样本构建直方图(每个特征统计 $G$ 和 $H$,按
feature_fraction采样特征),另一子节点用父节点直方图减去它 - 在两个新叶子的直方图上遍历 bin 边界,求出各自的最优分裂及增益
- 对于每个叶子 $j$:计算叶子输出 $w_j^* \leftarrow -\frac{G_j}{H_j + \lambda}$($\lambda$ 为
lambda_l2;有lambda_l1时用软阈值后的 $G_j$) - 更新预测:$\hat{y}_i \leftarrow \hat{y}_i + \eta \cdot f_t(x_i)$
- 检查早停条件:如果验证集指标在 $\mathit{patience}$ 轮内无提升,则停止
- 输出:最终模型 $F(x) = b_0 + \eta \sum_{t=1}^T f_t(x)$(LightGBM 存储的叶子值已乘上学习率)
实现细节洞察
从 LightGBM 源码的目录结构可以对应到上面各项技术(仓库原为 microsoft/LightGBM,现已迁移到 lightgbm-org/LightGBM,旧地址会自动跳转;以下路径以主分支为准):
- C++ 核心:主要训练逻辑在
src/目录下。 - 直方图与分裂查找:
src/treelearner/feature_histogram.hpp(及.cpp)实现直方图统计、分裂增益计算和类别特征分裂。 - Leaf-wise 树学习器:
src/treelearner/serial_tree_learner.cpp实现单机的 Leaf-wise 生长逻辑。 - 并行树学习器:
src/treelearner/下的feature_parallel_tree_learner.cpp、data_parallel_tree_learner.cpp、voting_parallel_tree_learner.cpp。 - GOSS 实现:
src/boosting/goss.hpp实现梯度单边采样(同目录的bagging.hpp实现普通 bagging)。 - EFB 实现:
src/io/dataset.cpp中的FastFeatureBundling/FindGroups在构建 Dataset 时执行特征捆绑。 - 网络通信:
src/network/目录实现 socket / MPI 通信与集合通信。
7.11 详细注释的Python代码示例(分类+回归+特征重要性+早停)
| |
