← 研踪 PaperTrailarXiv: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
摘要
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 with , 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 , known or unknown, we characterize exactly the identifiable classes. Incomparable hypotheses must cover the domain and share more than points, and Angluin's tell-tale sets must survive the loss of 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 with , 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 , known or unknown, we characterize exactly the identifiable classes. Incomparable hypotheses must cover the domain and share more than points, and Angluin's tell-tale sets must survive the loss of 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.
查看此版本解读 →查看此版本原文 ↗