Surprises in Proper Positive-Only Learning¶
会议: NeurIPS 2026
arXiv: 2606.28309
OpenReview: https://openreview.net/forum?id=v81L38ZyrQ
领域: 优化/理论
关键词: 正样本学习 (Positive-Only Learning)、PAC 学习理论、真学习 (Proper Learning)、VC 维 (VC Dimension)、一致外部可分性 (Uniform Exterior Separability)
一句话总结¶
论文彻底解决了正样本 PAC 学习领域长期悬而未决的“真学习（Proper Learning）”完全刻画难题，证明概念类真可学当且仅当具有有限 VC 维且满足一致外部可分性（UES），并揭示了正样本下真与非真学习分离、确定性与随机化分离以及 ERM 失效等一系列颠覆常识的理论现象。
研究背景与动机¶
在经典的 Valiant PAC 学习框架中，学习算法同时接收来自正例与负例区域的独立同分布样本，此时有限 VC 维充当了可学习性的充要条件，且任何经验风险最小化（ERM）规则都能保证 PAC 可学。然而在医疗诊断（仅有确诊病例而缺少确证无病的对照组）、网页检索与推荐系统（用户隐式反馈仅表明正面兴趣）等诸多真实场景中，负例往往极难收集、稀缺甚至完全缺失，这自然引出了仅能观测正例样本的正样本学习模型（Positive-Only Learning）。在此模型中，学习算法仅在正区域分布 \(\mathcal{D}_+\) 上抽取样本，但泛化误差却必须在包含正负区域的原始全空间分布 \(\mathcal{D}\) 上进行评估，算法必须在没有负例指导的前提下严格抑制负区域的假阳性（False Positive）。
对于非真学习（Improper Learning，即允许算法输出概念类 \(\mathcal{H}\) 之外的假设，如交集闭包），其可学习性在 20 世纪 80 年代末就已被完全刻画（充要条件为有限交集类的 VC 维有限，即 \(\operatorname{VCdim}(\mathcal{H}_{\cap}) < \infty\)），甚至被写入经典教科书习题。然而，要求学习器输出必须严格属于原始概念类 \(\mathcal{H}\) 的“真学习（Proper Learning）”问题，却作为基本理论悬案遗留了数十年之久。Natarajan 在 1987 年曾猜想单边无假阳性误差的交集封闭条件也是双边真可学的充要条件。
破解这一理论空白的核心矛盾在于：正样本只能直接锁定样本点落入的闭包内区域，而闭包之外的广阔未知空间在没有负例时极易引发无法控制的假阳性泛化错误；若原始概念类本身不具有交集封闭性，输出最小闭包就会直接破坏“真学习”的约束。核心 idea：通过引入随机化思想构造假阳性分散机制，将真可学习性等价刻画为有限 VC 维与一致外部可分性（Uniform Exterior Separability, UES）的结合，利用对偶 VC 维实现概率离散化，并建立确定性/随机化、真/非真以及经验风险最小化（ERM）有效性之间的严格理论分离。
方法详解¶
整体框架¶
论文的研究对象是正样本分布下的真 PAC 学习。输入为未知分布 \(\mathcal{D}\) 在未知目标概念 \(\ell \in \mathcal{H}\) 下条件化生成的 \(n\) 个独立同分布正样本 \(S_+ \sim \mathcal{D}_+ = \mathcal{D}\mid(x \in \ell)\)；输出必须是一个严格属于 \(\mathcal{H}\) 的假设 \(\widehat{h} \in \mathcal{H}\)；性能度量为全分布下的对称差误差 \(\operatorname{err}_{\mathcal{D}}(\widehat{h}, \ell) = \mathcal{D}(\widehat{h} \triangle \ell) \leq \varepsilon\)。整体理论框架围绕样本闭包（Closure）及其外部点覆盖概率的精确控制展开，分为核心条件建立、对偶维离散化、随机比特压缩以及理论分离性构建四个核心阶段。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["正样本集 S+ ~ D+<br/>条件正例观测输入"] --> B["一致外部可分性判定<br/>构建 UES 候选假设簇"]
B --> C["对偶 VC 维紧致离散化<br/>二阶一致收敛控制外部边际"]
C --> D["极低随机比特真学习器<br/>O~(d* + log 1/ed) 随机种子采样"]
D --> E["PAC 误差保证落盘<br/>真假设 h^ ∈ H, 误差 ≤ ε"]关键设计¶
1. 一致外部可分性（Uniform Exterior Separability, UES）：刻画真可学性的组合核心 在正样本学习中，样本版本空间为 \(\mathcal{H}_S = \{h \in \mathcal{H}: S \subseteq h\}\)，其最小闭包定义为 \(\operatorname{CLOS}_{\mathcal{H}}(S) = \bigcap_{h \in \mathcal{H}_S} h\)。闭包内的点由正样本强制约束为正，而外部点 \(x \notin \operatorname{CLOS}_{\mathcal{H}}(S)\) 则可能被不当纳入而产生假阳性。针对此问题，论文提出一致外部可分性（UES）：对于任意 \(\eta > 0\)，存在仅依赖于 \(\eta\) 的整数 \(M(\eta)\)，使得对任意有限可实现正样本集 \(S\)，存在候选假设集合 \(\{h_{S, 1}, \dots, h_{S, M(\eta)}\} \subseteq \mathcal{H}_S\)，满足闭包外任意单一测试点的平均命中率上界： $\(\sup_{x \notin \operatorname{CLOS}_{\mathcal{H}}(S)} \frac{1}{M(\eta)} \sum_{i=1}^{M(\eta)} \mathbf{1}\{x \in h_{S, i}\} \leq \eta\)$ 该设计的精妙之处在于不强求单个假设完全避开外部点（这在非交集封闭类中常常不可实现），而是通过假设簇的均匀稀疏覆盖，使得随机抽取一个假设时，任何负例点的期望假阳性测度均被压制在 \(\eta\) 以内。
2. 对偶 VC 维离散化桥梁：从分布外部可分（DES）跃升至一致外部可分（UES） 直接从算法存在性出发，只能诱导出任意概率测度 \(\mu_{S, \eta}\) 上的“分布外部可分性”（DES）。为了将其提升为仅依赖固定假设列表的组合性质 UES，论文将闭包外的外部测试点诱导的范围族定义为 \(\mathcal{R}_S = \{R_x^S : x \notin \operatorname{CLOS}_{\mathcal{H}}(S)\}\)，其中 \(R_x^S = \{h \in \mathcal{H}_S : x \in h\}\)。关键发现是：\(\mathcal{R}_S\) 本质上是对偶概念类 \(\mathcal{H}^\star\) 在子域上的限制。根据 Assouad 对偶定理，若原始类的 VC 维 \(d = \operatorname{VCdim}(\mathcal{H}) < \infty\)，则对偶类的 VC 维必定有限且满足 \(d^\star = \operatorname{VCdim}(\mathcal{H}^\star) < 2^{d+1}\)。论文借助有限对偶 VC 维上的二阶一致收敛理论（Second-Order Uniform Convergence），证明仅需抽取大小为 \(M(\eta) = O\left(\frac{d^\star \log(1/\eta)}{\eta}\right)\) 的有限假设子集，就能以正概率同时控制所有外部点上的经验平均频率不超过 \(\eta\)，从而完成了从测度到纯组合条件的升格。
3. 极低随机比特资源化：指数级少于正样本数的随机数消耗 既然真学习器需要借助随机化来规避假阳性，论文进一步定量回答了“学习需要消耗多少随机比特”这一基础问题。基于上述对偶离散化结果，论文构造了一个仅依赖于 \(O(\log M(\eta))\) 个均匀随机比特的真学习算法。该算法先通过 \(O\left(d + \log\frac{1}{\varepsilon\delta}\right)\) 个随机比特在一个规模为 \(K \in [M, 2M)\) 的离散索引集合中采样，再映射到选取的 UES 假设。由于样本复杂度需要 \(m(\varepsilon, \delta) = \widetilde{O}\left(\frac{d + \log(1/\delta)}{\varepsilon}\right)\)，在常数 VC 维下，随机比特数仅为对数级别 \(\widetilde{O}\left(\log\frac{1}{\varepsilon\delta}\right)\)，展现了随机性消耗与样本复杂度之间呈指数级的鸿沟。
4. 结构性反例构造：推翻 Natarajan 猜想与理论分离谱系 为了验证理论边界，论文构造了精巧的概念类 \(\mathcal{H}_{\mathrm{spr}} = \{\{1\}, \{2\}\} \cup \{\{1, 2, i\} : i \geq 3\}\)（定义于自然数域 \(\mathbb{N}\)）。对于正样本 \(\{1, 2\}\)，其闭包 \(\{1, 2\} \notin \mathcal{H}_{\mathrm{spr}}\)，因而不具备单边误差学习所需的精确外部可分性，直接推翻了 Natarajan 猜想；同时，论文进一步证明对该概念类，任何确定性 ERM 规则都必定存在对抗分布使得误差至少为 \(1/2\)。此外，针对概念类 \(\mathcal{H}_{\mathrm{tail}} = \{h_a : a \geq 3\}\)（其中 \(h_a = \{1, 2\} \cup \{m \in \mathbb{N} : m \geq a\}\)）与 \(\mathcal{H}_{\mathrm{bin}}\)，严格证明了有限 VC 维在正样本学习中甚至无法保证非均匀可学性（Non-Uniform Learnability），建立了 PAC 可学、非均匀可学与一致性（Consistency）之间的逐级分离。
损失函数 / 训练策略¶
该理论算法在执行时采用两阶段误差控制策略： - 假阴性误差界（False Negative Control）：对于包含在目标概念 \(\ell\) 内的正区域，由于 \(\operatorname{VCdim}(\mathcal{H}) = d < \infty\)，当正样本量满足 \(n \gtrsim \frac{1}{\varepsilon}\left(d \log \frac{1}{\varepsilon} + \log \frac{1}{\delta}\right)\) 时，由标准可实现 VC 维泛化界可得，所有包含样本点的假设 \(h \in \mathcal{H}_S\) 均以至少 \(1 - \delta/2\) 的概率满足： $\(\mathcal{D}(\ell \setminus h) \leq \mathcal{D}_+(\ell \setminus h) \leq \frac{\varepsilon}{2}\)$ - 假阳性误差界（False Positive Control）：对于闭包外部区域，利用 UES 假设集合的平均覆盖率，设置截断参数 \(\eta = \frac{\varepsilon\delta}{8}\)，使得随机抽样假设对任意外部点的包含概率受控。由 Fubini 定理与 Markov 不等式： $\(\Pr_{J}\left(\mathcal{D}(\mathcal{A}(S_+, J) \setminus \ell) > \frac{\varepsilon}{2} \;\middle|\; S_+\right) \leq \frac{\mathbb{E}_J[\mathcal{D}(\mathcal{A}(S_+, J) \setminus \ell)]}{\varepsilon/2} \leq \frac{2\eta}{\varepsilon/2} = \frac{\delta}{2}\)$ 联合两阶段界，算法以至少 \(1 - \delta\) 的总概率达成 \(\operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+, J), \ell) \leq \varepsilon\)。
实验关键数据¶
主实验¶
作为纯理论机器学习论文，本研究的核心结论体现在严格的定理证明与不同监督/学习范式之间的本质界限分离。
| 学习范式 / 机制 | 可学习性充要条件 | 确定性算法普适性 | ERM 普适性 | 典型反例类 |
|---|---|---|---|---|
| 标准双边 PAC 学习 | \(\operatorname{VCdim}(\mathcal{H}) < \infty\) | 是（确定性与随机化等价） | 是（任意 ERM 均为学习器） | 无（VC 维完全统治） |
| 非真正样本学习 (Improper) | \(\operatorname{VCdim}(\mathcal{H}_{\cap}) < \infty\) | 是（直接输出闭包交集） | 是（交集闭包即为 ERM） | \(\mathcal{H}_{\mathrm{improper}}\) (仅需交集 VC 维有限) |
| 真正样本学习 (Proper) [本文] | \(\operatorname{VCdim}(\mathcal{H}) < \infty\) 且满足 UES | 否（随机化严格强于确定性） | 否（存在无有效 ERM 的类） | \(\mathcal{H}_{\mathrm{spr}}\) (推翻猜想), \(\mathcal{H}_{\mathrm{tail}}\) |
| 单边误差正样本学习 (One-Sided) | \(\operatorname{VCdim}(\mathcal{H}) < \infty\) 且精确外部可分 | 是（依赖闭包自包含） | 是（仅闭包自身有效） | Natarajan 1987 模型（条件过强） |
| 稳定真正样本学习 (Stable) | \(\operatorname{VCdim}(\mathcal{H}) < \infty\) 且精确外部可分 | 是（强稳定性强制闭包归属） | 是 | \(\mathcal{H}_{\mathrm{spr}}\) 破坏稳定性退回精确分离 |
消融实验¶
论文对外部可分性层级链条及统计学习松弛条件展开了深度的理论“消融”与分离验证：
| 理论性质 / 条件组合 | 导出结论与学习能力 | 关键机制支撑 | 严格不可逆反例 |
|---|---|---|---|
| 精确外部可分 (Exact ES) | 蕴含 UES 与 DES，允许稳定学习器 | \(M(\eta) = 1\)，闭包属于原类 | \(\mathcal{H}_{\mathrm{spr}}\) 满足 UES 但非 Exact ES |
| 一致外部可分 (UES) | 等价于正样本真可学习性 | 依赖对偶 VC 维实现有限列表覆盖 | \(\mathcal{H}_{\mathrm{tail}}\) 满足有限可分但破坏 UES |
| 分布外部可分 (DES) + 有限 VC | 与 UES 在有限 VC 下等价 | 二阶一致收敛保证测度离散化 | 无差异（定理 3 证明其等价性） |
| 有限外部可分 (FES) | 仅能保证可数域上的一致性 (Consistency) | 无法控制无界集上的均匀收敛 | \(\mathcal{H}_{\mathrm{tail}}\) (满足 FES 但 PAC 不可学) |
| 有限 VC 维 + 非均匀学习 (Non-Uniform) | 样本复杂度允许依赖目标概念 \(\ell\) | 放宽样本依赖，消除单一全局下界 | \(\mathcal{H}_{\mathrm{bin}}\) (一致但非均匀不可学) |
关键发现¶
- 对偶 VC 维的意外作用：将测度级的分布外部可分性（DES）转化为有限列表的一致外部可分性（UES），关键并非依赖原始样本空间的 VC 维，而是利用了对偶空间 \(\mathcal{H}^\star\) 的有限 VC 维性质，这种离散化手法此前仅出现在样本压缩方案（Sample Compression Schemes）中。
- 随机性作为学习资源的不可消除性：证明了“单点闭包（Singleton Closure）”是确定性真正样本学习的必要条件；当概念类不满足单点闭包时，任何确定性算法均会彻底失效，必须借助外部随机数或内生经验计数扰动来破除假阳性集中。
- ERM 普适性的破灭：在标准 PAC 学习中被视为基石的经验风险最小化（ERM）原则在正样本真学习中失效，存在哪怕是确定性可学的类（如 \(\mathcal{H}_{\mathrm{spr}}\)），也绝对不存在任何能够完成学习任务的确定性 ERM 规则。
亮点与洞察¶
- 彻底终结了自 1987 年由 Natarajan 开启的长达近 40 年的理论悬案，给出了正样本真 PAC 学习简洁、优雅且深刻的充要组合刻画。
- 深刻揭示了监督信号弱化对学习系统带来的结构性突变：在正样本学习中，真与非真、随机与确定、ERM 与非 ERM 发生了全面分裂，颠覆了经典 PAC 学习中“一切归于 VC 维与 ERM”的认知常识。
- 引入的“外部可分性（Exterior Separability）”系列概念及其利用对偶 VC 维进行稀疏覆盖证明的技术路径，极具通用价值，可直接拓展到正未标记学习（PU Learning）、分布外检测（OOD Detection）以及弱监督泛化等理论前沿。
局限与展望¶
- 计算复杂度未予考虑：作为统计学习理论工作，该研究仅聚焦于样本复杂度与信息论可学习性，未探讨在计算受限（多项式时间）下的真学习算法实现。
- 最优随机比特下界未闭合：尽管证明了 \(O\left(d + \log\frac{1}{\varepsilon\delta}\right)\) 极低随机比特足以完成学习，且随机性不可完全消除，但实现真正样本学习所需的精确最优随机比特复杂度（Optimal Random-Bit Complexity）仍有待进一步攻克。
- 连续特征空间的延伸：非均匀学习与一致性的部分分离结论目前建立在可数或离散基底上，在连续流形或高维平滑分布下的完整刻画仍需后续理论拓展。
相关工作与启发¶
- vs Natarajan (STOC 1987): Natarajan 奠定了单边误差正样本学习的基础并猜想其充要条件适用于双边误差模型；本文通过构造 \(\mathcal{H}_{\mathrm{spr}}\) 反例推翻了该猜想，证明双边放宽后容许非闭包类的真学习。
- vs Kearns & Vazirani (1994) / Gereb-Graus (1989): 早期经典工作解决了非真学习的交集闭包刻画 \(\operatorname{VCdim}(\mathcal{H}_{\cap}) < \infty\)；本文则补齐了该体系缺失的关键一环——严格真学习（Proper Learning）的充要条件。
- vs Moran & Yehudayoff (JACM 2016): Moran 等人在样本压缩机制中利用对偶 VC 维进行概率测度离散化；本文敏锐地将这一深度几何工具移植到正样本外部点覆盖控制中，架起了测度理论与组合维度的桥梁。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 彻底解决了持续近 40 年的经典学习理论公开悬案，理论创新性极高。
- 实验充分度: ⭐⭐⭐⭐⭐ 作为纯理论顶会论文，构造了一系列严密且极具说服力的结构性反例与充要定理。
- 写作质量: ⭐⭐⭐⭐⭐ 逻辑结构严谨清晰，从简单反例铺垫到一般定理，数学推导详实优美。
- 价值: ⭐⭐⭐⭐⭐ 完善了统计学习理论关于不完全监督学习的理论版图，奠定了正样本真学习的标准参考坐标。