Realizable Bayes-Consistency for General Metric Losses

기술적 요약: 일반 거리 손실에 대한 실현 가능한 베이지안 일관성

1. 문제 제기

본 논문은 일반 거리 손실을 다루는 학습에서 실현 가능한 설정 하의 강한 보편적 베이지안 일관성 문제를 다룹니다. 이 설정은 다음을 포함합니다:

• 인스턴스 공간 $(X, \rho)$과 레이블 공간 $(Y, \ell)$로, 여기서 $\ell$은 유계일 필요가 없는 거리입니다.
• 가설 클래스 $\mathcal{H} \subseteq Y^X$.
• $\mathcal{H}$에 의해 실현 가능한 $X \times Y$ 위의 데이터 생성 분포 $\bar{\mu}$로, 이는 최적 리스크가 0임을 의미합니다 ($\inf_{h \in \mathcal{H}} R_{\bar{\mu}}(h) = 0$).

목표는 모든 실현 가능한 분포 $\bar{\mu}$에 대해 리스크가 거의 확실하게 0으로 수렴하는 분포 무관 학습 규칙이 존재하도록 하는 $\mathcal{H}$에 대한 필요충분조건을 결정하는 것입니다.

저자들은 유계 손실과 무계 손실 사이의 중요한 차이를 강조합니다. 유계 설정에서는 오류 확률을 제어하는 것이 리스크를 제어하는 것과 동의어입니다. 반면, 무계 거리 설정에서는 학습자가 소멸하는 확률의 사건에서 실수를 할 수 있지만, 이러한 오류의 크기가 너무 빠르게 증가하여 기대 리스크가 무한대로 남거나 0 으로 수렴하지 않을 수 있습니다. 본 논문은 이러한 "재앙적인 희귀 사건 실패"가 언제 회피 가능한지 규명하고자 합니다.

2. 방법론 및 이론적 프레임워크

본 논문은 0-1 분류 및 유계 회귀를 위해 이전에 개발된 프레임워크를 확장한 무한 게임 이론과 트리 장애물에 기반한 조합론적 접근법을 사용합니다.

주요 정의:

• 무한 비감소 $(\gamma_k)$-리틀스톤 트리: 내부 노드가 깊이 $k$에서 인스턴스 $x_{k,i}$이고, 나가는 간선이 $y_{k,i,1}, y_{k,i,2} \in Y$로 레이블링되어 거리 $\ell(y_{k,i,1}, y_{k,i,2}) \ge \gamma_k$를 만족하는 완전 이진 트리입니다. 여기서 수열 $(\gamma_k)$는 비감소하며 무한대로 발산합니다 ($\gamma_k \to \infty$). 모든 유한한 루트에서 잎까지의 경로가 어떤 가설 $\mathcal{H}$와 일치할 때 트리는 "실현 가능"합니다.
• 실현 가능성 가정: 저자들은 "컴팩트 매개변수화" 조건 (Lemma 4.3) 을 가정합니다: $\mathcal{H}$는 연속 평가 맵을 가진 컴팩트 공간 $\Theta$로 매개변수화됩니다. 이 온화한 가정 하에서, 유한 접두사 실현 가능성은 모든 무한 경로가 단일 가설에 의해 실현됨을 의미합니다.

증명 구조:
주요 결과는 하한 (필요성) 과 상한 (충분성) 을 통해 확립됩니다.

• 하한 (불가능성): $\mathcal{H}$가 무한 비감소 $(\gamma_k)$-리틀스톤 트리를 포함하는 경우, 저자들은 적대자가 빠르게 감소하는 확률 질량 뒤에 점점 더 분리된 레이블 선택을 숨기는 실현 가능한 분포를 구성합니다. Borel-Cantelli 논증을 사용하여, 모든 학습 알고리즘에 대해 모든 샘플 크기 $n$에 대해 기대 리스크가 무한대임을 보입니다. 학습자는 보지 못한 노드에서 $\gamma_k$만큼 분리된 레이블 사이에서 추측을 강요받게 되어 발산하는 리스크를 초래합니다.
• 상한 (구성적 알고리즘): 그러한 트리가 존재하지 않는다면, 저자들은 분포 무관 학습 규칙을 구성합니다. 증명은 네 단계로 진행됩니다:
  1. 게임 이론적 인코딩: 트리 장애물의 부재는 학습자가 특정 무한 Gale-Stewart 게임에서 적대자에 대해 승리 전략을 가짐을 의미합니다.
  2. 안정화: i.i.d. 샘플에서 이 게임을 시뮬레이션함으로써, 과정은 유한한 라운드 후 거의 확실하게 안정화됩니다. 이는 각 $x$에 대해 유계 지름을 가진 "허용 가능한" 레이블 집합 $H_K(x)$를 생성합니다.
  3. 분할: 인스턴스 공간 $X$는 $Y$의 조밀한 부분집합을 기반으로 가산 개의 셀로 분할됩니다. 각 셀 내에서 허용 가능한 레이블 집합은 유계 지름을 가집니다.
  4. 축소: 문제는 유계 손실을 가진 가산 개의 하위 문제로 축소됩니다. 저자들은 유계 거리 손실에 대해 강한 보편적 베이지안 일관성을 갖는 기존 MedNet 알고리즘 (Tsir Cohen & Kontorovich, 2022) 을 각 셀에 적용하고 결과를 집계합니다.

3. 주요 기여

1. 정밀한 규명: 본 논문은 일반 (유계일 필요 없는) 거리 손실 하의 실현 가능한 강한 보편적 베이지안 일관성에 대한 필요충분조건을 제공합니다. 이 조건은 가설 클래스 내 무한 비감소 $(\gamma_k)$-리틀스톤 트리의 부재입니다.
2. 미해결 문제의 해결: 이 작업은 Tsir Cohen & Kontorovich (2022) 가 제기한 미해결 문제의 실현 가능 사례를 해결합니다. 이는 베이지안 리스크의 유한성 ($R^* < \infty$) 이나 레이블 공간의 "기대값 내 유계" (BIE) 조건과 같은 자연스러운 유한성 유형의 조건들이 무계 설정에서 일관성을 보장하기에 불충분함을 보여줍니다.
3. 구성적 학습 규칙: 트리 장애물이 없는 경우, 본 논문은 MedNet 알고리즘과 게임 이론적 안정화에 기반한 명시적 학습 규칙을 제시하여 강한 보편적 베이지안 일관성을 달성합니다.
4. 반례 구성: 저자들은 구체적인 반례 (3 절) 를 제공하여, $R^* < \infty$일지라도 가설 클래스가 특정 무계 간격 트리 구조를 허용한다면 분포 무관 일관 학습자가 존재하지 않음을 보여줍니다.

4. 결과 및 의의

중심 정리 (Theorem 4.5) 는 온화한 측정 가능성 및 컴팩트성 조건을 만족하는 폴란드 공간 $(X, \rho)$와 $(Y, \ell)$ 및 가설 클래스 $\mathcal{H}$에 대해 다음이 동치임을 명시합니다:

1. 모든 실현 가능한 분포에 대해 강한 보편적 베이지안 일관성을 갖는 분포 무관 학습 규칙이 존재한다.
2. $\mathcal{H}$는 $\gamma_k \to \infty$인 무한 비감소 $(\gamma_k)$-리틀스톤 트리를 포함하지 않는다.

의의:
본 논문은 무계 거리 손실로 학습하는 어려움이 단순히 분포의 적분 가능성이나 모멘트 조건의 문제가 아님을 명확히 합니다. 대신, 장애물은 조합론적이며 가설 클래스에 내재적입니다. 모호성의 규모 (레이블 간의 간격) 는 트리의 깊이를 따라 무한히 커질 수 있어, 희귀 사건이 리스크를 지배하는 상황을 만듭니다. 이는 0-1 손실에 사용된 고전적 리틀스톤 트리 프레임워크와 유계 회귀에 사용된 스케일된 리틀스톤 트리를 일반 무계 거리 설정으로 확장하여, 무계 손실의 크기와 실현 가능성 사이의 정밀한 상호작용을 규명합니다.

저자들은 이 규명을 불완전 설정(분포가 반드시 실현 가능하지 않은 경우) 으로 확장하는 것은 부록에서 논의된 장애물 때문에 여전히 열린 방향이라고 언급합니다.