PAC 학습 (Probably Approximately Correct Learning)

난이도: 고급
선수 지식: 기초 확률론, 집합론
관련 문서: VC 차원 | 과적합과 과소적합 | 오컴의 면도날

핵심 요약: “충분한 데이터가 있으면 학습이 보장된다”는 수학적 증명. PAC 학습(Probably Approximately Correct Learning)은 가설 공간(Hypothesis Space)의 크기와 요구 정확도에 따라 필요한 최소 데이터 양을 이론적으로 제시한다. 모든 현대 ML의 “데이터가 많을수록 좋다”는 직관의 수학적 근거이다.

개요

PAC 학습(Probably Approximately Correct Learning)은 계산 학습 이론(Computational Learning Theory)의 핵심 프레임워크로, Leslie Valiant가 1984년에 제안했다. “높은 확률로(Probably) 거의 정확한(Approximately Correct) 가설을 학습할 수 있는가?”라는 질문에 대한 수학적 프레임워크를 제공한다.

PAC 학습 이론은 다음 질문에 답한다:

어떤 개념 클래스가 학습 가능한가?
좋은 가설을 찾기 위해 얼마나 많은 데이터가 필요한가?
학습에 필요한 계산 시간은 얼마인가?

탄생 배경

1984년, Leslie Valiant는 논문 “A Theory of the Learnable”을 발표하며 PAC 학습 프레임워크를 제안했다. 당시 신경망(Neural Network)은 이미 관심을 받고 있었지만, 블랙박스(Black Box) 성격이 강했다. 신경망이 “왜 동작하는지”, “어떤 조건에서 학습이 보장되는지”에 대한 이론적 기반이 전무했다.

Valiant의 핵심 동기는 학습(Learning)을 계산(Computation)의 관점에서 엄밀하게 정의하는 것이었다. 컴퓨터 과학에서 알고리즘의 효율성을 다항 시간(Polynomial Time)으로 측정하듯, 학습 알고리즘도 “얼마나 많은 데이터로, 얼마나 빠르게, 얼마나 정확하게” 학습할 수 있는지를 수학적으로 규명하고자 했다. 이 연구는 이후 계산 학습 이론(Computational Learning Theory)이라는 분야를 탄생시켰고, Valiant는 이 공로로 2010년 튜링상(Turing Award)을 수상했다.

비유: 가설 공간 = 사전

PAC 학습의 샘플 복잡도를 직관적으로 이해하기 위한 좋은 비유가 있다. 가설 공간(Hypothesis Space)을 사전(Dictionary)에 비유해 보자.

사전에 단어가 100개밖에 없다면, 누군가 말한 단어를 맞추기 위해 몇 가지 힌트(예제)만 있으면 충분하다. 하지만 사전에 단어가 10,000개라면, 같은 수준의 확신을 갖기 위해 훨씬 더 많은 힌트가 필요하다. 이것이 바로 샘플 복잡도 공식 $m \ge \frac{1}{\epsilon}(\ln|H| + \ln\frac{1}{\delta})$ 에서 $|H|$ (가설 공간 크기)가 로그 형태로 등장하는 이유이다.

작은 사전(작은 $|H|$ ): 적은 예제로도 올바른 “단어(가설)“를 찾을 수 있다
큰 사전(큰 $|H|$ ): 후보가 많으므로, 잘못된 단어를 걸러내기 위해 더 많은 예제가 필요하다
정확도 요구(작은 $\epsilon$ ): “대충 비슷한 단어”가 아니라 “정확한 단어”를 찾으려면 더 많은 단서가 필요하다

핵심 개념

1. 프레임워크 정의

설정

학습자는 알 수 없는 분포 $D$ 에서 i.i.d.로 추출된 샘플 $S = \{(x_1, y_1), ..., (x_m, y_m)\}$ 을 받는다
목표 개념(target concept) $c$ 가 존재
가설 공간(hypothesis space) $H$ 에서 가설 $h$ 를 선택

PAC 학습 가능성

개념 클래스 $C$ 가 PAC 학습 가능(PAC-learnable)하다는 것은:

모든 $\epsilon > 0$ , $\delta > 0$ , 그리고 모든 분포 $D$ 에 대해, 알고리즘 $A$ 가 존재하여 $m$ 개의 샘플로 확률 $\ge 1-\delta$ 로 다음을 만족하는 가설 $h$ 를 출력한다:

$P\left[\text{error}(h) \le \epsilon\right] \ge 1 - \delta$

여기서:

$\epsilon$ : 정확도 파라미터 (오류 허용 한계)
$\delta$ : 신뢰도 파라미터 (실패 확률 상한)
학습 시간이 $1/\epsilon$ , $1/\delta$ , $n$ (특성 수), $\text{size}(c)$ 에 대해 다항 시간

2. 샘플 복잡도 (Sample Complexity)

유한 가설 클래스의 경우

$m \ge \frac{1}{\epsilon}\left(\ln|H| + \ln\frac{1}{\delta}\right)$

해석

요소	효과
$\\|H\\|$ 증가	더 많은 데이터 필요 (더 많은 가설 중 선택)
$\epsilon$ 감소	더 많은 데이터 필요 (더 정확해야 함)
$\delta$ 감소	더 많은 데이터 필요 (더 높은 신뢰도)

이것은 직관적으로 이해할 수 있다: 가설 공간이 클수록 올바른 가설을 찾기 위해 더 많은 증거(데이터)가 필요하다.

숫자로 이해하기

구체적인 예를 통해 샘플 복잡도(Sample Complexity) 공식이 어떻게 작동하는지 살펴보자.

설정: 가설(Hypothesis) 100개짜리 가설 공간, 오류율(Error Rate) 5% 이하를 원하고, 95% 확률(Confidence)로 보장하고 싶다.

$|H| = 100$ (가설 공간 크기)
$\epsilon = 0.05$ (허용 오류)
$\delta = 0.05$ (실패 확률)

공식 $m \ge \frac{1}{\epsilon}(\ln|H| + \ln\frac{1}{\delta})$ 에 대입하면:

$m \ge \frac{1}{0.05}(\ln 100 + \ln 20) = 20 \times (4.6 + 3.0) = 20 \times 7.6 = 152$

즉, 최소 약 152개의 데이터가 필요하다. 만약 가설이 100개가 아니라 10,000개라면?

$m \ge \frac{1}{0.05}(\ln 10000 + \ln 20) = 20 \times (9.2 + 3.0) = 20 \times 12.2 = 244$

가설 공간이 100배 커져도 필요 데이터는 약 1.6배만 증가한다. 이것이 $\ln|H|$ (로그(Logarithm) 의존)의 힘이다. 실무에서는 가설 공간이 유한하지 않으므로 VC 차원을 사용하며, 그 경우 필요 데이터는 수천~수만 개 수준이 된다.

3. 실현 가능 vs 불가지론적 설정

실현 가능 설정 (Realizable Setting)

가정: 참 개념 $c \in H$ (완벽한 가설이 가설 공간에 존재)
훈련 오류 0인 가설을 찾으면 일반화 보장

불가지론적 설정 (Agnostic Setting)

가정 없음: 참 개념이 $H$ 에 있을 필요 없음
목표: $H$ 안에서 최선의 근사를 찾음

$\text{error}(h) \le \min_{h' \in H}\text{error}(h') + \epsilon$

더 현실적이지만 샘플 복잡도가 더 높음

설정	가정	보장	현실성
실현 가능	$c \in H$	$\text{error}(h) \le \epsilon$	이상적
불가지론	없음	$\text{error}(h) \le \text{best} + \epsilon$	현실적

4. 실무적 연결

PAC 학습 이론은 직접적으로 사용되기보다 ML의 기본 원리를 이해하는 프레임워크로 가치가 있다:

PAC 이론의 통찰	실무적 의미
복잡한 모델( $\\|H\\|$ 큼)은 더 많은 데이터 필요	복잡한 모델에는 충분한 데이터 확보
일반화는 확률적으로만 보장	검증 세트/교차 검증 필수
학습 가능성은 계산 효율을 포함	NP-hard 문제는 이론적 학습 가능해도 실용 불가
데이터 양과 모델 복잡도의 관계	훈련/테스트 분할의 이론적 근거

상세 내용

PAC 학습 프레임워크 흐름

PAC 학습 프레임워크 흐름 다이어그램

샘플 복잡도 심화 (Sample Complexity)

유한 가설 클래스의 PAC 학습 가능성에서 핵심은 얼마나 많은 데이터가 필요한가이다.

실현 가능 설정에서의 유도

훈련 데이터에서 오류 0인 가설 $h$ 가 실제 오류 $\epsilon$ 이상을 가질 확률을 분석한다:

단일 “나쁜” 가설 $h$ 가 $m$ 개 샘플에서 오류를 보이지 않을 확률: $(1 - \epsilon)^m$
$|H|$ 개 가설 중 하나라도 이런 일이 일어날 확률 (유니온 바운드): $|H| \cdot (1 - \epsilon)^m$
이를 $\delta$ 이하로 만들면:

$|H| \cdot (1 - \epsilon)^m \le \delta$

$(1-\epsilon)^m \le e^{-\epsilon m}$ 을 이용하면:

$m \ge \frac{1}{\epsilon}\left(\ln|H| + \ln\frac{1}{\delta}\right)$

불가지론 설정에서의 샘플 복잡도

불가지론 설정에서는 균일 수렴(Uniform Convergence)을 필요로 하며, 더 많은 샘플이 요구된다:

$m \ge \frac{c}{\epsilon^2}\left(\text{VC}(H)\ln\frac{1}{\epsilon} + \ln\frac{1}{\delta}\right)$

$\epsilon$ 에 대한 의존이 $1/\epsilon$ 에서 $1/\epsilon^2$ 으로 강해진다.

계산적 효율 vs 통계적 효율 (Computational vs Statistical Efficiency)

PAC 학습 가능성은 두 가지 독립적 조건을 모두 요구한다:

측면	질문	핵심 척도
통계적 효율	얼마나 적은 데이터로 학습 가능한가?	샘플 복잡도 $m(\epsilon, \delta)$
계산적 효율	얼마나 빠르게 좋은 가설을 찾는가?	시간 복잡도 $T(\epsilon, \delta, n)$

통계적으로 가능하지만 계산적으로 어려운 사례

3-DNF 공식 학습: 통계적으로 PAC 학습 가능하지만, 효율적 알고리즘은 $P \ne NP$ 가정 하에 존재하지 않는다고 알려져 있다.
적절한 학습(proper learning): 가설이 개념 클래스 자체에 속해야 한다면 더 어렵다. 부적절한 학습(improper learning)에서는 다른 표현을 사용하여 효율적으로 풀 수 있는 경우가 있다.

효율적 PAC 학습 가능성

개념 클래스 $C$ 가 효율적으로 PAC 학습 가능하려면:

샘플 복잡도가 $1/\epsilon$ , $1/\delta$ , $n$ 에 대해 다항적
학습 알고리즘의 실행 시간이 $1/\epsilon$ , $1/\delta$ , $n$ 에 대해 다항적

두 조건 모두 만족해야 실용적 의미의 학습 가능성이 보장된다.

PAC 학습의 한계

분포에 대한 가정이 없음 (distribution-free) —> 바운드가 느슨할 수 있음
최악의 경우(worst-case) 분석 —> 실제로는 훨씬 적은 데이터로 충분
유한 가설 클래스에서 시작했으나, VC 차원으로 무한 가설 클래스로 확장

PAC-Bayes 프레임워크

PAC 학습 + 베이지안 접근의 결합
가설에 대한 사전/사후 분포를 활용하여 더 타이트한 바운드 제공
현대적 일반화 이론에서 중요한 역할

언제 사용하는가

PAC 학습은 직접 적용하는 알고리즘이 아니라 이론적 프레임워크이다:

모델 복잡도와 데이터 양의 관계를 이해할 때
일반화 보장의 이론적 근거가 필요할 때
학습 알고리즘의 본질적 한계를 이해할 때
ML 이론 연구의 기초로

실전 사례: 신용 평가에서 PAC 이론의 활용

금융 분야의 신용 평가(Credit Scoring)는 PAC 학습 이론이 실무적으로 의미 있는 통찰을 제공한 대표적 사례이다.

한 금융 기관이 새로운 신용 평가 모델을 구축한다고 가정하자. 고객의 특성(Feature)이 50개이고, 이를 기반으로 이진 분류(대출 승인/거절)를 수행하는 선형 모델을 사용한다면, VC 차원은 약 51이다. PAC 이론의 샘플 복잡도 공식을 적용하면:

정확도 목표 $\epsilon = 0.05$ (오류율 5% 이하)
신뢰도 $\delta = 0.05$ (95% 확률로 보장)
최소 필요 데이터량: 수천 건 이상의 과거 대출 기록

실제로 금융 규제 기관(예: 미국 OCC)은 신용 모델 검증 시 “충분한 데이터에 기반한 모델인가”를 핵심 심사 기준으로 삼는다. PAC 이론은 이 “충분한 데이터”가 모델의 복잡도와 요구 정확도에 따라 어떻게 결정되는지에 대한 이론적 근거를 제공한다. 물론 실무에서 PAC 바운드의 구체적 숫자를 직접 사용하지는 않지만, “더 복잡한 모델을 쓰려면 더 많은 데이터가 필요하다”는 정성적 지침은 모델 설계의 핵심 원칙으로 작동한다.

흔한 오해와 함정

1. “PAC 바운드를 실무에서 직접 사용할 수 있다”

PAC 바운드는 매우 느슨하여 실무적으로 유용한 숫자를 제공하지 않는다. 정성적 통찰이 가치 있다.

2. “PAC 학습 가능 = 실제로 학습 가능”

PAC 학습 가능하더라도 필요한 데이터나 계산이 비현실적으로 클 수 있다.

3. “데이터가 많으면 항상 좋다”

PAC 이론은 더 많은 데이터가 더 나은 일반화를 보장한다고 하지만, 실무에서는 데이터 품질, 분포 변화, 레이블 노이즈 등도 고려해야 한다.

다른 주제와의 연결

VC 차원: PAC를 무한 가설 클래스로 확장; 모델 복잡도의 척도
과적합과 과소적합: PAC 이론이 설명하는 일반화 격차
오컴의 면도날: 단순한 모델이 더 적은 데이터로 학습 가능
No Free Lunch: PAC 이론에서도 귀납적 편향의 필요성
정규화 이론: 가설 공간 제약으로 PAC 바운드 개선

자주 묻는 면접 질문

PAC 학습이란 무엇인가?
- “높은 확률로( $1-\delta$ ) 거의 정확한(오류 $\le \epsilon$ ) 가설을 다항 시간 내에 찾을 수 있는” 학습 프레임워크
샘플 복잡도가 가설 공간 크기에 어떻게 의존하는가?
- $m \ge \frac{1}{\epsilon}(\ln|H| + \ln\frac{1}{\delta})$ : 가설 공간이 클수록 더 많은 데이터 필요
실현 가능 vs 불가지론 설정의 차이는?
- 실현 가능: 참 개념이 H에 존재한다고 가정. 불가지론: 그런 가정 없이 H 내 최선의 근사를 찾음
PAC 바운드가 실무에서 느슨한 이유는?
- 분포에 대한 가정 없이 최악의 경우를 고려하기 때문. 실제 데이터는 특정 구조를 가져 훨씬 적은 데이터로 충분

용어 정리

영어	한국어
PAC Learning	PAC 학습
Sample Complexity	샘플 복잡도
Hypothesis Space	가설 공간
Concept Class	개념 클래스
Realizable Setting	실현 가능 설정
Agnostic Setting	불가지론적 설정
Generalization Bound	일반화 바운드
Computational Learning Theory	계산 학습 이론

참고 자료

Valiant (1984) - “A Theory of the Learnable”
Shalev-Shwartz & Ben-David (2014) - Understanding Machine Learning: From Theory to Algorithms (Ch. 2-4)
Kearns & Vazirani (1994) - An Introduction to Computational Learning Theory
McAllester (1999) - “PAC-Bayesian Model Averaging”