기술 요약: 다중 정답 학습 – 서로 다른 피드백 모델 하에서의 후회 경계 (Regret Bounds)

1. 문제 정의 및 동기

본 연구는 단일 입력 인스턴스 $x$에 대해 단 하나의 타겟 라벨이 아닌, 유효한 라벨의 집합 $S \subseteq \mathcal{Y}$가 허용되는 다중 정답을 가진 온라인 학습(online learning with multiple correct answers) 문제를 다룹다. 이러한 정식화는 언어 생성(프롬프트에 대해 여러 개의 수용 가능한 완성이 존재하는 경우), 개방형 질의응답, 대화 생성, 추천 시스템과 같은 현대적 작업들에 의해 동기 부여된다.

본 연구는 $t \in [T]$ 라운드로 진행되는 온라인 학습 패러다임에 초점을 맞춘다. 각 라운드에서 적대적 대상(adversary)은 인스턴스 $x_t$와 허용 가능한 라벨의 집합 $S_t$를 제시한다. 학습자는 라벨 $\hat{y}_t$를 예측하며, 만약 $\hat{y}_t \notin S_t$라면 1의 손실을 입는다. 본 논문은 세 가지 구별되는 피드백 모델 하에서 이 문제를 분석한다:

1. Mistake-unknown (실수 미인지): 학습자는 단 하나의 유효한 라벨 $y_t \in S_t$만을 전달받지만(적대적 대상에 의해 선택됨), 자신의 예측이 맞았는지 여부는 알지 못한다.
2. Mistake-known (실수 인지): 학습자는 단 하나의 유효한 라벨 $y_t \in S_t$와 더불어, 자신의 예측 $\hat{y}_t$가 실수였는지 여부를 알려주는 이진 지표를 전달받는다.
3. Set-valued (집합 값 제공): 학습자에게 유효한 라벨 전체 집합 $S_t$가 공개된다.

분석은 실현 가능 설정(realizable setting)(모든 $t$에 대해 $h^*(x_t) = S_t$를 만족하는 가설 $h^* \in \mathcal{H}$가 존재하는 경우)과 애그노스틱 설정(agnostic setting)(학습자가 누적 손실을 최소화하는 $\mathcal{H}$ 내 최적의 가설과 경쟁하는 경우)을 모두 다룬다.

2. 방법론 및 조합론적 특성 규명

저자들은 각 피드백 모델에서 사용 가능한 정보에 맞춰 조정된 트리 섀터링(tree-shattering) 논증을 통해, 다중 라벨 가설 클래스 $\mathcal{H}$의 학습 가능성을 특성화하는 새로운 조합론적 차원들을 도입한다.

조합론적 차원

• Set-Valued Littlestone Dimension ($LD_{set}$): 노드가 $\mathcal{Y}$의 부분집합으로 라벨링된 집합 값 트리(set-valued tree) 상에서 정의된다. 트리가 섀터링(shattered)되었다는 것은, 모든 예측 경로에 대해, 공개된 집합 $S_t$와 일치하면서도 예측된 라벨에 대해 실수를 범하는 가설이 존재함을 의미한다.
• Mistake-Known Littlestone Dimension ($LD_{known}$): 노드가 단일 라벨로 라벨링된 다중 라벨 트리 상에서 정의된다. 섀터링을 위해서는 공개된 단일 라벨 $y_t$와 일치하면서 동시에 예측에 대한 실수 비트(mistake bit)를 충족해야 한다.
• Mistake-Unknown Littlestone Dimension ($LD_{unknown}$): "실수 오프셋(mistake offset)" 함수를 사용하여 정의된다. 트리가 $d$-섀터링되었다는 것은, 어떤 경로를 따르더라도 누적된 실수의 수와 가설에 대한 오프셋의 합이 $d$를 초과함을 의미한다. 이는 즉각적인 정답 여부에 대한 피드백의 부재를 반영한다.

알고리즘

실현 가능 설정을 위해, 저자들은 각 피드백 모델에 대한 **표준 최적 알고리즘(Standard Optimal Algorithms, SOA)**을 제안한다. 이 알고리즘들은 일관된 가설들의 버전 공간(version space)을 유지하며, 남은 버전 공간의 최악의 차원을 최소화하는 예측을 수행한다.

• Mistake-Unknown을 위한 SOA: 버전 공간과 오프셋 함수를 유지하며, 결과적인 하위 클래스의 최대 $LD_{unknown}$을 최소화하는 라벨을 예측한다.
• Mistake-Known을 위한 SOA: 잠재적인 실수 비트에 의해 형성되는 하위 클래스들의 최대 $LD_{known}$을 최소화하도록 예측한다.
• Set-Valued를 위한 SOA: 공개된 $S_t$에 의해 형성되는 하위 클래스들의 최대 $LD_{set}$을 최소화하도록 예측한다.

3. 주요 결과

실현 가능한 온라인 학습 (Realizable Online Learning)

본 논문은 임의의 다중 라벨 클래스 $\mathcal{H}$에 대해 실현 가능한 설정에서의 최적 실수 경계(optimal mistake bound)를 완전히 규명한다:

• Mistake-unknown: 최적 실수 경계는 $\min(LD_{unknown}(\mathcal{H}), T)$이다.
• Mistake-known: 최적 실수 경계는 $\min(LD_{known}(\mathcal{H}), T)$이다.
• Set-valued: 최적 실수 경계는 $\min(LD_{set}(\mathcal{H}), T)$이다.

이 결과들은 유한 클래스에 대한 기존 연구를 임의의 (가능한 무한한) 가설 클래스로 일반화한다. 저자들은 $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$임을 증명하며, 이는 모든 인스턴스에 대해 모든 가설의 라벨 집합의 교집합이 비어있지 않을 때 성립한다.

애그노스틱 온라인 학습 (Agnostic Online Learning - 후회 경계)

본 논문의 중요한 기여는 애그노스틱 설정에서 피드백 모델에 따라 후회율(regret rates)이 극적으로 달라짐을 보여준 것이다. 이는 단일 라벨 학습에서 후개가 일반적으로 $\tilde{\Theta}(\sqrt{T})$인 것과 대조적이다.

1. Mistake-Unknown: 저자들은 $LD_{unknown}=1$인 단순한 가설 클래스에 대해서도 후개가 $T$에 대해 선형적($\Omega(T)$)으로 성장할 수 있음을 보여준다. 이는 $LD_{unknown}$으로 특징지어지는 실현 가능한 학습 가능성이 이 피드백 모델의 애그노스틱 설정에서는 하선형(sublinear) 후개를 보장하지 못함을 시사한다.
2. Mistake-Known: 본 논문은 SOA 기반의 전문가 집합을 활용하여 문제를 전문가 조언이 있는 비확률적 밴딧(non-stochastic bandits) 문제로 환원함으로써, O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T}}의 하선형 후개 상한을 확립한다.
3. Set-Valued:
   • 특정 클래스(예: 예시 클래스 $H_3$)의 경우, 후개는 상수($O(1)$)이다.
   • 일반적인 클래스의 경우, 후개는 $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$로 제한된다. 주목할 점은 이 상한이 라벨 공간의 크기 $|\mathcal{Y}|$와 독립적이어서, 무한한 라벨 공간에서도 성립할 수 있다는 것이다.

배치 학습 함의 (Batch Learning Implications)

도출된 조합론적 차원과 온라인 경계는 대응하는 배치 학습 문제의 샘플 복잡도 경계를 함의한다. 저자들은 전체 집합 피드백 모델에 대한 최초의 배치 학습 상한을 제공하며, 단일 정답 케이스에 대한 기존의 유한 클래스 상한을 무한 클래스로 개선한다.

4. 의의 및 주장

본 논문은 세 가지 피드백 모델 하에서 실현 가능한 온라인 다중 라벨 학습에 대한 최초의 완전한 조합론적 특성화를 제공한다고 주장한다. 본 연구의 주요 이론적 의의는 $LD_{unknown}$이 의미 있는 후개 경계를 포착하지 못하는 Mistake-unknown 설정에서 실현 가능성과 애그노스틱 학습 가능성 사이의 분리를 보여준 데 있다.

나아가, 본 연구는 애그노스틱 다중 라벨 학습의 풍부한 구조를 강조한다:

• 피드백 모델은 달성 가능한 후개율을 근본적으로 변화시킨다 (선형에서 상수로).
• Set-valued 피드백 모델은 특정 클래스에 대해 상수 후개를, 일반적인 클래스에 대해 차원에 독립적인 상한을 허용하며, 이는 단일 라벨 학습에서는 관찰되지 않는 현상이다.
• 결과적으로, 애그노스틱 다중 라벨 학습을 특성화하기 위해서는 실현 가능한 학습 가능성에 충분한 것 이상의 조합론적 객체가 필요함을 시사한다.

저자들은 자신들의 후개 정의가 실제적인 예측 작업(단순히 드러난 특정 라벨을 포함하는 가설과 경쟁하는 것이 아니라, 수용 가능한 실제 집합에 대한 오류를 최소화하는 것)과 더 잘 일치하도록 기존 연구들(예: Joshi et al. [JLB+25], Raman et al. [RST24])과 다르다는 점을 명시적으로 밝히고 있다.