只看光明的一面：当机器学习失去"反面教材"时 | Positive-Only Learning深度解读

📖 论文概要

项目	内容
标题	Surprises in Proper Positive-Only Learning
作者	Shai Ben-David, Farnam Mansouri, Anay Mehrotra
领域	机器学习理论 / 计算学习理论
发布	2026年6月
arXiv	[待更新]
核心贡献	首次完整刻画了Proper Positive-Only学习的可学性条件，发现与标准PAC学习有显著差异的丰富景观

---

🎭 一、只认识笑脸的识别器：一个思想实验

想象一个婴儿，从出生起就被关在一个特殊的房间里。这个房间的设计很奇特：所有进入房间的人都被要求微笑。无论他们是开心的、悲伤的、愤怒的、疲惫的，只要踏入这个房间，就必须展露笑容。婴儿从未见过皱眉、怒目、哭泣、面无表情——在他短暂的生命中，人类的脸只有"笑脸"这一种形态。

现在，有一天，婴儿被抱出了这个房间，看到了外面的世界。他看到了街上形形色色的面孔：有人皱着眉头赶地铁，有人面无表情地刷手机，有人在争吵中涨红了脸，有人因为悲伤而流泪。婴儿困惑了。他的大脑里只有一个概念："人类的脸是笑脸"。面对这些"非笑脸"的面孔，他该如何理解？他该如何判断"这是不是一张人脸"？

这个思想实验揭示了一个深刻的认知问题：如果我们只见过"正面例子"，我们还能学会一个概念吗？ 更具体地说：如果一台机器学习模型只见过"正类"样本（如"笑脸"），从未见过"负类"样本（如"非笑脸"），它还能学会区分"笑脸"和"非笑脸"吗？

在机器学习中，这个问题被称为Positive-Only Learning（纯正面学习）或Learning from Positive and Unlabeled Data（从未标注数据中学习，LPUL）。它不是一个新问题——早在1987年，计算学习理论的先驱Natarajan就提出了这个模型。但近40年来，一个核心问题一直悬而未决：在"纯正面学习"的框架下，什么样的概念类是可以被"正确学习"的？

这里的"正确学习"（Proper Learning）有特定含义：它要求学习算法输出的假设（hypothesis）必须来自与目标概念相同的概念类。例如，如果目标概念是"二维平面上的圆形区域"，那么学习算法输出的假设也必须是圆形区域，而不能是椭圆形、多边形或任意形状。这与"非正确学习"（Improper Learning）形成对比——后者允许学习算法输出任何形状的假设，只要它能准确分类。

Surprises in Proper Positive-Only Learning这篇论文，正是要回答这个长期悬而未决的问题。而答案，出人意料地丰富、复杂，甚至颠覆了我们关于学习的直觉。

---

🧠 二、从标准PAC学习到纯正面学习：一场认知框架的冒险

2.1 PAC学习的标准剧本：正负样本的舞蹈

要理解纯正面学习的特殊性，我们首先需要回顾标准PAC学习（Probably Approximately Correct Learning）的剧本。

在标准PAC学习中，学习算法就像一个在教室里上课的学生：

• 老师（数据生成器）随机抽取样本，告诉学生"这是正例"或"这是负例"。
• 学生（学习算法）观察这些样本，尝试找出"规律"——即一个能区分正例和负例的"概念"。
• 考试（泛化测试）中，老师给学生看新的样本，学生需要判断它们是正例还是负例。

PAC学习的理论保证非常优美：只要概念类有有限的VC维（Vapnik-Chervonenkis Dimension），并且学生看到了足够多的样本，那么学生就能以很高的概率（Probably）学到近似正确（Approximately Correct）的概念。这个理论框架为机器学习奠定了坚实的数学基础。

但PAC学习有一个隐含的假设：正负样本都被标注了。学生不仅知道"什么是正例"，还知道"什么是负例"。这在很多现实场景中是不成立的。

2.2 纯正面学习的现实困境：为什么我们只能看到"一半世界"

纯正面学习之所以重要，是因为它对应着大量现实世界场景：

场景1：医学诊断

医院有一个数据库，记录了所有被确诊患有某种疾病的患者的病历。但健康人的病历呢？健康人通常不会来医院，所以数据库里没有"健康人"的明确样本。我们想让AI学会"预测谁患有这种疾病"。我们只能给AI看"病人"的数据，而没有"健康人"的数据。AI能学会吗？

场景2：欺诈检测

银行记录了所有被确认为"欺诈交易"的案例。但"正常交易"呢？绝大多数交易都是正常的，但银行不会标注"这是正常交易"——因为正常交易太多了，标注成本太高。我们想让AI学会"识别欺诈交易"。AI只能看到"欺诈交易"的样本，能学会吗？

场景3：异常检测

工厂记录了大量"正常运行"的数据。但"故障"数据呢？故障很少发生，而且每次故障的形式可能都不一样。我们想让AI学会"预测何时会发生故障"。AI只能看到"正常"的数据，能学会吗？

这些场景的共同点是：获取负类样本困难、昂贵或不可能。因此，理解"纯正面学习"的理论极限，对于设计和评估这类实际应用至关重要。

2.3 一个看似简单的问题："只给正面样本，能学到什么？"

直觉上，纯正面学习似乎"不太可能成功"。如果我只给你看"笑脸"，你怎么知道"不笑的脸"长什么样？你甚至不知道"不笑"的存在。你的世界里只有"笑脸"，所以你会把所有非笑脸的东西归类为"未知"或"异常"——但这不是真正的"学习"，只是"记忆"。

然而，计算学习理论告诉我们：直觉可能是错的。纯正面学习是否可行，取决于我们如何定义"学习"，以及我们允许学习算法使用什么样的"假设空间"。

早在1987年，Natarajan就提出了纯正面学习的基本框架：

• 输入：学习算法接收来自"正类区域"的i.i.d.样本（独立同分布样本）。
• 评估：但学习算法在评估时，是在原始分布上测试的——原始分布不仅包含正类区域，还包含负类区域。
• 目标：学习算法需要输出一个假设，使得在原始分布上的错误率（把正类错分为负类，或把负类错分为正类）足够小。

这个框架的微妙之处在于：学习算法只"见过"正类，但在测试时需要处理完整的正负分布。这就像那个婴儿——只见过笑脸，但走出房间后需要判断"这是不是一张人脸"（包括笑脸和非笑脸）。

2.4 非正确学习（Improper Learning）的已知答案

对于纯正面学习的一个变体——非正确学习（Improper Learning）——理论答案是已知的，而且出现在教科书中。

在非正确学习中，学习算法可以输出任何假设，不限于与目标概念相同的概念类。例如，即使目标概念是"圆形"，学习算法也可以输出"椭圆形"或"复杂的多边形"，只要这个假设能准确分类。

对于非正确纯正面学习，可学性的条件很简单：目标概念类需要有有限的VC维。只要VC维有限，非正确学习就是可行的。这个结果的证明思路是：即使只看到正类样本，我们也能推断出正类区域的"形状"。然后，我们可以构建一个"非正确"的假设——一个可能不属于原概念类，但能准确分类的假设。

但正确学习（Proper Learning）呢？ 如果学习算法必须输出一个与原概念类相同的假设（如"必须是圆形"），情况还一样吗？

近40年来，这个问题一直悬而未决。教科书只写了非正确学习的情况，对于正确学习，只标注了"open problem"（开放问题）。

---

🔍 三、破局：Uniform Exterior Separability的诞生

3.1 核心定理：正确纯正面学习的充要条件

这篇论文的核心结果是一个定理（Theorem），它给出了正确纯正面学习的充分必要条件（if and only if）：

一个概念类可以被正确地从纯正面样本学习，当且仅当： 1. 它具有有限的VC维（Finite VC Dimension）； 2. 它满足一个新的组合条件，称为"均匀外部可分离性"（Uniform Exterior Separability）。

这个定理本身就是一项重大的理论突破——它解决了困扰学界近40年的开放问题。但更有意思的是：这个定理揭示了一个令人惊讶的丰富景观——正确纯正面学习与标准PAC学习、非正确纯正面学习有本质的不同。

3.2 什么是"Uniform Exterior Separability"？一个几何直觉

要理解Uniform Exterior Separability，我们需要一些几何直觉。

想象一个概念类是由二维平面上的各种圆形区域组成的。每个"概念"就是一个圆——圆内的点是正类，圆外的点是负类。

现在，考虑两个不同的圆：圆A和圆B。如果圆A和圆B有重叠，它们会形成一个"交集区域"。如果圆A包含圆B，那么圆B完全在圆A内部。

Uniform Exterior Separability条件关注的是：当我们从正类区域中移除某些部分时，剩余部分的"外部"（负类区域）是否可以被"统一地"描述？

更具体地说：对于概念类中的每一个概念C，考虑它的正类区域P(C)。如果我们从P(C)中移除某个子集S，得到剩余区域P(C) \ S。Uniform Exterior Separability要求：存在一个与C无关的"分离函数"，能够区分P(C) \ S和外部区域。

这听起来很抽象，让我们用一个比喻来理解：

想象一个城市（概念C），城市里有各种建筑（正类区域）。我们想让学习算法只通过观察"城市内部的建筑"（纯正面样本），就能推断出"城市的边界在哪里"（区分正类和负类）。

Uniform Exterior Separability的意思是：无论你在城市内部怎么"删除"一些建筑（移除一些正类样本），城市的"外部"（负类区域）始终有一个统一的"特征"——比如"外部没有围墙"、"外部是绿地"、"外部有道路标记"——这些特征与城市内部的细节无关，只与"边界"本身有关。

如果这个条件成立，那么学习算法就可以通过观察城市内部的建筑，推断出"外部有什么特征"，从而重建出城市的边界。如果这个条件不成立（比如城市外部的特征"随着城市不同而不同"），那么学习算法就无法仅凭内部建筑推断出边界。

3.3 为什么这个条件如此关键？从"内部推断外部"的数学

Uniform Exterior Separability的核心思想是：从"正类样本"推断"负类区域"的可行性。在纯正面学习中，学习算法没有见过负类样本，所以它必须通过正类样本的"结构"来推断负类区域的位置。

具体来说，学习算法可以这样做： 1. 观察大量正类样本，推断出正类区域的"大致范围"。 2. 利用Uniform Exterior Separability条件，推断出"外部区域"的某种统一特征。 3. 基于这些特征，构建一个假设，使得它在正类区域上正确，在负类区域上也正确。

如果这个条件不成立，那么"外部区域"的特征会"变化莫测"——对于不同的概念，外部区域的特征完全不同。学习算法就无法仅凭正类样本推断出外部区域，因此无法正确学习。

这个条件的精妙之处在于：它既不是一个简单的几何条件（如"凸性"），也不是一个纯粹的统计条件（如"VC维有限"），而是两者的结合——一个涉及"概念类内部结构"与"外部区域关系"的组合条件。

---

🌌 四、颠覆直觉的丰富景观：四个令人惊讶的分离结果

这篇论文最令人兴奋的部分，不是证明了核心定理，而是揭示了正确纯正面学习与标准PAC学习之间惊人的差异。作者们通过一系列分离结果（Separation Results），展示了纯正面学习世界中"丰富多彩的意外"。

4.1 惊喜1：正确与非正确学习被分离了

在标准PAC学习中，正确学习与非正确学习的可学性条件几乎相同——只要VC维有限，两者都可学。VC维是唯一的"瓶颈"。

但在纯正面学习中，正确学习与非正确学习被彻底分离了！

具体来说：存在一些概念类，它们可以被非正确地从纯正面样本学习，但不能被正确地从纯正面样本学习。

这意味着什么？让我们回到那个"婴儿"的思想实验：

• 非正确学习：婴儿只见过笑脸，但他可以学会"识别笑容"——不是通过"笑脸"的概念，而是通过某种更复杂的、非"笑脸"的概念（比如"嘴角上扬+眼角皱纹+面部肌肉放松的组合"）。这就像一个"非正确"的假设——它不直接说"这是笑脸"，而是通过一些间接特征来识别。
• 正确学习：婴儿必须输出一个"笑脸"的概念——即"笑脸就是笑脸，不能用其他概念来替代"。如果Uniform Exterior Separability条件不满足，即使婴儿能"识别笑容"（非正确学习），他也无法真正"理解笑脸的概念"（正确学习）。

这个分离结果非常反直觉。它告诉我们：在纯正面学习的设定下，"能识别"和"能正确理解概念"是两回事。这是标准PAC学习中不存在的现象。

4.2 惊喜2：随机化与确定性正确学习被分离了

在标准PAC学习中，随机化学习（使用随机算法的PAC学习）和确定性学习（使用确定性算法的PAC学习）的能力基本相同。如果你能用随机算法学习，你通常也能用确定性算法学习（或至少可以"去随机化"）。

但在纯正面学习的正确学习设定下，随机化正确学习和确定性正确学习被分离了！

存在一些概念类：

• 可以被随机化正确学习（使用随机算法输出正确概念类中的假设）
• 但不能被确定性正确学习（使用确定性算法输出正确概念类中的假设）

这意味着什么？在某些情况下，"抛硬币"（随机化）能让学习算法做到"确定性的规则"做不到的事。这就像是：在某些迷宫中，一个随机行走的机器人能走出去，但一个按照确定规则行走的机器人会被困住。

这个结果尤其令人惊讶，因为在标准PAC学习中，随机化通常只是为了"简化证明"或"提高效率"，而不是"扩展可学性"。但在纯正面学习中，随机化是能力上的必要条件，而不仅仅是便利性上的选择。

4.3 惊喜3：有限VC维是不够的——即使是非均匀学习

在标准PAC学习中，有限VC维是学习能力的充分条件（对于非正确学习）。如果一个概念类的VC维有限，那么无论分布是什么，无论目标概念是什么，我们都能学习。

但在纯正面学习中，有限VC维甚至不足以保证非均匀学习（Non-Uniform Learning）！

非均匀学习比标准PAC学习更弱：它允许学习算法对于每个目标概念都有一个独立的样本复杂度（"学习概念A需要100个样本，学习概念B需要1000个样本"），而不是要求所有概念都统一用N个样本就能学会。

即使在这种更弱的设定下，有限VC维也不足以保证正确纯正面学习。这意味着Uniform Exterior Separability条件不是"锦上添花"，而是"必不可少"——即使VC维再小，没有这个条件，正确学习也是不可能的。

这个结果极大地挑战了我们的直觉。在标准PAC学习中，VC维是"万能钥匙"——它几乎能解决所有问题。但在纯正面学习中，VC维只是"必要条件之一"，而不是"充分条件"。这就像是：你有一把钥匙（VC维），但它只能打开锁的一部分——还需要另一把钥匙（Uniform Exterior Separability）才能完全打开。

4.4 惊喜4：ERM（经验风险最小化）会失效

经验风险最小化（Empirical Risk Minimization, ERM）是机器学习的"基石算法"：选择那个在训练样本上错误率最低的假设。在标准PAC学习中，ERM是"万能学习器"——对于任何有限VC维的概念类，ERM都能以高概率学到近似正确的概念。

但在纯正面学习中，作者们证明了：存在某些概念类，没有任何ERM算法能正确学习！

这意味着：即使你把所有纯正面样本都喂给一个ERM算法，它也无法输出正确概念类中的假设。这不是因为数据不够，而是因为ERM的优化目标与正确纯正面学习的目标"不兼容"。

这个结果是极其深刻的。它告诉我们：我们不能简单地把标准PAC学习中的"标准算法"（如ERM）搬到纯正面学习中，然后期望它们能工作。纯正面学习需要全新的算法设计思路。

---

🧬 五、Uniform Exterior Separability的深层结构：不仅仅是另一个条件

5.1 为什么"外部"如此重要？拓扑与几何的视角

Uniform Exterior Separability这个名字中，"Exterior"（外部）是关键词。为什么"外部"如此重要？

从拓扑学的角度看，一个概念的正类区域（"内部"）和负类区域（"外部"）构成了空间的划分。学习算法只见过"内部"，但它需要推断"外部"的边界。如果"外部"具有某种"统一的可描述性"，那么仅凭"内部"的信息就能推断出边界。否则，"外部"可能是"任意复杂"的，学习算法就无法推断。

从几何学的角度看，Uniform Exterior Separability类似于一种"规则性"条件：正类区域的边界不能"太不规则"。如果边界是"分形的"（无限复杂）或"随正类区域变化而变化"（没有统一规律），那么学习算法就无法仅凭正类样本来重建边界。

这个条件还与我们熟知的"凸性"等几何概念有关，但更弱也更灵活。凸性要求正类区域是"凸的"（任意两点之间的连线都在区域内），这是一个非常强的条件。Uniform Exterior Separability只要求"外部可统一描述"，这比凸性弱得多，因此适用于更广泛的概念类。

5.2 与已有学习理论概念的联系：Shadows、Shells和Boundaries

Uniform Exterior Separability虽然是一个新提出的条件，但它与计算学习理论中已有的多个概念有深刻的联系：

与Shattering（打散）的联系：VC维的核心概念是"打散"——一个概念类能否打散某个样本集，取决于它的"复杂度"。Uniform Exterior Separability可以看作是"打散"在纯正面学习中的"对偶概念"：不是问"能打散多少内部样本"，而是问"外部区域的规律是否能被统一描述"。

与Shells（壳层）的联系：在统计学习理论中，"壳层"（shells）描述的是假设空间中不同错误率的区域。Uniform Exterior Separability可以被理解为：正类区域的外部必须能被"有限的壳层"覆盖——即外部区域不能"无限复杂"。

与Boundaries（边界）的联系：分类问题的本质是学习"决策边界"。在标准PAC学习中，我们假设正负样本都可见，所以可以直接学习边界。在纯正面学习中，我们只能通过"内部样本"间接推断边界。Uniform Exterior Separability确保的是：这种"间接推断"是可行的——因为边界有某种"可被推断的结构"。

5.3 新组合维度的提出：工具的价值超越问题本身

这篇论文的另一个重要贡献，是引入了新的组合维度（Combinatorial Dimensions），这些维度不仅用于证明纯正面学习的结果，还可能对学习理论有更广泛的影响。

作者们引入的新维度包括：

• External Dimension（外部维度）：衡量概念类"外部区域"的复杂度。
• Separation Dimension（分离维度）：衡量"从正类样本推断外部区域"的难度。

这些维度是工具性的——它们被设计用来分析纯正面学习，但它们也可能被用来分析其他学习设定（如主动学习、迁移学习、元学习等）。这就像是：你发明了一把特殊的螺丝刀来解决一个特定的机械问题，但这把螺丝刀也可能适用于其他类型的螺丝。

作者们在论文中提到："我们引入的新组合维度，我们相信可能对学习理论有更广泛的兴趣。" 这不是谦虚，而是对"工具价值"的深刻理解——好的理论工具，其影响往往超越最初的问题。

---

🏛️ 六、历史回响：从1987到2026——近40年的开放问题终获解答

6.1 Natarajan的原始问题：一个被遗忘的基石

1987年，Natarajan在STOC（计算理论年度盛会）上发表了一篇论文，首次提出了纯正面学习的模型。在那个年代，机器学习还远未成为主流，"学习理论"还是一个非常小众的领域。Natarajan的问题在当时可能被视为"理论上的好奇心"——一个有趣但不太实用的数学问题。

然而，近40年后，当深度学习和大规模数据应用席卷全球，纯正面学习的问题突然变得极其现实。医学诊断、欺诈检测、异常检测、蛋白质结构预测……无数实际应用都面临着"只有正类样本"或"正类样本远多于负类样本"的困境。Natarajan那个看似"纯粹理论"的问题， suddenly 成了指导实践的关键。

这篇论文的发表，标志着一个长达近40年的开放问题终于被解决。这本身就是理论科学"慢工出细活"的一个典范：有些问题需要几十年才能找到答案，但这不意味着它们不重要。相反，正是因为这些问题足够深刻，才值得等待。

6.2 从开放问题到教科书：知识传承的链条

这篇论文的另一个意义在于知识传承。在标准的计算学习理论教科书中（如Kearns和Vazirani的《An Introduction to Computational Learning Theory》），纯正面学习的章节通常只涵盖了非正确学习的结果。对于正确学习，教科书会标注"这个问题仍然开放"或"留给读者作为练习"（尽管它远不是一道简单的练习题）。

现在，这篇论文的结果可以进入下一代教科书。未来的学生在学习计算学习理论时，会学到："正确纯正面学习的充要条件是有限VC维加上Uniform Exterior Separability。" 这个知识会被传承下去，成为标准理论的一部分。

这是一种知识的积累：每一个被解决的开放问题，都成为后来者的"垫脚石"，让他们能站在更高的地方看到更远的问题。

6.3 理论计算机科学的"优雅传统"

这篇论文延续了理论计算机科学的一个优雅传统：用简洁的条件刻画复杂的现象。就像NP-completeness（NP完全性）用"多项式时间归约"刻画了计算困难性，就像VC维用"打散"刻画了学习复杂度，Uniform Exterior Separability用"外部可统一描述"刻画了纯正面学习的可学性。

这种"简洁刻画"的美，是理论计算机科学的核心魅力之一。它不是"近似正确"或"实验上有效"，而是"if and only if"——充分且必要的条件。这种精确性，是理论科学与实验科学的区别之一。

---

🎨 七、结语：当"失去一半世界"时，我们还能学到什么？

读完这篇论文，我被一种深刻的矛盾感所震撼。

一方面，纯正面学习的结果是令人沮丧的：它告诉我们，当我们只能看到"一半世界"（只有正类样本）时，学习的难度大幅增加。正确的学习需要不仅是有限VC维，还需要Uniform Exterior Separability这种额外的条件。有些概念类即使能被非正确学习，也不能被正确学习。有些概念类需要随机化算法才能学习。有些概念类甚至没有任何标准算法（如ERM）能学习。这是一个充满限制和障碍的世界。

但另一方面，这个结果也是令人鼓舞的：它告诉我们，即使在"失去一半世界"的极端情况下，学习仍然是可能的——只要满足特定的条件。Uniform Exterior Separability不是一个"不可能条件"，很多自然的概念类（如某些几何形状、某些逻辑公式类）都满足这个条件。这意味着，在现实世界中，纯正面学习不仅是理论上的可能，也是实践上的可行。

更重要的是，这篇论文揭示了学习理论本身的丰富性。标准PAC学习只是学习理论的一个"特殊案例"——一个正负样本都容易获取、分布均匀的理想化场景。当我们偏离这个理想化场景（如只有正类样本、或分布有偏、或样本有噪声），学习的"景观"会变得更加复杂和有趣。每一个偏离，都揭示出新的理论结构和新的算法需求。

费曼曾经说："如果你认为你理解了量子力学，那你就还没理解它。" 学习理论也是如此：如果你认为"VC维足够解释一切"，那你还没真正理解学习的复杂性。Uniform Exterior Separability的出现，就像在学习理论的地图上发现了新的大陆——它告诉我们，还有更多的未知等待探索。

最后，回到那个婴儿的思想实验。如果那个只见过笑脸的婴儿，有一天真的走出了房间，看到了非笑脸的世界，他会怎样？也许他会困惑，会恐惧，会重新构建他对"人脸"的理解。这个过程会很艰难，但也不是不可能——如果他的大脑有某种"Uniform Exterior Separability"的直觉，某种从"内部"推断"外部"的本能。

这篇论文告诉我们：机器可以拥有这种本能。只要我们理解它的条件，并为之设计合适的算法。

---

📚 参考文献

[1] Ben-David, S., Mansouri, F., & Mehrotra, A. (2026). *Surprises in Proper Positive-Only Learning*. arXiv preprint.

[2] Natarajan, B. K. (1987). Machine learning: a theoretical approach. *Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC)*.

[3] Vapnik, V. N., & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. *Theory of Probability and Its Applications*, 16(2), 264-280.

[4] Kearns, M. J., & Vazirani, U. V. (1994). *An Introduction to Computational Learning Theory*. MIT Press.

[5] Valiant, L. G. (1984). A theory of the learnable. *Communications of the ACM*, 27(11), 1134-1142.

[6] Blumer, A., et al. (1989). Learnability and the Vapnik-Chervonenkis dimension. *Journal of the ACM*, 36(4), 929-965.

[7] Feynman, R. P. (1965). *The Character of Physical Law*. MIT Press.

---