극한에서의 대비 식별 및 생성

Contrastive Identification and Generation in the Limit

Gold (1967)의 고전적인 극한 식별 모델에서, 학습자는 긍정적인 예시들을 순차적으로 받으며, 결국 목표 가설을 복원해야 합니다. 최근 Kleinberg와 Mullainathan (2024)은 '극한에서의 생성'이라는 개념을 도입했는데, 여기서 학습자는 목표의 지지 집합의 새로운 요소를 결국 출력해야 합니다. 두 연구 모두 긍정적인 예시만 사용하거나 완전하게 레이블이 지정된 데이터에 초점을 맞춥니다. 하지만 많은 자연스러운 지도 신호는 개별 예시에 대한 레이블이 아닌, 예시들 간의 관계를 나타내는 경우가 많습니다. 본 연구는 '대비 식별 및 생성'이라는 새로운 연구 분야를 개척하며, 학습자가 대비되는 데이터 표현을 관찰합니다. 즉, 학습자는 정답 가설 $h$에 대해 $h(x) e h(y)$를 만족하는 정렬되지 않은 쌍 {x, y}의 스트림을 받지만, 어떤 요소가 긍정적인지는 숨겨져 있습니다. 먼저, 노이즈가 없는 환경에서 세 가지 결과를 제시합니다. 첫째, 대비 식별 가능한 클래스의 정확한 특성(Angluin (1980)의 지표 조건에 대한 간단한 기하학적 개선), 둘째, '대비 폐쇄 차원'이라는 조합론적 차원(Raman et al. (2025)의 폐쇄 차원에 대한 대비 분석), 셋째, 엄격한 샘플 복잡도를 갖는 균일한 대비 생성의 정확한 특성, 그리고 넷째, 대비 생성과 텍스트 식별이 서로 비교 불가능한 엄격한 계층 구조를 제시합니다. 다음으로, 유한한 적대적 손상에 대한 중요한 결과를 증명합니다. 즉, 어떤 유한한 손상 예산 내에서도 단일 알고리즘으로 대비 쌍으로부터 식별 가능한 클래스가 존재하지만, 심지어 하나의 손상된 관찰이 있는 경우에도 긍정적인 예시로부터는 식별 불가능한 클래스가 존재합니다. 이러한 연구의 핵심 기술적 도구는 '공통 교차 그래프'이며, 이는 쌍별 모호성, 집합 수준의 생성 제약, 그리고 손상 결함을 하나의 커버리지-인시던스 언어로 표현합니다.

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.