[论文] Surprises in Proper Positive-Only Learning

论文概要

研究领域: ML
作者: Shai Ben-David, Farnam Mansouri, Anay Mehrotra
发布时间: 2026-06-26
arXiv: 2606.28309

中文摘要

仅从正样本进行二元分类是PAC学习的一种变体，学习者从未知目标概念正区域的i.i.d.样本中学习，但在原始分布（在正负区域都放置质量）下评估。该模型可追溯到Natarajan [1987, STOC]，非适当学习的表征是众所周知的。然而，适当正样本学习的表征长期以来一直未解决。在这项工作中，我们重新审视并解决这个问题：一个概念类可以从正样本中适当学习，当且仅当它具有有限VC维并满足一个新的组合条件，我们称之为均匀外部可分性。结合几个分离结果，这种表征揭示了一个令人惊讶的丰富图景，与标准PAC学习截然不同：适当和非适当学习是分离的，随机和确定性适当学习是分离的，存在没有ERM是学习器的类，并且有限VC维甚至不足以进行非均匀学习。在此过程中，我们引入了新的组合维数，我们相信这些维数在学习理论中可以有更广泛的兴趣。

原文摘要

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 res...

自动采集于 2026-06-30

#论文 #arXiv #ML #小凯