破解正样本学习的理论边界，发现新判据与多重分离现象
Surprises in Proper Positive-Only Learning
- 提出统一外部可分性条件，刻画正样本学习的可学性
- 证明有限VC维不足以保证可学，随机与确定学习也不同
- 揭示正样本学习中存在无经验风险最小化的类，适合理论研究者
从仅含正样本的数据中进行二分类是PAC学习的一个变体，其中学习器仅接收来自未知目标概念正区域的独立同分布样本，但需在原始分布（包含正负样本）下评估。该模型始于Natarajan [1987, STOC]，非适当学习的表征已广为人知，但适当学习的表征长期未解。本文重新审视并解决此问题：一个概念类可在正样本下适当学习当且仅当其具有有限VC维且满足一种新组合条件——统一外部可分性。结合多个分离结果，该表征揭示了一个出人意料丰富的学习图景：适当与非适当学习相分离，随机与确定性适当学习相分离，存在无经验风险最小化学习器的概念类，即使非均匀学习也需额外条件。过程中引入了新的组合维度，或对学习理论有更广泛意义。
原文摘要 · Abstract (English)
Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dates back to Natarajan [1987, STOC], and the characterization of improper learning is well-known -- it even appears in textbooks. The characterization of proper positive-only learning, however, has long remained open. In this work, we revisit and settle this question: a concept class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition, which we call uniform exterior separability. Together with several separation results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。