Universal Multiclass Transductive Online Learning

기술 요약: 보편적 다중 클래스 전이적 온라인 학습 (Universal Multiclass Transductive Online Learning)

문제 정의
본 논문은 **가산 무한한 레이블 공간(countably infinite label space)**을 가진 보편적 전이적 온라인 분류(universal transductive online classification) 문제를 조사한다. 이 설정에서 학습자는 적대적 대상(adversary)과 순차적인 게임을 수행한다. 게임이 시작되기 전, 적대적 대상은 인스턴스 시퀀스 $X = \{X_t\}_{t \in \mathbb{N}}$를 선택하고 이를 학습자에게 미리 공개한다. 각 라운드 $t$에서 학습자는 알려진 인스턴스 시퀀스와 과거의 실제 레이블 $Y_{<t}$를 바탕으로 레이블 $\hat{Y}_t$를 예측한다. 그 후 적대적 대상은 실제 레이블 $Y_t$를 공개한다. 학습자의 성능은 실수 횟수(실현 가능 설정(realizable setting)의 경우) 또는 후회(regret)(무가설 설정(agnostic setting)의 경우)로 측정된다.

핵심 목표는 개념 클래스 $\mathcal{H}$의 **보편적 학습 가능성(universal learnability)**을 규명하는 것이다. 균등한 비율(uniform rates, 특정 데이터 시퀀스에 독립적인 경계를 제공함)과 달리, 보편적 학습 가능성은 모든 실현 가능한 시퀀스에 대해, 실수 횟수가 시간 지평 $T$에 따라 아선형적으로 증가하거나(또는 특정 경계를 만족하거나) 하는 알고리즘이 존재함을 요구한다. 본 논문은 주로 이진 분류나 균등한 비율에 집중해 온 기존 문헌의 공백을 메우기 위해, 이러한 개념들을 무한한 레이블을 가진 다중 클래스 설정으로 확장함으로써 이 문제를 구체적으로 다룬다.

방법론 및 핵심 개념
저자들은 조합론적 게임 이론과 개념 클래스의 구조적 분석을 사용하여 학습 가능성 조건을 도출한다.

1. 조합론적 구조:

   • 리틀스톤 트리 (Littlestone Tree): 노드는 인스턴스이고 엣지는 레이블인 표준적인 온라인 학습 구조.
   • 레벨 제약 리틀스톤 (Level-Constrained Littlestone, LCL) 트리: 모든 노드가 동일한 깊이에서 동일한 인스턴스를 공유하는 변형된 구조.
   • LCL-리틀스톤 (LCLL) 트리: 본 연구에서 도입된 새로운 구조이다. 이는 무한한 레이블을 가진 다중 클래스 설정을 위해 리틀스톤 트리를 확장한 것이다. LCLL 트리에서 깊이 $k$의 노드는 $k+1$개의 인스턴스 시퀀스와 연관되며, 엣지는 깊이 $k+1$인 LCL 트리의 경로에 대응하는 레이블 시퀀스를 나타낸다.
   • 무관성 성질 (Indifferent Property): 이진 분류 연구(Bousquet et al., 2023)에서 채택된 중요한 성질이다. 트리가 너비 우선 탐색(BFS) 순서에서 노드 $v$가 $u$보다 먼저 나타날 때, $u$의 모든 자손이 $v$의 레이블에 동의한다면 해당 트리는 "무관하다(indifferent)"고 한다. 이 성질은 학습자가 인스턴스 시퀀스를 알고 있음에도 불구하고 적대적 대상이 무작위 보행(random walk) 전략을 사용하여 실수를 강제할 수 있게 한다.

2. 게임 이론적 접근 (Gale-Stewart Games):
   저자들은 학습 가능성을 규명하기 위해 새로운 Gale-Stewart 게임을 설계한다. 적대적 대상이 인스턴스 시퀀스를 제안하는 기존의 게임과 달리, 여기서는 "레벨 제약 트리"(인스턴스 시퀀스와 가능한 레이블 시퀀스 집합)를 제안한다. 학습자(Player B)는 개념 클래스와 일치하는 경로를 선택하려고 시도한다.

   • 이 게임의 핵심적인 기술적 기여는 무관성 성질을 포착하도록 설계된 것이다. 저자들은 기존의 이진 분류 트리 확장 모델(DSL 또는 LCL 트리)이 무한한 레이블을 가진 다중 클래스 설정에서 학습 가능성을 규명하는 데 실패함을 보여준다. 이는 무한한 트리 환경에서 "무관한" 성질이 자동으로 성립하지 않기 때문이다.
   • 저자들은 **Borel 결정성 정리(Borel Determinacy Theorem)**를 활용하여, 개념 클래스에 무한한 무관한 LCLL 트리가 없다면 학습자(Player B)가 승리 전략을 가짐을 입증한다.

3. 알고리즘 설계:

   • 실현 가능 설정 (Realizable Setting): 저자들은 Gale-Stewart 게임의 진행 상황을 추적하는 알고리즘을 제안한다. 게임이 진행되면(파쇄된 부분 시퀀스가 존재함을 나타냄) 알고리즘은 상태를 업데이트한다. 게임이 정체되면, 알고리즘은 남은 부분 개념 클래스를 학습하기 위해 파쇄된 부분 시퀀스에 기반한 가중치 함수를 사용하는 가중 다수결(weighted majority) 전략으로 전환한다.
   • 무가설 설정 (Agnostic Setting): 저자들은 "전문가 학습(learning with experts)" 프레임워크를 사용하여 실현 가능 알고리즘을 확장한다. 환상(hallucinated) 시퀀스와 실수 인덱스에 대한 실현 가능 알고리즘의 동작을 기반으로 가산 집합의 전문가를 구성하고, 비균등 초기 가중치를 가진 Squint 알고리즘(Koolen & van Erven, 2015)을 사용하여 후회를 최소화한다.

주요 결과

1. 실현 가능 설정에 대한 삼분법 (Trichotomy):
   본 논문은 무한한 레이블을 가진 보편적 전이적 온라인 학습의 최적 실수율에 대한 삼분법을 확립한다:

   • 상수 실수 ($O(1)$): $\mathcal{H}$가 무한한 무관한 리틀스톤 트리를 갖지 않을 때 가능하다.
   • 로그 실수 ($\Theta(\log T)$): $\mathcal{H}$가 무한한 무관한 리틀스톤 트리를 가지지만 무한한 무관한 LCLL 트리는 갖지 않을 때 가능하다.
   • 선형 실수 ($\Omega(T)$): 만약 $\mathcal{H}$가 무한한 무관한 LCLL 트리를 가진다면, 어떤 알고리즘도 아선형 실수를 보장할 수 없다.

2. 무가설 설정 (Agnostic Setting):

   • 개념 클래스 $\mathcal{H}$가 무가설적으로 보편적 전이적 온라인 학습이 가능하다는 것은 $\mathcal{H}$가 무한한 무관한 LCLL 트리를 갖지 않음과 동치이다.
   • 이러한 클래스들에 대해, 저자들은 $\tilde{O}(\sqrt{T})$의 후회 경계(다항 로그 인자를 생략함)를 달성하는 알고리즘을 제공한다.
   • 두 개의 서로 다른 개념을 포함하는 모든 클래스에 대해 후회가 $\sqrt{T}$보다 작을 수 없다는 하한(lower bound)을 증명하였다.

3. 확률 과정 확장 (Stochastic Process Extension):
   결과는 학습자가 인스턴스 시퀀스 자체가 아니라 시퀀스를 생성하는 확률 과정을 알고 있는 설정으로 확장된다. "모든 프로세스가 보편적 온라인 학습을 허용한다"는 조건은 무한한 무관한 LCLL 트리의 부재와 동치임이 밝혀졌다.

의의 및 주장
본 논문은 온라인 학습 이론에 다음과 같은 중요한 기여를 한다고 주장한다:

• 다중 클래스 무한 사례의 해결: 이 연구는 무한한 가산 레이블 공간을 가진 다중 클래스 문제에 대한 보편적 전이적 온라인 학습의 첫 번째 완전한 규명을 제공하며, 기존의 이진 분류 중심 또는 유한 레이블 연구의 공백을 해결한다.
• 새로운 조합론적 규명: 무한한 레이블 환경의 올바른 규명으로서 LCLL 트리와 무관성 성질을 도입하였다. 저자들은 이전의 후보들(DSL 트리, LCL 트리 또는 표준 리틀스톤 트리)이 불충분함을 명시적으로 언급한다. 이는 해당 클래스가 무한한 LCLL 트리를 가짐에도 학습 가능하거나, 무한한 리틀스톤 트리를 가짐에도 하한에 필요한 무관성 성질을 결여한 반례를 통해 입증되었다.
• 새로운 게임 설계: 적대적 대상이 단순히 인스턴스를 제안하는 것이 아니라 인스턴스 구간에 대한 레이블 시퀀스를 제안하는 특정한 Gale-Stewart 게임의 설계를 강조한다. 이 설계는 무한한 설정에서 무관성 성질을 포착하기 위해 필요한 개념적 기여으로 제시된다.
• 낙관적 보편적 학습 (Optimistic Universal Learning): 본 연구는 전이적 학습 가능성을 "학습이 가능한 한 학습하는 것"(낙관적 보편적 온라인 학습)이라는 더 넓은 문제와 연결한다. 인스턴스 시퀀스를 아는 것(전이적)이나 확률 과정을 아는 것(낙관적)이 LCLL 트리 구조에 의해 정의되는 동일한 학습 가능성 조건을 따른다는 점을 명확히 한다.

저자들은 무가설 설정에 대해 겸허한 태도를 유지하며, 상한($\tilde{O}(\sqrt{T})$)과 하한($\Omega(\sqrt{T})$) 사이의 다항 로그 격차를 인정하고 이를 좁히는 것을 향후 과제로 남겨두었다. 또한 무한한 레이블을 가진 프로세스에 대한 보편적 온라인 학습의 규명 역시 미해결 과제로 식별하였다.