Probably Approximately Correct
Valiant's Question (1984)
Leslie Valiant은 겉으로는 단순해 보이는 질문을 던졌습니다: 기계가 학습한다는 것은 무엇을 의미하는가? '기억할 수 있는가?'도 아니고 '완벽하게 예측할 수 있는가?'도 아닙니다. 대신: 유한한 샘플로부터 다항 시간 안에, 높은 확률로 대략적으로 잘 학습할 수 있는가?
이러한 관점은 2010년 Turing Award 수상으로 이어졌으며, 계산 학습 이론의 기초를 마련했습니다.
두 개의 조절 장치
ε (엡실론) — 오차 허용 범위. 대략적으로 정확하다는 것은 오차 ≤ ε을 의미합니다. ε이 작을수록 학습 조건이 엄격해집니다.
δ (델타) — 신뢰도 파라미터. 아마도 성공 확률 ≥ 1 − δ을 의미합니다. δ가 작을수록 더 높은 신뢰도가 요구됩니다.
정의
개념 클래스 C가 PAC-learnable하다고 하려면, 어떤 알고리즘이 존재하여 임의의 데이터 분포 D와 C에 속하는 목표 개념 c에 대해, D에서 추출되고 c에 의해 레이블링된 m개의 샘플이 주어졌을 때, 다음을 만족하는 가설 h를 반환해야 합니다:
P[error(h) ≤ ε] ≥ 1 − δ
여기서 m은 1/ε, 1/δ 및 개념 크기에 대해 다항식(polynomial)이다.
In Korean: 예제를 충분히 주면 충분히 자주 충분히 가까워지며, 그 '충분함'은 지수적으로 폭발하지 않는다.
유한 가설 공간에 대한 샘플 복잡도
가설 공간 H가 유한한 수의 후보 가설을 포함한다면, 고전적 분석은 다음과 같이 제시한다:
m ≥ (1/ε)(ln|H| + ln(1/δ))
이 공식을 예산으로 이해하라. ε를 절반으로 줄이면 필요한 샘플 수가 두 배가 된다. δ를 절반으로 줄이면 상수가 추가된다. |H|를 두 배로 늘리면 ln(2)개의 샘플이 추가된다 — 로그 스케일로, 매우 완만한 증가다.
가설 클래스를 위한 샘플 크기 결정
스팸 필터가 |H| = 1,000,000개의 후보 규칙 집합 중에서 선택합니다. 오차 ε ≤ 0.05, 신뢰도 1 − δ = 0.99(즉 δ = 0.01)를 원합니다.
샤터링과 VC 차원
가설 공간이 무한해질 때
m ≥ (1/ε)(ln|H| + ln(1/δ)) 경계는 |H| = ∞일 때 성립하지 않습니다. 대부분의 유용한 가설 클래스(ℝᵈ에서의 선형 분류기, 결정 트리, 신경망)는 무한히 많은 후보를 포함합니다. Vapnik와 Chervonenkis는 1971년경 더 풍부한 복잡도 척도인 VC 차원을 제시하여 이 문제를 해결했습니다.
샤터링
가설 클래스 H는 n개의 점 집합에 대해 가능한 모든 라벨링(2ⁿ개의 모든 이진 분할)을 생성할 수 있을 때 해당 집합을 샤터링한다고 합니다. ℝ²에서의 선형 분류기는 일반 위치에 있는 임의의 3개 점을 샤터링합니다. 3개 점에 대한 8가지 가능한 +/− 라벨링 각각에 대해, 이를 정확히 분리하는 직선이 존재합니다.
하지만 ℝ²에서의 선형 분류기는 XOR 형태로 배치된 4개의 점을 shatter할 수 없습니다. 어떤 직선도 대각선 쌍과 반대각선 쌍을 분리할 수 없습니다.
VC 차원
VC(H) = H가 어떤 n-점 집합을 shatter할 수 있는 가장 큰 n. 2차원 선형 분류기의 경우 VC = 3. 2차원 축 정렬 사각형의 경우 VC = 4. W개의 가중치를 가진 신경망의 경우 VC ≤ O(W² log W) (Bartlett & Anthony 1999).
VC 차원을 이용한 표본 복잡도
PAC 경계식에서 ln|H|를 VC 차원 d로 대체합니다:
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
VC 차원은 무한 가설 클래스의 '유효 복잡도' 역할을 합니다. VC 차원이 낮은 가설 클래스는 적은 샘플로도 일반화되지만, VC 차원이 높은 클래스는 더 많은 데이터를 요구합니다.
유효 가설 수로서의 VC 차원
신경망은 W = 10⁹개의 가중치를 가집니다. Bartlett-Anthony 경계에 따라 VC ≤ O(W² log W)이며, VC ≈ W² log₂ W로 근사합니다.
Dropping Realizability, Posteriors over Hypotheses
Two Important Generalizations
Classical PAC assumes our target concept c lives inside our hypothesis class H. Real data carries noise, mislabels, & concepts our class cannot represent. Two extensions handle this.
Agnostic PAC
우리의 c ∈ H 가정은 이제 버린다. 이제 best-in-class 가설 h* = argmin_{h ∈ H} risk(h)과 경쟁한다. 경계 형태가 바뀐다: 완벽에 가까워지는 대신, H 내에서 최선 가능한 것에 가까워진다.
Agnostic bound: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ이며, 표본 복잡도는 m = O(1/ε² × (VC(H) + log(1/δ)))이다. 분모에서 ε 대신 ε²가 사용됨에 주의하라: agnostic 학습은 동일한 정밀도를 위해 더 많은 표본이 필요하다.
PAC-Bayes (McAllester 1999)
단일 가설을 선택하는 것에서 가설에 대한 분포를 선택하는 것으로 이동한다. 사전 분포 P에서 시작하여 데이터를 관찰한 뒤 사후 분포 Q를 유도한다. PAC-Bayes는 Q 하에서의 기대 위험을 다음과 같이 경계한다:
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P)는 우리의 사후분포가 사전분포로부터 얼마나 멀어졌는지를 측정합니다. 두 가지 해석이 있습니다:
1. 압축 관점. 사전분포에 가까운 사후분포(작은 KL)는 일반화가 잘 됩니다 — 정보 비용이 작으면 일반화 격차도 작습니다.
2. 베이지안 관점. 강한 사전분포 + 약한 데이터 업데이트 = 더 타이트한 바운드; 약한 사전분포 + 강한 데이터 업데이트 = 더 느슨한 바운드.
PAC-Bayes가 중요한 이유. Catoni(2007), Dziugaite & Roy(2017) 등의 경험적 PAC-Bayes 바운드는 실제 신경망에 대해 수치적으로 의미 있는 일반화 보장을 제공하며, 기존 PAC 바운드가 공허(vacuous)해지는 경우에도 유효합니다. 이는 과매개변수화된 모델의 일반화에 대한 가장 타이트한 이론적 도구 중 하나입니다.
PAC-Bayes 범위 읽기
네트워크를 n = 50,000개의 레이블된 예제로 학습했다고 가정합니다. 학습 후, 가중치에 대한 사후 분포 Q는 가우시안 사전 분포 P에 대해 KL(Q‖P) = 200 nats를 가집니다. Q 하에서의 경험적 위험은 0.10입니다. δ = 0.05로 설정합니다.
과매개변수화 & 이중 하강
고전적 PAC의 예측된 재앙
고전적 PAC 이론은 다음과 같이 예측합니다: 파라미터 수가 샘플 수보다 많으면 = 치명적인 과적합. 학습 데이터에서는 완벽하게 학습하고, 테스트 데이터에서는 무작위로 일반화합니다. VC 경계는 학습 없이 단순 암기를 예측합니다.
현대의 신경망은 일반적으로 학습 샘플보다 10배에서 1000배 더 많은 파라미터를 가지고도 여전히 일반화합니다. 이는 고전 이론상으로는 일어날 수 없는 현상입니다. 그러나 실제로는 일어납니다.
우리가 배운 U-곡선
고전적 편향-분산: 모델 용량이 커질수록 학습 오차는 단조롭게 감소한다. 반면 테스트 오차는 처음에는 감소하다가(과소적합 완화) 최솟값에 도달한 후 다시 증가한다(과적합). VC 이론이 예측하는 U자형 곡선이다.
실제로 일어나는 일 — 이중 하강
Belkin et al (2019)은 테스트 오차가 보간 임계점(용량 = 샘플 수)까지는 우리가 아는 U자 곡선을 따르지만, 그 임계점을 넘어서면 다시 하락한다는 것을 보였다. 매우 과매개변수화된 모델이 “충분히 큰” 모델보다 일반화 성능이 더 좋다.
고전적 PAC가 이를 놓치는 이유
1. 분포-무관 가정이 지나치게 비관적이다. 실제 데이터는 구조(낮은 내재 차원, 매니폴드 기하)를 갖는다. PAC 경계는 최악의 분포에 대해 성립하지만, 실제 분포는 SGD가 활용하는 구조를 이용한다.
2. 암묵적 정규화. 과매개변수화된 네트워크에서 SGD는 임의의 보간 해가 아니라 최소 노름 또는 최소 복잡도 보간 해를 찾는다. 고전 이론은 최악의 경우 경험적 위험 최소화자를 가정하지만, 실제 알고리즘은 양성 해를 선택한다.
3. 가설 클래스 정의 오류. SGD가 탐색하는 유효 가설 클래스는 명목상의 가중치 공간보다 훨씬 작다. PAC-Bayes 사후분포는 이를 포착하지만, VC 차원은 그렇지 않다.
현대 이론 연구(Bartlett, Long, Lugosi, Tsigler 2020의 benign overfitting; Nakkiran et al 2020의 double descent)는 과매개변수화 체제를 반영하는 post-PAC 일반화 이론을 구축하고 있다.
고전 PAC의 실패 진단
한 연구팀이 100,000개의 레이블된 예제에 대해 10억 개 매개변수 네트워크를 학습시킨다. 고전 PAC는 공허한 경계를 예측한다. 실험적으로 테스트 정확도는 95%에 도달한다.
Kaplan, Chinchilla, & Sizing Automated General Intelligence [BLOCK_TYPE CONTENT scaling_data_wall/scaling_content]
From Bounds to Empirical Scaling Laws
[BLOCK_TYPE CONTENT scaling_data_wall/scaling_content]고전 PAC는 데이터셋 크기를 이론적으로 예측하지만 공허하다. 경험적 스케일링 법칙은 관측으로부터 데이터셋 크기를 예측하며 실제로 작동한다. 대형 모델을 위한 실용적인 크기 결정 도구로서 PAC를 대체했다. [BLOCK_TYPE CONTENT scaling_data_wall/scaling_content]
[BLOCK_TYPE CONTENT scaling_data_wall/scaling_content]
Kaplan et al (2020)
손실은 파라미터 수 N, 데이터셋 토큰 수 D, 그리고 연산량 C에 대해 멱법칙(power law)을 따른다:
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
파라미터 수를 두 배로 늘리면 손실이 일정한 곱셈 인수만큼 감소한다. 데이터 양을 두 배로 늘리면 손실이 또 다른 일정한 인수만큼 감소한다. 이 지수(αN, αD, αC)는 여러 자릿수(order of magnitude) 범위에서 프론티어(frontier) 동작을 측정하고 예측한다.
Hoffmann et al 2022 (Chinchilla)
Chinchilla는 Kaplan의 지수가 파라미터 수에 비해 데이터의 중요성을 과소평가했음을 보여주었다. Compute-optimal 학습을 위해서는 대략 파라미터당 20 토큰이 필요하다:
D_opt ≈ 20 × N
GPT-3(175B 파라미터)는 약 300B 토큰으로 학습되었는데, Chinchilla 기준으로는 크게 under-trained이다. Compute-optimal한 175B 파라미터 모델은 약 3.5조 토큰이 필요하다.
The Data Wall
매개변수 수를 확장하려면 토큰 수도 비례하여 확장해야 합니다. 공개 웹 크롤은 약 10¹³개의 유용한 토큰을 산출합니다. 가상의 10¹⁵-매개변수 자동화된 범용 지능은 약 2×10¹⁶개의 토큰을 필요로 할 것입니다 — 이는 공개 웹 데이터보다 세 자릿수 더 많은 양입니다.
이것이 우리의 데이터 장벽입니다. 스케일링 법칙은 우리가 컴퓨팅 부족에 도달하기 훨씬 전에 코퍼스 부족에 직면할 것이라고 예측합니다. 합성 데이터, 멀티모달 코퍼스(비디오, 오디오, 센서 스트림), 그리고 환경 기반 강화학습(RL-from-environment)은 모두 이 장벽을 넘기 위한 시도입니다.
고전적인 PAC 이론은 (잘못된 예측으로) 10²¹개의 샘플이 필요하다고 말했습니다. 스케일링 법칙은 (현실에 맞춰 보정된) 2×10¹⁶개의 샘플이 필요하다고 말합니다. 두 숫자 모두 이용 가능한 텍스트 양을 초과합니다. 오늘날 프론티어 연구는 이 격차를 메우는 데 집중하고 있습니다.
자동화된 범용 지능 코퍼스 추정
프론티어 연구소가 10¹⁴-매개변수 모델을 제안하며, 이 모델이 자동화된 범용 지능에 도달할 것이라고 주장합니다. 우리는 Chinchilla 규칙을 사용하여 해당 모델의 학습 코퍼스 크기를 추정하고자 합니다.
From Theoretical Bounds to Production Measurements
Stop Computing Bounds; Start Measuring Them
고전적인 PAC 경계는 공허합니다. PAC-Bayes 경계는 검증하기 어려운 가정 하에서만 타이트합니다. 실질적인 대안은 실제 분포에서 ε을 경험적으로 측정하고, 시스템이 동작하는 동안 지속적으로 업데이트하는 것입니다.
아이디어 1 — 경험적 PAC로 커버리지 만들기
make coverage 타겟은 N개의 홀드아웃 질문을 쿼리 시스템에 실행하고 두 가지 비율을 측정합니다:
- cache_hit_rate — 시스템이 알려진 답변을 찾은 비율
- i_dont_know_rate — 시스템이 솔직하게 답변을 유보한 비율
각 측정 = Bernoulli 시행. 관측된 카운트로부터 실제 비율에 대한 Wilson 신뢰구간을 계산합니다. 예: N = 1000 쿼리, 관측된 i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. 상한 0.226은 δ = 0.05에서의 PAC ε과 동일한 기능을 하며, 최악의 이론적 분석이 아닌 실제 분포에 대한 실측 데이터로부터 도출됩니다.
고전적 PAC 용어(ε, δ, 신뢰도)가 그대로 적용됩니다. 사용되는 수학적 도구는 다릅니다(이항 집중 vs. VC 이론). 실제 분포가 활용 가능한 구조를 갖고 있기 때문에 더 타이트한 결과를 얻을 수 있습니다.
아이디어 2 — Falsification Events를 통한 PAC-Bayes 감사
시스템 답변이 명백히 틀린 falsification을 실제 오차율 ε에 대한 사후분포를 갱신하는 증거로 취급합니다:
1. 사전분포: ε ~ Beta(α₀, β₀). 약한 사전분포를 선택합니다. 예: Beta(1, 1) = 균등분포.
2. 각 쿼리는 Bernoulli 결과물을 생성합니다: 위조(falsified, 1) 또는 유지(held, 0).
3. n개의 쿼리 중 k개의 위조 후 사후분포: Beta(α₀ + k, β₀ + n − k).
4. 사후평균: (α₀ + k) / (α₀ + β₀ + n) → n → ∞일 때 경험적 위조율(empirical falsification rate)로 수렴.
5. ε에 대한 95% 신뢰구간은 1/√n에 따라 좁아집니다.
이것이 우리에게 주는 것
- 최악의 이론적 가정이 아닌 실제 배포에서 얻은 실세계 ε₀ 추정치
- Anytime-valid alarm: posterior credible interval이 계약 임계값을 넘으면 담당자에게 페이지 발송
- Monotone confidence: 관측된 쿼리가 많아질수록 CI가 좁아져 더 강력한 보장
관련 기법: 온라인 재보정 conformal prediction (Vovk), sequential probability ratio tests (Wald), online PAC-Bayes (Haddouche & Guedj 2022). 같은 계열이지만 수학적 도구가 다름.
Computing a Beta Posterior on Falsifications
우리 팀이 운영 중인 쿼리 시스템에 대해 coverage audit을 수행합니다. 참 오류율 ε에 대한 사전분포: Beta(1, 1) (균등). 200개의 hold-out 쿼리 중 8개의 falsification을 관측했습니다.