提升法是机器学习中的一类方法,通过组合一系列较简单的模型来构建预测模型,其中每个新模型都针对当前组合的不足进行训练。它是集成学习的一种主要形式,用于分类、回归、排序及其他预测任务。这个术语源于一个理论问题:在适当的假设下,能否将一种表现仅略优于随机猜测的学习过程,转化为一种能够达到任意高准确率的学习过程?
提升法的核心特征是相继进行的各个学习阶段之间存在依赖关系。先前的预测结果决定了哪些样本会得到更多关注,或下一个模型将尝试纠正哪些错误。不同算法通过样本权重、残差、损失函数的导数或其他优化信号来实现这一原则。AdaBoost 确立了一个影响尤为深远的分类框架,而梯度提升则建立了提升法与数值优化之间更广泛的联系。现代提升决策树系统广泛用于结构化数据,因为它们无需庞大的神经网络架构,就能表示非线性关系和交互作用。
起源与理论基础
提升法源于20世纪80年代的计算学习理论。迈克尔·卡恩斯和莱斯利·瓦利安特研究了在如今称为概率近似正确学习(简称 PAC 学习)的框架下,弱可学习性与强可学习性是否等价。在这一设定中,学习算法接收从未知分布中抽取的样本,并须以高概率生成预测误差较小的假设。两者的核心区别在于对学习器准确性的要求。
对于二分类问题,弱学习器通常被定义为误差至多为 的学习器,其中 表示相较于随机猜测的优势。强学习器则能够将误差降至任意指定的正容差以下,且所需资源在问题参数和精度要求下受到适当的约束。关键在于,理论上的弱学习条件必须对样本上的所有相关分布均成立。一种方法如果仅在某个有利于自身的分布上表现略优于随机猜测,并不意味着它自然就满足这一假设。
罗伯特·沙皮尔于1990年发表的论文《弱可学习性的力量》,首次在标准的无分布假设 PAC 设定下,给出了两者等价的构造性证明。他的构造方法将基于不同选定分布训练得到的弱假设组合起来。随后,约阿夫·弗罗因德提出了另一种颇具影响力的构造方法,通常称为“多数表决提升法”(boost-by-majority)。这些结果表明,反复调用弱学习过程能够提高预测准确性,而非仅仅重复同样有限的表现。
弗罗因德和沙皮尔于1995年提出了自适应提升(AdaBoost)。与早期的构造方法不同,AdaBoost 不要求用户预先给出弱学习器的优势大小,而是根据每个后续分类器的实际表现,自适应地调整样本权重和投票系数。这使得上述理论原理更易于实现,也推动了它在实践中的应用。AdaBoost 这一名称是“adaptive boosting”(自适应提升)的缩写。
另一项重大发展是将提升法与统计模型拟合联系起来。20世纪90年代末,利奥·布雷曼从优化的角度解释了 AdaBoost,而杰罗姆·弗里德曼、特雷弗·哈斯蒂和罗伯特·蒂布希拉尼则从加性逻辑回归的角度对其进行了阐释。弗里德曼于2001年发表的梯度提升论文提供了一个通用框架,通过在函数空间中沿着使损失减小的方向前进来拟合加性模型。因此,提升法的历史发展包含两项相互关联但又有所区别的成就:一是证明弱学习的效果可以得到增强,二是发展出通过依次构建模型来最小化预测损失的实用方法。
序列式集成与基学习器
提升法构建的预测器通常是如下形式的加性模型:
其中, 是初始预测, 是在第 阶段拟合的模型, 控制该模型的贡献。根据算法的不同,最终输出可以是实数值预测、类别得分、经变换得到的概率,或排序得分。加性结构是提升法的根本特征,但各类提升方法训练每个 的方式有所不同。
在监督学习中,学习器接收由输入 及其对应目标 组成的训练数据。普通模型可能只在固定目标函数下,对全部样本进行一次拟合。提升法则会依次构造一系列拟合问题。AdaBoost 改变样本的相对权重;采用平方误差的梯度提升则拟合当前集成模型的残差。这两种过程都使后续模型依赖于当前集成模型,而不是将各个模型视为相互独立的估计。
由决策树学习生成的小型树是尤为常见的基学习器。决策树桩仅进行一次分裂,通常有两个叶节点区域。较深的树可以在单个阶段内表示更复杂的交互作用。“弱学习器”一词有时被非正式地用来指代任何小型基模型,不过,这种实践中的用法比形式化的弱学习条件更宽泛。对于理论上的提升过程可能产生的每一种分布,浅层树并不一定都能取得优于随机猜测的表现。
树深度的选择决定了集成模型能够表示的结构。在给定特征表示方式下,多个树桩之和形成的是各个单一特征效应的加性组合。具有两次或更多连续分裂的树可以表示交互作用,例如价格对不同客户群体的影响有所不同。反复迭代会增加拟合分量的数量,但无法消除基学习器类别所施加的全部结构限制。尤其是,仅仅增加树桩的数量,并不能在原始输入变量之间产生任意的交互作用。
提升法不同于自助聚合:后者在重采样得到的数据集上拟合模型,再汇总其预测结果,各次拟合之间通常具有较强的独立性。随机森林则在一种相关的树集成策略中进一步引入特征随机化。提升法引导后续拟合着重弥补现有集成模型的不足,而自助聚合主要通过平均来提高对数据变化敏感的学习器的稳定性。人们常说,自助聚合降低方差,而提升法降低偏差;这种说法有助于粗略区分二者,却不是普遍规律:提升法可能同时影响偏差和方差,具体取决于模型容量、损失函数、数据和停止规则。
AdaBoost 与自适应样本加权
标准的离散 AdaBoost 算法适用于二分类,其中标签为 ,基分类器为 。算法首先为所有样本赋予相同的权重,通常为 。在第 轮,使用当前权重拟合一个基分类器,并按下式计算其加权错误率:
在通常的更新规则中,该分类器获得的系数为
因此,加权错误率越低,分类器的影响就越大。错误率为 的分类器获得的权重为零;通常的算法流程要求分类器的表现优于这一水平,才能取得进展。错误率为零是一个极限情形,此时上述系数发散,因此实际实现会通过终止训练或采取数值保护措施来处理。
样本权重按下式更新:
其中, 用于归一化,使权重之和为一。分类正确的样本,其权重乘以 ;分类错误的样本,其权重则乘以 。因此,下一个学习器面对的样本重要性分布发生了变化。最终分类器取加权投票结果的符号:
例如,若某个学习器的加权错误率为 ,则 。在归一化之前,分类错误的样本权重乘以 ,而分类正确的样本权重乘以 。因此,前者与后者的权重之比变为原来的四倍。这并不意味着每个难以分类的样本最终都必然会被正确分类:下一个学习器的表示能力仍然有限,必须在所有加权样本之间进行权衡。
AdaBoost 对训练错误率有一个尤为明确的保证。记 ,则最终投票结果对训练样本的误分类比例,其上界为
因此,只要持续保持正向优势,训练错误率就会随着轮数增加而呈指数下降。这一结论针对的是训练样本,并不直接保证模型在未见数据上的表现也能同样迅速地改善。不断变化的权重还可能使学习器将注意力集中到标签错误或本身就存在歧义的样本上,在评估算法对噪声的敏感性时,这一点尤为重要。
损失最小化、间隔与泛化
AdaBoost 可以理解为一种逐步降低指数损失的过程,其损失函数为
在某一步中,选择一个输出为二元值的分类器及其系数,使这一目标函数减小,就能得到熟悉的加权误差准则和系数公式。各样本的权重与其在当前集成模型中的指数损失贡献成正比。这一解释将自适应重加权与经验风险最小化联系起来,而不是将其视为一种孤立的投票启发式方法。
对于二元标签, 是有符号间隔:正值表示分类正确,数值越大,表示有符号得分越高。归一化投票间隔则将其除以投票权重总和,使比较结果较少受集成模型整体尺度的影响。即使样本已被正确分类,只要其间隔继续增大,指数损失就会继续下降。因此,在训练集分类错误率达到零之后,提升法仍可能继续改变模型。
这种行为推动了基于间隔来解释泛化(机器学习)的研究。针对投票分类器推导的误差界,将预测误差与训练样本中小间隔样本的比例,以及基学习器类别的复杂度度量联系起来。这些结果有助于解释,为什么仅凭组成集成模型的分类器数量,不足以衡量模型的有效复杂度。但这并不意味着每增加一轮提升都能改善测试性能,也不意味着最大化某一个间隔统计量总能得到最好的预测模型。
从统计角度理解提升法,还可以将提升模型的得分与条件类别概率联系起来。若 ,则在不施加函数形式限制时,使总体条件指数损失最小的函数满足
相应的概率转换公式为 。其中的系数 2 取决于得分的定义约定;直接使用逻辑斯蒂损失训练的模型,通常以完整的对数优势作为得分。在有限样本下,不能仅凭这一总体层面的关系,就认为集成模型的数值得分一定能转换为校准良好的概率。
提升法与过拟合之间的关系也很复杂。在某些数据集上,即使进行很多轮提升,留出集上的准确率也几乎不会下降;但标签噪声、样本量小或基学习器过于灵活,都可能导致严重的过拟合。拟合所得预测模型的方差、损失函数的尾部行为,以及在模型空间中经过的路径,都会产生影响。指数损失对较大的负间隔尤为敏感,因此少数样本可能会产生越来越大的影响。这些观察说明,关于训练误差的定理,并不等同于对预测可靠性的完整统计解释。
作为函数优化的梯度提升
梯度提升将逐步加性建模的思想推广到广泛的可微损失函数。给定观测数据 ,它旨在寻找使下式最小的函数 :
初始模型通常取为一个使上述目标最小的常数。在第 阶段,该方法为每个样本计算损失函数的负导数:
然后用基学习器 拟合这些值。它们通常称为伪残差,因为它们是普通回归残差的推广。
对于平方误差损失 ,伪残差恰好为 。因此,下一个模型预测的是现有集成模型尚未解释的部分。对于标签为 和 、以对数几率作为得分 的二元逻辑损失,负导数为 ,其中 是当前估计的概率。置信度很高却预测错误的样本会收到较强的修正信号,但这种信号不同于 AdaBoost 中按指数增长的权重。
基本的更新形式为:
其中, 可以通过线搜索求得,而 通常介于零和一之间,称为收缩因子或学习率。在树提升中,具体实现通常会为每个叶节点对应的区域分别计算更新值,而不只是使用一个共享系数。较小的更新通常需要更多阶段,因此既会改变计算成本,也会改变模型逼近拟合解的路径。
许多现代实现会利用二阶信息。若用 和 分别表示损失函数对当前得分的一阶和二阶导数,就可以借助二次近似高效地评估候选分裂。对于包含观测样本集合 的叶节点,一种常见的正则化叶节点值为:
其中, 用于惩罚过大的叶节点值。这类似于一种受限的牛顿更新。具体的分裂准则还取决于增加叶节点的惩罚项,以及各实现特有的约束条件。
这一框架可用于逻辑损失、计数建模、稳健回归及其他目标。绝对误差损失和分位数损失在不可微点需要特殊处理,例如使用次梯度或适当的分区域更新。这里的重要区别在于:“拟合残差”对于平方误差而言是字面意义上的准确描述,但对于其他损失而言只是一种简略说法。梯度提升拟合由目标函数的导数指示的方向,并将该方向限制在基学习器能够表示的函数范围内。
向多分类预测、排序及其他目标的扩展
提升法并不局限于二分类问题。早期的扩展包括 AdaBoost.M1 和 AdaBoost.M2,它们采用不同的形式处理多分类问题。AdaBoost.M1 保留了加权误分类准则,但要求每个选中的学习器的加权错误率低于二分之一;当类别较多时,这一条件相当苛刻。由朱季、Saharon Rosset、邹辉和 Trevor Hastie 提出的 SAMME,采用了多分类指数损失形式。在一种常见的投票约定下,其系数为
其中, 为类别数。此时,要获得正权重,学习器的准确率必须高于均匀随机猜测的准确率 。
多项梯度提升则为每个类别维护一个得分,并通过 softmax 变换将得分向量转换为概率。更新由多分类交叉熵的导数决定。根据具体实现,一个提升阶段可以为每个类别分别构建一棵树,也可以采用叶节点取值为向量的结构。这一区别既影响内存需求,也影响类别之间共享信息的方式。
回归进一步拓宽了预测目标和损失函数的选择范围。平方误差提升更侧重较大的数值误差,而绝对误差目标则以条件中位数为预测目标。分位数提升通过对高估和低估施加不对称惩罚,以指定的条件分位数为预测目标。对于计数数据,泊松损失提升可将对数连接函数与加性得分相结合,确保预测均值为正。选定的似然函数提供了拟合目标,但这并不意味着数据实际上满足该似然模型的所有假设。
提升法在学习排序中也占有重要地位,其目标是对同一查询或其他分组内的项目进行排序。成对方法利用项目得分之间的差异,对顺序错误的项目对施加惩罚。LambdaMART 将提升回归树与专门设计的更新信号相结合,使这些信号反映排序偏好,以及排序指标下交换位置的重要程度。这类信号并不总是某个全局光滑目标函数的普通梯度,因此,实际应用中的这类方法比教科书中基于可微损失的提升法涵盖面更广。在训练和评估的相关环节中,同一查询对应的项目组必须保持完整。
另一些扩展则改变了提升过程本身的动态机制。随机梯度提升在每个阶段使用随机抽取的观测子样本进行拟合,将逐步纠错与基于采样的正则化相结合。特征子采样进一步改变了每个阶段可供选择的候选函数。有些方法在拟合新树时会随机暂时排除已有的树,将随机失活背后的思想应用于加性树集成。代价敏感提升通过调整损失或权重来体现不同错误的代价差异,还有一些专门的形式用于处理生存结局和删失观测。这些变体都具有迭代组合的结构,但不一定采用与 AdaBoost 完全相同的重新加权规则,也不一定具有相同的训练误差界。
实现与计算结构
提升树的实际计算开销主要来自反复寻找有效的划分。对于每个候选划分,学习器都会评估节点划分对目标函数的影响。精确方法考察按特征值排序后所确定的阈值。直方图方法则先将数值映射到数量有限的分箱中,再在各分箱内汇总计数或导数统计量。这大幅减少了需要考察的阈值数量,代价是只能近似表示可选的划分位置。
陈天奇与 Carlos Guestrin 于 2016 年介绍的 XGBoost,将带正则化的树模型目标函数与多种系统技术相结合,涵盖稀疏数据处理、并行划分评估、缓存感知处理,以及超出内存容量的数据计算。它的重要性不在于发明了梯度提升本身,而在于将数学方法与工程设计整合成一个高效的通用系统。通过学习缺失值的默认去向,树可以根据训练过程中获得的增益决定将缺失值分配到哪个分支,而不必事先填补所有缺失项。
柯国霖及其同事于 2017 年推出的 LightGBM,着重于在大型数据集上高效训练提升树。其公开发表的技术包括基于梯度的单边采样和互斥特征捆绑。前者保留梯度幅值较大的样本,同时对其他样本进行采样并重新赋权;后者将满足互斥条件的特征组合起来,以降低有效维度。其标志性的按叶生长策略会扩展估计增益最大的叶节点,而不是同时扩展同一深度的所有节点。由于这种策略可能生成高度不平衡的树,深度和叶节点数量的约束仍然很重要。
Yandex 的研究人员于 2017 年推出、并在 2018 年的一篇研究论文中介绍的 CatBoost,着重处理类别变量,以及某些依赖目标值的训练过程所引起的预测偏移。其有序方法利用随机排列,使某个观测的目标值不会直接参与计算用于编码该观测本身的目标统计量。有序提升也以类似方式,在构建训练预测时施加限制,以减少这类偏差。该系统还以采用对称树著称:在同一深度的所有节点上使用相同的划分,从而实现紧凑的表示和高效的预测。
提升法的顺序依赖关系限制了常规提升轮次之间的并行计算,但单轮内部仍有大量工作可以同时执行。特征处理、直方图构建、数据分区处理以及导数聚合都可以并行执行,也可以在图形处理器上进行。分布式计算会引入通信开销,因为各工作节点必须合并用于选择划分的充分统计量。在预测阶段,不同的树可以独立求值,但内存访问、树深度和批量大小会显著影响实际吞吐量。因此,训练速度与预测服务速度是两个不同的性能指标。
应用及与其他模型家族的关系
提升树广泛用于结构化或表格数据集:这类数据集中的记录由交易金额、产品类别、时间戳和测量属性等字段构成。提升树的吸引力源于其预测模型的形式。阈值分裂能够捕捉非线性效应,树中的路径能够表达交互作用,而集成模型则汇总了许多局部修正。数值输入通常不需要仅仅为了让树的分裂有意义而进行特征缩放,不过,数据变换仍可能改变有用的表示方式或数值行为。
应用场景包括需求预测、客户响应预测、欺诈检测、设备故障预测和工业质量监控。在这些场景中,输入往往是一组经过特征工程处理的测量数据,而不是原始图像或音频。例如,在预测问题中,提升模型可以使用滞后观测值、日历指标、近期均值和外部变量。树本身并不会自动提供时序模型:这些输入的构造方式及其可用性,决定了模型能够学到哪些时间信息。
提升法在计算机视觉领域有着重要的应用历史。保罗·维奥拉和迈克尔·琼斯于 2001 年提出的人脸检测框架,在级联分类器中采用了基于 AdaBoost 的方法来选择和组合简单的图像特征。级联的早期阶段以相对较少的计算量排除大量非人脸窗口,后续阶段则更细致地检查剩余候选窗口。这一应用展示了提升法如何在更大的架构中同时用于预测和特征选择。级联机制与单个分类器内部的加权投票是不同的机制。
在信息检索中,提升排序模型结合文本匹配程度、文档属性和行为特征等信号,对候选结果进行排序。在推荐系统中,这类模型可以结合用户、物品和上下文属性,也可以用作后续阶段的排序模型。这些应用往往高度依赖特征工程,并且需要先检索出规模可控的候选集,再使用计算成本较高的评分模型。因此,提升模型经常只是多阶段决策流程中的一个组成部分。
提升法与深度学习的关系是互补的,而不是两种技术在所有场景下的竞争。神经网络能够学习分布式表示,对许多原始感知输入和语言输入尤其有效;提升树则对固定特征向量施加了不同的归纳结构。神经网络生成的嵌入表示可以作为特征输入提升模型,多个模型家族的预测结果也可以在更大的集成模型中加以组合。相对性能取决于样本量、特征结构、预测目标、调优投入和评估设计。没有任何模型家族能在所有数据集上无条件地占据准确率优势,而基准测试结果只能说明模型在该测试特定实验条件下的性能。
模型选择、解释与局限性
迭代轮数、学习率、树深度、最大叶节点数、叶节点最小样本数以及采样比例是主要的超参数。它们相互影响,而非各自独立起作用。较小的学习率通常需要更多轮迭代;较深的树能够刻画更复杂的交互关系,但也可能拟合样本中更小、稳定性更差的局部区域。正则化可以约束叶节点的取值、对新增叶节点施加惩罚、限制树的生长,或引入采样。早停法根据模型在验证集上的表现来选择停止时机,而不是假定持续降低训练损失始终有益。
评估必须反映模型未来生成预测的实际过程。如果同一客户、机器或文档来源同时出现在训练部分和评估部分中,随机划分记录就可能产生误导。与时间有关的任务往往需要按时间先后划分数据。未来信息、由目标变量衍生的编码,或在训练分区之外拟合的预处理步骤,都可能造成数据泄漏。最终的测试集用于估计模型选择完成后的性能;如果反复利用它来选择配置,它就成了模型选择过程的一部分。在使用重复重采样时,嵌套交叉验证可以将调参与性能估计分开。
误差指标也决定了何为“改进”。分类准确率不考虑预测概率的数值大小及其校准情况,而对数损失则用于评价概率预测。稀有事件任务可能需要进行精确率—召回率分析,或评估指定决策阈值下的性能。分位数回归的评估方式不同于均值预测,而排序指标必须按查询组进行评估。调整类别权重可能改善所选的加权目标,却也会改变预测概率的含义,因此不应将排序质量与校准程度视为可以互相替代的性质。
解释技术包括分裂次数、累计分裂增益、置换重要性,以及基于沙普利值的方法。这些技术描述的是已拟合模型的不同性质。基于分裂的重要性指标可能偏向可用分裂机会较多的特征,而相关的输入变量可能相互替代,从而掩盖各自的贡献。部分依赖图可能会评估数据中罕见甚至从未出现过的特征组合。对某次预测的解释,描述的是特定方法下的模型行为,并不能确立因果关系。
模型结构与训练目标直接带来了一些重要局限。普通回归树在叶节点所对应的区域内预测一个常数,因此由它们构成的集成模型无法自然地将数值变化趋势外推到已观测特征范围之外。在某些损失函数下,标签噪声和极端观测值可能使模型投入过多精力去拟合它们。大型集成模型会增加存储和推理成本,而灵活的模型可能利用不稳定的相关关系。在发生分布偏移时,即使某种历史关系曾被准确拟合,也可能不再成立。标准提升算法本身也不提供有效的预测区间,亦不保证对不同群体的公平对待;这些性质需要另行定义,并采用专门的方法和评估手段。