세 분류기 다수결이 최적임을 증명, 앙상블 이론의 견고한 토대 마련

PAC 학습과 최적성의 의미

기계학습 이론의 출발점은 1984년 레슬리 발란트가 제시한 PAC(Probably Approximately Correct) 학습 프레임워크다. 이 틀 안에서 핵심 질문은 단순하다. 우리는 얼마나 적은 데이터로, 충분히 높은 확률로, 충분히 좋은 분류기를 학습할 수 있는가? 이 질문에 대한 답은 표본 복잡도(sample complexity)라는 개념으로 정식화된다. 어떤 학습 알고리즘이 주어진 문제에서 이론적으로 가능한 최소한의 데이터만으로 목표 성능에 도달한다면, 그 알고리즘은 최적 학습자(optimal learner)라 불린다.

실현 가능 설정(realizable setting)은 이 맥락에서 자주 등장하는 이상적인 조건이다. 우리가 고려하는 가설 클래스 안에 훈련 데이터를 완벽하게 분류하는 분류기가 반드시 존재한다고 가정하는 이 설정에서, 일관된(consistent) 분류기—즉 훈련 데이터를 하나도 틀리지 않는 분류기—를 학습하는 일은 자연스러운 출발점이 된다.

수십 년간 최적 학습자를 찾는 작업은 기계학습 이론의 핵심 과제였다. 2016년 스티브 한네케가 VC 차원(VC dimension)에 기반한 최적 알고리즘을 처음 증명했지만, 그 알고리즘은 개념적으로도 분석적으로도 상당한 복잡성을 요구했다. 바로 이 지점에서 Divit Rawal과 Nikita Zhivotovskiy의 새 논문이 등장한다.

셋이면 충분하다

이 논문의 주장은 간결하다. 독립적인 데이터로 학습된 일관된 분류기 세 개의 다수결만으로 PAC 실현 가능 설정에서 최적 학습자를 구현할 수 있다. 단순히 "잘 작동한다"는 수준이 아니라, 이론적으로 달성 가능한 최선의 표본 복잡도를 달성한다는 뜻이다.

다수결 투표(majority vote)는 앙상블 학습의 가장 원초적인 형태다. 세 분류기가 각자 독립적인 훈련 데이터로 학습된 뒤, 새로운 입력에 대해 각자 예측을 내리고, 그 중 둘 이상이 동의하는 답을 최종 예측으로 채택한다. 직관적으로도 설득력 있는 방식이다. 세 전문가 중 적어도 두 명이 동의한다면 그 답이 옳을 가능성이 높다는 논리다.

그런데 이 직관이 정확히 최적성과 맞닿는다는 사실은 자명하지 않다. 세 분류기 각각이 독립적으로 학습됐다고 해도, 그들의 오류가 서로 어떻게 상호작용하는지를 정밀하게 분석해야 한다. 각 분류기는 보지 못한 데이터에서 상당한 오류를 가질 수 있다. 그러나 세 분류기의 오류가 항상 같은 지점에서 발생하지는 않는다. 독립적으로 학습됐기 때문에 오류가 겹치는 영역은 충분히 작고, 이 작은 교집합이 최적 표본 복잡도 경계와 일치한다는 것이 증명의 핵심이다.

Rawal과 Zhivotovskiy는 이 분석을 기존 접근법보다 훨씬 짧고 명확하게 수행했다. 논문이 강조하는 "짧은 증명(short proof)"이라는 표현 자체가 이 작업의 미덕을 말해준다. 수학에서 더 짧은 증명은 단순히 읽기 편한 것이 아니라, 결과의 본질이 무엇인지를 더 선명하게 드러낸다는 뜻이기도 하다.

단순함이 이론을 다시 쓰는 방식

이 결과의 파급력은 한네케 알고리즘의 재증명에 그치지 않는다. 논문은 크리스토퍼 크리스텐센 라르센이 분석한 배깅(bagging)의 최적성도 같은 틀 안에서 포괄한다. 배깅은 훈련 데이터의 부트스트랩 복원 표본으로 여러 분류기를 훈련시킨 뒤 다수결을 취하는 방식으로, 오늘날 랜덤 포레스트를 비롯한 수많은 실용적 앙상블 기법의 이론적 뿌리다. 라르센의 분석은 복잡한 확률론적 논증을 요구했지만, 다수결-셋 프레임워크는 그 결과를 훨씬 자연스러운 방식으로 포섭한다.

기계학습 이론에서 단순화는 단순히 "더 읽기 쉬운 증명"을 의미하지 않는다. 더 단순한 알고리즘이 같은 결과를 낸다면, 그 알고리즘의 각 구성 요소가 왜 필요한지를 더 명확히 드러낸다. 최적성을 달성하기 위해 복잡한 절차가 필요하지 않다면, 우리는 이전의 복잡성이 어디서 비롯됐는지를 다시 물어야 한다.

물론 이 결과가 실용적 맥락에서 즉시 적용 가능한 레시피를 제공하는 것은 아니다. 실제 배포 환경에서 세 개의 완전히 독립적인 분류기를 훈련시키는 비용, 분배 이동(distribution shift), 비실현 가능 설정(agnostic setting)의 복잡성은 여전히 열린 문제다. 그럼에도 이 결과는 다수결 앙상블의 이론적 근거를 정면으로 확립함으로써, 앙상블 방법론 전반의 이론적 분석에 새로운 출발점을 제공한다.

수학이 가장 아름다울 때는 가장 복잡해 보였던 결과가 가장 단순한 형태로 표현될 수 있음이 드러나는 순간이다. 세 분류기의 다수결이 최적이라는 이 결과는, 그런 순간 중 하나로 기억될 것이다.