[머신러닝] 학습 가능성과 일반화 이론 (Feasibility of Learning)

기계학습의 핵심 질문은 이것입니다: 훈련 데이터에서 잘 작동하는 모델이 새로운 데이터에서도 잘 작동할 것이라고 어떻게 보장할 수 있는가?

우리는 훈련 오차 $E_{\text{in}}$ 은 계산할 수 있지만, 진짜 알고 싶은 것은 일반화 오차 $E_{\text{out}}$ 입니다. 이 둘의 관계를 정량적으로 분석하는 것이 이 글의 목표입니다.

이 글의 여정

확률 부등식에서 출발하여, 성장 함수와 VC 차원을 거쳐, PAC 학습과 라데마허 복잡도까지 — 하나의 논리적 흐름으로 연결됩니다.

1. 확률 부등식의 계층

마르코프에서 Hoeffding까지

우리가 하고 싶은 것은 " $E_{\text{in}}$ 과 $E_{\text{out}}$ 의 차이가 $\epsilon$ 보다 클 확률에 상한을 두는 것"입니다. 이것이 확률 부등식의 역할입니다.

확률변수 X가 항상 0 이상이고, 기댓값이 10이라고 합시다. 그러면 X가 100 이상일 확률에 대해 뭔가 말할 수 있을까요?

직관적으로 생각해 봅시다.

X \geq 100

인 값이 자주 나온다면, 평균이 10이 될 수 있을까요?

100 이상인 X가 1번 나올 때마다 0에 가까운 X가 9번은 나와야 평균이 10이 됩니다. 따라서 $P(X \geq 100) \leq 10/100 = 0.1$ , 즉 10% 이하입니다.

이것이 바로 마르코프 부등식입니다:

2. Union Bound와 다중 가설

단일 가설에서 가설 공간으로

Hoeffding 부등식은 고정된 가설 h 하나에 대해 성립합니다. 하지만 학습 알고리즘은 여러 가설 중에서 $E_{\text{in}}$ 이 가장 작은 것을 선택합니다.

동전을 한 번 던져서 앞면이 나올 확률은 50%입니다. 그런데 동전을 100번 던지고 그중 앞면이 나온 것만 보여준다면, "이 동전은 항상 앞면이 나온다"고 착각할 수 있겠죠. 이 비유가 학습에서 어떻게 적용될까요?

가설 공간에 가설이 M개 있다면, 각각에 대해 Hoeffding이 성립합니다. 하지만 우리가

E_{\text{in}}

이 가장 작은 가설을 선택하면, 우연히

E_{\text{in}}

과

E_{\text{out}}

이 많이 다른 "운 좋은" 가설을 고를 수 있습니다.

"M개 중 하나라도 나쁜 가설이 있을 확률"을 bound해야 합니다.

3. 성장 함수와 Shattering

가설 공간의 실효적 크기

핵심 아이디어: 가설의 개수가 아니라, 데이터에 대해 만들 수 있는 서로 다른 분류 패턴의 수로 복잡도를 측정합니다.

성장 함수 (Growth Function)

N개의 점에 대해 가설 공간 H가 만들 수 있는 서로 다른 분류의 최대 개수:

m_{\mathcal{H}}(N) \leq 2^N

m_H(N) = 2^N일 때, "H가 N개의 점을 shatter한다"고 합니다.

2차원에서 직선 분류기를 생각해 보세요. 점이 2개일 때, 점이 3개일 때, 점이 4개일 때 각각 모든 분류(2^N가지)를 만들 수 있을까요?

2개: 2² = 4가지 모두 가능 → shatter 가능 ✓
3개 (일반 위치): 2³ = 8가지 모두 가능 → shatter 가능 ✓
4개: XOR 패턴(대각선 방향으로 같은 클래스)은 직선으로 분리 불가능 → shatter 불가능 ✗

4. VC 차원 (Vapnik-Chervonenkis Dimension)

가설 공간 복잡도의 척도

VC 차원의 정의

가설 공간 H의 VC 차원은 H가 shatter할 수 있는 최대 점의 개수입니다.

2차원 직선 분류기: 3개까지 shatter 가능, 4개는 불가능 → d_VC = 3

VC 차원이 유한하면 왜 학습이 가능해질까요?

놀라운 정리가 있습니다 (Sauer의 보조정리):

VC 차원이 d_VC로 유한하면, 성장 함수가 다항식으로 bound됩니다:

m_{\mathcal{H}}(N) \leq \sum_{i=0}^{d_{\text{VC}}} \binom{N}{i} = O(N^{d_{\text{VC}}})

다항식은 지수함수 e^(-cN)보다 느리게 성장하므로, N이 커지면 bound가 줄어듭니다!

5. VC 일반화 경계

일반화 오차의 정량적 경계

VC 일반화 경계

확률 1 - δ 이상으로 다음이 성립합니다:

E_{\text{out}}(g) \leq E_{\text{in}}(g) + O\left(\sqrt{\frac{d_{\text{VC}}}{N} \ln\frac{N}{d_{\text{VC}}}}\right)

이 bound가 말해주는 것:

E_in 작아야

훈련 오차가 크면 일반화도 보장 못함

d_VC 작을수록

단순한 모델일수록 일반화 ↑

N 클수록

데이터 많을수록 gap ↓

📐 일반화 경계 계산기

VC 차원 d_VC: 10

샘플 수 N: 1000

신뢰도 1-δ: 95%

일반화 오차 상한

± 67.7%

E_out ≤ E_in + 0.677 (확률 95%)

💡 Bound가 너무 느슨합니다. N을 늘리거나 d_VC를 줄여보세요. N/d_VC 비율이 클수록 의미 있는 bound를 얻습니다.

6. PAC 학습 (Probably Approximately Correct)

학습 가능성의 형식적 정의

PAC 학습의 의미

Probably (확률 1-δ 이상으로) Approximately (오차 ε 이내로) Correct (올바른 답)

주어진 ε(허용 오차)과 δ(실패 확률)를 달성하려면 샘플이 최소 몇 개 필요할까요?

이것이 샘플 복잡도(Sample Complexity)입니다:

N = O\left(\frac{d_{\text{VC}} + \ln(1/\delta)}{\epsilon^2}\right)

이 식에서:
• ε을 절반으로 줄이면 → N은 4배 필요
• d_VC가 2배면 → N도 대략 2배 필요

7. 라데마허 복잡도 (Rademacher Complexity)

데이터 의존적 복잡도 측도

VC 차원의 한계: 데이터 분포와 무관하게 최악의 경우를 고려합니다. 실제 데이터가 특정 구조를 가지고 있다면, 더 정밀한 bound를 얻을 수 있지 않을까요?

라데마허 복잡도의 핵심 질문

가설 공간이 무작위 레이블을 얼마나 잘 맞출 수 있는가?

무작위 레이블을 잘 맞출 수 있다 = 노이즈를 외울 수 있다 = 과적합 위험

만약 가설 공간이 상수 함수 하나만 포함한다면 (항상 +1 출력), 무작위 레이블과의 상관관계는 어떻게 될까요?

각 레이블이 +1 또는 -1일 확률이 50%이므로, 상수 함수와의 상관관계 기댓값은 0입니다.

반면, 모든 가능한 함수를 포함하는 가설 공간은 어떤 레이블 패턴이든 완벽히 맞출 수 있어서 상관관계가 1이 됩니다.

요약: 학습 가능성의 조건

전체 흐름 정리

확률 부등식

마르코프 → 체비셰프 → Hoeffding

기댓값 → 분산 → 유계 조건 활용

Union Bound

단일 가설 → 다중 가설

M개 가설에 대한 동시 보장

성장 함수 & VC 차원

가설 공간의 실효적 크기

Shatter 가능한 최대 점 수

VC 일반화 경계

E_out ≤ E_in + O(√(d_VC/N))

복잡도-데이터 트레이드오프

PAC 학습

VC 유한 ↔ 학습 가능

샘플 복잡도: O(d_VC/ε²)

라데마허 복잡도

데이터 의존적 복잡도

실제 분포의 구조를 반영

핵심 메시지

VC 차원이 유한한 가설 공간은, 충분한 데이터가 있으면, 높은 확률로 좋은 일반화를 보장받습니다.

이것이 기계학습의 이론적 토대입니다.