📊 statistics

An Optimal Agnostic PAC Algorithm

이 논문은 기성립된 하한선과 일치함으로써 보편적 상수를 제외한 샘플 복잡도를 확정하며 통계적으로 최적의 리스크 경계를 달성하는 이진 분류를 위한 불가지론적 PAC 학습 알고리즘을 제시한다.

원저자: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

게시일 2026-08-07

📖 6 분 읽기🧠 심층 분석

원저자: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 로봇에게 고양이와 강아지를 구별하는 법을 가르치려 한다고 상상해 보세요. 당신은 로봇에게 수천 장의 사진을 보여주지만, 세상은 무질서합니다: 때로는 고양이가 어둠 속에 숨어 있고, 때로는 강아지가 모자를 쓰고 있으며, 때로는 당신이 로봇에게 주는 라벨 자체가 완전히 틀리기도 합니다. 이것이 바로 머신러닝(machine learning), 구체적으로는 **통계적 학습 이론(statistical learning theory)**이라 불리는 분야의 세계입니다. 여기서 핵심적인 질문은 이것입니다: 로봇이 정답을 맞히는 데 능숙해지기 위해 얼마나 많은 사례를 보아야 하는가?

이를 해결하기 위해 과학자들은 VC 차원(VC dimension)(Vapnik과 Chervonenkis의 이름을 딴)이라는 개념을 사용합니다. VC 차원을 로봇의 뇌가 얼마나 "혼란스러운지" 또는 "복잡한지"를 나타내는 척도라고 생각하십시오. 귀 모양만 보는 단순한 뇌는 낮은 VC 차원을 가지며, 모든 픽셀을 하나하나 살피는 초복잡한 뇌는 높은 VC 차원을 가집니다. 목표는 로봇이 유용할 만큼 빠르게 배우면서도, 규칙을 배우는 대신 훈련 사진을 단순히 암기해 버리는 과적합에 빠지지 않는 "최적의 지점(sweet spot)"을 찾는 것입니다. 수십 년 동안 수학자들은 특정 수의 사례와 특정 수준의 복잡도가 주어졌을 때, 로봇이 최상의 가능한 로봇과 비교하여 얼마나 많은 "추가적인" 오차를 낼 것인지에 대한 완벽한 공식을 찾기 위해 노력해 왔습니다.

오랫동안 지식의 공백이 존재했습니다. 우리는 데이터가 완벽할 때(라벨에 오류가 없을 때)의 최적의 학습 속도를 알고 있었고, 데이터가 매우 무질서할 때의 속도도 알고 있었습니다. 하지만 그 중간 단계는 어떠했을까요? 데이터에 약간의 노이즈가 섞여 있다면 어떻게 될까요? 이전의 시도들은 마치 무거운 배낭을 메고 경주를 하는 것과 같았습니다. 근접하기는 했지만, 필요 이상으로 느리게 만드는 "로그(logarithmic)" 무게를 짊어지고 있었습니다. 큰 질문은 이것이었습니다: 데이터에 노이즈가 얼마나 있든 상관없이, 저 추가적인 무게 없이 절대적으로 가장 빠른 속도로 달릴 수 있는 학습기를 구축할 수 있을까?

"An Optimal Agnostic PAC Algorithm"이라는 제목의 이 논문은 그 질문에 대해 단호하게 "예"라고 답합니다. 저자들인 Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy는 **통계적으로 최적의 리스크 바운드(statistically optimal risk bound)**를 달성하는 특정한 학습 알고ically를 구축했습니다. 쉬운 말로 설명하자면, 그들은 어떤 다른 방법도 (보편적인 상수 범위 내에서) 자신들을 이길 수 없음을 수학적으로 증명하면서, 최소한의 실수를 범하는 분류기를 학습시키는 방법을 찾아낸 것입니다. 그들은 단순히 추측한 것이 아니라, 증명해 냈습니다.

그들이 어떻게 이 일을 해냈는지, 매우 체계적인 도서관과 영리한 "원-인클루전(one-inclusion)" 게임에 대한 이야기를 통해 설명하겠습니다.

문제: 노이즈가 섞인 도서관

모든 책이 사진이고, 모든 책의 책등에는 "고양이" 또는 "강아지"라고 적힌 라벨이 붙어 있는 거대한 도서관을 상상해 보십시오. 하지만 사서는 조금 서투릅니다. 가끔 책의 라벨을 잘못 붙이거나 책이 손상되기도 합니다. 당신은 이 새로운 라벨이 없는 책을 보고 정답을 맞힐 수 있는 시스템을 만들고 싶습니다.

"최상의 가능한" 시스템(이를 **오라클(Oracle)**이라고 부릅시다)은 우주의 진정한 규칙을 알고 있습니다. 하지만 사서의 라벨이 가끔 틀리기 때문에 오라클조차도 실수를 할 것입니다. 이 최소 오차율을 $L^*$ 라고 합니다. 당신의 목표는 도서관에서 제한된 수의 책( $n$ )을 사용하여 오라클의 성능에 최대한 가까워지는 시스템을 만드는 것입니다.

이 논문은 그들의 새로운 시스템(이를 **옵티마이저(The Optimizer)**라고 부릅시다)의 오차율( $L(\hat{h})$ )이 다음과 같이 제한될 것임을 증명합니다:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
수식이 무섭게 느껴지지 않도록 하십시오. 핵심은 제곱근 항입니다. 이 공식은 당신이 저지르는 추가적인 실수(즉, "초과 리스크")가 더 많은 책( $n$ )을 얻을수록 줄어든다는 것을 의미하며, 확률 법칙이 허용하는 가장 빠른 속도로 줄어든다는 것을 의미합니다. 이전 방법들은 속도를 늦추는 추가적인 요인(예: $\log(n)$ )을 가지고 있었지만, 옵티마이저는 이를 제거했습니다.

비법: 큐브와 방향성

그들은 어떻게 해냈을까요? 그들은 **원-인클루전 그래프(One-Inclusion Graph)**와 **접미사 평균화(Suffix Averaging)**라는 두 가지 아이디어의 탁월한 조합을 사용했습니다.

1. 원-인클루전 그래프 (큐브 게임)
샘플에 포함된 책들이 가질 수 있는 모든 가능한 라벨링 방식을 상상해 보십시오. 만약 $n$ 권의 책이 있다면, $2^n$ 개의 가능한 라벨 조합이 존재합니다. 이 조합들을 거대한 다차원 큐브("불리언 큐브")의 꼭짓점들로 시각화할 수 있습니다.

두 꼭짓점은 정확히 한 권의 책의 라벨만 다를 경우 하나의 모서리(edge)로 연결됩니다.
"오라클"(최상의 규칙)은 이 큐브 어딘가에 살고 있습니다.
목표는 당신이 어느 꼭짓점에 있든, 오라클에 더 가까워지기 위해 어느 방향을 가리켜야 할지 알아내는 것입니다.

저자들은 방향성(orientation) 기법을 사용합니다. 이 거대한 큐브의 꼭짓점에 서 있다고 상상해 보십시오. 당신은 어느 방향으로 갈지 결정해야 합니다. 논문은 "클래스 의존적 에지 등주 부등식(class-dependent edge isoperimetric inequality)"인 Lemma 2.1이라는 새로운 수학적 도구를 도입합니다. 우리 도서관 비유로 치면, 이것은 "올바른 방향을 찾기 위해 확인해야 하는 경로의 수는 당신이 오라클로부터 얼마나 떨어져 있는지, 그리고 도서관이 얼마나 복잡한지에 달려 있다"라는 규칙과 같습니다.

그들은 당신이 어디서 시작하든, 최상의 답에 도달하기 위해 정해진 수 이상의 단계를 거칠 필요가 없도록 이 거대한 큐브의 모든 모서리에 방향을 부여할 수 있음을 증명합니다. 이 단계는 무질서한 추측 게임을 결정론적인 경로로 바꾸는 데 매우 중요합니다.

2. 접미사 평균화 (위원회 투표)
이 완벽한 방향성을 확보했다면, 이제 이를 실제 예측기로 전환해야 합니다. 그들은 **접미사 평균화(suffix averaging)**라는 트릭을 사용합니다.
당신이 전문가 팀을 구성하고 있다고 상상해 보십시오. 단 한 명의 전문가에게 의견을 묻는 것이 아닙니다. 대신, 약간씩 다른 양의 데이터를 본 일련의 전문가들에게 의견을 묻습니다.

전문가 1은 처음 $k$ 권의 책을 보았습니다.
전문가 2는 처음 $k+1$ 권의 책을 보았습니다.
...
전문가 $m$ 은 처음 $2k-1$ 권의 책을 보았습니다.

최종 예측은 이 전문가들 의견의 평균입니다. 이것은 강력합니다. 왜냐하면 이는 무작위성을 완화해주기 때문입니다. 만로 한 명의 전문가가 노이즈가 섞인 책 때문에 운이 나쁘더라도, 다른 전문가들이 이를 균형 있게 잡아줍니다. 논문은 이 평균화 과정이 완벽한 큐브 방향성과 결합되었을 때, 데이터에 노이즈가 있어도 오차율을 낮게 유지한다는 것을 증명합니다.

3. 마지막 다듬기: 임계값 설정 (Thresholding)
평균화된 결과는 -1과 1 사이의 숫자(즉, "점수")입니다. 최종적인 "고양이" 또는 "강아지" 답변을 얻기 위해, 그들은 **임계값(threshold)**을 사용합니다. 그들은 별도의 검증용 책들을 사용하여 가장 잘 작동하는 컷오프 지점을 선택하기 위해 여러 가지 서로 다른 절단점을 테스트합니다. 이 단계는 최종 결과가 모호한 확률이 아니라 단순하고 결정론적인 규칙(이진 분류기)이 되도록 보장합니다.

이것이 왜 중요한가

이 논문 이전에는, 가장 빠른 학습률을 원한다면 완벽한 데이터를 위한 방법과 노이즈가 있는 데이터를 위한 방법 중 하나를 선택해야 했습니다. 페널티를 지불하지 않고 두 가지 장점을 모두 가질 수는 없었습니다.

이 논문은 당신이 두 가지 장점을 모두 가질 수 있음을 보여줍니다. 그들은 다음과 같은 학습기를 구축했습니다:

노이즈 수준을 알 필요가 없음: 데이터가 얼마나 무질서한지( $L^*$ ) 또는 당신이 얼마나 확신하고 싶은지( $\delta$ )를 몰라도 작동합니다.
최적임: Devroye, Györfi, Lugosi와 같은 이전 연구자들이 세운 이론적 하한선(학습 속도 제한)과 일치합니다.
결정론적임: 운에 의존하지 않습니다. 동일한 데이터에 대해 실행할 때마다 항상 같은 답을 줍니다.

저자들은 최적의 결과를 얻기 위해 "폴리로그(polylogarithmic)" 요인(그 느려지는 요소들)이 반드시 필요하다는 생각을 명시적으로 부정합니다. 그들은 아그노스틱(agnostic, 노이즈가 있는) 환경에서 그러한 요인들이 불필요함을 증명했습니다. 또한, 단순한 다수결 투표와 같은 이전의 일부 방법들은 완벽한 데이터에서는 잘 작동하지만, 노이즈가 도입되면 최적의 속도를 유지하는 데 실패한다는 점도 보여주었습니다.

요약하자면, 이 논문은 머신러닝 이론의 역사에서 오랜 한 페이지를 마무리 짓습니다. 이는 데이터가 결코 완벽하지 않은 현실 세계의 이진 분류를 위한 "완벽한" 알고리즘을 제공합니다. 이것은 마치 길에 아무리 많은 구멍이 있더라도 최소한의 단계로 보물을 찾을 수 있다는 것을 보장하는 지도를 찾는 것과 같습니다. 저자들은 이것이 가능하다는 것을 제안하는 데 그치지 않고, 실제로 지도를 만들고 그것이 작동함을 증명했습니다.

기술 요약: 최적의 아그노스틱(Agnostic) PAC 알고리즘

문제 정의
본 논문은 이진 분류를 위한 아그노스틱 확률적 근사 가능(Probably Approximately Correct, PAC) 학습에서 날카로운 리스크 경계(sharp risk bounds)를 결정하는 근본적인 문제를 다룬다. $H \subseteq \{-1, +1\}^{\mathcal{X}}$ 를 VC 차원이 $d \geq 1$ 인 가설 클래스라고 하자. $\mathcal{X} \times \{-1, +1\}$ 상의 분포로부터 추출된 크기 $n$ 의 i.i.d. 샘플 $S$ 가 주어졌을 때, 목표는 최적 리스크 $L^* = \min_{h \in H} L(h)$ 에 근접한 분류기 $\hat{h}$ 를 출력하는 학습자를 구축하는 것이다.

역사적으로, 이 설정에서의 경계들은 두 가지 구별된 체제(regime)를 통해 도출되어 왔다:

실현 가능한 경우 (Realizable Case, $L^*=0$ ): 원-인클루전 그래프(one-inclusion graph, Haussler, Littlestone, Warmuth)나 특정 집합(aggregation) 기법과 같은 조합론적 논증을 통해 $O(d/n)$ 의 최적 속도가 달성된다.
아그노스틱 경우 (Agnostic Case, $L^* > 0$ ): 고전적인 경험적 과정(empirical process) 방법론(chaining, covering)은 $L^*$ 이 0에서 떨어져 있을 때 $O(\sqrt{d/n})$ 의 최적 속도를 산출한다.

Devroye, Györfi, Lugosi의 하한(lower bounds)에 의해 확립된 미해결 과제는, 단일 알고리즘이 전체 $L^*$ 스펙트럼에 걸쳐 최적의 속도를 달성할 수 있는지, 즉 다음 경계와 일치할 수 있는지 여부이다:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
이전의 상한(upper bounds)들은 빠른 속도(fast rate) 항에서 부적절하게 높은 폴리로그(polylogarithmic) 인자를 포함하거나, 최적성을 달하기 위해 $L^*$ 에 대한 특정 조건(예: $L^* \lesssim (d+\log(1/\delta))/n$ )을 요구했다.

방법론
저자들은 $L^*$ 이나 신뢰 매개변수 $\delta$ 에 대한 사전 지식 없이도 최적의 경계를 달성하는 결정론적이고 일반적으로 부적절한(improper) 학습자를 구축한다. 방법론은 세 가지 주요 단계로 진행된다:

클래스 의존적 에지 등주 부등식 (Edge Isoperimetry, 섹션 2):
핵심적인 이론적 혁신은 불리언 큐브(Boolean cube) 상의 **클래스 의존적 에지 등주 부등식(Lemma 2.1)**이다. 에지 수를 단순히 VC 차원이나 트레이스(trace)와의 거리로 제한했던 이전 결과들과 달리, 이 보조정리는 다음을 동시에 만족하는 가중치 $w_{v,p}$ 를 도입한다:
- $w_{v,p} + w_{v \oplus p, p} = 1$ (에지 분할).
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ , 여기서 $\rho_F(v)$ 는 트레이스 $F$ 까지의 해밍 거리(Hamming distance)이고, $R_D(F)$ 는 좌표 $D$ 로의 투영(projection)에 대한 정규화되지 않은 라데마허 폭(unnormalized Rademacher width)이다.
이 부등식은 유도된 에지(induced edges) $|E_U|$ 의 수를 제어함으로써, 최적의 트레이스까지의 거리와 투영의 복잡도를 모두 사용하여 국소적인 경계를 허용한다.
최적의 Leave-One-Out 방향성 (Section 2):
Hall의 결혼 정리(Hall's Marriage Theorem)를 사용하여, 저자들은 이 등주 부등식을 전체 불리언 큐브의 결정론적 방향성(orientation) $\sigma$ 로 변환한다. 이 방향성은 임의의 정점 $v$ 에 대해 외차수(out-degree)가 다음과 같이 제한됨을 보장한다:
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
이는 기대 오차가 최적 경험적 리스크에 $\sqrt{d L^*/n}$ 및 $d/n$ 에 비례하는 항을 더한 값으로 제한되는 leave-one-out 규칙으로 이어진다.
Leave-One-Out에서 PAC 경계로 (Section 3):
leave-one-out 규칙을 고확률 PAC 보증으로 변환하기 위해, 저자들은 두 단계의 디랜도마이제이션(derandomization) 및 평균화 과정을 사용한다:
- 대칭화 및 접미사 평균화 (Symmetrization and Suffix Averaging): 결정론적 leave-one-out 규칙을 순열(permutations)에 대해 대칭화한다. 샘플의 접미사(indices $k$ to $2k-1$ )에 대해 이러한 대칭화된 점수들을 평균하여 무작위 예측기 $\hat{p}$ 를 구성한다. 이 단계는 과잉 리스크(excess risk)의 분산과 편차를 제어하기 위해 Aden-Ali 등의 연구에서 적응된 역방향 및 순방향 마팅게일(martingale) 논증(Lemma 3.1, 3.2)을 활용하며, 이를 통해 경계가 $L^*$ 에 대해 균등하게 성립하도록 보장한다.
- 임계값 설정 및 ERM: $[-1, 1]$ 값을 갖는 무작위 예측기 $\hat{p}$ 를 결정론적 이진 분류기로 변환한다. 이는 임계값 적용된 가설들의 클래스 $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ 를 고려함으로써 수행된다. 독립적인 검증 샘플을 사용하여 이 클래스에서 경험적 리스크 최소화(ERM)를 선택한다. 결정적으로, 임계값 클래스의 중첩 구조(nested structure) 덕 인해 샘플 크기에 대한 추가적인 로그 인자 없이 국소 엔트로피 경계를 얻을 수 있으며, 이를 통해 $L^*$ 에 대한 최적 계수를 보존한다.

주요 기여 및 결과
본 논문은 임의의 분포, 샘플 크기 $n$ , 신뢰도 $\delta$ 에 대해, 다음을 만족하는 분류기 $\hat{h}$ 를 출력하는 결정론적 학습자의 존재를 증명하는 **정리 1(Theorem 1)**을 제시한다:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
단, 확률은 최소 $1-\delta$ 이다. 정리 1의 증명 과정에서의 최종 유도는 약 $3.1 \cdot 10^7$ 의 더 타이트한 상수를 산출한다.

최적성 (Optimality): 이 경계는 보편적 상수(universal constants) 범위 내에서 Devroye, Györfi, Lugosi의 하한과 일치한다. 이는 모든 고정된 $L^*$ 에 대해 최적의 속도를 달성하는 최초의 결과이며, 부적절한 폴리로그 인자 없이 실현 가능한(realizable) 영역과 완전한 아그노스틱(agnostic) 영역 사이의 간극을 메운다.
알고리즘 특성: 학습자는 결정론적이며, 일반적으로 부적절하고(improper), $H$ 에 반드시 속할 필요는 없으며, $L^*$ 이나 $\delta$ 에 대한 지식을 요구하지 않는다.
기술적 참신함: 증명은 새로운 클래스 의존적 에지 등주 부등식(Lemma 2.1)에 의존하며, 이는 근사 오차와 투영된 라데마허 폭의 조합을 통해 유도된 에지 수를 제어한다. 이는 기존의 조합론적 또는 순수 경험적 과정 접근 방식과는 구별되는 기법이다.

의의
본 논문은 보편적 상수에 대한 아그노스틱 PAC 학습의 샘플 복잡도 문제를 해결했다고 주장한다. 모든 고정된 $L^*$ 에 대해 이진 분류의 미니맥스 과잉 리스크(minimax excess risk)를 달성하는 알고리즘을 구축함으로써, 저자들은 노이즈 수준의 전체 스펙트럼에 대해 최적의 알고리즘이 존재하는지에 대한 오랜 미해결 과제를 해결하였다. 이 연구는 $L^*$ 항의 선행 계수를 희생하지 않고도 최적의 속도를 달성할 수 있음을 보여주며, 이는 실현 가능한 분석과 아그노스틱 분석 기법 사이의 긴장 관계로 인해 어렵다고 여겨졌던 성과이다.

문제: 노이즈가 섞인 도서관

비법: 큐브와 방향성

이것이 왜 중요한가

기술 요약: 최적의 아그노스틱(Agnostic) PAC 알고리즘

유사한 논문