2020/06/18 14:39

Ji Feng、Yi-Xuan Xu、Yuan Jiang、Zhi-Hua Zhou作者Panda编译

速度提升、准确率更胜一筹，周志华等人提出可微XGBoost算法sGBM

梯度提升机（GBM）的重要性无需多言，但传统的 GBM 仍存在一些固有缺点。近日，南京大学周志华, 创新工场冯霁等人提出了一种新型的软梯度提升机（sGBM），并基于此构建了新型的软梯度提升决策树（sGBDT），作为XGBoost的替代性模型。相比于传统的「硬」GBM，sGBM 在准确度、训练时间和增量学习，多维度回归等多方面都有更优的表现。

论文链接：https://arxiv.org/pdf/2006.04059.pdf

梯度提升机（GBM）已被证明是一种成功的函数近似器并已在多种不同的领域得到了广泛应用。GBM 的基本思想很简单，即训练一系列基学习器（base learner）并且这些学习器的目标是按顺序最小化某个预定义的可微分损失函数。

在构建这些学习系统时，通常的做法是用不可微分的决策树充当基学习器。梯度提升决策树（GBDT）及 XGBoost、LightGBM 和 CatBoost 等变体，是最常见也是最广泛使用的具体模型实现。

现阶段，对于表格式数据而言，GBDT 模型仍旧是最佳选择，其应用领域也很广泛，从协同过滤到信息检索再到粒子发现均有其身影。但是，此类模型较难用于在线学习，因为流数据的环境是会变化的，而基模型在训练完成后难以随环境而变化。

另一方面，同 GBM 不同，可微分编程不仅需要损失函数是可微分的，学习模块也需要可微分。具体来说，通过将多个可微分学习模块构建为任意有向无环图（DAG）形式，就可通过随机梯度下降或其变体优化方法来联合优化其整个结构。这样的系统有一些出色的特性，包括强大的表征学习能力、可扩展性以及可在线使用。

2018 年，周志华和冯霁等人发表的一篇 NeurIPS 论文提出了一种用于表征学习的多层梯度提升决策树（mGBDT），这项研究开创性地融合了上述两个研究方向的优势。具体来说，mGBDT 具有和可微分编程模型一样的分层表征能力，同时又具备非可微分模型的一些优良特性，因此能以更好的方式处理表格式数据。这项开创性研究带来了新的挑战和机遇，但也存在很大的进一步探索空间。

今天要介绍的这项研究是周志华，冯霁等人在相关问题上的又一种开创性思考。这一次，他们研究的不是如何构建一个能像可微分程序一样工作的 GBM，而是探索了如何构建能像不可微分的 GBM 一样工作的可微分系统。软梯度提升机（Soft Gradient Boosting Machine）就是他们的探索成果。这种「软」版本的 GBM 是将多个可微分的基学习器连接在一起，受 GBM 启发，同时引入了局部损失与全局损失，使其整体结构可以得到联合优化。在此基础上，他们还提出使用软决策树（soft decision tree）来充当基学习器，在硬决策树不是最合适的选择时，软决策树对应的软梯度提升决策树就可被视为 XGBoost 的替代选择。据介绍，这种设计具有如下优势：

首先，相比于传统的（硬）梯度提升机，软梯度提升机的训练速度更快。软 GBM 不是一次一个地训练基学习器，而是能同时训练所有基学习器。该团队也对该设计进行了实验实测，结果表明在使用同样的基学习器时，软 GBM 在多个基准数据集上能带来超过 10 倍的速度提升，同时还有更胜一筹的准确度。此外，在拟合传统 GBM 模型时，一个基学习器必须在「看」完所有训练数据之后才能转向下一个学习器；这样的系统不适合增量学习或在线学习。而软 GBM 天生就具备这样的能力。

其次，XGBoost 等当前的 GBDT 实现使用了 CART 作为基学习器，因此不能很直接地用于多维回归任务。但 sGBDT 可使用软决策树作为基学习器来自然地处理这些任务。这样的特性也使得 sGBDT 更适用于知识蒸馏或二次学习，因为蒸馏过程会将分类的 one hot 标签转换为一个在训练集上的稠密向量。

最后，由于局部和全局的损失注入，软 GBM 会让基学习器之间的交互呈指数增长，使得该系统能比对多个基学习器使用软平均 (soft averaging, 可微加权平均集成) 的方法更有效和更高效。

先从 GBM 讲起

在详细介绍新提出的方法之前，先来看看梯度提升机（GBM）的工作方式。具体来说，对于给定的数据集

，GBM 的目标是获得函数 F*(x) 的一个优良近似，而评估标准是看其能否在实验中最小化损失

。

GBM 假设 F*(x) 有这样的加法展开形式：

，其中

由 θ_m 参数化，而 β_m 是第 m 个基学习器的系数。

GBM 的训练过程是基于训练数据学习参数

。GBM 首先假设

，然后就能按顺序决定

和 β_m。首先，给定 y^i 和 GBM 前一轮获得的预测结果，

GBM 可为每个训练样本计算出所谓的残差：

其次，下一个基学习器 h_m 会与该残差进行拟合。系数 β_m 则通过最小二乘法确定或设定为常数。最后，完成对学习器 h_m 和系数 β_m 的参数更新之后，就可以将其用作条件来更新 GBM 的预测结果：

图 1：GBM 和 sGBM 示意图

然后进入下一轮训练流程。算法 1 总结了这个训练过程，图 1 左图也给出了其示意图。

算法 1：常规（硬）GBM 的训练过程

sGBM 有何不同？

可以看出，GBM 的训练过程难以并行化，因为只有在一个基学习器拟合之后才能转向下一个基学习器。也因为这个原因，这类算法也难以在线应用。

软梯度提升机（sGBM）就是针对这些问题而提出的。该研究团队首先假设所有基学习器都是可微分的。然后，他们没有选择为相连的基学习器执行软平均，而是提出使用两种类型的损失函数——全局损失和局部损失；将这两种损失函数注入训练过程之后，可使得基学习器之间的交互成指数增长，进而实现梯度提升效果（而非所有基学习器的直接加权平均）。

具体来说，令 M 为可微分基学习器的数量，其中每个基学习器的参数为 θ_m。这里 M 是预先确定的，指定了训练之前所使用的基学习器的数量。和硬 GBM 一样，sGBM 的输出为所有基学习器的输出之和：

。训练中整个结构的最终损失定义为

。其中，l_m 是基学习器的损失：

，而 o_m 则是当前学习器 h_m 的输出，r_m 是对应的残差

图 1 右图为新提出的 sGBM 的示意图。可以看到，输入数据的流动过程是一个有向无环图（DAG），因此其整个结果都可通过 SGD 或其变体进行训练，即最小化局部和全局损失目标。算法 2 阐释了这一过程。

算法 2：训练 sGBM

软梯度提升决策树

下面来看看适合 sGBM 的基学习器。研究者在论文中探讨了基学习器是决策树的具体情况。

梯度提升决策树（GBDT）是 GBM 应用最广的实例之一，其使用了硬（而且通常较浅）的二叉决策树作为基学习器。具体来说，这个硬决策树内每个无叶的节点会形成一个轴平行的决策平面，每个输入样本都会根据对应的决策平面被引导至左侧或右侧的子节点。这样的流程是按递归方式定义的，直到输入数据抵达叶节点。最终的预测结果是输入样本所在的叶节点内的类分布。

XGboost、LightGBM 和 CatBoost 等 GBDT 的成功实现已经证明 GBDT 是一种绝佳的数据建模工具，尤其是对于表格式数据而言。

另一方面，软决策树使用了 logistic 单元作为内部非叶节点的路由门，而输入样本的最终预测结果是所有叶节点之间的类别分布的加权和，其中权重是由在内部节点上沿决策路径的 logit 积确定。这样的结构可通过随机梯度下降进行训练，图 2 给出了示意图。

图 2：单个软决策树的示意图

当使用软决策树作为基学习器时，对应的软 GBDT 相较于硬 GBDT 有多项优势。第一，硬 GBDT 并非处理流数据的最佳选择；而 sGBDT 是参数化的，因此整个系统可以根据环境更快地进行调整。第二，在面对多输出回归任务时，硬 GBDT 必须为每个树设置一个维度，这会导致训练效率低下；相较而言，由于 sGBDT 会同时训练所有树，因此速度会快得多。

实验

sGBM 的有效性也在实验之中得到了验证。具体来说，研究者基于同样的基学习器比较了传统硬 GBM 和新提出的软 GBM 在准确度、训练时间、多输出回归、增量学习任务和知识蒸馏能力上的表现。

准确度方面的表现比较如表 2 所示。可以看到，sGBM_CNN 在图像分类任务上的表现优于 GBM_CNN，而 sGBM_MLP 在除 Letter 数据集之外的几乎所有数据集上都有优于 GBM_MLP 的表现。在使用树方法时，相较于经典的 XGBoost 模型，sGBDT 仅在 Letter 和 USPS 数据集上得到了较差的结果。

表 2：分类准确度（均值 ± 标准差）比较。

图 3 和图 4 则展示了 sGBM 相较于传统 GBM 的速度提升效果。可以看出，效果极其显著，这主要得益于 sGBM 能自然地同时训练所有基学习器。

图 3：sGBM 对训练的加速效果。很显然，基学习器越多，加速效果越显著。

图 4：使用 MLP 和 CNN 作为基学习器时的训练时间（秒）。

研究者也探索了添加更多基学习器能否有助于提升准确度表现。结果见图 5，可以看出，答案是肯定的，可以认为主要原因是在 sGBM 的架构设计中基学习器之间有更多的交互。

图 5：具有不同数量的基决策树的 sGBDT 的学习曲线

下表 3、图 6 和表 4 则分别给出了 sGBDT 在多输出回归任务、增量学习设置及知识蒸馏上的表现。总体而言，sGBDT 相较于传统 GBDT 基本都有更优的表现。

表 3：使用 10 个基学习器的均方误差（均值 ± 标准差）。可以看到 sGBDT 在大多数数据集上表现更优，另需注意 sGBDT 可轻松自然地插入其它任务，而硬 GBDT 需要一些额外的修改才行。

图 6：在增量学习设置下的表现比较。相比于 XGBoost，sGBDT 在收敛速度方面优势明显。此外，sGBDT 相比于离线设置的准确度下降也更低。

表 4：sGBDT 和 XGBoost 的知识蒸馏能力对比。sGBDT 同样表现更佳，作者认为原因是 XGBoost 及其它使用硬 CART 树作为基模型的 GBDT 实现在执行多维回归任务时，负责目标维度的树之间交互更少，使得模型难以蒸馏存在于标签分布向量之中的信息。

理论周志华XGBoost梯度提升树梯度提升

2 1

相关数据

周志华人物

周志华分别于1996年6月、1998年6月和2000年12月于南京大学计算机科学与技术系获学士、硕士和博士学位。主要从事人工智能、机器学习、数据挖掘等领域的研究工作。主持多项科研课题，出版《机器学习》(2016)与《Ensemble Methods: Foundations and Algorithms》(2012)，在一流国际期刊和顶级国际会议发表论文百余篇，被引用三万余次。

来源：个人页面 Zhou, Z.

冯霁人物

冯霁，南京大学博士，师从华人机器学习领袖周志华教授，其最近的工作深度森林（deep forest）获得学术界的广泛关注。2018年，冯霁加入创新工厂，担任南京国际人工智能研究院负责人。

来源：Ji Feng

增量学习技术

增量学习作为机器学习的一种方法，现阶段得到广泛的关注。对于满足以下条件的学习方法可以定义为增量学习方法： * 可以学习新的信息中的有用信息 * 不需要访问已经用于训练分类器的原始数据 * 对已经学习的知识具有记忆功能 * 在面对新数据中包含的新类别时，可以有效地进行处理

来源：Polikar R, Upda L, Upda S S, et al. Learn++: An incremental learning algorithm for supervised neural networks Wikipedia

最小二乘法技术

最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。 “最小二乘法”是对过度确定系统，即其中存在比未知数更多的方程组，以回归分析求得近似解的标准方法。在这整个解决方案中，最小二乘法演算为每一方程式的结果中，将残差平方和的总和最小化。

来源：维基百科

信息检索技术

信息检索（IR）是基于用于查询检索信息的任务。流行的信息检索模型包括布尔模型、向量空间模型、概率模型和语言模型。信息检索最典型和最常见的应用是搜索引擎。

来源：机器之心

权重技术

线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。

来源：Google AI Glossary

协同过滤技术

协同过滤（英语：Collaborative Filtering），简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息，个人通过合作的机制给予信息相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选信息，回应不一定局限于特别感兴趣的，特别不感兴趣信息的纪录也相当重要。协同过滤又可分为评比（rating）或者群体过滤（social filtering）。其后成为电子商务当中很重要的一环，即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”，也就是借由社区的喜好提供个人化的信息、商品等的推荐服务。除了推荐之外，近年来也发展出数学运算让系统自动计算喜好的强弱进而去芜存菁使得过滤的内容更有依据，也许不是百分之百完全准确，但由于加入了强弱的评比让这个概念的应用更为广泛，除了电子商务之外尚有信息检索领域、网络个人影音柜、个人书架等的应用等。

来源：维基百科

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

学习曲线技术

在机器学习领域，学习曲线通常是表现学习准确率随着训练次数/时长/数据量的增长而变化的曲线

来源：Wikipedia

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

有向无环图技术

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

来源：维基百科

梯度提升技术

梯度提升是用于回归和分类问题的机器学习技术，其以弱预测模型（通常为决策树）的集合的形式产生预测模型。它像其他增强方法一样以阶段式方式构建模型，并且通过允许优化任意可微损失函数来推广它们。

来源：Wikipedia

损失函数技术

在数学优化，统计学，计量经济学，决策理论，机器学习和计算神经科学等领域，损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

来源：Wikipedia

表征学习技术

在机器学习领域，表征学习（或特征学习）是一种将原始数据转换成为能够被机器学习有效开发的一种技术的集合。在特征学习算法出现之前，机器学习研究人员需要利用手动特征工程（manual feature learning）等技术从原始数据的领域知识（domain knowledge）建立特征，然后再部署相关的机器学习算法。虽然手动特征工程对于应用机器学习很有效，但它同时也是很困难、很昂贵、很耗时、并依赖于强大专业知识。特征学习弥补了这一点，它使得机器不仅能学习到数据的特征，并能利用这些特征来完成一个具体的任务。

来源：Wikipedia

软决策树技术

软决策树作为模糊决策树的一类，通过结合了树的生长和修剪来确定软决策树的结构，并对树进行了修正来提高它的泛化能力。相比较于标准决策树，软决策树的分类结果更准确。此外，一项全球模型方差研究显示，软决策树的方差远低于标准树，这是提高准确度的直接原因。

来源：Olaru, Cristina, and Louis Wehenkel. "A complete fuzzy decision tree technique." Fuzzy sets and systems 138.2 (2003): 221-254.

流数据技术

流数据是一组顺序、大量、快速、连续到达的数据序列,一般情况下,数据流可被视为一个随时间延续而无限增长的动态数据集合。应用于网络监控、传感器网络、航空航天、气象测控和金融服务等领域。

来源：百度百科

随机梯度下降技术

梯度下降（Gradient Descent）是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知，使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。在机器学习中，我们可以利用随机梯度下降的方法来最小化训练模型中的误差，即每次迭代时完成一次评估和更新。这种优化算法的工作原理是模型每看到一个训练实例，就对其作出预测，并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

来源：机器之心

在线学习技术

在计算机科学中，在线学习是一种机器学习方法。和立即对整个训练数据集进行学习的批处理学习技术相反，在线学习的数据按顺序可用，并在每个步骤使用未来数据更新最佳预测器。

来源：维基百科

知识蒸馏技术

Hinton 的工作引入了知识蒸馏压缩框架，即通过遵循“学生-教师”的范式减少深度网络的训练量，这种“学生-教师”的范式，即通过软化“教师”的输出而惩罚“学生”。为了完成这一点，学生学要训练以预测教师的输出，即真实的分类标签。这种方法十分简单，但它同样在各种图像分类任务中表现出较好的结果。

来源：机器之心

XGBoost技术

XGBoost是一个开源软件库，为C ++，Java，Python，R，和Julia提供了渐变增强框架。它适用于Linux，Windows，MacOS。从项目描述来看，它旨在提供一个“可扩展，便携式和分布式的梯度提升（GBM，GBRT，GBDT）库”。除了在一台机器上运行，它还支持分布式处理框架Apache Hadoop，Apache Spark和Apache Flink。由于它是许多机器学习大赛中获胜团队的首选算法，因此它已经赢得了很多人的关注。

来源：Wikipedia

图像分类技术

图像分类，根据各自在图像信息中所反映的不同特征，把不同类别的目标区分开来的图像处理方法。它利用计算机对图像进行定量分析，把图像或图像中的每个像元或区域划归为若干个类别中的某一种，以代替人的视觉判读。

来源：百度百科

创新工场机构

创新工场由李开复博士创办于2009年9月，作为国内的创业投资机构，创新工场深耕在人工智能&大数据、消费和互联网、B2B&企业升级、教育、医疗等领域，并不断探索与创新，致力于打造集创业平台、资金支持、投后服务等的全方位生态投资服务平台。

http://www.chuangxin.com/