LightGBM
2025年9月25日
9:04
- 不是在每次构建树之前进行分桶。
- 更不是在每次分裂之后进行分桶。
- 分桶完成后，在整个训练过程中，每个特征的桶边界都是固定不变的。
- 时机：在真正开始构建第一棵决策树之前，LightGBM会对整个训练数据集进行预处理，为每个特征计算桶的边界（bin edges）。这个过程只发生一次。
- 目的：将连续特征值离散化为固定的桶索引（例如，0到255之间的整数）。桶边界基于特征值的分布（如近似分位数）自适应确定。
- 结果：每个样本的特征值都被映射到一个固定的桶索引。在您的算法片段中，I.f[k][j].bin 就是指特征k的样本j的预计算桶索引。这意味着分桶结果已经存储在训练数据对象I中。
- 时机：在树的每一层，对于每个节点，算法需要为每个特征构建直方图（如Algorithm 1所示）。
- 目的：累积当前节点中样本的统计信息（如梯度之和y和样本数n）到每个桶中。直方图是基于预计算的桶索引构建的。
- 过程：如算法所示，对于每个特征k，遍历当前节点的样本索引usedRows，从I.f[k][j].bin获取桶索引，然后更新直方图H的对应桶的统计信息。
- XGBoost（加权分位数）：像是一个厨师每次做菜时，都要根据食材的新鲜度（梯度）重新调整切菜的刀法（分桶边界），然后再切菜。
- LightGBM（直方图）：像是提前准备好了一套标准尺寸的切菜模具（固定分桶），每次做菜时直接把食材放进模具里按压即可。
- 通常使用全局模式（global） 而非局部模式（local），即在构建每棵树之前计算一次候选分裂点，而不是在每个节点都计算。
- 即使这样，每棵树前的重新分桶开销仍然比LightGBM的整个训练前一次性分桶要大得多。
- 计算梯度统计量：构建直方图时，梯度值会乘以样本权重
- 计算信息增益：分裂点评估时考虑权重
- 计算叶节点值：叶节点的输出值计算也考虑权重
- 特征维度可能达到数万甚至数百万（如one-hot编码后的类别特征）
- 但很多特征是互斥的（exclusive） - 即它们不会同时取非零值
- 传统方法需要为每个特征单独处理，计算开销大
- 城市_北京: [1,0,0,0]
- 城市_上海: [0,1,0,0]
- 城市_广州: [0,0,1,0]
- 城市_深圳: [0,0,0,1]
- 互斥特征：在任意样本中，最多只有一个特征取非零值
- 特征捆绑：将多个互斥特征合并成一个特征
- 偏移量：为每个原始特征在捆绑特征中分配不同的数值区间
- 将每个特征视为图的一个节点
- 如果两个特征不是互斥的（即存在样本中同时取非零值），则在它们之间添加边
- 问题：用最少的颜色给所有节点着色，相邻节点不能同色
- 每个颜色对应一个特征束（bundle）
- 由于图着色是NP难问题，LightGBM使用贪心近似算法
- 特征A：原始值范围[0, 10]
- 特征B：原始值范围[0, 20]
- 特征C：原始值范围[0, 15]
- 特征A：使用区间[0, 10]
- 特征B：使用区间[11, 31]（偏移量=10+1=11）
- 特征C：使用区间[32, 47]（偏移量=31+1=32）
- 如果特征A=5，特征B=0，特征C=0 → 捆绑特征值=5
- 如果特征A=0，特征B=8，特征C=0 → 捆绑特征值=11+8=19
- 如果特征A=0，特征B=0，特征C=12 → 捆绑特征值=32+12=44
- 识别互斥特征：城市相关的三个特征是互斥的
- 创建特征束：将三个城市特征捆绑成一个"城市捆绑"特征
- 分配偏移量：
- 城市_北京 → 区间[0,1]（值0-1）
- 城市_上海 → 区间[2,3]（值2-3）
- 城市_广州 → 区间[4,5]（值4-5）
- 输入：原始特征矩阵。
- 输出：一个“捆绑特征”的映射关系，以及一个新的、特征数量更少的“虚拟”特征矩阵。
LGB的分桶策略：
LightGBM的特征分桶（Binning）是 在整个模型训练之前，预处理阶段一次性完成的。也就是说：
这是一种“一次分桶，全程使用”的策略，这也是其高效的关键原因之一。
LightGBM使用的不是等宽分桶（每个桶的数值范围固定），而是采用了一种基于分位数的近似算法，力求让每个桶里的样本数量尽量均匀。但它又不仅仅是简单的分位数，还做了很多工程优化。
算法会设定一个最大桶数 max_bin（默认是255）。
它的目标是将排序后的特征值分布划分为最多 max_bin 个桶，并确定 max_bin - 1 个切割点（桶边界）。
这个过程是自适应的，因为它完全依赖于当前特征值的实际分布。对于分布密集的区域，桶的宽度会较窄；对于分布稀疏的区域（如长尾部分），桶的宽度会较宽。
特征分桶（binning，即确定桶的边界）和直方图构建（histogram construction，即累积统计信息）是两个不同的步骤！！！！
1. 特征分桶（Binning）是训练前一次性完成的，特征分桶的结果即I.f[k][j].bin，指示了第j个样本，第k个特征的bin
2. 直方图构建（Histogram Construction）是每次分裂时进行的
问题：那么xgboost的加权分位数方法之所以慢，就是因为它需要在每次构建树之前（global）或节点分裂之前（local），既计算特征分桶，又构建直方图，而lightgbm只需要构建直方图就行了。我的理解 对吗
deepseek回答：
您的理解非常准确，完全正确！ 这正是两个算法在效率上产生差异的核心原因。
让我再帮您清晰地总结一下：
XGBoost的加权分位数方法为什么相对较慢：
动态分桶：需要在每次需要候选分裂点时（无论是global每棵树前还是local每个节点前）重新计算分桶边界。
依据变化：分桶的依据是当前节点样本的二阶梯度分布，这个分布在每棵树、每个节点都不同。
双重开销：既要计算加权分位数来确定桶边界，又要构建直方图来累积统计量。
LightGBM的直方图方法为什么更快：
静态分桶：在整个训练开始前一次性完成分桶，桶边界固定不变。
依据固定：分桶只依赖于特征值的原始分布，与梯度无关。
单一开销：在节点分裂时，只需要构建直方图（简单的整数累加操作），无需重新分桶。
更形象的比喻：
补充说明：
XGBoost也意识到了这个问题，因此在实践中：
您的理解抓住了问题的本质：LightGBm通过将昂贵的"分桶"操作从训练循环中移出，变为一次性预处理，从而获得了巨大的效率优势。 而XGBoost的加权分位数虽然理论更优美，但计算开销确实更大。
It costs O(#data × #feature) for histogram building and O(#bin × #feature) for split point finding. Since #bin is usually much smaller than #data, histogram building will dominate the computational complexity. If we can reduce #data or #feature, we will be able to substantially speed up the training of GBDT. 构建直方图的计算复杂度是 O(#data × #feature)，特征分裂点寻找的计算复杂度是O(#bin × #feature)，特征分桶的计算复杂度：排序：每个特征需要O(n log n) ，m 个特征需要O( #feature × #data log #data)。
LGB首先通过一次性特征分桶，省去了频繁的特征分桶计算O( #feature × #data log #data)，又通过GOSS和EFB，进一步减少 #data or #feature样本和特征数量，来加速。
GOSS
GOSS keeps all the instances with large gradients and performs random sampling on the instances with small gradients. In order to compensate the influence to the data distribution, when computing the information gain, GOSS introduces a constant multiplier for the data instances with small gradients (see Alg. 2). Specifically, GOSS firstly sorts the data instances according to the absolute value of their gradients and selects the top a×100% instances. Then it randomly samples b×100% instances from the rest of the data. After that, GOSS amplifies the sampled data with small gradients by a constant 1−a/ b when calculating the information gain. By doing so, we put more focus on the under-trained instances without changing the original data distribution by much.
对大梯度样本采样a%，对小梯度样本理论上也应该采样 a%，但是小梯度的样本数量可能很多，想采样 比例大于a%，但是就改变了大梯度样本数量和小梯度样本数量的比例了，所以乘以1−a/ b ,不改变分布。
1. 采样是在每棵树学习之前进行的。
从算法伪代码可以看出：
外层循环 for i = 1 to d do 对应 boosting 的迭代次数（即树的个数）
在每轮迭代开始时，先计算当前模型的预测 preds 和梯度 g
然后立即进行基于梯度的采样操作
所以GOSS是每棵树前都重新采样，而不是一次性采样后所有树都用同样的子集。
2. w[randSet] 的作用（核心机制）
w[randSet] ×= fact 这一行是GOSS算法的关键补偿机制，它的作用非常重要：
问题背景：
我们保留了全部大梯度样本（topSet）
但只随机采样了一小部分小梯度样本（randSet，比例为b）
如果直接这样训练，会严重高估大梯度样本的贡献，扭曲数据分布
解决方案：权重补偿
对随机采样的小梯度样本，通过乘以权重因子 fact = (1-a)/b 来补偿
数学原理：让小梯度样本的"有效数量"恢复到大致的原始比例
具体计算例子：
假设有1000个样本，设置 a=0.1, b=0.2：
topN = 0.1 × 1000 = 100（保留全部100个大梯度样本）
randN = 0.2 × 1000 = 200（从900个小梯度样本中随机取200个）
fact = (1-0.1)/0.2 = 4.5
补偿效果：
大梯度样本：100个，权重都为1 → 有效数量 = 100
小梯度样本：200个，每个权重4.5 → 有效数量 ≈ 200 × 4.5 = 900
这样大梯度:小梯度的比例就从 100:200 恢复到了接近原始的 100:900
3. 权重在训练中的使用
在伪代码的最后一行：
python
newModel ← L(I[usedSet], −g[usedSet], w[usedSet])
权重 w[usedSet] 会传递给弱学习器 L（通常是决策树），在以下地方使用：
EFB
EFB是LightGBM的三大核心创新之一（另外两个是GOSS和直方图算法），它专门针对高维稀疏特征进行优化，能够显著减少特征数量，提升训练速度。
1. EFB要解决什么问题？
高维数据的挑战：
典型例子：One-Hot编码
假设有"城市"特征，取值为{北京,上海,广州,深圳}，one-hot编码后得到4个特征：
这些特征是互斥的 - 每个样本只有一个城市，所以只有一个特征为1，其他为0。
2. EFB的核心思想
将互斥的特征捆绑（bundle）成一个新的复合特征，从而减少特征数量。
基本概念：
3. EFB的具体实现步骤
EFB算法分为两个主要阶段：
阶段一：寻找可捆绑的特征对（图着色问题）
步骤1: 构建冲突图
步骤2: 图着色问题
步骤3: 贪心捆绑算法
python
# 伪代码
1. 按特征的非零值数量排序（降序）
2. 初始化空的特征束列表
3. 遍历每个特征:
-
尝试将当前特征加入到现有的某个特征束中
-
如果与束内所有特征的冲突数小于阈值，则加入
-
否则创建新的特征束
冲突阈值：允许的少量冲突（通常很小，如1-3），因为完全互斥很难保证。
阶段二：合并特征到捆绑中
步骤1: 为每个特征分配偏移量
假设要将3个特征捆绑成一个：
分配偏移量：
步骤2: 合并特征值
对于每个样本：
4. 实际例子说明
原始数据：
|
样本 |
城市_北京 |
城市_上海 |
城市_广州 |
年龄 |
收入 |
|
1 |
1 |
0 |
0 |
25 |
5000 |
|
2 |
0 |
1 |
0 |
30 |
8000 |
|
3 |
0 |
0 |
1 |
28 |
6000 |
应用EFB后：
转换后数据：
|
样本 |
城市捆绑 |
年龄 |
收入 |
|
1 |
1 |
25 |
5000 |
|
2 |
3 |
30 |
8000 |
|
3 |
5 |
28 |
6000 |
特征数量从5个减少到3个！
总结
我们可以将LightGBM的完整训练流程细化为以下几个阶段，EFB处于非常靠前的位置：
阶段一：数据预处理（一次性）
1 数据加载：读取训练数据。
2 特征分桶（Binning）：为每个连续特征计算直方图的桶边界。
3 Exclusive Feature Bundling (EFB)：识别互斥特征，创建特征束，并为每个原始特征分配偏移量。
阶段二：Boosting迭代（循环执行）
4 对于每轮迭代（对于每棵树）：
a. 计算梯度（如果使用GOSS，则在此步骤后进行采样）。
b. 构建决策树：在构建树的过程中，当需要为节点寻找最佳分裂特征时，算法会遍历所有特征束。
c. 在特征束内部分裂：对于每个特征束，算法会在其内部检查每一个原始特征的最佳分裂点（利用偏移量来区分不同特征的值域）。