2. LightGBM核心原理：直方图算法、GOSS与EFB的数学基础与实现逻辑
说起 LightGBM，很多人第一反应就是“快”。但为什么快？今天咱们就把它最核心的三个引擎拆开看看：直方图算法、GOSS、EFB。我个人把这三点叫做 LightGBM 的“三驾马车”，少了哪个它都没这么能打。
2.1 直方图算法
传统的决策树在寻找最佳分裂点时，需要遍历所有特征的所有可能取值。数据量一上来，计算量就爆炸了。LightGBM 是怎么干的？它把连续特征离散化成 k 个桶，然后只在这些桶上找分裂点。
为什么要这么做？举个例子。假设你有 100 万行数据，特征是“用户年龄”。传统做法要把所有不同的年龄值（比如 0~100）都算一遍信息增益。LightGBM 把年龄分成 10 个桶（0-10, 11-20…），只算 10 次就够了。你说快不快？
我曾在一次风控项目中用 GBDT 跑 50 万样本，单机跑了 3 个小时。换成 LightGBM 后，直方图加下去，同样参数 15 分钟搞定。嗯，当时我就把那个 GBDT 脚本删了。
数学上的关键步骤
- 分桶：对每个特征，按分位数或等宽分成
num_bins个桶，默认 255。 - 累积梯度统计：在每个桶内累加一阶梯度和二阶梯度。
- 查找最优分裂：遍历桶边界，计算分裂后的增益，选出增益最大的桶边界。
你看，原本 O(#样本×#特征) 的复杂度降到了 O(#桶×#特征)。说实话，这就是工程上最聪明的“暴力美学”。
max_bin 参数。
2.2 GOSS：梯度单边采样
另一个提升速度的利器是 GOSS。名字挺唬人，但说白了就是：只挑那些“难搞”的样本去计算，剩下的走个过场。
传统的样本采样是随机扔一部分，容易把关键信息也扔了。GOSS 的思路是：把样本按梯度大小排序，梯度大的（误差大的）全保留，梯度小的（误差小的）按比例随机保留一部分，然后放大这部分样本的权重来补偿。
算法流程
- 按梯度绝对值降序排列样本。
- 取前
a%的大梯度样本（全部保留）。 - 从剩余小梯度样本中随机取
b%。 - 对随机采出的小梯度样本乘上权重系数
(1 - a) / b，以平衡分布。
| 参数 | 含义 | 默认值 | 我常用的值 |
|---|---|---|---|
top_rate |
大梯度样本保留比例 | 0.2 | 0.1 |
other_rate |
小梯度样本采样比例 | 0.1 | 0.2 |
2.3 EFB：互斥特征捆绑
第三板斧是 EFB。高维稀疏特征很常见，比如用户 ID 的 one-hot 编码，特征之间很少同时非零（互斥）。EFB 就把这些互斥特征捆绑成一个“复合特征”，从而减少特征维度。
你想想看，一万个用户 ID 特征，理论上可以捆绑成几个甚至一个特征，维度直接干掉。LightGBM 在训练前会做一个特征互斥度的贪心扫描，把冲突率低于某个阈值（默认 0.01）的特征捆在一起。
实现逻辑
- 构建图：每个特征一个节点，边表示两个特征之间的冲突次数。
- 贪心排序：按度数降序排列特征。
- 捆绑：遍历特征，如果当前特征与已有捆绑簇的冲突量小于阈值，则加入；否则新建一个簇。
- 合并特征值：给每个捆内的特征分配一个偏移量，使得合并后的特征值不重叠。
记得我第一次处理一个 CTR 预估任务，原始特征有 5000 维，其中有 3000 多个是互斥的广告类目 ID。打开 EFB 后实际训练特征变成了 1200 维，内存降了 60%，训练时间从 2 小时降到 20 分钟。说实话，这种效果用其他方法很难达到。
三大核心的协同工作流
下面这张图可以直观看到 LightGBM 的训练流水线：数据先经过直方图离散化，然后 GOSS 筛选样本，EFB 压缩特征，最后用带深度限制的叶子节点生长策略建树。
小结一下这三个东西的关系
| 算法 | 作用对象 | 核心收益 | 我常调的参数 |
|---|---|---|---|
| 直方图算法 | 特征 | 降低分裂点搜索复杂度 | max_bin |
| GOSS | 样本 | 减少样本数量，聚焦难样本 | top_rate, other_rate |
| EFB | 特征 | 降低特征维度，减少内存 | max_conflict_rate |
feature_fraction 或手动分析一下稀疏性。
好了，原理方面就这些。你可能会问：这三个算法能并行吗？当然能。直方图的构建可以按特征并行，GOSS 和 EFB 的预处理也有并行实现。但那是另一层的话题了。咱们先消化掉这些核心思想，后面在分箱和图谱衍生中你会看到它们怎么跟业务特征工程结合。