12 年后，树模型 ABC-Boost 终于开源，精度超过 XGBoost、LightGBM

近期，前百度研究院副院长李平等人开源了多年的研究成果 Fast ABC-Boost 机器学习包。

开源代码连接：
https://github.com/pltrees/abcboost

据悉，该研究十多年前就已经开始，2010 年，李平发表了题为“Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost”的论文，2018 年的图灵奖得主 Yoshua Bengio 当时还与人讨论了李平在树模型和 boosting 上的工作。

根据介绍，李平在 2007 年斯坦福大学博士毕业后，曾在任康奈尔大学和后罗格斯大学任教，并于 2013 年成为计算机系和统计系两系的终身教授。其主要研究方向是算法学习、高效检索、机器存储、数据流和推荐等，曾获得 NIPS2014 最佳论文奖、ASONAM2014 最佳论文奖、KDD2006 最佳论文奖，以及美国空军和青年科学家奖（AFOSR-YIP）、美国海军杰出数据科学家奖（ONR-YIP）等奖项。

2020 年 1 月，李平开始担任百度研究院副院长，其团队与百度的凤巢广告、Feed 流、搜索、百度知道、中文输入法、百度地图等业务部门展开合作，把研究成果应用到各项产品中。

概览

? http://statistics.rutgers.edu/home/pingli/STSCI6520/Lecture/ABC-LogitBoost.pdf

? http://www.stat.rutgers.edu/home/pingli/doc/PingLiTutorial.pdf (pages 15–77)

正如最近一篇关于决策树综述的论文（Fan 和 Li，2020）所总结的那样，在过去 15 年左右的时间里，多种实现技术提升了增强树算法的精度和效率，包括:

与基于仅使用一阶增益信息相比，使用二阶增益信息公式的树分裂实现（李，2010b）（即“Robust LogitBoost”）通常可以提升精确度（Friedman，2001）。它现在是流行的树模型平台中的标准实现。

李等人（2007）提出的自适应分箱策略有效地将特征值转换为整数值，大大简化了实现，并提高了树模型的效率。分箱技术也是流行树模型平台的标准实现。

用于多分类的“adaptive base class boost”（ABC-boost）模式（Li，2008，2009，2010a，b；Li and Zhao，2022a）通过重写经典多分类逻辑回归损失函数的导数，在许多情况下可以大大提高多分类任务的准确性。

特征预处理固定长度的分箱方法

回归树（Brieman 等人，1983）是分类、回归和排序任务的基础构建模块。树的思想是基于一些“增益”标准以轴对齐的方式递归划分数据点，并 告最终（子划分）区域中数据点的平均（或加权平均）响应作为预测值。子划分的区域作为一个树来组织或者查看，叶节点对应于最终的子划分区域。

因此，一项关键任务是计算每个特征的最佳分割点，并通过将当前节点中的数据点分成两部分来选择最佳特征（即增益最大的特征）来进行实际分割。该过程递归继续，直到满足某些停止标准。在李等人（2007）之前，典型的树实现首先根据特征值对每个维度的数据点进行排序，并需要在分割后跟踪数据点。如图 1 所示，李等人（2007）首先将特征值量化（分箱）为整数，然后按照自然顺序排序。这个技巧大大简化了实现。如果分箱总数不太大，可以使程序更高效。图 1 中的分箱也适用于数据分布，因为它仅在有数据的地方分配分箱值。

如以下 matlab 代码所示，分箱方法非常简单：首先从非常小的初始分箱长度开始（例如，10^?10） ，预先指定最大的分箱参数，比如 128 或者 1024。对于每个特征，根据特征值对数据点进行排序。将分箱编 从最小到最大分配给数据点，只要有数据点，就一直分配，直到所需的分箱数量超过 MaxBin。然后通过加倍分箱长度来重新开始。

总之，这种看似非常简单（固定长度）的分箱算法能适用于增强树方法，可能有两个主要原因：

对于增强树，允许的最大分箱数（即 MaxBin 参数）无论如何都不应太小。如果数据量化过粗，将丢失太多信息。对于如此多的分箱（例如，MaxBin=1000），就增强树的精度而言，改进这种固定长度策略可能并不那么容易。

不应该期望所有特征都使用相同数量的分箱。通常，在一个数据集中，特征可能会有很大差异。例如，一些特征可能是二值的（即，使用 MaxBin=1000 也只能生成两个值），一些特征可能只有 100 个不同的值（即，使用 MaxBin=1000 仍最多只能生成 100 个值），而一些特征确实需要更多的量化级别。因此，参数 MaxBin 只是一个粗略的准则。根据给定的 MaxBin 过于努力地“优化”分箱过程可能会适得其反。

Lp 回归

读者请参阅关于 Lp 增强回归的详细 告（Li and Zhao，2022c）。一个训练数据集{yi，xi}(i=1,n)，其中 n 是样本数，xi 是第 i 个特征，yi 是第 i 个标签。Lp 回归的目标是建立模型 F（x），以最小化 Lp 损失：

使用“加法模型”（Friedman 等人，2000；Friedman，2001），假设 F 是 M 项的总和：

其中，基学习器 fm(x) 是一棵回归树，以分段贪婪的方式从数据中学习。根据 Friedman 等人（2000）的想法，在每次增强迭代中，通过加权最小二乘法拟合 fm，响应值{zi}和权重{wi}：

李（2010b）推导了使用响应值{zi}和权重{wi}建立回归树时，确定分裂位置所需的相应增益公式。历史上，基于加权最小二乘法的增强方法被认为存在数值问题（Friedman 等人，2000，2008），因此后来 Friedman（2001）提出仅使用一阶导数拟合树，即，

现在很清楚，如李（2010b）所示，可以推导出使用二阶信息计算增益的显式的和数值稳定 / 鲁棒的公式。

基于二阶信息的树分裂准则

考虑一个具有 N 个数据点和一个特定特征的树节点。权重 wi 和响应值 zi，i=1 到 N。已经根据特征值的排序顺序对数据点进行了排序。树分裂过程是查找索引 s，1≤ s<N，因此如果在 s 处分割，加权平方误差（SE）减少得最多。也就是说，寻求 s 最大化：

这个过程在数值上是鲁棒、稳定的，因为，不需要直接计算响应值 zi=-Li’//Li’’，它可以（并且应该）很容易地接近无穷大。由于原始 LogitBoost（Friedman 等人，2000）使用了单个响应值 zi=-Li’//Li’’，因此该过程被认为存在数值问题，这是 Friedman（2001）仅使用一阶导数构建树的动机之一。因此增益公式成为:

Lp 增强算法

算法 1 描述了 Lp 增强回归树使用的分裂增益公式（7）（对于 p≥ 2） 或树分裂增益公式（8）（对于 1≤ p<2）。注意，在构建树之后，终端节点的值通过以下公式计算：

实验

遵循
https://github.com/pltrees/abcboost 上的说明，用户可以安装 Fast ABC-Boost 软件包。假设可执行文件位于当前目录，数据集位于“data/”目录。“comp-cpu”数据集有 libsvm 和 csv 两种格式，有 4096 个训练样本和 4096 个测试样本。在终端，执行以下命令

其中ε默认为 10^5。在本例中，程序在 933 次迭代后退出（而不是 10000 次迭代）。在训练后，将在当前目录中创建两个文件：

为了在测试数据集上测试训练后的模型，运行

它会生成另外两个（文本）文件来存储测试结果：

.testlog 文件记录了测试损失和其他信息。“.prediction”存储最终（或指定）迭代中所有测试样本的回归预测值。

用参数 J∈ {6, 10, 20}, ν ∈ {0.06，0.1，0.2}，p 从 1 到 10，MaxBin 从 10 到 10^4 进行实验。图 2 绘制了每个 MaxBin 值的最佳（在所有参数和迭代中）测试 MSE。在每个面板上，实心曲线绘制 L2 回归的最佳测试 MSE 和 Lp 回归的虚线曲线（在最佳 p 处）。右面板是左面板的放大版本，重点放在 100 到 10^4 的 MaxBin 上。对于这个数据集，使用 MaxBin=1000 可以获得很好的结果，而使用较大的 MaxBin 值不会产生更好的结果。

图 3 绘制了所有三个包的 L2 回归的最佳测试 MSEs：ABC-Boost（L2）、XGBoost 和 LightGBM，MaxBin 范围为 10 到 10^4。同样，右面板只是左面板的放大版本。当然，如图 2 所示，ABC-Boost 将能够通过使用 p≠2 的 Lp 回归实现更低的 MSE。

最后，图 4 绘制了所有迭代的测试 L2 MSEs，在一组特定的参数 J、ν和 MaxBin 下。注意，ABC-Boost 包在等式（9）中设置了保守停止标准。

使用鲁棒 LogitBoost 分类

同样，用{yi，xi}(i=1,n) 表示训练数据集，其中 n 是训练样本数，xi 是第 i 个特征向量，yi∈ {0，1，2，…，K? 1} 是第 i 类标签，其中 K=2 表示二分类，K≥ 3 表示多类分类。假设类概率 p(i,k) 为

其中 F 是 M 项的函数：

其中，基学习器 fm 是一棵回归树，通过最小化负对数似然损失进行训练：

其中，如果 yi=k，则 r(i,k)=1，否则，则 r(i,k)=0。优化过程需要损失函数（12）的前两个导数，分别对应于函数值 F(i,k)，如下所示：

这些是教科书中的标准结果。

基于二阶信息的树分裂准则

再次，考虑具有 N 个权重 wi 和 N 个响应值 zi，i=1 到 N 的节点，假设其根据相应特征值的排序顺序排序。树分裂过程寻求 t 最大化

因为计算涉及∑p(i,k)（1? p(i,k) 作为一个组，该程序在数值上是鲁棒、稳定的。这解决了 Friedman 等人（2000）的担忧；Friedman（2001）；Friedman 等人（2008 年）。相比之下，MART（Friedman，2001）使用一阶导数来构造树，即，

算法 2 使用等式（14）中的树分裂增益公式描述鲁棒的 LogitBoost。注意，在构建树之后，终端节点的值通过以下公式计算：

这解释了算法 2 的第 5 行。对于 MART（Friedman，2001），该算法几乎与算法 2 相同，除了第 4 行，MART 使用树分裂增益公式，等式（15）。

注意，对于二分类（即 K=2），只需要在每次迭代中构建一棵树。

二分类实验

二分类数据集“ijcnn1”包含 49990 个训练样本和 91701 个测试样本，可在
https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/dataset/binary.html 查看。这个在一次比赛中使用了该数据集，获得冠军的是 LIBSVM（核 SVM），测试误差为 1293 个（在 91701 个测试样本中）。

再次在终端发出以下命令

使用 J=20 个叶节点、ν=0.1 收缩率和 M=10000 次迭代，MaxBin=1000，使用“鲁棒 LogitBoost”算法训练二分类模型。创建两个文件：

打印出“.trainlog”文件的前 3 行和后 3 行：

下一个命令

输出测试结果

.testlog 文件的最后 10 行如下所示：

其中第三列记录了测试错误。回想一下，L