다중 클래스 선형 분류기의 효율적이고 노이즈에 강한 PAC 학습

선형 모델의 노이즈 내성 PAC (Probably Approximately Correct) 학습은 지난 세기부터 머신러닝 (Machine Learning) 커뮤니티의 핵심 관심사였습니다. 최근 몇 년 동안, 다양한 노이즈 모델 하에서 선형 임계 함수 (Linear Threshold Functions)를 학습하는 문제에 대해 많은 계산 효율적인 알고리즘들이 제안되었습니다. 그러나 문제를 다중 클래스 (Multiclass) 학습 설정, 즉 클래스의 수 $k$가 최소 $3$ 이상인 경우로 고려할 때, 데이터 세트가 악의적으로 오염되었을 때 계산 효율적인 PAC 학습 알고리즘이 존재하는지는 알려져 있지 않습니다. 본 논문에서 우리는 주변 분포 (Marginal Distribution)가 유계 분산 (Bounded Variance) 분포들의 혼합이며, 데이터 세트가 마진 조건 (Margin Condition)을 동시에 만족한다고 가정합니다. 우리는 악의적인 노이즈 (Nasty Noise)의 비율이 일정하더라도, 최대 $O(k^2 imes (d ext{log } d + ext{log } k))$개의 샘플을 사용하여 다중 클래스 선형 분류기 (Multiclass Linear Classifiers) extstyle ext{{}h_w:x \mapsto \arg\max_{y ext{in } [k]}w_y ext{⋅} x, x ext{in } ext{\mathbb{R}}^d, w ext{in } ext{\mathbb{R}}^{kd} ext{}}를 PAC 학습하는 계산 효율적인 알고리즘이 존재함을 보여줍니다. 우리의 알고리즘은 두 가지 주요 요소, 즉 클러스터 기반 프루닝 (Cluster-based Pruning) 기법과 표준 다중 클래스 힌지 손실 (Multiclass Hinge Loss) 최소화 프로그램으로 구성됩니다. 이진 설정 (Binary Setting), 즉 $k=2$인 특수한 경우에서도 우리의 결과는 이전의 모든 연구들보다 엄격하게 더 강력합니다.