这篇论文搞清楚了只给正样本时proper学习到底能学啥，发现了VC维不够用，还新造了个叫“均匀外部可分离性”的条件，搞理论的人值得看。
揭示了仅从正样本进行二分类的proper可学习性的完整刻画：一个概念类可proper学习当且仅当其VC维有限且满足新引入的组合条件“均匀外部可分离性”。该研究证明proper与improper学习在此设定下可分离，随机与确定性proper学习间也存在分离。存在概念类无ERM可作为学习器，且有限VC维对非一致学习不足。这些结果通过新组合维度得到，丰富了学习理论。
Surprises in Proper Positive-Only Learning
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.