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

요약

본 논문은 다중 클래스 선형 분류기를 악의적인 노이즈가 존재하는 환경에서도 효율적으로 학습할 수 있는 PAC 학습 알고리즘을 제안합니다. 주변 분포가 유계 분산 분포의 혼합이며 마진 조건을 만족한다는 가정하에, 클러스터 기반 프루닝과 다중 클래스 힌지 손실 최소화 기법을 사용하여 계산 효율성을 확보했습니다.

핵심 포인트

• 클래스 수가 3개 이상인 다중 클래스 설정에서 악의적 노이즈에 강한 PAC 학습 알고리즘의 존재를 증명함
• 최대 $O(k^2 \times (d \text{log } d + \text{log } k))$개의 샘플을 사용하는 계산 효율적인 학습 방식 제안
• 클러스터 기반 프루닝(Cluster-based Pruning)과 다중 클래스 힌지 손실(Multiclass Hinge Loss) 최소화 결합
• 이진 분류($k=2$) 설정에서도 기존 연구보다 더 강력한 성능과 이론적 근거를 제공함