纯正例学习中的意外发现

论文信息

标题: Surprises in Proper Positive-Only Learning

作者: Shai Ben-David, Farnam Mansouri, Anay Mehrotra, et al.

发布日期: 2026-06-26

PDF 链接: 下载 PDF

背景与研究动机

在经典的 PAC 学习框架中，学习者能够观察到来自正负两类的标注样本。然而在许多现实场景里，负样本往往难以获取或标注代价高昂。例如医疗诊断中只记录确诊病例，未确诊人群无法简单视为健康对照；推荐系统中点击或购买行为提供正反馈，但未点击却蕴含多种可能性。这种 “仅正样本学习” 问题早在 Valiant 的开创性工作中就被提及，并被形式化为一种 PAC 学习的变体：学习者仅从目标概念的正区域中独立同分布采样，但最终假设的误差仍要在原始分布（包含正负区域）下评估。

这一模型中，不当学习者可以输出不在原概念类 $\mathcal{H}$ 中的假设。已有经典结论： $\mathcal{H}$ 能被不当学习当且仅当其有限交闭包 $\mathcal{H}_{\cap}$ 的 VC 维有限。然而，恰当学习要求输出必须属于 $\mathcal{H}$ 本身，其可学性的充要条件却长期悬而未决。Natarajan 曾猜想恰当仅正样本学习的充要条件依旧是 $\mathcal{H}$ 的交闭性质，但这篇论文通过一系列精彩的反例和定理彻底否定了这一猜想，揭示了恰当仅正样本学习拥有比标准 PAC 学习远为丰富的理论图景。

核心概念：外部可分离性

为了刻画仅用正样本时的恰当学习，论文引入了一系列 “外部可分离性” 条件，它们都围绕一个关键对象——闭包。给定一个观察到的正样本集 $S$ ，所有包含 $S$ 的 $\mathcal{H}$ 中子集的交集称为 $S$ 在 $\mathcal{H}$ 下的闭包，记作 $\operatorname{CLOS}_{\mathcal{H}}(S)$ 。闭包中的点是已被样本强制为正的，而闭包之外的点才是学习真正的挑战：一个恰当学习者必须在不在闭包内的区域控制假阳性。

基于此，论文定义了四个层次加强的条件：

精确外部可分离性：要求闭包本身始终属于 $\mathcal{H}$ （最强的条件）。
均匀外部可分离性：对任意 $\eta>0$ ，存在仅依赖于 $\eta$ 的常数 $M(\eta)$ ，使得对任一样本 $S$ ，都存在 $M(\eta)$ 个来自 $\mathcal{H}_S$ （包含 $S$ 的假设）的列表，列表中的假设在闭包外任何一点的平均覆盖频率不超过 $\eta$ 。
分布外部可分离性：将均匀列表放松为任意的概率分布 $\mu_{S,\eta}$ 支撑在 $\mathcal{H}_S$ 上，且对闭包外的每一点，从该分布采样出的假设包含该点的概率不超过 $\eta$ 。
有限外部可分离性：最弱的条件，只要求对闭包外的任意有限点集 $F$ ，都存在一个包含 $S$ 的假设与 $F$ 不相交。

论文证明，在有限 VC 维的前提下，分布外部可分离性可以被加强为均匀外部可分离性。这一升级证明用到了对偶类 $\mathcal{H}^{\star}$ 的 VC 维和二阶均匀收敛技术，是该工作的一个技术亮点。

主要结果：恰当仅正样本学习的特征化

论文的核心定理 4 给出了恰当仅正样本学习的完整刻画：

$\mathcal{H}$ 能被恰当仅正样本学习当且仅当 $\operatorname{VCdim}(\mathcal{H})<\infty$ 且 $\mathcal{H}$ 满足均匀外部可分离性。

这一结果将标准 PAC 学习中 “有限 VC 维” 的单一条件，替换为有限 VC 维加上一个新的组合条件，使恰当学习与不当学习严格分离。更令人意外的是，该特征化还衍生出一系列与标准 PAC 学习截然不同的性质：

恰当与不当学习分离：存在概念类能被不当仅正样本学习，但不能被恰当学习（定理 14）。
随机学习与确定学习分离：有些类能被随机化恰当学习，但没有任何确定性恰当学习算法（定理 6）。这与标准 PAC 学习中随机和确定的恰当学习等价形成了鲜明对比。
ERM 不是通用学习者：在标准 PAC 可学习类中，任何经验风险最小化规则都是学习算法；但在仅正样本的恰当学习里，存在可被确定性恰当学习的类，却没有一个确定性的 ERM 规则能够学习它（定理 7）。
有限 VC 维不足以保证非均匀学习：不同于标准模型，存在 VC 维为 1 的类，它们不是恰当仅正样本可学的，甚至不满足一致性（定理 8）。

此外，论文还精确量化了随机性资源：任何能被随机化恰当学习的类，都只需 $\widetilde{O}(d + \log 1/\varepsilon\delta)$ 个随机比特（ $d$ 为 VC 维），但随机性不能被完全消除，证明了随机性是恰当仅正样本学习的一种必要资源。

方法概览：如何反驳 Natarajan 猜想

理解这一系列结果的核心，是论文巧妙构造的一类反驳 Natarajan 猜想的例子 $\mathcal{H}_{\mathrm{spr}}$ ：

\mathcal{H}_{\mathrm{spr}} = \left\{ \{1\}, \{2\} \right\} \cup \left\{ \{1,2,i\} : i\ge 3 \right\}

它的 VC 维为 1，但闭包 $\{1,2\}$ 并不属于该类。Natarajan 猜想这会阻碍恰当学习。然而，论文设计了一个随机化的恰当学习器：当样本中只有 1 和 2 出现，且两者均有足够次数时，学习器随机地从 $\{1,2,M\}$ 中选一个，其中 $M$ 均匀取自一个很大集合。这样，任何闭包外的特定点被包含的概率仅约为 $1/N$ ，预期假阳性错误可以通过选择 $N\approx 1/\varepsilon\delta$ 来控制。这一构造完美逃逸了闭包不在类中的困境，是利用均匀外部可分离性的雏形。

在充分性证明中，作者直接使用分布外部可分离性：给定样本 $S$ ，学习器从 $\mu_{S,\eta}$ 中采样输出，其中 $\eta\approx\varepsilon\delta$ 。有限 VC 维通过标准一致收敛保证了假阴性很小，而分布外部可分离性则限制了假阳性的期望，再通过马尔可夫不等式转化为高概率保证。必要性证明分两步：第一步，给定一个恰当的仅正样本学习器，通过精心构造 “硬实例” 分布族 $\mathcal{D}_x$ ，可以从中提取出一个满足分布外部可分离性的分布；第二步，利用对偶类 VC 维有限的事实，通过二阶均匀收敛技术将分布外部可分离性提升为均匀外部可分离性。

创新点与贡献

本论文的贡献不仅在技术层面，更在于深刻重塑了人们对仅正样本恰当学习的理解：

首次解决长期开放问题：给出了恰当仅正样本学习的组合特征化。
提出新型组合维度：外部可分离性系列条件，可能扩展到其他弱监督学习场景。
揭示分离现象：恰当与不当、随机与确定、ERM 与非 ERM 之间的多条分离线，表明仅正样本学习的恰当版本远比经典 PAC 学习复杂。
随机性作为资源：建立了随机比特与样本复杂度的定量关系，并严格证明了随机性的必要性。
稳定性新刻画：定义了 “稳定” 恰当学习者，证明其恰对应于精确外部可分离性，为设计具有一致性的算法提供了指南。

实践应用建议

从应用角度看，本论文为那些只能获取正样本的分类任务提供了具体的算法设计原则：

恰当学习器设计：若领域专家要求模型输出始终在预定义的概念类内（如医疗诊断中只能输出某种已知疾病），则必须保证 $\mathcal{H}$ 除了 VC 维有限外，还应具备均匀外部可分离性。实际操作中，可检测给定类别是否能通过随机化策略（如 $\mathcal{H}_{\mathrm{spr}}$ 中的均匀选择）将闭包外的风险摊平。
首选随机化：当闭包不在类中时，使用随机化输出一个恰当的 “超集” 往往比强行输出畸形的确定假设更优。尤其在假阴性代价高、假阳性可通过随机分摊降低的场景中，随机化是有效工具。
样本效率与随机比特：仅正样本学习通常需要比全标注学习更多的样本，但随机比特的需求却可以很低（对数级别），这对于边缘设备上的学习方案具有实际意义。实践中可预先在云端用大量样本训练一个随机化策略，部署时仅传输少量随机种子。

在量化交易中，仅正样本对应罕见的交易信号或欺诈模式，模型需要在保持恰当类别约束的同时进行推断，此时利用分布外部可分离性设计组合模型可能有效。对于量子计算领域，虽然直接联系不紧密，但论文对组合维度的分析技巧可能启发量子态分类中类似弱监督设置的研究。

未来方向

尽管给出了特征化，最优样本复杂度和随机比特数的紧界仍待确定。非均匀学习和一致性的完全刻画也是开放问题。此外，外部可分离性的计算复杂度、如何在实际数据上验证这一条件、以及如何将其推广到不可分（agnostic）情况，都是下一步值得探索的方向。

总结

这篇论文不仅漂亮地解决了一个长期开问题，更通过一系列令人惊讶的分离结果，揭示了仅正样本恰当学习独有的结构美。它提醒我们，弱监督下的恰当性不是标准 PAC 学习的简单移植，而是需要全新的组合洞察。外部可分离性思想的提出，以及随机性作为资源的认识，都将对学习理论产生持续影响。