1. 项目概述不变性假设下的PAC学习理论在机器学习领域我们经常希望模型不仅能拟合训练数据更能捕捉数据背后的本质规律从而对未见过的数据做出可靠预测。PACProbably Approximately Correct学习理论为这一期望提供了坚实的数学基础。它回答了一个核心问题需要多少样本才能以高概率学习到一个在整体数据分布上错误率足够低的模型传统的答案通常围绕VC维Vapnik-Chervonenkis dimension展开——一个衡量假设类“表达能力”或“复杂度”的度量。VC维越高假设类越复杂所需的样本量也越大。然而现实世界的数据往往具有丰富的内在结构。例如一张猫的图片无论它出现在画面的左上角还是右下角无论它是否被轻微旋转它依然是一只猫。这种“猫”的概念对于平移、旋转等变换是不变的。在自然语言处理中一个句子的含义对于同义词替换在特定上下文中也可能是不变的。将这种先验知识——不变性假设——纳入学习框架是提升模型样本效率即用更少数据达到相同性能和泛化能力的关键。本文要探讨的正是PAC学习理论在不变性假设下的深化与拓展。我们不再仅仅问“学习这个假设类需要多少样本”而是问“在已知数据可能具有某种变换不变性的前提下学习这个假设类最少需要多少样本” 以及“我们能否设计出聪明的算法自动适应目标函数所具有的不变性强度从而用更少的样本完成学习” 这不仅仅是理论上的精进更是通向更高效、更鲁棒机器学习系统的必经之路。2. 核心概念解析从VC维到不变性VC维要理解不变性下的学习我们必须先夯实几个基石概念并看清它们是如何演进的。2.1 经典PAC学习与VC维经典的PAC学习设定如下我们有一个实例空间 $\mathcal{X}$如图片像素空间和一个标签空间 $\mathcal{Y}$如{0,1}。一个假设类 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\mathcal{Y}$ 的一组函数如所有可能的神经网络结构。数据从一个未知分布 $\mathcal{D}$ 中独立同分布地采样。学习器的目标是给定一个误差参数 $\epsilon$近似正确和一个置信参数 $\delta$概率找到一个假设 $h \in \mathcal{H}$使得其真实错误率 $\text{err}{\mathcal{D}}(h)$ 与可能的最佳错误率 $\inf{h \in \mathcal{H}} \text{err}_{\mathcal{D}}(h)$ 之差不超过 $\epsilon$且这一事件发生的概率至少为 $1-\delta$。VC维 $\text{VCdim}(\mathcal{H})$ 是衡量 $\mathcal{H}$ “打散”能力的一个指标。如果存在一组大小为 $d$ 的实例能被 $\mathcal{H}$ 以所有 $2^d$ 种方式分类且这是最大的此类数字则 $\text{VCdim}(\mathcal{H}) d$。一个里程碑式的结论是对于可实现情况存在 $h^* \in \mathcal{H}$ 实现零误差样本复杂度的上界为 $O(\frac{d \log(1/\delta)}{\epsilon})$下界为 $\Omega(\frac{d \log(1/\delta)}{\epsilon})$。VC维完美刻画了假设类的内在复杂度。2.2 引入不变性群作用与轨道不变性通过一个变换群$\mathcal{G}$ 来形式化。$\mathcal{G}$ 中的每个元素 $g$ 代表对实例 $x \in \mathcal{X}$ 的一个变换如旋转90度。我们要求 $\mathcal{G}$ 在 $\mathcal{X}$ 上构成一个群作用。对于任意 $x$其所有可能的变换构成的集合 $\mathcal{G}x { gx : g \in \mathcal{G} }$ 称为 $x$ 的轨道。不变性假设的核心是处于同一轨道内的所有实例应共享相同的标签。这意味着真实的目标函数 $h^$ 满足对于所有 $x \in \mathcal{X}$ 和所有 $g \in \mathcal{G}$有 $h^(gx) h^(x)$。我们的假设类 $\mathcal{H}$ 中的函数可能并不全都满足这个性质但至少 $h^$ 满足。注意这里的不变性是施加在数据分布或目标函数上的假设而非对学习算法或假设类的硬性约束。算法可以利用这一假设来更高效地学习但假设类本身可能包含非不变的函数。2.3 不变性VC维VCao经典VC维在衡量一个假设类对“一组点”的打散能力时将这组点视为彼此独立的个体。但在不变性假设下我们知道同一轨道内的点必须同标签。因此打散一组点的“成本”降低了——你不需要对轨道内每个点独立赋值只需对整个轨道赋予一个标签。不变性VC维记为 $\text{VCao}(\mathcal{H}, \mathcal{G})$正是捕捉了这种结构带来的复杂度降低。其定义精妙地考虑了轨道结构我们选取一组实例 $S {x_1, ..., x_m}$。我们只关心那些能被 $\mathcal{H}$ “打散”的集合但这里的“打散”有了新含义我们要求存在假设 $h \in \mathcal{H}$能够实现给定的轨道标签模式。也就是说对于 $S$ 中属于不同轨道的实例我们可以自由分配标签但对于同一轨道内的所有实例它们必须获得相同的标签。$\text{VCao}(\mathcal{H}, \mathcal{G})$ 是最大的整数 $d$使得存在一个大小为 $d$ 的实例集 $S$其不同轨道的数量至少为 $d$并且 $\mathcal{H}$ 能打散这些轨道即能给这些轨道分配所有可能的 $2^d$ 种标签组合。直观上$\text{VCao}$ 度量的是假设类在遵守轨道内标签一致约束下仍能产生的“有效”区分模式的数量。显然$\text{VCao}(\mathcal{H}, \mathcal{G}) \leq \text{VCdim}(\mathcal{H})$而且当不变性很强轨道很大时$\text{VCao}$ 可以远小于 $\text{VCdim}$。实操心得理解 $\text{VCao}$ 的关键在于思维转换——从“点级”打散转向“轨道级”打散。在设计算法或分析模型时如果你知道数据具有旋转不变性那么你的模型复杂度不应该由“所有可能的像素组合”来决定而应由“所有可能的、在旋转下等价的语义组合”来决定。$\text{VCao}$ 正是后者的理论对应物。3. 样本复杂度分析上界、下界与自适应算法有了 $\text{VCao}$ 这个工具我们就可以重新审视PAC学习的样本复杂度。研究通常分为两种场景松弛可实现和不可知。3.1 松弛可实现场景下的样本复杂度在松弛可实现场景中我们假设存在一个目标假设 $h^* \in \mathcal{H}$但它可能只对“大多数”变换保持标签一致即存在一个小的违反概率 $\eta$。形式化地$\eta(h^) \mathbb{P}_{x \sim \mathcal{D}}[\exists x \in \mathcal{G}x, h^(x) \neq h^*(x)]$。当 $\eta 0$ 时就是严格的不变可实现场景。核心结论在松弛可实现场景下样本复杂度的上界可以由 $\text{VCao}(\mathcal{H}, \mathcal{G})$ 和 $\eta$ 共同控制。存在算法如基于1-包含图预测器的改进版本能够达到 $O\left(\frac{\text{VCao}(\mathcal{H}, \mathcal{G}) \log(1/\delta)}{\epsilon} \frac{\eta}{\epsilon}\right)$ 的样本复杂度。算法解析1-包含图预测器思路核心思想该算法是一种在线学习策略的离线模拟。给定一个带标签的训练集 $S$ 和一个测试点 $x$算法考虑所有与 $(S, x)$ 一致的假设即那些在训练集上预测正确的假设并从中选择一个对 $x$ 的预测。不变性整合关键改进在于“一致”的定义。我们不仅要求假设在训练点 $S_{\mathcal{X}}$ 上预测正确还要求它在每个轨道的观测到的实例上预测一致。即对于训练集中出现的 $x_i$如果 $x_j$ 与 $x_i$ 在同一轨道内$x_j \in \mathcal{G}x_i$那么假设必须满足 $h(x_j) h(x_i)$。这定义了一个受限的假设集 $\mathcal{H}(X_S)$。预测规则算法使用一个称为 $Q$ 的确定性预测函数由1-包含图理论保证存在在受限假设集 $\mathcal{H}(X_S \cup {x})$ 上运作为 $x$ 给出一个预测。如果这个受限集为空在不可知场景可能发生则随机预测。理论保证通过对称化Symmetrization和鞅Martingale论证可以证明该算法的期望误差不超过 $\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{n1}$其中 $n$ 是训练样本数。再通过标准的置信度提升技术多次运行取最优即可得到高概率保证。这个上界的意义在于当目标函数近乎不变$\eta$ 很小时样本复杂度主要由 $\text{VCao}$ 主导而 $\text{VCao}$ 可能远小于 $\text{VCdim}$从而带来了样本量的显著节约。3.2 不可知场景下的样本复杂度在不可知场景中我们不再假设存在零误差或近乎零误差的 $h^* \in \mathcal{H}$。我们只追求找到 $\mathcal{H}$ 中误差最小的假设。此时问题更具挑战性。核心结论在不可知场景下样本复杂度的下界是 $\Omega\left(\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{\epsilon^2} \frac{\log(1/\delta)}{\epsilon^2}\right)$而上界可以达到 $O\left(\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{\epsilon^2} \log^2\left(\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{\epsilon}\right) \frac{\log(1/\delta)}{\epsilon^2}\right)$。上下界在 $\epsilon$ 和 $\delta$ 的依赖上匹配但在对 $\text{VCao}$ 的依赖上存在一个 $\log^2$ 因子的差距。算法解析压缩方案与经验风险最小化ERM-INV经验风险最小化-不变性一种自然的想法是在经验风险最小化的基础上强制要求候选假设在训练数据上满足轨道内标签一致。然而直接分析这种算法的泛化性能较为复杂。证明的关键在于将误差分解为两部分在“大轨道”包含样本多的轨道上的误差和在“小轨道”上的误差并分别用不变性结构和经典VC维理论进行约束。基于压缩的方案另一种途径是构建一个不可知压缩方案。首先使用一个类似松弛可实现场景中的弱学习器如前述的1-包含图预测器变种它在数据的一个“可实现子集”上工作。然后通过多数投票Majority Vote的方式将多个弱学习器组合成一个强学习器。这个组合过程可以被视为一种压缩——最终的假设仅由训练样本中的一个小子集即各弱学习器所用的数据所决定。最后应用不可知压缩方案的泛化界如Lemma J.3即可得到样本复杂度上界。注意事项在不可知场景中不变性带来的好处不如在可实现场景中那么直接和巨大。因为最优假设本身可能就不完全满足不变性算法必须在拟合数据和不变性先验之间做权衡。上界中的 $\log^2$ 因子可能从技术上是必要的也可能存在更紧的算法可以消除它这是一个开放问题。3.3 自适应算法无需先知 $\eta$ 的智能学习前述理论假设我们知道目标函数的不变性水平 $\eta$从而可以选择合适的算法或参数。但在实践中$\eta$ 是未知的。自适应算法的目标就是在不知道 $\eta$ 的情况下自动实现与知道 $\eta$ 时相近的性能。3.3.1 松弛可实现场景的自适应算法算法的核心思想是模型选择。数据分割将训练集 $S$ 分为两部分 $S_1$ 和 $S_2$。网格搜索在 $\eta$ 的可能范围 $[0, 1]$ 上以一定步长 $\Delta$ 划分出一系列候选值 $\eta_i$。候选假设生成对每个 $\eta_i$使用一个子程序 $\mathcal{A}{\eta_i, \Delta}$。该子程序基于 $S_1$尝试学习一个在“近似 $(1-\eta_i)$-不变”的假设类中表现良好的假设。这里“近似”意味着允许经验不变性违反率在 $\eta_i \pm \Delta$ 内。子程序内部通常使用基于 $\text{VCo}{\eta_i\Delta}$一种分布相关的近似不变性VC维的预测器。验证选择在验证集 $S_2$ 上评估所有候选假设的经验误差选择最小的那个作为最终输出。理论保证该算法可以以高概率实现误差 $O\left(\frac{\text{VCo}{2i^\Delta}(h^, \mathcal{H}, \mathcal{G}, \mathcal{D}{\mathcal{X}}) \log(1/\delta) \log(m)}{m}\right)$其中 $i^$ 是使得 $2i^\Delta$ 刚好超过真实 $\eta(h^*)$ 的最小索引。这意味着算法自动适应了未知的 $\eta$其性能退化仅是对数级别的。3.3.2 不可知场景的自适应算法不可知场景的自适应更为棘手因为无法直接定义一个与 $\eta$ 相关的“干净”的可实现子集。思路使用一个无标签数据集$U$ 来估计每个假设 $h \in \mathcal{H}$ 的经验不变性违反率 $\hat{\eta}_U(h)$。假设类划分根据 $\hat{\eta}_U(h)$ 将 $\mathcal{H}$ 划分为多个桶 $\hat{\mathcal{H}}_i$每个桶对应一个不变性水平区间。并行学习与选择在一个有标签训练集 $S_1$ 上对每个桶 $\hat{\mathcal{H}}_i$ 独立运行不可知学习算法如基于压缩的方案得到假设 $h_i$。验证选择在另一个有标签验证集 $S_2$ 上选择经验误差最小的 $h_i$。理论挑战与保证这个算法的性能上界不仅依赖于最优假设所在桶的 $\text{VCao}$还依赖于整个假设类 $\mathcal{H}$ 的“不变性指示函数”类的VC维 $\text{VCdim}(\mathcal{I})$。$\mathcal{I}$ 包含了所有形如 $\iota_h(x)1_{\exists x \in \mathcal{G}x, h(x) \neq h(x)}$ 的函数。这个值可能很大甚至远大于 $\text{VCdim}(\mathcal{H})$。因此如何设计一个不依赖于 $\text{VCdim}(\mathcal{I})$ 的自适应算法仍是一个开放问题。实操心得自适应算法的价值在于其鲁棒性。在实际项目中我们往往难以精确量化数据的不变性程度。采用自适应策略相当于做了一个“保险”算法会自己探索从强不变性到弱不变性的各种可能性并选择在验证集上最有效的那个。虽然理论分析复杂但实现上网格搜索配合验证集选择是一个非常通用且强大的范式。4. 理论推导与证明思路精讲要深刻理解上述结论我们需要深入一两个关键证明看看不变性是如何被巧妙地利用来提升界的。4.1 1-包含图预测器误差上界的证明核心我们聚焦于松弛可实现场景中1-包含图预测器期望误差上界 $\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{n1}$ 的证明。这是后续很多结果的基石。证明思路拆解对称化这是学习理论中的标准技巧。考虑 $n1$ 个 i.i.d. 样本 $(x_1, y_1), ..., (x_{n1}, y_{n1})$。算法的期望误差等于随机选择一个样本作为测试点、其余作为训练集时出错的概率。通过对这 $n1$ 个样本的所有排列取平均我们可以将期望误差重写为 $\mathbb{E}[\text{err}] \mathbb{E}\left[\frac{1}{(n1)!} \sum_{\sigma} \mathbf{1}{\mathcal{A}(S\sigma, x_{\sigma(n1)}) \neq y_{\sigma(n1)}}\right]$ 其中 $S_\sigma$ 是前 $n$ 个样本$\sigma$ 遍历所有排列。关键观察对于任何一个固定的样本序列 $(x_1, y_1), ..., (x_{n1}, y_{n1})$上述求和式中的每一项 $\mathcal{A}(S_\sigma, x_{\sigma(n1)})$其预测只依赖于这个排列 $\sigma$ 下的训练集 $S_\sigma$ 和测试点 $x_{\sigma(n1)}$。而算法 $\mathcal{A}$ 的预测规则是在一个受限假设集 $\mathcal{H}(X_{S_\sigma \cup {x_{\sigma(n1)}}})$ 上运行1-包含图预测器。与VC维的联系1-包含图预测器有一个经典性质对于任何假设类 $\mathcal{H}$ 和实例集 $X$该预测器在随机排列测试下的平均误差不超过 $\frac{\text{VCdim}(\mathcal{H})}{n1}$。这个结论源于图论和鞅的论证。应用与放缩在我们的设定中对于每个固定的未标记实例集合 $X {x_1, ..., x_{n1}}$算法实际工作的假设类是 $\mathcal{H}(X)$。因此对于固定 $X$内部平均误差不超过 $\frac{\text{VCdim}(\mathcal{H}(X))}{n1}$。注意$\mathcal{H}(X)$ 中的假设必须满足在 $X$ 上观测到的轨道内一致。由于目标函数 $h^$ 在轨道内是一致的因此 $h^|_X \in \mathcal{H}(X)$ 总是成立在松弛可实现场景以概率1成立。取期望与定义我们对 $X$ 取期望并注意到 $\text{VCdim}(\mathcal{H}(X))$ 在 $X$ 上的期望在 $h^|_X \in \mathcal{H}(X)$ 的条件下正是 $\text{VCo}_0(h^, \mathcal{H}, \mathcal{G}, \mathcal{D}_{\mathcal{X}})$ 在 $mn1$ 时的定义。而在严格不变可实现场景$\eta0$$\text{VCo}_0$ 退化为 $\text{VCao}(\mathcal{H}, \mathcal{G})$。因此最终得到期望误差上界 $\frac{\text{VCao}(\mathcal{H}, \mathcal{G})}{n1}$。这个证明的精妙之处在于它通过对称化将算法在随机样本上的期望误差转化为在一个固定样本集上、对所有可能训练/测试划分的平均误差。而后者的上界可以直接用该固定样本集上定义的、考虑了不变性的假设类的VC维来刻画。不变性通过缩小有效假设类 $\mathcal{H}(X)$ 来降低 $\text{VCdim}$从而直接降低了误差上界。4.2 从期望误差到高概率保证置信度提升上述证明给出了期望误差的上界。但我们需要的是高概率保证以至少 $1-\delta$ 的概率误差小于 $\epsilon$。这通过一个经典的“置信度提升”技术实现。提升步骤独立运行基础算法 $\mathcal{A}$ 共 $k \lceil \log(2/\delta) \rceil$ 次每次使用 $n \Theta(\frac{\text{VCao}}{\epsilon})$ 个新样本得到假设 $h_1, ..., h_k$。由于每个 $h_i$ 的期望误差 $\leq \frac{\text{VCao}}{n1} \approx \epsilon/2$由马尔可夫不等式可知每个 $h_i$ 有至少1/2的概率其真实误差 $\leq \epsilon$。因为运行了 $k$ 次所有 $h_i$ 的真实误差都大于 $\epsilon$ 的概率 $\leq (1/2)^k \leq \delta/2$。所以以概率 $\geq 1-\delta/2$至少存在一个“好”的 $h_i$误差 $\leq \epsilon$。现在我们需要从 $h_1, ..., h_k$ 中识别出这个“好”的假设。我们再采集一个大小为 $t \Theta(\frac{1}{\epsilon} \log(k/\delta))$ 的新鲜验证集$S_0$。对于误差 $\leq \epsilon$ 的假设其在 $S_0$ 上的经验误差显著大于 $1.5\epsilon$ 的概率很小由切尔诺夫界控制。对于误差 $\geq 2\epsilon$ 的假设其在 $S_0$ 上的经验误差显著小于 $1.5\epsilon$ 的概率也很小。通过设置合适的阈值如 $1.5\epsilon$并选择在 $S_0$ 上经验误差最小的假设我们可以以高概率$\geq 1-\delta/2$选中一个真实误差 $\leq O(\epsilon)$ 的假设。最后用联合界将步骤3和步骤6的成功概率结合起来得到总成功概率 $\geq 1-\delta$。参数选择技巧这里 $n$ 和 $t$ 的大小需要精心平衡。$n$ 主要控制基础算法的期望误差与 $\text{VCao}/\epsilon$ 成正比。$t$ 用于区分“好”假设和“坏”假设与 $\log(\text{候选数}/\delta)/\epsilon$ 成正比。因为候选数 $k$ 是 $\log(1/\delta)$ 量级所以 $t$ 是 $\log\log(1/\delta)/\epsilon$ 量级通常远小于 $n$。总样本量 $m k \cdot n t O(\frac{\text{VCao}}{\epsilon} \log(1/\delta) \frac{\log\log(1/\delta)}{\epsilon})$主导项是前者。5. 实践启示与未来方向理论的价值在于指导实践。不变性PAC学习理论给我们带来了哪些启示5.1 模型设计中的归纳偏置理论明确告诉我们将不变性作为归纳偏置Inductive Bias注入学习过程可以从根本上降低样本复杂度。这不仅仅是经验上的技巧如数据增强而是有严格理论保障的。在设计神经网络架构时使用群等变卷积如旋转等变的Harmonic Networks或不变池化就是在假设类 $\mathcal{H}$ 中硬编码不变性这可能会显著降低其 $\text{VCao}$即使其 $\text{VCdim}$ 可能依然很高。5.2 数据增强的理论基础数据增强Data Augmentation是实践中利用不变性的最主要手段。从理论视角看对训练样本应用群 $\mathcal{G}$ 中的变换并复制标签等价于在经验风险最小化中强制要求模型对这些变换保持不变。这可以理解为在优化过程中对假设空间进行了隐式约束使其更接近满足不变性的子集。理论分析表明这种做法的好处是有上限的其样本效率的提升受限于 $\text{VCao}$ 与 $\text{VCdim}$ 的差距。5.3 自适应算法的工程意义自适应算法的思想非常实用。在面对一个新问题时我们不必纠结于“我的数据到底在多大程度上满足旋转不变性”我们可以设计一个系统同时训练多个不同不变性强度约束的模型例如使用不同程度、不同类型数据增强的模型或不同架构的模型然后在一个干净的验证集上进行模型选择。这本质上是将理论中的网格搜索和验证选择落地。5.4 开放问题与挑战紧致性不可知场景下上界中的 $\log^2(\text{VCao}/\epsilon)$ 因子能否消除是否存在匹配下界 $\Omega(\text{VCao}/\epsilon^2)$ 的算法更复杂的不变性当前理论主要处理群作用下的不变性。对于更复杂的、非群结构的变换如弹性形变或近似不变性如“大多数情况下不变”的量化理论仍需发展。计算效率1-包含图预测器等算法主要是理论构造计算上可能不可行。如何设计计算高效且能实现或接近这些样本复杂度上界的算法是连接理论与实践的关键。与深度学习的结合如何将 $\text{VCao}$ 之类的复杂度度量与超大规模的深度神经网络联系起来尽管直接计算深度网络的VC维不现实但研究不变性先验如何影响其泛化行为仍然极具价值。例如通过测量网络对变换后的数据在特征空间的表示距离可以间接评估其不变性这可能与泛化 gap 相关。不变性学习理论为我们提供了一套精确的语言和工具来分析和理解“先验知识如何帮助学习”。它告诉我们成功的机器学习不仅关乎数据和算力更关乎我们对问题结构的深刻洞察与巧妙利用。将对称性、不变性等先验编码到学习系统中是迈向更通用、更高效人工智能的重要一步。
