跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2605.06211 · v2

Contrastive Identification and Generation in the Limit

首次提交 2026-05-07 21:14
版本更新 2026-11-16 23:36
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

In identification in the limit (Gold, 1967), a learner reads positive examples and must eventually name the target hypothesis; in generation in the limit (Kleinberg and Mullainathan, 2024), it must eventually produce new positive examples. We study a weaker, relational signal: each observation is an unordered pair {x,y}\{x,y\} with h(x)≠h(y)h(x)\neq h(y), such as a cannot-link constraint or a dissimilar-pair label, and the learner never learns which point is positive. All our results come from one object: a pair is valid for every member of a finite family exactly when its points lie in antipodal cells of the family's membership map. (1) For every corruption budget kk, known or unknown, we characterize exactly the identifiable classes. Incomparable hypotheses must cover the domain and share more than 2k2k points, and Angluin's tell-tale sets must survive the loss of 2k2k points. Every unbounded budget makes any two hypotheses confusable. (2) A contrastive closure dimension characterizes uniform generation. On finite classes, generation fails exactly when a family that shares a presentation has a finite common support; on countable classes this finite condition no longer suffices. (3) On clean data the four learning criteria form a strict diamond. (4) Under corruption the order changes: some classes are identifiable from contrastive pairs under every finite budget by one algorithm, but not from positive examples with one corrupted example.

作者备注:Extended version of a NeurIPS 2026 paper. 42 pages, 9 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-16 23:36 · 最新观测版本

Contrastive Identification and Generation in the Limit

In identification in the limit (Gold, 1967), a learner reads positive examples and must eventually name the target hypothesis; in generation in the limit (Kleinberg and Mullainathan, 2024), it must eventually produce new positive examples. We study a weaker, relational signal: each observation is an unordered pair {x,y}\{x,y\} with h(x)≠h(y)h(x)\neq h(y), such as a cannot-link constraint or a dissimilar-pair label, and the learner never learns which point is positive. All our results come from one object: a pair is valid for every member of a finite family exactly when its points lie in antipodal cells of the family's membership map. (1) For every corruption budget kk, known or unknown, we characterize exactly the identifiable classes. Incomparable hypotheses must cover the domain and share more than 2k2k points, and Angluin's tell-tale sets must survive the loss of 2k2k points. Every unbounded budget makes any two hypotheses confusable. (2) A contrastive closure dimension characterizes uniform generation. On finite classes, generation fails exactly when a family that shares a presentation has a finite common support; on countable classes this finite condition no longer suffices. (3) On clean data the four learning criteria form a strict diamond. (4) Under corruption the order changes: some classes are identifiable from contrastive pairs under every finite budget by one algorithm, but not from positive examples with one corrupted example.

查看此版本解读 →查看此版本原文 ↗