VC dimension과 일반화 — 표현력과 단순함의 수학적 다리

occam-mdl-kolmogorov가 단순함의 정당화를 다뤘다면, 이 노트는 단순함이 generalization에 도움이 된다는 사실의 수학적 형식화를 다룬다. Vapnik-Chervonenkis 이론은 한 줄로 요약된다 — 표현력이 클수록(hypothesis space가 풍부할수록) training error와 true error의 격차가 커진다. 이 격차를 양으로 측정하고, 그 양을 작게 하려면 표현력을 제한하라는 것.

한 그림으로

VC dim은 표현력의 측도, generalization gap은 우리가 진짜로 걱정하는 양, bias-variance는 그 gap의 실용적 분해. 이 셋이 하나의 사슬.

출발 — PAC learning이 답하려는 질문

Probably Approximately Correct (PAC) learning, Valiant (1984). 다음 두 양을 구별하는 데서 시작한다.

(이미 bias-variance-tradeoff에서 본 $\text{error}_{train}$ vs $\text{error}_{true}$의 형식화)

학습이 의미 있으려면 우리가 train으로 고른 $h$가 true 분포에서도 잘 작동해야 한다. 즉:

$|R(h) - \hat{R}(h)| \leq \epsilon \quad \text{높은 확률로}$

이 격차를 generalization gap이라 한다. PAC learning은 이 gap을 데이터 수 $n$, hypothesis space 크기, 신뢰도 $\delta$의 함수로 묶는 정리들의 모음.

VC dimension — 표현력의 측도

직접 hypothesis space의 함수 수를 세면 너무 거칠다. 무한한 hypothesis space(예: 모든 직선)를 어떻게 비교할까?

Shatter라는 개념: $h$가 $n$개 점을 임의의 라벨링으로 분리할 수 있으면, $H$가 그 $n$개 점을 shatter한다고 한다.

VC dimension $d$: $H$가 shatter할 수 있는 점의 최대 개수.

→ VC dim이 클수록 H가 다양한 라벨링을 표현할 수 있다 = 표현력이 큼 = decision-tree-structure-and-hypothesis에서 본 "hypothesis 후보가 많다"는 직관의 정량화.

PAC bound — 표현력이 generalization gap에 미치는 영향

VC theory의 핵심 정리. 직관적 형태로 (정확한 상수는 생략):

$|R(h) - \hat{R}(h)| \leq O\left(\sqrt{\frac{d \log n}{n}}\right) \quad \text{높은 확률로}$

읽는 법:

한 줄로: 표현력 $d$가 데이터 수 $n$에 비해 너무 크면 gap이 커진다. 따라서 데이터에 비해 표현력을 제한해야 한다 — 이게 simple-vs-expressive thesis의 수학적 정당화다.

Bias-Variance — 같은 사실의 직관적 형태

bias-variance-tradeoff의 분해를 PAC bound와 나란히 두면 같은 이야기가 보인다.

$\mathbb{E}[(y - \hat{f}(x))^2] = \underbrace{\text{Bias}^2}_{\text{표현력 부족}} + \underbrace{\text{Variance}}_{\text{데이터 의존성}} + \underbrace{\sigma^2}_{\text{noise}}$

둘은 같은 현상을 다른 언어로:

• Bias-variance = error의 분해 (실용적, 추정 가능)
• PAC bound = gap의 상한 (이론적, 추정 어려움)

대학 강의에서 bias-variance를 먼저 배우는 게 자연스러운 이유 — 직관이 먼저, 형식화가 다음. 그러나 두 시각을 같이 봐야 단순함 처방이 어디서 오는지 알 수 있다.

단순함이 답이라는 결론까지

PAC bound가 simple-vs-expressive thesis에 답하는 방식:

표현력 키우면 (d↑)
    ↓
training data 더 잘 맞춤 (R̂ 작아짐)
    ↓
하지만 generalization gap 커짐 (sqrt(d log n / n)↑)
    ↓
true error R = R̂ + gap, 어느 시점에 gap이 R̂ 감소를 압도
    ↓
적정 표현력에서 R 최소

→ 결론: 데이터 수에 맞는 표현력을 골라라. 그게 단순함을 강제하는 수학적 동기.

여기서 "표현력 제한"이 두 가지 형태로 나타난다:

1. 모델 자체를 작게 — 더 작은 NN, 더 얕은 트리, 더 낮은 polynomial degree
2. 모델은 크게 두되 effective $d$를 낮춘다 — regularization, dropout, early stopping

regularization-as-unified-pattern에서 후자를 자세히. 핵심은 regularization이 effective hypothesis space를 줄이는 도구라는 것.

약점 — bound가 너무 loose하다

VC theory의 가장 큰 약점이자, 4번 축 follow-up의 출발점.

Loose하다는 게 무슨 뜻

PAC bound는 최악의 경우 보장이다. 가능한 모든 분포, 가능한 모든 hypothesis 선택 알고리즘에 대해 성립한다. 그래서 실제로는 훨씬 큰 모델이 잘 작동해도 bound는 비관적인 값을 준다.

Modern NN이 보여주는 균열

VC dim으로는 over-parameterized 모델이 일반화하면 안 되는데, 실제로는 잘 한다. 이게 double descent 현상의 이론적 도전이고, occam-mdl-kolmogorov의 단순함 thesis와 정면 충돌하는 부분.

왜 loose한가

VC theory가 가정하는 것:

• 가능한 모든 분포에 대해 성립 (worst case)
• hypothesis 선택 알고리즘 무관
• 데이터의 구조를 활용하지 않음

실제 학습:

• 자연 데이터는 worst case 분포가 아니라 매우 구조화됨
• SGD 같은 알고리즘이 hypothesis 공간 안의 특정 영역으로 흐름 (implicit bias)
• 데이터의 구조와 알고리즘의 inductive bias가 결합

→ VC theory는 표현력 자체만 보지만, 실제 generalization은 표현력 + 데이터 구조 + 알고리즘 bias의 상호작용. 이걸 형식화하는 게 modern learning theory의 과제.

대안적 시각 — Rademacher complexity와 알고리즘별 분석

VC dim이 worst case라는 한계 때문에 대안 측도가 등장했다.

이 대안들은 VC dim보다 tight한 bound를 주지만 modern NN을 완전히 설명하진 못한다. 4번 축에서 다룰 implicit regularization 가설들은 이 대안들의 연장선이다.

인사이트

1. PAC bound는 simple-vs-expressive thesis의 수학적 뼈대다. 단순함을 강제하라는 처방이 미적 선호가 아니라 generalization gap의 양적 분석에서 나온다는 점이 중요.

2. Bias-variance는 PAC bound의 직관적 사촌. 강의에서 bias-variance만 배우고 PAC theory를 안 보면, "왜 그런 trade-off인가?"의 깊은 이유를 못 본다. 둘은 같은 현상의 다른 언어.

3. Bound가 loose하다는 사실 자체가 인사이트. VC theory가 정확히 들어맞지 않는 곳에서 modern ML의 흥미로운 영역이 시작된다 — 4번 축 follow-up이 자랄 토양.

4. "표현력 제한"의 두 형태를 구분하라. 모델 자체를 줄이는 것과 effective capacity를 줄이는 것은 다른 도구. 후자는 같은 모델로 더 큰 effective dataset에서 학습할 때 답을 준다.

다음 노트

• 표현력 제한의 다양한 발현(L1, L2, dropout, ...) → regularization-as-unified-pattern
• 단순함 찾기가 왜 어려운가 → simple-is-not-easy
• bound가 깨지는 영역 → 4번 축 follow-up
• 직관적 사촌 (강의 자료) → bias-variance-tradeoff