arXiv:2605.06211cs.LGcs.AI2026-05被引 3

提出对比学习下的识别与生成新范式,突破传统标签学习限制。

Contrastive Identification and Generation in the Limit

  • 通过无序对比对学习未知二元假设,隐藏正负标签信息
  • 首次证明对比可识别类的几何特征与生成样本复杂度下界
  • 揭示对比学习在对抗污染下更鲁棒,适合高噪声场景

在经典的识别于极限模型中,学习者逐轮接收正例并最终恢复目标假设。近期工作引入生成于极限,要求学习者输出目标支持集中的新元素。两者均基于单一标签或全标注数据,但许多自然监督信号是关系型而非单例标签。本文首次研究对比识别与生成于极限:学习者观察无序对 {x,y} 的流,满足 h(x)≠h(y),但不知哪个为正。在无噪声情况下,我们给出对比可识别类的精确刻画(对Angluin[1980]的条件进行几何简化)、定义对比闭包维数(对应于Raman等[2025]的闭包维数),并精确刻画统一对比生成的样本复杂度;发现对比生成与识别存在严格不可比性。在有限对抗污染下,存在一类可通过任意有限污染预算被单一不依赖预算的算法识别,却在仅一个观测污染时无法从正例中识别。核心工具是公共交叉图,以统一覆盖-关联语言编码成对模糊、族级生成障碍与污染缺陷。

原文摘要 · Abstract (English)

In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [2024] introduced generation in the limit, where the learner instead must eventually output novel elements of the target's support. Both lines of work focus on positive-only or fully labeled data. Yet many natural supervision signals are inherently relational rather than singleton, which encode relationships between examples rather than labels of individual ones. We initiate the study of contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data: a stream of unordered pairs $\{x,y\}$ satisfying $h(x)\ne h(y)$ for an unknown target binary hypothesis $h$, but which element is positive is hidden from the learner. We first present three results in the noiseless setting: an exact characterization of contrastive identifiable classes (a one-line geometric refinement of Angluin [1980]'s tell-tale condition), a combinatorial dimension called contrastive closure dimension (a contrasitive analogue of the closure dimension in Raman et al. [2025]) and exactly characterizing uniform contrastive generation with tight sample complexity, and a strict hierarchy in which contrastive generation and text identification are mutually incomparable. We then prove a sharp reversal under finite adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget by a single budget-independent algorithm, yet not identifiable from positive examples under even one corrupted observation. The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.

机器学习形式理论对比学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。