可能近似正确学习,通常称为 PAC学习,是一种数学框架,用于明确学习过程在什么条件下能够从有限的样例中推导出可靠的预测规则。莱斯利·瓦利安特于1984年提出了这一框架,为成功的学习赋予了精确定义:对于随机提供的样例,学习器必须以高概率输出一个预测误差较小的假设。“可能”指的是对这一结果的置信程度,而“近似正确”则指对未来样例所容许的预测误差。
这一框架在机器学习中占据核心地位,因为它区分了几个仅凭实测表现无法回答的问题:现有观测是否包含足够的信息、需要多少次观测,以及计算高效的算法能否提取这些信息。通过对采样、预测和计算资源作出明确假设,它将监督学习、统计学和计算复杂性联系起来。
经典PAC学习研究如何从独立采样且标注正确的样例中学习二元概念。其扩展形式涵盖了含噪声的标注、相互竞争的假设类、实值损失以及其他信息来源。由此形成的理论既解释了泛化为何可能,也揭示了学习保证实际上能够确立什么结论的重要局限。
学习问题及其量词
在经典设定中,实例空间 包含待分类的对象。概念是一个函数 ,而概念类 则是预先指定的一组可能的目标函数。例如,实例可以是直线上的点,而概念可以表示某个点是否位于某个阈值之上。假设类 包含学习器可以输出的函数;它不必与 相同。
一个未知的概率分布 决定哪些实例会出现。学习器接收到的训练数据为
其中, 是从 中独立抽取的。这是可实现设定:标签由属于指定概念类的目标函数生成。对于假设 ,其总体误差为
这一误差针对的是从该分布中新抽取的实例,而不只是已观测样本上的预测与标签不一致的情况。
如果对于每一个允许的目标 、每一个允许的分布 ,以及所有精度参数和置信参数 ,只要样例足够多,就能保证
那么该学习器就满足 PAC 保证。这里, 是学习算法的输出;如果算法是随机化算法,上述概率也涵盖算法内部的随机性。样本量界必须对定义所涵盖的所有目标和分布统一成立。学习器通常不知道 ,也不允许在观测数据之后再选择一个更容易学习的分布。
这两个层次的概率至关重要。内层的量 衡量的是某个固定输出假设的预测错误频率。外层概率衡量的则是训练过程产生合格假设的频率。因此, 和 意味着,在相互独立的运行中,至少 99% 的运行会产生总体误差不超过 5% 的分类器。这并不意味着每一次预测都有 99% 的概率是正确的。
标准的分布无关定义要求,对实例空间上的每一个 ,上述保证都成立。特定分布下的学习则对 加以限制,例如要求它是一个已知的均匀分布。在统计学讨论中,PAC 可学习性往往主要指有限样本量界的存在性。在计算学习理论中,高效 PAC 可学习性还要求:以适当的表示参数、 和 衡量时,样本用量和运行时间都有多项式上界。
有限假设类与一致性
最简单的 PAC 论证针对的是包含正确目标的有限假设类。如果一个假设对样本中观测到的标签不作出任何错误预测,就称它与该样本一致。假设某个特定假设的真实误差大于 。由于样例相互独立,全部 次观测都避开其错误区域的概率至多为
因此,一个误差较大的假设可能在小样本上表现得毫无差错,但这种情况发生的概率会随着样本量的增加而呈指数下降。
误差较大的假设可能有很多,而学习过程可以在看到样本后从中作出选择。联合界可以控制这种选择效应:
其中
为经验误差。因此,只要
就能以至少 的置信度保证,所有与样本一致的输出假设都是准确的。这一论证不依赖于寻找一致假设的具体方法。
这个界说明了为什么假设类的大小以对数形式而非线性形式出现在样本量要求中。如果每个假设都能用一个互不相同、长度固定为 的二进制串编码,那么 ,由此得到充分条件
这种计数论证是学习与描述长度之间联系的一种早期体现。只要编码方案的确定独立于样本,或者已适当考虑选择编码方案所带来的影响,可用的表示越短,就能给出越强的泛化保证。
布尔合取式是一个具体的例子。对于 个布尔变量,考虑这样一类合取式:每个变量可以不出现,也可以以原变量或其否定形式出现。除去对恒假概念可采用的不同约定,共有 种语法组合。在可实现情形下,学习器可以从包含所有文字的合取式开始,删除所有与正例矛盾的文字。剩余合取式将所有正例都判为正。由于目标合取式中的文字从不会被删除,所得合取式也会将所有负例都判为负。因此,有限假设类的论证给出的样本量要求为
这一量级。
一致性是一种统计性质,而不是普遍适用的计算解决方案。对于某些表示方式,即使已知存在一致的假设,要找到它也很困难。当标签相互矛盾,或假设类中没有任何假设能够完全拟合数据时,一致性要求也不再适用。尽管如此,有限假设类的证明确立了一条反复出现的原则:只有在考虑了学习过程本可以选择多少种其他解释之后,拟合观测数据这一事实才具有参考价值。
无限假设类与Vapnik–Chervonenkis维
对于许多基本的学习问题,仅仅计算假设的数量是不够的。实数轴上的阈值函数类是不可数的,却有简单的学习规则。重要的不是整个实例空间上的函数数量,而是这些函数在有限样本上能够产生多少种不同的标记。VC维,全称为Vapnik–Chervonenkis维,衡量的就是二值函数类的这种多样性。
如果一个有限点集的每一种二元标记都能由 中的某个成员实现,就称假设类 能够打散这个点集。其VC维是可被打散的点集的最大大小;如果能够打散任意大的有限点集,则VC维为无穷大。阈值函数 的VC维为1。它们可以给单个点赋予任一标记,却无法将按从小到大排列的两个点依次标记为正类和负类。实数轴上的区间类的VC维为2:两个点可以获得任意标记,但按从小到大排列的三个点无法获得“正—负—正”的标记。
增长函数 是 在 个点上所能产生的不同标记方式的最大数量。Sauer–Shelah引理指出,当VC维 有限时,
当 时,这个上界不超过 。因此,一个假设类即使包含无穷多个函数,在任意有限样本上产生的不同行为的数量仍可能仅以多项式速度增长。在泛化分析中,这一界限取代了假设类基数有限的条件。
在可实现情形下,一个标准的VC界保证,一致学习器只需
个样本就能成功学习。在满足标准可测性条件的前提下,一个二值函数类是分布无关PAC可学习的,当且仅当它的VC维有限。这一限定很重要,因为任意构造的函数集合可能存在可测性问题;常见的几何函数类和可用算法表示的函数类通常满足理论所要求的正则性假设。
VC维往往与可用假设的数量或其参数精度有很大差别。例如, 中的仿射半空间类的VC维为 ,尽管其系数可以取无穷多个实数值。反之,如果一个假设类能够对任意多个点独立赋予标记,那么它的VC维就是无穷大,也就不具备分布无关的有限样本PAC保证。
标准一致学习器界中的对数因子并非总是必要的。通过更精细、且可能允许输出假设类之外的假设的学习方法,可以在一般可实现情形下得到如下量级的上界:
这是最坏情况下最优的一般依赖关系。但这并不意味着每一种一致学习规则,或每个假设类中所有仅输出类内假设的学习器,都能达到这一最优速率。
不可知学习与含噪观测
可实现性是一个很强的假设。标签可能含有噪声,所选的表示方式可能遗漏相关信息,或者潜在关系可能不属于假设类。不可知学习不再要求所有标签都由 中的某个单一目标生成。取而代之的是,样本 从 上的任意分布 中独立抽取。
对于二元分类,总体风险变为
评价学习器时,以其指定假设类内可达到的最优风险为基准:
不可知 PAC 保证要求
此时,容差 限制的是超额风险,而非总误差。如果类中每个分类器的误差都至少为 20%,那么 1% 的超额风险保证意味着输出的误差至多为 21%,而不是 1%。
经验风险最小化选择使观测到的平均损失最小的假设。其统计学依据通常借助一致收敛:以高概率,对所有假设,经验风险与总体风险都同时彼此接近。对于有限假设类和二元损失,霍夫丁不等式给出
如果这一一致偏差至多为 ,那么精确最小化经验风险所得到的假设,其超额风险至多为 。若采用近似优化,还需加上相应的经验优化误差。
对于 VC 类,一般不可知学习的最优样本量级为
在通常的参数范围内,最坏情形下的下界与之匹配,仅相差常数因子。与可实现学习相比,样本量对精度的一般依赖关系从大约 变为 。要区分两个非零风险极为接近的假设,可能需要大量观测,因为随机波动可能掩盖二者之间的微小差异。
特定的噪声假设可以导出更强的结论。在分类噪声模型中,标签以固定概率 独立翻转。更一般的有界噪声模型允许翻转概率随实例变化,但要求所有实例的翻转概率都有一个严格小于二分之一的统一上界。其他假设则约束实例落在模糊决策边界附近的频率。这些条件可以带来更快的统计收敛速率,但它们引入了完全不可知学习中并不存在的结构性约束。不可知学习的保证始终是相对于所选假设类而言的;它们并不能证明该类本身涵盖了可能达到的最佳预测器。
样本效率、计算与表示
样本复杂度定理回答的是需要多少信息才足够,但它未必能给出实用的算法。学习器可以枚举所有假设,逐一用样本检验,最终返回一个符合要求的假设。对于有限假设类,这种方法或许足以证明其可学习性,但所需时间可能随输入维度或目标的紧凑描述长度呈指数增长。
因此,计算意义上的 PAC 学习需要明确表示方式和访问方式的假设。实例可以是 位字符串;目标的描述大小可以为 ;而高效学习器通常要求运行时间是 、、 和 的多项式。具体细节因情况而异,因为有些类自然地以维度、公式大小、电路大小或其他结构参数来刻画。如果不明确相关的输入大小和数值编码方式,仅仅声称运行时间是多项式是不完整的。
正规学习与非正规学习之间的区别也很重要。正规学习器输出目标类 中的一个成员。非正规学习器则可以输出另一个类中的假设,只要该假设满足所要求的误差保证,且求值成本可以接受。例如,一个由简短逻辑表达式表示的目标,可能用规模更大的投票分类器来近似。允许采用不同的输出表示语言,可以改变计算上的可行性,有时也会改变样本复杂度。
寻找一个与样本完全一致的假设,可能隐含着一个困难的组合搜索问题。在某些正规学习设定中,一致性问题具有NP难性,但仅凭这一结果,并不能证明所有 PAC 学习器都低效。学习器可以容忍少量误差、利用随机采样,或采用目标类之外的表示。因此,计算下界必须与确切的学习模型相匹配。反过来,仅有一个能够高效优化训练误差的过程也不够:假设类还必须具备适当的统计保证。
密码学提供了另一种学习困难性的来源。在适当的密码学假设下,伪随机函数族可以高效求值,但对于采用指定访问方式的高效过程而言,它们在计算上与随机函数不可区分。如果某个学习器在新的随机输入上,对这类函数的预测效果显著优于随机猜测,就可能违背这种不可区分性。这些论证表明,即便目标具有紧凑的计算描述,高效学习仍可能面临依赖特定假设的障碍。
数值表示还带来了进一步的区别。一个几何算法可能只执行多项式次算术运算,但所处理数值的位长度却可能增长过快。完整的运行时间分析必须考虑精度和编码成本,而不能只计算运算次数。因此,PAC 分析区分了三种资源:样例提供的信息、用于表达预测的表示形式,以及构造所得假设并对其求值所需的计算。
实值预测与更丰富的复杂度度量
尽管 PAC 学习最初以二元分类为研究背景,PAC 式保证也可推广到实值预测和一般的损失函数。假设可以预测数值响应、概率或向量。给定损失 ,其风险为
学习目标仍然是以高概率给出风险或超额风险的上界。然而,此时的数学假设必须同时控制函数类的丰富程度,以及损失的大小或尾部行为。
对于有界损失,可以利用覆盖数或其他函数类复杂度度量来建立一致收敛性。伪维将 VC 维推广到实值函数:在选定的一组点上,为每个点分别固定一个阈值,再考察函数值能否实现所有高于或低于相应阈值的模式。对于那些关注函数具体取值、而不仅仅关注二元决策的回归函数类,伪维尤为有用。
胖分裂维引入了显式的尺度。如果能够实现所有二元模式,同时使函数值比适当的阈值至少高出或低于 ,就称该点集在尺度 上被打散。这种尺度敏感性很重要,因为两个实值函数虽然在数学上不同,但在预测所关心的精度下可能几乎无法区分。在标准表述下,对于有界实值函数类,每个正尺度上的胖分裂维都有限,是一致收敛的充要条件。
拉德马赫复杂度衡量一个函数类与独立随机符号的相关程度能够有多高。对于固定样本 ,一种常用定义为
其中,每个 都独立地以相同概率取 或 。一个函数类拟合随机符号的能力越强,利用采样波动的能力就越强。与单一的最坏情形维度不同,这个量可以依赖于观测数据,并给出反映数据几何结构的界。
这些工具有助于解释线性预测器和支持向量机基于范数及间隔的理论保证。即使一个函数类包含大量参数,只要输入范数、权重范数和分类间隔得到控制,仍然可以得到有用的界。正则化可以显式施加这些约束,而优化过程本身也可能偏向于可能解中的某个受限子集。
对于无界损失,则需要更加谨慎。平方误差可以任意大,因此样本可能未能呈现那些罕见、却对总体风险起主导作用的结果。此时,为获得有限的高概率界,可能需要矩假设、尾部条件、截断或稳健估计。不能仅仅改变输出类型,就将二元分类定理直接用于不加限制的回归问题;损失和分布假设本身就是学习问题的组成部分。
其他访问模型与扩展
学习器能够获得哪些样例,是界定其学习任务的重要因素。经典 PAC 学习以被动方式提供独立采样的带标签观测数据。在主动学习中,学习器可以从可用实例中选择要获取标签的实例,也可以与指定的查询机制交互。此时,核心资源可能是标签复杂度,而非无标签观测数据的总量。在有利的假设下,通过自适应方式选择要标注的实例,可以显著提高标签所提供的信息量。
阈值学习可以说明这种差异。如果学习器可以在一个已知的有序区间内选择点并查询其标签,且标签由无噪声的阈值规则决定,那么利用二分搜索,只需对数级数量的查询就能将边界定位到所需的空间精度。相比之下,被动样例的效果取决于采样分布将概率质量分配在何处。空间精度与分布意义下的预测误差是不同的目标,因此,比较查询学习与被动 PAC 学习的界时,必须采用相匹配的假设。
成员资格查询直接询问所选实例的标签。等价查询模型则询问所提出的假设是否正确;如果不正确,就会收到一个反例。这些访问模型可以使某些类得到高效学习,即便在仅使用随机样例时,这些类尚无已知的高效算法。不过,这些模型所得的结论并不自动适用于无法构造任意实例,或无法为其可靠标注的情形。例如,人工合成的输入在实际应用中可能并没有明确无歧义的标签。
迈克尔·卡恩斯于 20 世纪 90 年代提出的统计查询学习模型,允许学习器获取带标签样例上有界函数的近似期望,而不是直接访问单条记录。许多容忍噪声的学习过程都可以用这种方式表述。统计查询下界限制的是这一访问模型内的算法,并不能证明所有基于样本的算法都难以完成相应任务。奇偶校验学习是一个典型例子:对于无噪声的奇偶校验函数,可以通过线性代数从样例中高效学得;但在具有实用价值的容差水平下,不受限制的奇偶校验函数类对统计查询方法而言却很难学习。
PAC 式推理也见于满足差分隐私的学习:当训练集中的单条记录发生变化时,输出必须满足某种稳定性要求。隐私在通常的预测准确性要求之外引入了额外约束,因此,经典的样本界未必仍然充分。在半监督学习中,无标签样例可以揭示输入的边缘分布,但仅凭这些样例本身,无法确定标签与该分布之间的关系。要从中获益,需要作出将分布结构与学习目标联系起来的假设。
另一个独立框架是PAC贝叶斯理论,它为预测器上的概率分布提供高概率风险界。典型的界将经验表现与某种散度联系起来,该散度衡量依赖于数据的后验分布与独立于训练样本选定的先验分布之间的差异。二者在术语上的相似,反映出它们都强调概率性的准确性保证,但 PAC 贝叶斯分析并不只是经典概念类 PAC 可学习性的另一种说法。
保证的适用范围、假设与局限
PAC 定理以其抽样模型为前提。标准设定假定训练样本独立同分布,并在同一分布下衡量未来的预测误差。如果存在时间依赖、自适应数据采集或运行环境变化,就需要进一步分析。在发生分布偏移时,分类器即使满足训练分布下的有效保证,在部署分布上的表现仍可能很差。
“分布无关”这一说法有时会被误解。它的含义是:对于允许的分布族中的每一个固定分布,定理都分别成立,而且样本量界不依赖于具体选取了哪个分布。它并不意味着学习器可以在任意一种分布下训练,然后自动泛化到另一种分布。有关域适应的结果需要额外的限制,例如源分布与目标分布之间须存在某种关系,或者需要对标签在不同域中的变化方式作出假设。
PAC 准确性是关于平均风险的陈述。总错误率较低的分类器,在某个罕见子群体或实例空间中的一小片区域内,仍可能表现很差。同样,常规分类错误率也不能确立概率校准、因果有效性、可解释性,或对刻意选取的输入的鲁棒性。对抗样本关注的是经过扰动或策略性选取的实例,而经典 PAC 界则是对从指定分布中常规抽取得到的样本取平均。
假设类的选择也是一项实质性假设。如果不限制可能的目标函数,通常就无法保证能够从有限样本成功外推。如果未见过的点仍然可以采用任意一种标记方式,那么已观测到的标签就无法提供普适依据,来帮助我们在这些点上相互矛盾的预测之间作出选择。这正是归纳偏置的作用:学习依赖于某种限制、偏好或结构性假设,将已观测和未观测的情形联系起来。有限 VC 维用数学形式明确表达了这样一种限制。
最坏情况下的上界也可能偏于保守。定理必须涵盖其适用范围内的所有分布和目标,包括与特定应用中遇到的情况截然不同的组合。如果某个界要求的样本量超过了现有样本量,这并不能证明训练出的模型会表现不佳;它只意味着这个界无法为预期性能提供保证。反过来,在少数任务上取得良好的实证结果,也不能证明整个类具有分布无关的 PAC 可学习性。
独立评估回答的是另一个问题。对于一个固定的分类器,只要使用全新的测试集进行评估,就可以获得其错误率的高置信度估计,而无须对整个训练过程给出容量界。为了选择模型而反复查看同一个测试集,会削弱这种独立性,并可能引入数据泄漏。PAC 理论区分两类问题:一类是训练前对学习方法作出的保证,另一类是训练后对某个具体预测器进行的统计评估。
历史发展及其与其他学习理论的关系
莱斯利·瓦利安特在1984年的论文《可学习性理论》(A Theory of the Learnable)中提出了这一框架。其独特贡献在于,将近似正确性、高置信度与计算效率结合到一个统一的形式化模型中。此前的学习理论已经研究过如何从样例中进行推断,而PAC学习则为理论计算机科学提供了一套系统的语言,用于探讨哪些概念类存在高效的学习过程。
这一框架的部分统计学基础在其提出之前就已形成。弗拉基米尔·瓦普尼克和阿列克谢·切尔沃年基斯在1971年发表的研究中,给出了一致收敛结果,并提出了以他们的名字命名的组合维数。诺伯特·绍尔和萨哈龙·谢拉赫于1972年各自独立证明了关键的组合增长上界。这些结果后来成为将无限二元概念类的表达能力与样本需求联系起来的理论工具。
安塞尔姆·布卢默、安杰伊·埃伦福伊希特、戴维·豪斯勒和曼弗雷德·沃穆特于1987年研究了奥卡姆式论证与可学习性之间的联系,并于1989年对可学习性和VC维作出了奠基性的论述。他们的工作阐明了为什么简短的描述和有界的组合复杂度能够支持泛化。戴维·豪斯勒1992年关于决策论推广的研究,则推动这一框架超越无噪声的二元概念,扩展到更广泛的预测与损失设定。
另一项重要进展涉及提升法。罗伯特·沙皮尔于1990年证明,在PAC框架中,只要满足适当的假设,就可以将弱学习转化为强学习。弱学习器只需比随机猜测略胜一筹,而强学习器则能够在置信度和资源消耗可控的条件下,将误差降至任意小。随后,约阿夫·弗罗因德和沙皮尔在20世纪90年代开发了AdaBoost,将这一理论问题与一种实用的集成学习方法联系起来。这种归约方法反复调整对样例分布中不同部分的侧重,并将弱假设组合成更强的预测器。
PAC学习不同于在线学习;后者依次作出预测,其性能通常以错误次数或相对于某个比较基准的遗憾来衡量。这一区别具有实质意义:在线学习可能需要对对抗性序列而非随机样本提供保证。不过,在数据以适当方式采样时,通过从在线学习到批量学习的转换,可以将合适的序贯保证转化为统计保证。相关的容量度量也可能不同;在完全对抗性的在线分类模型中,仅凭VC维有限并不足以刻画可学习性。
深度学习的发展,使人们重新关注最坏情况下的类别复杂度与特定训练过程的实际行为之间的差距。大型人工神经网络可能拥有足以拟合任意标签的容量,同时仍能在具有结构的任务上实现泛化。这并不与PAC理论矛盾:基于整个不受限制的假设类得到的界,可能只是过于粗略。因此,研究者考察范数、间隔、压缩、算法稳定性以及优化过程的性质,以期为实际训练得到的预测器找出更有参考价值的保证。