Contrastive Identification and Generation in the Limit

Gold [1967] 의 고전적인 'limit model(한계 모델)'에서 식별 (identification) 은 순차적으로 제시된 양의 예시 (positive examples) 를 통해 학습자가 결국 목표 가설 (target hypothesis) 을 복원해야 하는 과정입니다. 최근 Kleinberg 와 Mullainathan [2024] 는 학습자가 결국 목표 집합의 지지집합 (support) 의 새로운 요소를 출력해야 하는 'generation in the limit(한계 생성)'을 도입했습니다. 두 연구 모두 양식만 있는 데이터 (positive-only data) 또는 완전 라벨링된 데이터를 기반으로 합니다. 그러나 많은 자연스러운 감독 신호는 단일 항목이 아니라 예시 간의 관계 (relational relationships) 를 인코딩하는 것이므로, 개별 항목의 라벨이 아닙니다. 우리는 학습자가 데이터의 대조적 제시 (contrastive presentation) 를 관찰하는 한계 식별과 생성 (contrastive identification and generation in the limit) 을 연구합니다: 학습자는 알 수 없는 목표 이진 가설 $h$ 에 대해 $h(x)\ne h(y)$ 를 만족하는 무서제 쌍 $\{x,y\}$ 의 흐름을 관찰하지만, 어떤 요소가 양 (+) 인지는 학습자에게 숨겨져 있습니다. 우리는 잡음 없는 환경 (noiseless setting) 에서 세 가지 결과를 제시합니다: Angluin [1980] 의 'tell-tale condition(구별 조건)'의 한 줄 기하학적 정밀화 (one-line geometric refinement) 를 포함한 대조적 식별 가능 클래스 (contrastive identifiable classes) 의 정확한 특성화, Raman et al. [2025] 의 closure dimension(폐쇄 차원) 의 대조적 유사체인 '대조적 폐쇄 차원' (contrastive closure dimension) 을 포함한 조합론적 차원, 그리고 엄밀한 샘플 복잡도 (tight sample complexity) 와 함께 균일 대조적 생성 (uniform contrastive generation) 의 정확한 특성화, 그리고 대조적 생성과 텍스트 식별이 서로 비교할 수 없는 엄격한 계층 구조 (strict hierarchy). 우리는 유한 적대적 교란 (finite adversarial corruption) 하에서 날카로운 반전 (sharp reversal) 을 증명합니다: 단일 예산 독립 알고리즘 (single budget-independent algorithm) 으로 임의의 유한 교란 예산 (corruption budget) 에서 대조적 쌍으로 식별 가능한 클래스가 존재하지만, 하나의 교란된 관찰 (corrupted observation) 이 있어도 양식 예시로는 식별 불가능합니다. 통합적인 기술적 객체는 공통 교차 그래프 (common crossing graph) 입니다: 이는 쌍의 모호성 (pairwise ambiguity), 가족 수준의 생성 장애물 (family-level generation obstructions), 그리고 교란 결함 (corruption defects) 을 단일 커버리지 및 발생 언어로 인코딩합니다.