近年来，梯度提升决策树（GBDT）在各种机器学习应用中取得了显著成功。传统上，GBDT的训练算法使用高精度浮点数来计算梯度和统计信息。
本论文探讨了一个之前文献中基本被忽视的重要问题——训练GBDT需要多少位来表示梯度？为了解决这个问题，作者提出在GBDT的训练算法中对所有高精度梯度进行量化。
作者提出了一种简单但有效的方法来量化梯度。他们的理论分析和实证研究表明，在不损害性能的情况下，所需的梯度精度可以很低，例如2或3位。使用低精度梯度，大多数算术运算可以被8位、16位或32位的整数运算替代。
unsetunset背景介绍unsetunset
GBDT是一种强大的机器学习算法，尽管近年来深度学习取得了很大成功，GBDT仍然在许多现实任务中（如在线广告、搜索排名、金融预测等）表现出色。工具如XGBoost、LightGBM和CatBoost的设计进一步增强了GBDT的性能，使其在各种数据科学竞赛和工业应用中表现突出。
尽管GBDT取得了成功，但其算法在充分利用现代计算资源方面仍有改进空间：
- 高精度计算问题：GBDT的训练需要进行高精度浮点数的算术运算，限制了低精度计算资源的使用，而低精度训练已成为显著加速神经网络训练的标准技术。
- 分布式训练的通信成本：对于大数据集，GBDT需要分布式训练，但高精度统计信息的传递导致通信成本高，尤其是在特征数量庞大的情况下，这严重影响了GBDT在分布式系统中的扩展性。
unsetunsetGBDT算法原理unsetunset
GBDT的训练过程
GBDT是一种集成学习算法，通过迭代地训练决策树作为基础组件。在每次迭代中，对每个训练样本计算损失函数相对于当前预测值的梯度（一阶导数）和海森矩阵（二阶导数）。然后训练一棵决策树以拟合梯度的负值。
梯度和海森矩阵计算
设第 (k+1) 次迭代中，样本 (i) 的当前预测值为 (\hat{y}_i^k)。
梯度 (g_i) 和海森矩阵 (h_i) 计算如下：
损失函数的近似
对于叶子节点 (s)，令 (I_s) 表示叶子节点中的数据索引集合。
和 分别是梯度和海森矩阵的和。
在第 (k+1) 次迭代中，固定树结构，训练损失可以用二阶泰勒多项式近似：
其中 是常数， 是叶子节点 的预测值。
通过最小化近似损失，可以得到叶子节点 (s) 的最优值和数据 (I_s) 的最小损失：
树结构的优化
寻找最优树结构非常困难，因此通过贪心方法迭代地将叶子节点分裂为两个子叶节点，从单一根叶节点开始。
当在树 中将叶子节点 分裂为两个子节点 和 时，可以计算近似损失的减少量：
为了找到叶子节点 的最佳分裂条件，需要枚举所有特征的所有分裂候选，并选择损失减少量最大的那个。
直方图加速算法
为了加速最佳分裂寻找过程，最先进的GBDT工具采用基于直方图的算法。基本思想是将特征值划分到不同的箱中，每个箱对应特征值的一个范围。
然后构建直方图，每个箱记录该箱中数据的梯度和海森矩阵的累加值。只有这些箱的边界会被考虑作为分裂阈值的候选。
- 输入：梯度 、海森矩阵 ，箱数据 ，叶子节点数据索引
- 对于每个样本 和每个特征 ，找到样本 在特征 上所属的箱，将梯度和海森矩阵值累加到相应的直方图箱中。
unsetunset量化训练GBDTunsetunset
量化训练框架
我们将梯度 () 和 Hessian 矩阵 () 量化为低位宽整数 ( 和 )。将所有训练样本的 和 范围划分为等长区间。
使用 位 () 整数梯度时，使用 个区间。每个区间的端点对应一个整数值，总共 个整数值。由于 可以取正负值，区间一半分配给负值，另一半分配给正值。对于 通常为非负值，其区间如下：
低位宽梯度和 Hessian 计算如下：
整数运算
在算法1中用 和 替换 和 。 原始梯度的加法操作替换为整数加法。直方图箱中的统计量 和 变为整数，累积梯度只需要整数加法。
大多数操作用低位宽整数完成。只有在计算原始梯度、Hessian 和分裂增益时需要浮点操作：
四舍五入策略
直接四舍五入到最接近的整数通常会导致严重的准确性下降，尤其是在梯度位数较少的情况下。因此采用随机四舍五入策略：
四舍五入策略的正式定义如下：
unsetunset量化训练GBDT的评估unsetunset
表1列出了实验中使用的数据集。对于Criteo数据集，我们通过目标编码和计数编码对类别特征进行编码。我们使用开源GBDT工具XGBoost、LightGBM和CatBoost作为基准。
量化训练的准确性
我们评估了量化训练的准确性。对于每个数据集和每个算法，我们报告测试集中最佳迭代的结果。我们使用2-bit、3-bit、4-bit和5-bit的整数梯度，并将结果与32-bit单精度浮点梯度进行比较。表2列出了在所有提升迭代中测试集上达到的最佳指标。我们用SR表示随机四舍五入，用RN表示最接近四舍五入，并使用下标表示是否应用叶子值重拟合。
单机加速
我们通过比较流行开源GBDT工具的CPU和CUDA实现，评估了量化训练（SRrefit）在单机上的加速效果。我们的CPU量化训练基于LightGBM。我们将我们的CPU实现与XGBoost、CatBoost和32-bit梯度的LightGBM进行比较。
分布式训练的加速
我们在Epsilon数据集的扩展版本上评估了量化在分布式GBDT训练中的效果。该扩展版本包含原始Epsilon数据集训练集的20个副本（记为Epsilon-8M）和Criteo。
unsetunsetLightGBM对应参数unsetunset
https://lightgbm.readthedocs.io/en/latest/Parameters.html
use_quantized_grad 🔗︎, default = false, type = bool
- 启用此选项将把梯度和hessians离散化（量化）到
num_grad_quant_bins 的箱中。 - 使用量化训练时，训练过程中的大多数算术运算将是整数运算。
- 梯度量化可以加速训练，在大多数情况下精度损失很小。
num_grad_quant_bins 🔗︎, default = 4, type = int
quant_train_renew_leaf 🔗︎, default = false, type = bool
- 对于排名目标，更新叶子值对良好的量化训练精度非常有帮助。
stochastic_rounding 🔗︎, default = true, type = bool
