Local Regularization Does Not Characterize Multiclass PAC Learnability

기술적 요약: 국소 정규화는 다중 클래스 PAC 학습 가능성을 특징짓지 못한다

문제 정의
통계적 학습 이론의 핵심 질문 중 하나는 가설 집합의 학습 가능성을 특징짓는 단순한 알고리즘 원칙을 식별하는 것이다. 이진 분류에서 경험적 위험 최소화(Empirical Risk Minimization, ERM)는 PAC 학습 가능성을 특징짓는다. 그러나 다중 클래스 설정은 더 복잡하다. 적절한 학습자가 존재하더라도 적절한 학습이 실패할 수 있으며, 최적의 학습자는 고정된 가설 순서보다는 샘플에 의존적인 구조에 의존하는 경우가 많다.

Asilis 등은 다중 클래스 설정에서 ERM의 일반화된 형태로서 **국소 정규화(local regularization)**를 제안했다. 국소 정규화는 모든 테스트 지점 $x$에 대해 모든 가설 $h$에 대하여 샘플과는 독립적인 고정된 점수 $\psi(h, x)$를 할당한다. 이러한 정규화자에 의해 유도된 학습자는 관측된 샘플과 일치하는 가설들 중 최소 점수를 가진 가설의 레이블을 예측한다. Jafar, Asilis, Dughmi는 이전에 특정 유보된 지점(withheld point)을 테스트하는 전이적(transductive) 모델에서 국소 정규화가 학습 가능성을 특징짓지 못함을 입증했으나, 유보된 지점이 모집단의 질량(mass)에 미미한 영향을 줄 수 있고 반복적인 샘플링이 이론적으로 이를 드러낼 수 있는 PAC 학습 모델에서도 이 원칙이 학습 가능성을 특징짓는지 여부는 미해결 과제로 남아 있었다.

방법론 및 구성
본 논문은 토너먼트(tournaments)(완전 유향 그래프)를 기반으로 하는 가산 가설 집합을 사용하여 반례를 구성한다.

• 가설 집합 ($H$): 정수 $q \ge 3$에 대하여, 가설은 $q$개의 정점을 가진 완전 그래프 $K_q$의 에지(edge)에 대응한다. 가설 $h_{q,e}$는 토너먼트 인스턴스 $\tau$ 내의 에지 $e$의 "머리(head)"(대상 정점)를 예측한다.
• 인스턴스 공간: 인스턴스는 $(q, \tau)$의 쌍으로, 여기서 $\tau$는 $q$개의 정점을 가진 토너먼트이다.
• 어려운 분포(Hard Distributions): 저자들은 타겟 에지 $e=\{u,v\}$와 종점 $v$에 대한 "어려운" 분포 군(family) $D_{e,v}$를 정의한다. 이 분포들은 에지 $e$가 $v$를 향하도록 방향이 정해진 토너먼트들에 대해 균등 분포를 따른다. 결과적으로, 관측된 훈련 샘플의 모든 레이블은 동일하게 $(q, v)$가 된다.
• 실패 메커니즘:
  1. 필터링(Filtering): 훈련 샘플(모든 레이블이 $v$임)은 버전 공간(version space)을 필터링하여, 샘플링된 토너먼트들에서 $v$를 향하도록 방향이 정해진 $v$에 인접한 에지들에 해당하는 가설들만을 남긴다.
  2. 고정된 순위(Fixed Ranking): 국소 정규화 $\psi$는 샘플이 관측되기 전에 테스트 지점에서의 인접한 에지들에 대해 엄격한 전순서(total ordering)를 부과한다.
  3. 순환적 역전(Cyclic Inversions): 핵심적인 어려움은 토너먼트의 **순환 삼각형(cyclic triangles)**에서 발생한다. 훈련 샘플이 많은 경쟁자를 제거하더라도, 남겨진 에지들에 대한 고정된 순서는 실제 타겟에 대해 "역전"될 수 있다. 구체적으로, (타겟이 아니어야 할) 나가는 에지가 필터링 과정을 통과하여 정규화자의 고정된 순위에서 실제 들어오는 타겟 에지보다 앞선 순위에 나타나면 학습자는 오류를 범한다.

주요 기여 및 결과

1. 반례의 존재성: 본 논문은 PAC 학습 가능하지만 어떤 국소 정규화로도 학습할 수 없는 가산 다중 클래스 가설 집합 $H$의 존재를 증명한다.

   • 학습 가능성: 해당 클래스는 $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$의 샘플 복잡도를 가지며 PAC 학습 가능하다. 명시적인 학습자는 샘플에서 두 종점 레이블이 모두 나타날 때까지 타겟 에지를 식별함으로써 성공한다.
   • 차원 경계: 이 클래스는 Daniely–Shalev-Shwartz (DS) 차원이 최대 2임을 보인다. 이는 모든 가설의 이미지가 최대 두 개의 레이블을 포함함을 보여줌으로써, 3차원 유사 큐브(pseudo-cube) 형성을 방 ngăn하기 때문이다.

2. 불가능성 정리: 임의의 국소 정규화 $\psi$에 대하여, $H$를 PAC 학습하는 데 실패하는 유도된 학습자 $A_\psi$가 존재한다.

   • 실패 모드: 임의의 고정된 정규화자에 대해, 저자들은 샘플 크기 $n$이 임의로 크더라도 오차 확률이 상수 $\delta_0 = \frac{1}{192e}$를 초과하는 실현 가능한(realizable) 분포들이 존재함을 보여준다.
   • 정량적 경계: 오차 확률은 0으로부터 멀리 떨어져 있다($\varepsilon_0 = \frac{1}{96e}$). 이는 토너먼트 구조 내에서 "역전"(들어오는 에지보다 앞서 순위가 매겨진 나가는 에지)의 기대 횟수가 유의미하게 유지되기 때문이다. 증명은 무작위 토너먼트가 $\Theta(q^3)$의 순환 삼각형을 포함한다는 사실을 활용하며, 이를 통해 어떤 에지 순서에 대해서도 타겟 인시던스(incidence)의 상수 비율이 예측 오류를 초래함을 보장한다.

의의 및 주장

본 논문은 국소 정규화가 다중 클래스 실현 가능한(realizable) PAC 학습 가능성을 특징짓지 못한다고 결론짓는다.

• 전이적 결과와의 차이: Jafar 등이 제시한 전이적 하한(transductive lower bound)과 달리, 이 구성은 오류를 토너먼트의 모집단 전체에 분산시킨다. 오류는 샘플 크기가 임의로 커짐에 따라 지속되며, 이는 학습자가 반복적인 샘플링을 통해 숨겨진 구조를 "학습"하는 것을 방지한다.
• 고정된 점수의 한계: 이 결과는 국소 정규화의 근본적인 경직성을 강조한다. 테스트 지점에서의 가설 순위가 샘플을 관찰하기 전에 고정되어 있기 때문에, 학습자는 훈련 데이터의 특정 구조에 기반하여 생존한 경쟁자들의 상대적 순서를 조정할 수 없다. 토너먼트 설정에서 이러한 재정렬 능력의 부재는 낮은 DS-차원과 최적의 샘플 복잡도를 가졌음에도 불구하고 상수 수준의 모집단 오류를 초래한다.
• 범위: 이 결과는 정규화 규칙이 샘플과 독립적으로 고정된 점수를 갖는 정규화자에 국한된다. 이는 정규화 규칙이 라벨이 없는 샘플에 의존할 수 있는 비지도 학습 프레임워크를 다루지 않는다.

요약하자면, 본 논문은 국소 정규화가 다중 클래스 PAC 학습 가능성을 특징짓는다는 질문에 결정적인 부정적 답변을 제공하며, 낮은 조합론적 차원(DS-dim $\le 2$)과 효율적인 학습 가능성을 가진 클래스라 할지라도 고정된 점수 정규화자는 학습에 실패할 수 있음을 입증한다.