한국어 초록
극한에서의 식별(identification in the limit, Gold, 1967)에서 학습자는 긍정 예시를 읽으며 결국 목표 가설을 지목해야 하고, 극한에서의 생성(generation in the limit, Kleinberg and Mullainathan, 2024)에서는 결국 새로운 긍정 예시를 생성해야 한다. 본 연구는 더 약한 관계적 신호를 다룬다. 각 관측은 $h(x)\neq h(y)$를 만족하는 순서 없는 쌍 $\{x,y\}$이며, 예를 들어 cannot-link 제약이나 비유사 쌍 레이블이 이에 해당하고, 학습자는 어느 점이 긍정인지 결코 알지 못한다. 본 연구의 모든 결과는 하나의 대상에서 도출된다. 즉, 어떤 쌍이 유한 족의 모든 구성원에 대해 유효한 것은 정확히 그 쌍의 점들이 해당 족의 소속 사상(membership map)의 대척 셀(antipodal cells)에 놓일 때이다. (1) 알려져 있든 알려져 있지 않든 모든 오염 예산 $k$에 대해, 식별 가능한 클래스를 정확하게 특성화한다. 비교 불가능한 가설들은 정의역을 덮어야 하며 $2k$개보다 많은 점을 공유해야 하고, Angluin의 tell-tale 집합은 $2k$개 점의 손실에도 유지되어야 한다. 예산이 유계가 아니면 임의의 두 가설이 혼동 가능해진다. (2) 대조적 폐쇄 차원(contrastive closure dimension)이 균일 생성을 특성화한다. 유한 클래스에서는 표현(presentation)을 공유하는 족이 유한한 공통 지지집합을 가질 때 정확히 생성이 실패하며, 가산 클래스에서는 이 유한 조건만으로 더 이상 충분하지 않다. (3) 깨끗한 데이터에서는 네 가지 학습 기준이 엄격한 다이아몬드 구조를 이룬다. (4) 오염이 있으면 순서가 달라진다. 어떤 클래스는 하나의 알고리즘으로 모든 유한 예산 아래에서 대조 쌍으로부터 식별 가능하지만, 오염된 예시가 하나만 있어도 긍정 예시로부터는 식별할 수 없다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2605.06211v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.