PAC 학습 (Probably Approximately Correct Learning)¶

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

개요¶

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

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

핵심 개념¶

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\) 감소	더 많은 데이터 필요 (더 높은 신뢰도)

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

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 학습 프레임워크 흐름¶

flowchart TD
    D["미지의 분포 D"] -->|"i.i.d. 샘플링"| S["훈련 데이터 S = {(x₁,y₁), ..., (xₘ,yₘ)}"]
    S --> A["학습 알고리즘 A"]
    H["가설 공간 H"] --> A
    A -->|"가설 선택"| h["출력 가설 h ∈ H"]
    h --> E{"error(h) ≤ ε ?"}
    E -->|"확률 ≥ 1-δ"| YES["PAC 학습 성공"]
    E -->|"확률 < 1-δ"| NO["더 많은 샘플 필요\n또는 H 재설계"]

    style D fill:#e3f2fd
    style S fill:#fff3e0
    style A fill:#f3e5f5
    style h fill:#e8f5e9
    style YES fill:#c8e6c9
    style NO fill:#ffcdd2

샘플 복잡도 심화 (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. 샘플 복잡도가 \(1/\epsilon\), \(1/\delta\), \(n\)에 대해 다항적 2. 학습 알고리즘의 실행 시간이 \(1/\epsilon\), \(1/\delta\), \(n\)에 대해 다항적

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

PAC 학습의 한계¶

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

PAC-Bayes 프레임워크¶

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

언제 사용하는가¶

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

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

흔한 오해와 함정¶

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"