Learning with Monotone Adversarial Corruptions

기술 요약: 단조적 적대적 부패(Monotone Adversarial Corruptions) 하에서의 학습

문제 정의
본 논문은 표준 머신러닝 알고리즘이 데이터의 독립성(independence) 및 교환 가능성(exchangeability) 가정에 어느 정도까지 의존하는지를 조사한다. 저자들은 이러한 가정들이 일반화(generalization)에서 수행하는 역할을 격리하기 위해 **단조적 적대적 부패 모델(monotone adversarial corruption model)**을 도입한다. 이 모델에서 적대자는 $n$개의 깨끗한 i.i.d. 샘플(분포 $D$로부터 추출됨)과 타겟 가설 $h^\star$를 관찰한다. 그 후 적대자는 데이터셋에 $m$개의 추가적인 "부패된(corrupted)" 점들을 삽입한다. 결정적으로, 이 부패된 점들은 **단조적(monotone)**이다. 즉, 이들의 레이블은 실제 정답 함수 $h^\star$에 따라 결정된다. 레이블 자체는 정직하지만, 적대자는 $D$, 가설 클래스 $\mathcal{H}$, 그리고 $h^\star$에 대한 완전한 지식을 가지고 있으며, 깨끗한 샘플들에 기반하여 적응적으로(adaptively) 부패된 점들을 선택할 수 있다. 학습 알고리즘은 $n+m$개의 점이 결합된 데이터셋(무작위로 섞임)을 전달받으며, $D$로부터 추출된 새로운 테스트 포인트에 대해 낮은 오차를 갖는 가설을 출력해야 한다.

핵심적인 긴장 관계는 추가된 데이터가 "깨끗하다"(정확하게 레이블링됨)는 점에도 불구하고, 부패된 점들의 적응적 선택이 데이터셋의 교환 가능성을 위반한다는 데 있다. 본 논문은 일반적으로 i.i.d. 데이터를 가정하는 표준 최적 학습 알고리즘들이 이 설정에서도 보장(guarantees)을 유지할 수 있는지 묻는다.

방법론 및 프레임워크
저자들은 깨끗한 점들의 함수로서 부패된 점들을 생성하는 단조적 적대자(Monotone Adversary)(정의 2.1)를 정식화한다. 또한, 부패된 점들이 깨끗한 샘플과는 독립적이지만 여전히 $D$와 $h^\star$에 대한 지식을 가진 무관심적 단조적 적대자(Oblivious Monotone Adversary)(정의 2.2)를 정의한다.

본 연구는 VC 차원이 $d$인 이진 분류 가설 클래스 $\mathcal{H}$에 초점을 맞춘다. 저자들은 세 가지 주요 학습 알고리즘 클래스를 분석한다:

1. 경험적 위험 최소화(Empirical Risk Minimizers, ERM): 훈련 데이터와 일치하는 가설을 출력하는 알고리즘.
2. 다수결 투표 알고리즘(Majority Voting Algorithms): 데이터의 부분 집합에 대해 ERM을 학습시키고 다수결 투표를 통해 예측을 집계하는 알고리즘 (예: 배깅(Bagging), Majority-of-Three, Hanneke의 알고리즘).
3. 원-인클루전 그래프(One-Inclusion Graph, OIG) 알고리즘: 표준 i.i.d. 설정에서 최적의 오차율을 달성하기 위해 원-인클루전 그래프의 구조적 특성(특히 최대 외차수(out-degree)를 최소화하는 것)을 활용하는 알고리즘.

주요 기여 및 결과

1. 최적 i.i.d. 알고리즘의 취약성
본 논문은 표준 i.i.d. 설정에서 최적의 오차율($\Theta(d/n)$)을 달 achieving하는 알고리즘들이 단조적 적대자에 의해 하위 최적(suboptimal) 성능으로 강제될 수 있음을 보여준다.

• OIG의 실패: i.i.d. 설정에서 VC 클래스에 대해 최적인 원-인클루전 그래프 알고리즘은, $n$개의 깨끗한 점과 $n$개의 부패된 점이 주어졌을 때 VC 차원 $d=1$에 대해서도 기대 오차가 상수 수준(구체적으로 $1/4$)에 달하도록 강제될 수 있음을 보여준다 (정리 1.1, 정리 4.4). 이는 최대 외차수를 최소화하는 "자연스러운" 방향성 전략을 사용하더라도 마찬가지이다.
• 다수결 투표의 실패: 최소 $t$ 크기의 부분 집합을 사용하는 모든 다수결 투표 알고리즘은 단 $2n/t$개의 부패된 점을 사용하여 $\Omega(d \log(n/d)/n)$의 기대 오차를 겪도록 강제될 수 있다 (정리 1.2, 정리 4.2, 정리 4.3). 이는 일반적으로 $\Omega(n)$ 크기의 부분 집합을 사용하는 Bagging이나 Majority-of-Three와 같은 최첨단 최적 학습기들에게도 적용된다. 적대자는 투표 알고리즘이 사용하는 부분 집합들을 서로 상관관계가 있게 만듦으로써, 이들이 동시에 실패하도록 적응적 성질을 악용한다.

2. 균등 수렴(Uniform Convergence)의 강건성(Robustness)
이와 대조적으로, OIG 및 다수결 투표의 실패와 달리, 본 논문은 **경험적 위험 최소화(ERM)**가 단조적 부패에 강건함을 보여준다.

• 상한(Upper Bound): 저자들은 결합된 데이터셋(깨끗한 데이터 + 부패된 데이터)에 대한 모든 ERM이 부패된 점의 개수에 관계없이 $O(d \log(n/d)/n)$의 기대 오차를 달성함을 증명한다 (정리 1.3, 정리 3.1).
• 메커니즘: 증명은 적대자가 레이블을 부패시킬 수 없기 때문에, 전체 데이터셋과 일치하는 모든 ERM은 깨끗한 부분 집합과도 일치한다는 관찰에 기초한다. 데이터의 무작위 순열에 조건부(conditioning)를 설정함으로써, 깨끗한 점들은 $D$로부터 추출된 i.i.d. 상태를 유지한다. 따라서 표준 균등 수렴 논리가 깨끗한 부분 집합에 적용되며, 이는 ERM이 깨끗한 분포를 해치면서 부패된 점들에 과적합(overfit)되지 않음을 보장한다.
• 의의: 이는 ERM의 i.i.d. 설정에서의 하위 최적성(최적의 $d/n$ 대비 $\log(n/d)$ 인자 차이)이 바로 이러한 형태의 의존성에 대한 강건함을 위해 지불하는 "대가"임을 시사한다.

3. 교환 가능성의 역할
본 논문은 OIG와 다수결 투표의 실패가 직접적으로 교환 가능성의 결여에 기인함을 강조한다.

• 무관심적 적대자: 만약 적대자가 무관심한 제약(부패된 점이 깨끗한 점들과 독립적임)을 받는다면, OIG 알고리즘은 $O(d/n)$의 최적 기대 오차를 회복한다 (정리 1.4, 정리 3.2). 이는 적응적 의존성이 도입된 단조적 적대자가 이러한 알고리즘들을 무너뜨리는 구체적인 메커즘임을 확인해 준다.

의의 및 주장
저자들은 자신들의 결과가 최적 학습 알고리즘들이 교환 가능성에 과도하게 의존하고 있음을 폭로한다고 주장한다.

• 이론적 통찰: 이 연구는 "데이터가 많을수록 좋다"라는 직관에 도전한다. 비록 추가된 데이터의 레이블이 정확하더라도, 단조적 부패가 정교한 학습 기법들(예: leave-one-out 및 앙상블 방법)을 증명 가능한 수준으로 망가뜨릴 수 있음을 보여준다.
• 실무적 함의: 이 결과는 현대 머신러닝 실무에서 손실 최소화(ERM)의 성공이 특정 형태의 데이터 오설정(misspecification) 및 의존성에 대한 내재적 강건성에서 비롯될 수 있음을 시사하는 반면, i.i.d. 설정에서 최적의 속도를 위해 설계된 더 정교한 기법들은 취약할 수 있음을 시사한다.
• 열린 질문: 저자들은 단조적 적대자 하에서의 최적 기대 오차를 찾는 것을 미해결 과제로 남겨두었다. ERM이 $O(d \log(n/d)/n)$의 상한을 제공하지만, 어떤 알고리즘이 최적의 $O(d/n)$ 비율을 달성할 수 있는지는 여전히 알려지지 않았다. 또한, 균등 수렴 원리가 적용되지 않는 Littlestone 클래스나 부분/다중 클래스(partial/multiclass) 클래스의 학습 가능성 또한 향후 과제로 남아 있다.

요약하자면, 본 논문은 ERM이 단조적 부패가 존재하는 상황에서도 약간의 하위 최적성을 감수하면서 강건한 보장을 제공하는 반면, i.i.d.를 위한 기존의 최적 알고리즘들은 교환 가능성을 위반하는 적응적, 레이블 정합적 부패에 매우 취약하다는 것을 입증한다.