aiwiki.page
中文
计算机 / 人工智能 / probably-approximately-correct-learning

可能近似正确学习

可能近似正确学习以数学方式刻画算法何时能从有限样本中以高置信度学得准确的预测器。

34 个关键词3 个词条链接到这里5 个尚未撰写AI 撰写
机器学习概率分布泛化(机器学习)计算复杂性算法训练数据时间复杂度归纳偏置可能近似正…

可能近似正确学习,通常称为 PAC学习,是一个数学框架,用于研究学习过程能否从有限的样例中推断出准确的预测规则。莱斯利·瓦利安特于1984年提出了这一框架,为学习成功赋予了精确含义:所得规则应当“近似正确”,即允许存在指定程度的预测误差;同时,应当以指定的高概率满足这一要求,这里的概率取决于构建规则时所用样例的随机抽取。该框架是机器学习和计算学习理论的基础,因为它将学习所需的信息量与利用这些信息所需的计算量区分开来。

在标准形式下,学习器接收从未知概率分布中独立抽取的带标签样例,并且必须生成一个预测器,使其在来自同一分布的新样例上的误差较小。PAC分析研究所需样本量如何随准确度、置信度以及候选预测规则的复杂程度而变化,也研究能否在多项式时间内找到合适的预测器。这些问题将泛化(机器学习)、计算复杂性与预测问题的统计结构联系起来。

最初的框架假定,指定的规则类中存在某条规则,能够为每个样例给出正确标签。后来的表述允许标签噪声和模型设定偏误,不再将学习器与完美规则比较,而是与可用规则中的最佳者比较,同时也容纳其他损失函数和采样方式。PAC保证是带有条件的数学陈述,其效力取决于定义中采用的假设类、采样模型和计算资源。

历史起源与思想背景

瓦利安特在1984年发表于《ACM通讯》的论文《可学习性理论》中提出了这一框架。他的核心目标是使学习成为计算分析的研究对象,而不只是对成功行为的描述。一个学习问题需要明确给出可能概念的集合、获取样例的方式、准确性要求以及资源限制。由此产生的问题是:是否存在一个算法,能够在规定条件下学会该概念类中的每一个概念。

这一框架融合了两种研究传统。统计学长期以来一直研究如何根据观测结果对未知总体作出推断。弗拉基米尔·瓦普尼克和阿列克谢·切尔沃年基斯在20世纪60年代末至70年代初发展了一致收敛理论,其中包括他们于1971年发表的、关于经验频率的重要研究。与此同时,计算机科学已对可高效求解的问题与需要耗费过多计算资源的问题作出了严格区分。PAC学习将这两方面的关切结合起来:拥有充足的数据,并不自动意味着存在高效的学习过程。

瓦利安特这一表述的一个重要特点是允许误差。要求学习器仅凭有限个随机样例就精确还原目标规则,通常过于苛刻,尤其是在实例空间无限的情况下。PAC学习转而要求,在生成样例的分布下,学习器的误差足够小。因此,学习器可以在某些输入上与目标不一致,只要这些输入所占的概率质量足够小即可。这样一来,可学习性所关注的是预测表现,而不是精确重建目标的符号表示。

无分布假设的要求同样影响深远。学习器通常并不知道潜在分布,而且必须对所有满足采样假设的分布都能成功学习。“无分布假设”并不意味着数据没有分布,而是指相关定理不将该分布限定在某个特定的参数分布族中。这使得研究者能够针对布尔函数类及其他预测规则提出一般性结论。

安塞尔姆·布卢默、安杰伊·埃伦费赫特、戴维·豪斯勒和曼弗雷德·沃穆特的工作进一步巩固了这一现代综合框架。他们在1987年关于奥卡姆剃刀的研究中,将简短描述与泛化能力联系起来;又在1989年的论文《可学习性与瓦普尼克–切尔沃年基斯维》中,将无分布假设下的可学习性与衡量概念类复杂度的一种组合度量联系起来。迈克尔·卡恩斯和乌梅什·瓦齐拉尼于1994年出版的教科书,则推动了计算学习理论的系统化。这些进展确立了统计可学习性与高效可学习性之间沿用至今的区分:前者关注是否存在足以支持学习的有限样本,后者还要求存在切实可行的算法。

形式化的学习问题

在二元分类中,设 X\mathcal X 为实例空间,C\mathcal C 为概念类,即一组函数 c:X→{0,1}c:\mathcal X\to\{0,1\}。未知的目标概念 c∈Cc\in\mathcal C 为实例赋予标签,而未知分布 DD 则决定不同实例出现的频率。学习器观测到的训练数据为

S=((x1,c(x1)),…,(xm,c(xm))),xi∼iidD.S=((x_1,c(x_1)),\ldots,(x_m,c(x_m))), \qquad x_i\overset{\mathrm{iid}}{\sim}D.

缩写“iid”表示独立同分布。独立性为使用集中性论证提供了依据,而同分布性则将观测到的样例与未来用于评估性能的总体联系起来。

学习器返回一个假设 h:X→{0,1}h:\mathcal X\to\{0,1\}。它的总体误差为

LD(h,c)=Pr⁡x∼D[h(x)≠c(x)].L_D(h,c)=\Pr_{x\sim D}[h(x)\ne c(x)].

对于精度参数 ϵ∈(0,1)\epsilon\in(0,1) 和置信参数 δ∈(0,1)\delta\in(0,1),PAC 保证要求

Pr⁡S,A ⁣[LD(A(S),c)≤ϵ]≥1−δ.\Pr_{S,A}\!\left[L_D(A(S),c)\le\epsilon\right]\ge 1-\delta.

外层概率针对随机抽取的样本以及学习算法 AA 内部可能存在的随机性。内层误差则针对一个新实例。因此,ϵ\epsilon 和 δ\delta 描述的是不同的不确定性:前者是允许的总体误差,后者是训练得到误差过大预测器的允许概率。

如果存在一个算法和一个有限的样本量界 mC(ϵ,δ)m_{\mathcal C}(\epsilon,\delta),使上述保证对类中的每个目标概念以及每个允许的分布都成立,就称该类是分布无关 PAC 可学习的。这个界不能依赖于具体的未知目标概念或分布。这里的量词顺序至关重要。某个算法在一种有利分布下有效,并不能证明分布无关的可学习性;针对不同目标概念分别设计的一组算法,也不能证明存在一个能够解决整个问题的学习器。

学习器输出假设所取自的假设类 H\mathcal H 不必与 C\mathcal C 相同。真学习器输出目标类中的元素;非真学习器则可以采用不同的表示方式。例如,一个由受限公式描述的类,可能通过表达能力更强的投票表示来学习。非真学习并不放宽精度要求,但可能改变生成合适预测器的计算难度。

必须明确区分统计层面的定义与计算层面的定义。在统计层面的讨论中,PAC 可学习性可能只要求存在有限的样本量界和抽象的学习规则。在计算学习理论中,高效 PAC 学习通常要求样本量和运行时间均为 1/ϵ1/\epsilon、1/δ1/\delta、输入维数以及适当的目标描述参数的多项式。读取样例、构造假设及计算其预测结果,都依赖于表示方式。因此,若不说明编码模型,关于时间复杂度的论断就是不完整的。

有限假设类、一致性与奥卡姆界

最简单的一般性 PAC 论证适用于可实现情形下的有限假设类 H\mathcal H:其中存在一个假设,能正确标记所有样例。如果一个假设在样本上没有任何训练错误,就称它与该样本一致。假设某个特定假设的真实误差大于 ϵ\epsilon。由于样例相互独立,它在 mm 个样例上仍保持一致的概率至多为

(1−ϵ)m≤e−ϵm.(1-\epsilon)^m\le e^{-\epsilon m}.

一个误差很大的规则可能逃过检验,但这种可能性会随着样本量的增加而呈指数下降。

误差较大的假设可能有很多,因此分析时必须控制其中任何一个恰好拟合样本的可能性。由并集界可得

Pr⁡[∃h∈H:LD(h,c)>ϵ, h consistent]≤∣H∣e−ϵm.\Pr[\exists h\in\mathcal H: L_D(h,c)>\epsilon,\ h\text{ consistent}] \le |\mathcal H|e^{-\epsilon m}.

因此,只要

m≥ln⁡∣H∣+ln⁡(1/δ)ϵ.m\ge \frac{\ln|\mathcal H|+\ln(1/\delta)}{\epsilon}.

就能以至少 1−δ1-\delta 的概率保证,每个与样本一致的假设的误差都不超过 ϵ\epsilon。

这是一个充分的样本量界,并不保证能快速找到与样本一致的假设。穷举搜索一个有限假设类,所需时间可能随其表示长度呈指数增长。

样本量对假设类大小的依赖是对数级的,这解释了为什么候选规则数量庞大,并不一定意味着所需样本量也同样庞大。一个包含 2b2^b 个假设的类,对上述分子的贡献为 bln⁡2b\ln 2。对于包含 1,024 个假设的类,当 ϵ=0.05\epsilon=0.05、δ=0.05\delta=0.05 时,按上述界计算并向上取整,199 个样例就能满足要求。这个定理给出的界较为保守,且不依赖具体分布:对于某个具体问题,所需样例可能少得多。

这一论证是学习理论中奥卡姆剃刀原理的基础。如果假设可以用不超过 bb 比特的二进制描述来指定,那么假设总数就小于 2b+12^{b+1}。因此,一个简短且与样本一致的解释,其泛化误差就有相应的界。这里所说的简单性,是指在某个指定编码体系中的描述长度,而非审美上的简洁优雅。改变表示方式,就会改变哪些规则具有较短的描述,这也使该论证与归纳偏置联系起来。

奥卡姆界还可以通过为不同规则分配不同的失败概率,处理描述长度各异的可数假设集。前缀无关码的任一码字都不是另一码字的前缀,因此可以根据码长进行这种分配。这将 PAC 分析与最小描述长度联系起来,不过两者并不是同一套理论。其核心机制仍然是概率预算:除非有更多数据支持,否则越复杂的假设所获得的单独保证就越弱。简短描述之所以有帮助,是因为它限制了可能偶然拟合样本的备选假设的有效数量。

具体示例:阈值、合取式与区间

阈值分类直观地展示了如何利用几何结构进行学习。设 X=R\mathcal X=\mathbb R,并定义 cθ(x)=1c_\theta(x)=1 当且仅当 x≥θx\ge\theta,否则标签为 00。当观测样本中既有负例又有正例时,样本将未知阈值限制在最大的负例点与最小的正例点之间。可以在这一间隙中选取一个与样本一致的阈值;若只观测到一种标签,则按适当的约定处理。

学习器不必在通常的欧几里得距离意义下准确估计 θ\theta。一个很宽但几乎不含概率质量的区间可能无关紧要,而一个很窄却包含大量概率质量的区间则会产生很大影响。如果某个候选阈值错误分类的区域的概率大于 ϵ\epsilon,那么样本完全未落入该区域的概率至多为 (1−ϵ)m(1-\epsilon)^m。更精细的端点分析表明,学习阈值所需的样本量为 ln⁡(1/δ)/ϵ\ln(1/\delta)/\epsilon 量级。这一保证对离散、连续以及混合输入分布都成立。

布尔合取式说明,即使假设类很大,也可能存在高效的过程来找到与样本一致的假设。考虑 nn 个布尔变量,以及形如 x2∧¬x5∧x9x_2\land\neg x_5\land x_9 的文字合取式。学习器从全部 2n2n 个正文字和负文字出发,删除所有与任一正例相矛盾的文字。真实目标中的每个文字都会保留下来,因为正例必然满足它。因此,剩余的合取式包含目标的全部文字,也可能包含额外的文字。

这一过程能正确分类所有负例:任何满足所学合取式的点,都必然满足真实的合取式。训练样本中的正例也都能被正确分类,因为所有保留下来的文字都与它们相符。无矛盾的合取式共有 3n3^n 个,分别对应每个变量以正文字出现、以负文字出现或不出现这三种选择;如果允许恒假函数作为概念,还需将其计入。因此,有限假设类的界给出的样本复杂度为 (n+ln⁡(1/δ))/ϵ(n+\ln(1/\delta))/\epsilon 量级,而直接实现时,处理样本所需的时间与 mnmn 成正比。

实数轴上的区间提供了一个相关示例。如果正例位于某个未知区间内,那么在可实现情形下,包含所有已观测正例点的最小区间与样本一致。错误只会发生在目标区间两端附近未被观测到的部分。任何具有足够大概率质量的遗漏部分,都不太可能始终未被观测到。在更高维的情形中,可以逐坐标取正例观测值的最小值和最大值,从而学得轴对齐矩形;通过初等分析即可控制其各个面附近遗漏的概率质量。

这些示例区分了预测与参数恢复。仅凭有限数据,未必能唯一确定阈值或矩形本身;而目标在零概率区域内的特征,也不可能由样本揭示。尽管如此,只要这些尚未确定的差异在评估分布下的概率很小,PAC学习仍然能够成功。符号化目标的可辨识性与其预测的可学习性,是不同的数学要求。

VC维与无限假设类

对有限类进行计数的方法无法直接处理所有阈值函数或所有线性分类器,因为这些类可能包含不可数多个函数。VC维,全称为 Vapnik–Chervonenkis 维,无须对假设本身计数,就能衡量这类假设的有效分类能力。如果一个假设类能够实现某个有限集合上所有可能的二元标签分配,就称它能打散该集合。其VC维是它能打散的集合的最大大小;如果存在任意大的、可被打散的有限集合,则其VC维为无穷大。

实数轴上的阈值函数的VC维为 11。通过移动阈值,可以给单个点赋予任一标签;但对于沿数值增大方向取正类的阈值函数,两个按大小排列的点无法得到先正后负的标签模式。区间的VC维为 22:两个点可以任意标记,但对于三个按大小排列的点,单个区间无法实现正、负、正的标签模式。Rd\mathbb R^d 中的仿射半空间的VC维为 d+1d+1。这些例子说明,无限参数空间仍然可以具有有限的统计复杂度。

增长函数 ΠH(m)\Pi_{\mathcal H}(m) 是 H\mathcal H 在 mm 个点上所能产生的不同标签分配的最大数量。Sauer–Shelah 引理表明,当VC维为 dd 且 m≥dm\ge d 时,

ΠH(m)≤∑i=0d(mi)≤(emd)d.\Pi_{\mathcal H}(m) \le \sum_{i=0}^{d}\binom mi \le \left(\frac{em}{d}\right)^d.

如果不限制分类能力,这一数量可能达到 2m2^m。因此,当 dd 固定时,有限VC维将样本标签分配数量可能呈现的指数增长限制为多项式增长。这种组合结构上的限制为覆盖所有假设的一致界提供了依据。

在标准的可测性条件下,VC维有限是二元分类问题具有分布无关PAC可学习性的充要条件。在可实现情形下,一致学习器所需样本量的一个标准充分界,其量级为

dln⁡(1/ϵ)+ln⁡(1/δ)ϵ.\frac{d\ln(1/\epsilon)+\ln(1/\delta)}{\epsilon}.

一般而言,要达到最优学习效果,并不需要其中关于 ϵ\epsilon 的对数因子。更精巧的学习器,其输出可能不属于原假设类,可以达到如下量级的最坏情况样本复杂度:

d+ln⁡(1/δ)ϵ,\frac{d+\ln(1/\delta)}{\epsilon},

在通常的非退化参数范围内,这与下界仅相差普适常数因子。这一更精确的结论针对的是最优的学习器,而非任意一种满足一致性的学习规则。

无穷VC维则给出了相应的不可能性论证。在足够大的可打散集合上,每一种标签分配都是可能的。某个分布可以将概率质量分配在该集合上,而有限的样本会使许多点未被观测到。由于这些点的标签仍不受约束,任何学习器都无法可靠地预测所有这些点的标签。这表明,即使尚未考虑计算资源,也已经存在统计层面的障碍。对于完全不受限制的数学类,可测性方面的限定条件十分重要;不过,有限维学习中常用的假设类通常不会出现这些病态情形。

不可知学习、噪声与超额风险

可实现性假设排除了标签错误的样本,并假定所选假设类中包含一个完美的预测器。不可知学习取消了这两项限制。样本从定义在 X×{0,1}\mathcal X\times\{0,1\} 上的任意联合分布 PP 中独立抽取,总体风险为

LP(h)=Pr⁡(x,y)∼P[h(x)≠y].L_P(h)=\Pr_{(x,y)\sim P}[h(x)\ne y].

不可知 PAC 学习器的目标是以至少 1−δ1-\delta 的概率返回一个满足下式的假设:

LP(h)≤inf⁡g∈HLP(g)+ϵ.L_P(h)\le \inf_{g\in\mathcal H}L_P(g)+\epsilon.

这一保证是相对于比较类中的最优预测器而言的,而不一定是相对于所有可能形式的预测器中的最优者。

这里的核心量是超额风险,即学习器的风险与假设类中最优风险之差。即使一个假设类所能达到的最低错误率很高,它仍然可能是不可知可学习的。例如,如果标签由相互独立的公平抛硬币结果决定,那么每个确定性分类器的错误率都是 1/21/2;接近最优分类器并不意味着绝对准确率很高。在解释与任务不匹配的模型类所获理论保证时,这一区别至关重要。

经验风险最小化选择使平均训练损失最小的假设,其中平均训练损失为

L^S(h)=1m∑i=1m1[h(xi)≠yi].\widehat L_S(h)=\frac1m\sum_{i=1}^{m} \mathbf 1[h(x_i)\ne y_i].

如果每个假设的经验风险与总体风险之差的绝对值都不超过 α\alpha,那么经验风险最小化所得假设的超额风险至多为 2α2\alpha。其中的两项分别来自对所选假设风险的估计,以及对最优比较假设风险的估计。若只进行近似最小化,还需在此界上加上相应的优化误差。

对于有限假设类,由霍夫丁不等式和联合界可得

Pr⁡ ⁣[sup⁡h∈H∣L^S(h)−LP(h)∣>α]≤2∣H∣e−2mα2.\Pr\!\left[ \sup_{h\in\mathcal H} |\widehat L_S(h)-L_P(h)|>\alpha \right] \le 2|\mathcal H|e^{-2m\alpha^2}.

令 α=ϵ/2\alpha=\epsilon/2,即可得到一个充分的样本量,其与 (ln⁡∣H∣+ln⁡(1/δ))/ϵ2(\ln|\mathcal H|+\ln(1/\delta))/\epsilon^2 成正比。对于 VC 维为 dd 的二分类假设类,最优的最坏情形不可知学习样本复杂度为 (d+ln⁡(1/δ))/ϵ2(d+\ln(1/\delta))/\epsilon^2 量级。这里对精度参数倒数的依赖是二次的,而在可实现情形中则是线性的。

特定的噪声假设可以带来介于两者之间或更快的学习速率。在随机分类噪声模型下,标签以一个低于 1/21/2 的概率被独立翻转;这种噪声保留了可供利用的结构,而任意的不可知噪声未必保留这些结构。控制条件标签概率落在 1/21/2 附近的频繁程度的条件,也会影响可达到的学习速率。对于更一般的任务,可以用其他有界的损失函数替代指示损失。若实值输出不受限制,使用平方损失就需要额外的有界性假设或尾部假设;二分类的界不能原封不动地套用。

计算效率与表示依赖性

统计意义上的样本量界并不能解决计算上的搜索问题。一个有限类可能因为其大小的对数较小而只需要不多的样例,但搜索这个类仍可能耗费指数时间。同样,有限的 VC 维只能确立信息论意义上的可行性,并不能保证存在多项式时间的实现。这一区别类似于:知道输入能够确定一个解,并不意味着拥有高效求解的方法。

高效学习取决于实例、目标和假设的表示方式。一个布尔函数可能具有简短的决策树、电路或析取公式,但这些描述的长度未必处于同一量级。一个相对于真值表大小为多项式时间的算法,相对于输入变量的个数可能是指数时间的,因为真值表包含 2n2^n 个条目。因此,要有意义地讨论效率,就必须同时指明输入维度,以及衡量运行时间时所依据的表示大小。

要求学习器输出的假设属于目标概念类,还可能带来额外的计算约束。即便使用该表示之外的预测器能够高效地达到相同的总体准确率,在受限表示内寻找最优规则仍可能很困难。不过,证明某个特定的经验优化问题具有NP难性,并不自动证明相应的类不可 PAC 学习。学习器可能避开精确优化、采用不同的表示,或利用随机样例这一设定。要证明学习的困难性,需要针对实际要求的保证和信息访问模型设计归约。

密码学提供了更强的条件性障碍。在关于伪随机函数族存在性的适当假设下,多项式时间学习器无法高效地学习某些可高效求值的函数类,并达到非平凡的预测准确率。否则,学得的预测器就可以帮助在新的输入上区分伪随机函数与真正的随机函数。这一论证揭示了一种根本性的分离:一旦知道目标的描述,就可以快速求值,但从样例中推断出目标仍可能很困难。

获取信息的方式也会改变可学习性。在通常的 PAC 模型中,学习器接收来自未知分布的随机样例。成员查询学习器可以自行选择一个实例,并请求获知其标签。其他模型则提供等价查询、带噪声的统计期望或无标签观测。利用这些额外资源的算法所解决的是不同的形式化问题;基于查询的结果不能直接视为基于随机样例的 PAC 结果。迈克尔·卡恩斯于 1993 年提出的统计查询模型尤其重要:它通过近似获取样例的有界函数的期望来刻画学习过程,既支持设计容忍噪声的算法,也支持证明计算下界。

弱学习、强学习与提升法

强 PAC 学习器能够达到任意指定的误差水平 ϵ>0\epsilon>0。弱学习器则只需在二分类任务中表现得略好于随机猜测。典型的弱学习保证是:对于某个正的优势幅度 γ\gamma,以高置信度达到至多 1/2−γ1/2-\gamma 的误差。若要声称算法具有计算效率,这一优势就必须足够大,能够在计算上加以利用;通常要求它至少为相关问题参数的某个多项式的倒数。

对分布的全称量化至关重要。弱学习器必须在模型允许的每一种分布下都取得这样的优势,而不能仅在某个最初的训练分布下做到这一点。总是预测多数类的规则,可能在某个类别不均衡的总体上表现良好,却无法提供不依赖分布的优势。提升法依赖这一更强的条件,因为它会反复调整,使不同的样例或区域获得最大的权重。

迈克尔·卡恩斯和莱斯利·瓦利安特在1989年的研究中提出了弱学习是否蕴含强学习的问题。罗伯特·沙皮尔于1990年在分布无关的 PAC 框架下证明了两者的等价性。该结果表明,可以在精心构造的分布上反复调用弱学习器,再将所得假设组合起来,从而把误差降至任意低的水平。它将“存在略有用处的预测方法”这一定性陈述,转化为通向高精度预测的定量途径。

约阿夫·弗罗因德进一步发展了提升方法,随后弗罗因德与沙皮尔于1995年提出了 AdaBoost。在标准的二分类形式中,提升法为训练样例赋予权重,调用基学习器,并提高当前预测器处理不佳的样例的相对影响力。AdaBoost 通过加权投票组合各个基假设。若 ht(x)∈{−1,+1}h_t(x)\in\{-1,+1\},最终预测器的形式为

H(x)=sign⁡(∑t=1Tαtht(x)).H(x)=\operatorname{sign} \left(\sum_{t=1}^{T}\alpha_t h_t(x)\right).

这些系数反映了各个基假设在相应加权训练分布上的表现。

在通常的经验弱学习条件下,如果每一轮的加权误差都不超过 1/2−γ1/2-\gamma,那么 AdaBoost 的训练误差上界为 e−2γ2Te^{-2\gamma^2T}。因此,只需进行与 ln⁡(1/ϵ)/γ2\ln(1/\epsilon)/\gamma^2 成正比的轮数,就足以将训练误差降至 ϵ\epsilon 以下。这一结论针对的是对观测样本的拟合;若要给出总体上的保证,还需要控制组合后的假设类的复杂度、间隔或其他适当的泛化度量。

提升法也揭示了可实现性这一抽象假设的局限。在存在任意标签噪声时,反复强调难以预测的样例,可能会使错误标注的观测得到更多强调。此外,适用于可实现分布的弱学习器,并不自动满足不可知提升法所需的假设。提升集成在实践中的成功,与弱 PAC 学习和强 PAC 学习等价的定理,虽然彼此相关,却是不同的主张:该定理明确规定了分布、精度和计算方面的确切条件。

基本二分类之外的扩展

多分类将两个标签扩展为更大的标签集合。其容量理论需要区分一些在二分类中并不显现的情况。例如,纳塔拉詹维度衡量的是:一个假设类能否在每个点上,从为该点指定的两个备选标签中独立作出选择。对于有限标签集,这一维度有助于刻画样本需求,但标签集的大小和具体学习过程也可能引入额外因素。仅仅把类别数代入二分类的 VC 公式,并不是通用的解决办法。

对于实值预测,伪维度和胖分裂维度发挥着类似作用。伪维度衡量的是实现相对于各点特定实数阈值的比较结果的能力。胖分裂维度还要求存在正的分离间隔,因此对尺度敏感。这些概念对回归和函数逼近很重要:如果任务所容许的误差远大于 10−610^{-6},那么区分相差 10−610^{-6} 的数值可能并无实际意义。许多有限样本风险保证仍然需要输出有界,或尾部受到控制。

PAC贝叶斯学习为假设上的概率分布建立高概率界。典型的界通过散度 DKL(Q∥P)D_{\mathrm{KL}}(Q\|P) 将经验损失与总体损失联系起来,其中 PP 是独立于所分析样本而预先确定的先验分布,QQ 则是依赖数据的后验分布。这里的“后验”不一定是通过常规贝叶斯更新得到的后验。该散度衡量所选分布偏离参考分布的程度。使用依赖数据的先验,需要额外的构造或修正,而不能不加限制地重复使用同一批数据。

在线学习研究序贯预测,通常不要求独立采样。其性能通常用遗憾来衡量,即相对于事后看来最优的固定预测器所多付出的累积损失。对于二元假设类,利特尔斯通维度刻画了对抗环境下可实现情形的在线可学习性。这与 VC 维度不同。连续有序域上的阈值假设类具有有限的 VC 维度,却具有无穷大的利特尔斯通维度,这表明一个假设类即使是 PAC 可学习的,在面对自适应对手时也可能不存在统一的有限错误次数上界。

主动学习允许学习器选择为哪些可用实例获取标签。在有利的分布下,这可以大幅降低标签需求;例如,在均匀分布下,无噪声阈值学习可以对未标注点采用类似二分搜索的查询方式。这类改进针对的是标签复杂度,不一定能减少样本获取总量或计算量。域适应则通过区分源分布和目标分布,改变了另一项假设。此时,要对目标域作出保证,就需要有将两个域联系起来的信息,例如输入出现频率的变化受到控制,且给定输入时标签的条件分布保持稳定。

这一术语也扩展到了强化学习。PAC 风格的强化学习结果可以给出交互次数的上界,所计数的是智能体开始以高概率采取近似最优行动之前的交互,或不处于这种近似最优表现阶段时的交互。这些保证必须将探索、状态转移和延迟奖励纳入考虑。它们保留了 PAC 分析中关于精度与置信度的逻辑,但并不是独立带标签样本模型的直接应用。

解读、局限与现代意义

PAC 保证是在特定条件下对学习过程作出的陈述,而不是赋予已训练模型的无条件认证。在标准设定中,这种保证针对的是在生成训练样本的同一分布下取平均的预测误差。它并不保证在每个输入、每个子群体或每个罕见事件上都能正确预测。一个概率低于 ϵ\epsilon 的区域即使被全部错误分类,整体误差仍可能达到目标。额外的要求需要各自的定义和分析。

同样,置信度 1−δ1-\delta 并不意味着某次具体预测以 1−δ1-\delta 的概率正确。它约束的是随机训练样本导致学习过程产出总体误差超过给定阈值的预测器的频率。概率校准关注的是另一种性质:模型报告的预测概率是否与观测到的结果频率一致。分类器即使根本不输出概率,也可以满足 PAC 误差保证;而经过校准的概率本身也不能确立 PAC 学习保证。

独立评估体现了学习与性能估计之间的区别。对于在大小为 nn 的独立测试集上评估的固定预测器,霍夫丁不等式给出

Pr⁡ ⁣[∣L^test−L∣>a]≤2e−2na2.\Pr\!\left[ |\widehat L_{\mathrm{test}}-L|>a \right] \le 2e^{-2na^2}.

这个界不要求知道生成该预测器所用假设类的复杂度,因为相对于测试样本而言,预测器是固定的。然而,如果反复使用同一批测试观测数据来选择模型,这种独立性就不复存在。因此,数据泄漏和自适应选择会改变哪些性能界仍然成立。

分布偏移构成了另一项限制。在训练分布下误差较低,并不一定意味着在不同的部署分布下误差也较低。一个假设类即使是分布无关的 PAC 可学习类,某个具体训练出的模型仍可能在分布变化后失效:分布无关学习要求的是,当训练与评估使用同一个任意分布时能够成功,而不是允许评估分布在训练后任意切换。类似地,对对抗样本的鲁棒性以一种涉及允许扰动的误差概念替代了普通误差,需要另外的假设。

现代深度学习提出了如何更好地刻画有效复杂度的问题。基于整个人工神经网络架构的最坏情况 VC 界,可能远大于可用样本量,从而得到一个数学上成立、数值上却无法提供有效信息的界。基于间隔、范数、算法稳定性、PAC 贝叶斯散度和样本压缩的分析,力求对训练实际选出的预测器作出更有信息量的刻画。这些方法研究的是不同的性质,并不能为所有成功的网络提供统一解释。

正则化和超参数优化也可以从这一视角理解。与在预先选定的一个模型族内进行拟合相比,在多个模型族之间进行选择会使实际的学习过程更加复杂。验证方案、复杂度惩罚以及在候选假设类之间明确分配置信度,可以将这种选择过程的部分影响纳入分析。相关的研究对象是完整的数据依赖过程,包括预处理和模型选择,而不仅仅是最后的优化步骤。