AdaBoost 是 **adaptive boosting(自适应提升)**的缩写,是一种通过组合一系列相对简单的模型来构建预测模型的监督学习方法。它是提升法的基础算法,也是集成学习的重要代表。在其经典的分类形式中,后续每个模型都在同一数据集重新赋权后的版本上训练:当前模型误分类的样本获得更高的相对权重,而正确分类的样本则获得更低的相对权重。最后,通过加权投票汇总各模型的预测结果。
AdaBoost 由约阿夫·弗罗因德和罗伯特·沙皮尔于 1995 年提出,在弱学习的理论成果与实用分类系统之间架起了桥梁。它的重要性并不局限于某一种具体实现。该算法帮助确立了这样一种认识:许多准确率不高的预测器可以组成准确率很高的集成模型;它还推动了对分类间隔和泛化(机器学习)的研究,并成为对损失函数进行逐阶段优化的典型范例。
AdaBoost 这一名称通常指采用指数权重更新的二分类算法,不过也有相关形式用于多分类、实值预测和回归。其表现取决于基学习器、提升轮数、学习率以及训练标签的质量。AdaBoost 尤其常与浅层决策树,以及早期实时目标检测器所采用的特征选择过程联系在一起。
历史起源与理论背景
AdaBoost 源于计算学习理论中的一个问题:能否将一种表现仅略优于随机猜测的学习方法,转化为误差任意小的学习方法?这里区分的是两类学习器:一类是弱学习器,其预测优势虽然不大,却具有系统性;另一类是强学习器,在适当假设下能够达到很高的准确率。最初的理论问题关注的是可学习性,而不仅仅是将几个现有模型的结果取平均能否提高基准测试得分。
1990 年,罗伯特·沙皮尔证明,在标准的分布无关学习框架下,弱可学习性蕴含强可学习性。此后,约阿夫·弗罗因德又提出了其他提升算法的构造方法。这些成果确立了提升的可行性,但早期方法并不十分适合常规的统计建模。尤其在实际应用中,更需要一种能够根据各轮基学习器的实际表现作出调整的方法,而不必预先指定它们相对于随机猜测的固定优势。
弗罗因德和沙皮尔在 1995 年的论文《在线学习的决策理论推广及其在提升中的应用》中提出了 AdaBoost;扩充后的期刊版本于 1997 年发表。该算法将提升与乘法权重更新联系起来。乘法权重更新是一大类方法,会根据观测到的表现,反复增大或减小各个备选项的影响力。在 AdaBoost 中,被赋予这些权重的是训练样本。另有一个独立的系数,用于决定每个训练所得的分类器对最终预测的影响力。
“自适应”一词指的是算法根据各个组成分类器的实测误差作出调整的方式。每一轮的加权误差既决定该分类器的投票权重,也决定下一轮训练样本的分布。与某些早期的提升构造方法不同,标准 AdaBoost 流程不要求预先知道基学习器相对于随机猜测的优势所具有的共同下界。这种自适应性并不意味着可以免除弱学习条件:基学习器仍须在训练过程中产生的各个分布上提供有用的预测。
20 世纪 90 年代末的实验表明,对决策树进行提升能够显著提高预测准确率。研究人员还观察到,在某些情况下,训练误差降至零后,测试误差仍会继续下降,这对仅以拟合训练标签来解释算法表现的观点提出了挑战。随后,围绕间隔、加性统计模型和函数优化的研究相继展开。弗罗因德和沙皮尔因其在提升领域的工作获得了 2003 年哥德尔奖。由此,AdaBoost 不仅成为一种实用的分类方法,也成为理解按顺序组合而成的模型如何泛化到训练数据之外的重要研究对象。
经典二分类算法
标准的离散 AdaBoost 算法适用于二分类。设训练数据包含 个样本 ,其标签为 。在第 轮,算法为各样本维护非负权重 ,所有权重之和为一。若采用均匀初始化,则 。基学习器利用这些权重进行拟合,得到分类器 。
该分类器的加权错误率为
当 时,AdaBoost 为该分类器赋予如下系数:
随后,按下式更新样本权重:
其中, 用于对权重进行归一化。由于预测正确时 等于 ,预测错误时等于 ,因此在归一化之前,分类正确的样本权重乘以 ,分类错误的样本权重则乘以 。
经过 轮后,集成模型的得分与预测分别为
当得分恰好为零时,需要约定如何给出预测。这些系数使最终决策采用加权投票,而非简单的多数投票:加权错误率较低的分类器,其系数比表现仅略优于随机猜测的分类器更大。重要的是,错误率是在当前权重分布下评估的,而不一定是在最初的均匀分布下评估的。
例如,加权错误率为 时,得到 ,约为 。归一化之前,分类错误的样本权重乘以 ,分类正确的样本权重乘以 。因此,每个误分类样本相对于每个正确分类样本的权重都变为原来的四倍。采用最优系数时,在下一轮的权重分布下,误分类样本的权重总和变为二分之一。该算法并非只是在不断积累一份固定不变的困难样本清单;每个新分类器都会改变哪些样本最为重要。
有两种边界情况需要明确处理。如果 ,系数公式会发散,因此实现时通常会停止训练,或约定使用一个有限值。如果 ,系数为零,该分类器对最终结果没有贡献。在对称的二分类假设类中,可以将表现劣于随机猜测的分类器的输出取反,但实际实现也可能选择弃用该分类器或终止训练。此外,AdaBoost 并不保证每个样本的权重都单调上升:同一个样本在不同轮次中可能交替出现分类正确和分类错误的情况。
指数损失与逐阶段优化
AdaBoost 可以理解为一种在加性模型上最小化指数损失的方法。对于评分函数 ,定义经验目标函数为
带符号得分 为正表示分类正确,为负则表示分类错误。带符号得分越大,指数损失越小;而当预测以很高的置信度给出错误结果时,指数损失会迅速增大。因此,与那些在得分为绝对值很大的负数时仅线性增长的损失函数相比,指数损失对严重误分类的样本更为敏感。
假设当前模型为 ,下一阶段的模型形式为
在加入新分类器之前,样本 对损失的贡献与 成正比。将这些量归一化,得到的恰好就是分布 。对于取值为二元类别标签的候选分类器 ,更新后的损失正比于
其中, 是其加权错误率。对 求导可得
因此,这个看似特殊的投票系数,实际上来自对指数损失的一维精确最小化。
这一解释将 AdaBoost 纳入了经验风险最小化的框架,但在计算方式上有一个重要限定。它是一种逐阶段方法:每加入一个新分类器后,通常会保留先前的分类器及其系数,而不是对它们重新进行联合拟合。每一轮,算法都从可用的基学习器中选择一个新方向,并沿该方向前进。如果学习器只是近似地最小化加权分类错误率,那么相应的优化步骤也是近似的。最终能够得到的模型既受基学习器族的限制,也受这一序贯搜索过程的限制。
AdaBoost 与梯度提升的关系也源于同一个目标函数。指数损失对每个训练样本得分的负导数与 成正比,因此其绝对值就是当前的样本权重。一般的梯度提升方法利用适当的梯度信息来拟合学习器,并且适用于许多其他可微损失函数。相比之下,经典的离散 AdaBoost 使用加权分类,以及一个特定的闭式系数。它与函数空间中的梯度方法密切相关,但并不等同于所有被称为梯度提升的算法。
指数损失在总体层面也有概率解释。若 ,则当 时,最小化条件期望指数损失可得
由此可得变换关系 。然而,这一关系描述的是理想的最优解,并不保证训练得到的集成模型所输出的有限得分能够对应校准良好的概率。基学习器的限制、有限样本、正则化以及优化过程的历史都会影响这一解释的适用性。
训练误差界、间隔与泛化
AdaBoost 的一个核心理论性质是其训练误差的上界。假设初始权重均匀,并采用不含学习率缩减的经典更新方式,则归一化常数满足
由于误分类样本或零间隔样本的指数损失至少为一,这类样本所占的比例不会超过上述乘积。采用标准系数时,
令 ,其中 表示学习器相较于随机猜测的优势,可得
如果每一轮的优势都至少为某个固定值 ,那么这一上界就会随迭代轮数呈指数下降。
这一结果的条件性至关重要。它并不能证明,任意选定的基学习器都能无限期地保持正优势。随着样本分布发生变化,先前有效的假设族可能不再包含足够准确的分类器。同样,训练误差上界很小,本身也不能保证模型在未见过的观测数据上具有较低的误差。这一论证针对的是已观测到的数据集,以及拟合过程中取得的加权误差。
与简单区分预测正确或错误相比,分类间隔提供了更细致的描述。当投票系数为正时,一种常用的归一化间隔定义为
其取值介于 和 之间。正值表示加权投票结果正确;接近零的值表示投票胜负接近;较大的正值则表示各模型对真实标签具有较强的一致支持。即使所有训练样本都已被正确分类,这些间隔的分布仍可能继续变化。
20 世纪 90 年代发展起来的基于间隔的分析,将泛化能力与间隔低于某个选定阈值的训练样本比例联系起来,同时纳入了基假设类的复杂度项和样本量相关项。这些结果有助于解释:尽管集成模型的规模不断扩大,增加分类器却不一定会导致过拟合。仅靠统计树的数量,并不足以刻画这里相关的统计复杂度。
不过,间隔并不能完整解释 AdaBoost 的每一种学习曲线。标准 AdaBoost 并不总能最大化最小归一化间隔,而算法之间的比较可能取决于整个间隔分布,而非仅取决于其最小值。此外,训练过程中优化的损失并未经过归一化:在可分数据上,随着评分的绝对值无限增大,损失仍可持续下降。因此,泛化能力共同取决于数据分布、样本量、可用的基学习器、停止规则,以及拟合所得集成模型的几何结构。
基学习器、表示能力与计算成本
AdaBoost 是一种组合预测器的方法,而非某种固定的模型架构。它的基学习器必须能够有效利用样本权重。加权拟合方法可以将这些权重直接纳入划分准则或其他目标函数。如果学习器只接受不带权重的观测数据,也可以按照当前分布对样本进行抽样。这种重采样会引入额外的随机性,而且在重采样数据集大小有限时,只能近似实现直接加权拟合的效果。
最常见的基学习器是决策树桩,即只进行一次划分的决策树。对于数值特征,它可以根据 是否成立来对观测样本分类,在阈值两侧赋予相反的标签。训练时会搜索特征、阈值以及两侧标签的分配方式,以最小化加权误差。一个树桩表示的规则非常简单,但多个树桩可以构成表达能力丰富得多的分类器。因此,使用树桩的 AdaBoost 是由低容量组件构建高表达能力模型的一个重要例子。
基学习器的结构决定了集成模型能够表示哪些交互作用。由针对单个数值特征的树桩组成的集成模型,其加性评分具有如下形式:
其中,每个 都由特征 上各阈值对应的贡献组合而成。虽然最终的分类边界可能很复杂,但该评分并不直接包含不同特征之间的任意交互作用。更深的树则通过在同一路径上检验多个特征来引入交互作用。因此,不能认为在提升轮数相同的情况下,提升树桩与提升更深的树是等价的。
对于 个样本和 个数值特征,一种直接的树桩搜索方法是按特征值对观测样本排序,并考察候选阈值。对所有特征分别排序的成本约为 ;如果复用排序结果,后续每一轮就可以在 时间内扫描并评估各候选划分的加权误差。这些只是用于说明的时间复杂度估计,并非适用于所有实现的保证。稀疏数据、类别变量、缺失值、树的深度以及专门的划分搜索方法,都会改变实际成本。使用 个树桩进行预测时,通常需要对每个观测样本执行 次简单检验。
各轮提升之间存在固有的先后依赖:第 轮需要使用由第 轮计算得出的权重。不过,搜索不同特征或评估候选划分时仍可采用并行计算。当大量指数更新导致权重极不均衡时,数值稳定性也很重要。在对数域中计算并谨慎进行归一化,可以减少下溢或上溢。相比之下,对权重进行截断会改变算法的数学定义,并可能改变其行为。结果的可复现性还可能取决于如何在同样优良的划分之间打破平局,以及基学习器中是否存在随机因素。
多分类、实值与回归变体
常见的二分类算法并不是 AdaBoost 的唯一形式。它的各种扩展在标签表示、对基学习器准确率的要求以及更新规则上各不相同。这些区别很重要,因为适用于标签取值为 的公式,不能直接套用于具有多个类别或连续目标值的问题。因此,“AdaBoost”既指一种特定算法,也指一个算法家族。
AdaBoost.M1 是面向多分类的一种早期扩展。对于每个样本,它只区分基分类器的预测是正确还是错误,并要求基分类器的加权错误率低于 。当类别较多时,这一条件可能远比“优于均匀随机猜测”更为严格。相比之下,AdaBoost.M2 对真实类别与错误标签之间的比较进行加权,从而采用了不同的弱学习条件。这两种方法都不是将二分类中的标签乘积更新规则原封不动地应用于多分类标签。
Ji Zhu、Hui Zou、Saharon Rosset 和 Trevor Hastie 在 2009 年发表的研究中提出了 SAMME,给出了一种广泛使用的多分类形式。对于 个类别,一种常见的系数约定为
分类错误的样本的权重乘以因子 ,随后进行归一化;预测时则选择累计票数最多的类别。当 时,该系数为正,这与均匀随机猜测所对应的错误率阈值一致。当 时,这一约定会得到与经典二分类算法相同的权重调整结果,不过投票系数的数值相差一个正的比例因子。
实值 AdaBoost(Real AdaBoost)允许基学习器提供实值输出,而不只是类别标签。这些输出可以表示局部的类别概率信息,通常采用对数几率的一半进行变换。这样,单个基学习器就能在某些区域表达比其他区域更高的置信度。Jerome Friedman、Trevor Hastie 和 Robert Tibshirani 在 2000 年前后提出的统计学分析,将这类方法与加性建模联系起来,并引入了 LogitBoost。LogitBoost 优化的是逻辑斯蒂目标函数,而不是指数目标函数。实值 AdaBoost 与 LogitBoost 彼此相关,但属于不同的算法。
回归需要采用不同的处理方式,因为对于通常的实值预测,并没有直接对应于二分类中“正确或错误”指示量的概念。Harris Drucker 于 1997 年提出的 AdaBoost.R2 根据归一化后的预测损失确定样本权重,并通过加权中位数组合回归器,而不是采用经典的带符号投票方式。选择不同的回归损失会产生不同的行为。因此,多分类、实值和回归变体都必须分别明确其目标函数、系数约定及聚合规则;同样以 AdaBoost 为名的软件实现,未必实现的是这一算法家族中的同一成员。
噪声敏感性、正则化与评估
AdaBoost 将注意力集中于难以预测的观测样本,这既是其核心机制,也是其脆弱性的来源。一个样本难以预测,可能是因为它揭示了有价值的决策边界,也可能是因为其标签错误、特征受损,或与其余样本之间的关系异常。指数损失并不区分这些原因。如果一个观测样本的带符号得分持续为负,它就可能在后续轮次中获得不成比例的影响力,因此,标签错误或相互矛盾的样本可能显著左右整个集成模型。
这种行为说明,对 AdaBoost 鲁棒性的论断需要附加条件。AdaBoost 使用较弱的基学习器也能取得良好表现,并且在集成规模的相当大范围内能够抵抗过拟合,但它并非天生不受标签噪声影响。特征向量相同、标签却相反的样本揭示了一个结构性问题:任何仅使用这些特征的确定性分类器,都不可能将两者同时正确分类。增加轮次可能只会不断调整它们的影响力,而无法消除根本矛盾。因此,数据质量问题可能产生与真正具有信息价值的困难样本相似的权重模式。
一种常见的正则化方式,是用学习率 对每轮新拟合的系数进行缩放,通常取 :
较小的步长通常需要更多轮次才能达到相近的训练拟合程度,也会改变模型在模型空间中的演进路径。引入收缩后,这一步便不再是经典推导中完整的一维最小化步。因此,归一化常数和下一轮错误样本总权重的常见精确公式,不能再原样套用。
其他超参数包括估计器数量、树深度、叶节点最小样本数,以及对特征搜索施加的各种限制。限制树深度会改变模型所能表示的交互作用类型;限制轮次则约束了逐阶段添加模型的次数。早停法利用模型在留出数据上的表现,判断何时继续拟合已无助益。可以通过验证集或交叉验证评估这些选择,再用独立的测试集估计模型选择完成后的性能。
评估时还必须区分分类准确率、概率估计质量和具体应用中的代价。类别频率不均衡时,总体准确率可能掩盖模型在少数类上的不佳表现。样本的初始权重和决策阈值都可以改变模型在实际应用中的表现,但两者的作用并不能相互替代。如果需要概率估计,可以将概率校准与排序或分类性能分开评估。如果使用评估样本来拟合预处理步骤、进行特征选择或拟合校准模型,就会造成数据泄漏(机器学习);AdaBoost 内部逐轮调整权重的机制并不能防止这类实验错误。
应用与 Viola–Jones 检测器
AdaBoost 已被用于结构化数据分类、识别、文本分类,以及其他能够构建有效的加权基学习器的问题。当候选规则数量众多、计算成本低廉,而其中只有部分规则具有信息价值时,它的优势尤为明显。在每一轮中,学习器都可以选出最能区分当前加权样本的规则。由于只有被选中的规则才会纳入集成模型,提升法既进行预测,也实现了一种形式的特征选择。
AdaBoost 在历史上最著名的应用,是保罗·维奥拉(Paul Viola)和迈克尔·琼斯(Michael Jones)于 2001 年提出的 Viola–Jones 目标检测框架。该框架将矩形图像特征、利用积分图进行的高效特征计算、基于 AdaBoost 的特征选择,以及级联分类器结合起来。这些组成部分分别解决了不同的计算问题:快速计算候选特征、从庞大的特征池中进行选择,以及在执行高成本处理之前排除大多数不含目标的窗口。
矩形特征衡量的是相邻区域内像素强度总和之间的差异。这类特征能够响应粗略的明暗对比,例如某些正面人脸图像中,眼部区域相对于邻近面部区域更暗的现象。积分图存储像素强度的累积和,使得只需固定次数的数组访问,就能得到任意矩形区域的像素强度总和。弱分类器通常对单个特征设置阈值,并选定判别方向。AdaBoost 会选出一系列有效的“特征—阈值”规则,并为它们分配权重,从而构成一个更强的分类器。
分类器级联与单个阶段内部的提升过程并不相同。前期阶段规模较小,能够快速排除大量背景窗口。后期阶段只检查通过前面测试的窗口,并且可以使用更多特征。各阶段的阈值被设定为在保留高比例真实目标的同时,逐步减少误报。因此,大多数窗口所消耗的计算量仅占完整检测流程的一小部分。检测器的速度不能仅归功于 AdaBoost:高效的图像表示和级联组织方式同样是这一设计的核心。
在现代深度学习检测器占据主导地位之前,该框架使人脸检测能够在当时的硬件上切实运行。因此,它在算法和历史两个层面都具有重要意义:它展示了如何将基于学习的简单测量项选择,与经过明确工程设计的计算架构相结合。后来,基于卷积神经网络及其他学习所得表示的系统,大幅改变了目标检测领域。在视觉领域之外,只要数据和基学习器符合其适用假设,AdaBoost 仍然可以使用,但它相对于其他分类器并不具有普遍优势。在文本、稀疏表格数据或含噪测量数据上的表现,取决于数据表示、模型容量和评估设置,而不只是提升机制本身。
与其他集成方法和优化方法的关系
AdaBoost 与自助聚合(bagging)有根本区别。自助聚合在重采样得到的数据集上训练基学习器,通常通过等权投票或平均来组合它们。这些学习器基本可以独立训练,该方法对于降低不稳定预测器的方差尤其有效。相比之下,AdaBoost 的每轮拟合都依赖于此前的错误,并为模型分配不均等的系数。它在各轮中构造训练分布,目的是重新引导学习的关注重点,而不只是通过自助采样引入变异。
随机森林将自助聚合与树构建过程中的随机特征选择相结合。它通常使用较深的树,而经典 AdaBoost 则常以决策树桩或浅层树为例加以说明。随机森林通过采样和随机化来获得多样性;AdaBoost 则通过样本权重自适应地改变学习问题。这些并非对两类方法的绝对限制,但有助于解释为什么它们在训练并行性、对难处理样本的敏感性,以及单棵树复杂性所起的作用等方面往往有所不同。
现代梯度提升树系统将逐步建模方法推广到了广泛的目标函数。例如,XGBoost 和 LightGBM 所采用的树构建机制与优化机制,都超出了经典 AdaBoost 更新规则的范围。逻辑损失、平方误差、排序损失等目标会产生不同的梯度,对异常样本也会有不同的反应。将所有提升树系统都称为“AdaBoost”,会掩盖这些区别。反过来,从指数损失的角度理解 AdaBoost,也能看出它属于加性优化方法这一更广泛的发展脉络,而非完全独立于梯度提升之外。
AdaBoost 还通过间隔这一概念与支持向量机产生联系。两者都可以从带符号的决策得分,以及样本与决策边界的分离程度来讨论。不过,它们通常采用的优化问题并不相同。标准支持向量机在范数惩罚与合页损失之间进行权衡,而经典 AdaBoost 则通过降低指数损失来构造基假设的组合。基于间隔的解释,并不意味着两者具有相同的目标、相同的解,也不意味着 AdaBoost 无条件地保证获得最大间隔。
最后,AdaBoost 还与乘法权重法以及学习的博弈论视角有关。可以将样本权重分布理解为对那些暴露当前分类器集合弱点的样本给予更多关注,而学习器则以一个在这种关注分配下表现良好的假设作出回应。这类表述揭示了样本上的分布与假设组合之间的相互作用,也说明了 AdaBoost 与静态加权投票的区别:集成模型与训练分布是在反复反馈的过程中共同形成的,而改变更新规则,也会改变这一过程的优化性质和统计性质。