Contrastive Identification and Generation in the Limit
Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
原文摘要
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\}$ with $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 $k$, known or unknown, we characterize exactly the identifiable classes. Incomparable hypotheses must cover the domain and share more than $2k$ points, and Angluin's tell-tale sets must survive the loss of $2k$ 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.
cs.LG · cs.AI · cs.CL · cs.DS