VC 차원 (VC Dimension)

난이도: 고급
선수 지식: PAC 학습, 기초 조합론
관련 문서: PAC 학습 | 과적합과 과소적합 | 정규화 이론 | 오컴의 면도날

핵심 요약: 모델이 얼마나 복잡한 패턴을 표현할 수 있는지의 척도. VC 차원(VC Dimension)이 높을수록 표현력이 강하지만, 그만큼 과적합(Overfitting) 위험이 커지고 더 많은 데이터가 필요하다. “모델 복잡도 vs 데이터 양”의 관계를 이론적으로 설명하는 핵심 개념이다.

---

초보자를 위한 핵심 용어

• 산산조각내기(Shattering): 어떤 점들에 대해 가능한 모든 라벨 조합을 그 모델이 만들어낼 수 있는 것. $m$개 점이면 $2^m$가지를 전부 표현할 수 있어야 한다.
• VC 차원: 산산조각낼 수 있는 점의 최대 개수. 모델의 표현력을 하나의 숫자로 나타낸 값이다.
• 성장 함수(Growth Function): 점이 $m$개일 때 모델이 만들 수 있는 서로 다른 라벨링의 수. VC 차원을 넘어서면 $2^m$에서 다항식으로 꺾인다.
• 일반화 상계(Generalization Bound): “훈련 오류와 실제 오류의 차이가 이보다 크지 않다”는 이론적 보장. 실무 수치로는 너무 헐렁하지만 방향성은 정확하다.
• Rademacher 복잡도: VC 차원의 대안. 모델이 무작위 잡음에 얼마나 잘 들러붙는지로 복잡도를 재며, 데이터에 따라 달라진다.

개요

VC 차원(Vapnik-Chervonenkis Dimension)은 가설 클래스의 복잡도(표현력)를 측정하는 척도이다. PAC 학습 이론을 무한 가설 클래스로 확장할 수 있게 해주는 핵심 개념이며, 모델이 얼마나 복잡한 패턴을 학습할 수 있는지를 수학적으로 나타낸다.

직관적으로: VC 차원이 높을수록 모델이 더 복잡한 패턴을 표현할 수 있지만, 그만큼 더 많은 데이터가 필요하다.

비유: VC 차원은 찰흙의 유연함을 재는 값이다. 뻣뻣한 판자(선형 모델)로는 만들 수 있는 모양이 몇 가지 없고, 무른 찰흙(복잡한 모델)으로는 거의 모든 모양을 만들 수 있다. 문제는 너무 무른 찰흙은 손자국까지 그대로 남긴다는 것이다 — 데이터의 잡음까지 그대로 외워버리는 과적합이다. VC 차원이 높을수록 표현력은 크지만 그만큼 더 많은 데이터로 눌러줘야 한다.

---

탄생 배경

1971년, 소련의 수학자 Vladimir Vapnik과 Alexey Chervonenkis는 논문 “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”에서 VC 차원 개념을 처음 제안했다. 이 연구의 핵심 동기는 경험적 위험(훈련 오류)이 실제 위험(테스트 오류)에 수렴하는 조건을 수학적으로 규명하는 것이었다.

이 이론적 작업은 단순한 학술적 호기심에 그치지 않았다. Vapnik은 이후 VC 이론을 기반으로 구조적 위험 최소화(Structural Risk Minimization, SRM) 원리를 발전시켰고, 이것이 1990년대에 서포트 벡터 머신(SVM)의 개발로 이어졌다. SVM은 “마진을 최대화하면 효과적 VC 차원이 줄어든다”는 VC 이론의 직접적 응용이었으며, 딥러닝 이전까지 가장 강력한 분류 알고리즘 중 하나로 군림했다.

비유: VC 차원 = 자물쇠의 핀 개수

VC 차원을 직관적으로 이해하기 위해 자물쇠(Lock)에 비유할 수 있다. 자물쇠의 핀(Pin) 개수가 VC 차원에 해당한다.

• 핀이 3개인 자물쇠: 구별할 수 있는 열쇠의 종류가 제한적이다. 몇 개의 열쇠만 시도하면 올바른 열쇠를 찾을 수 있다.
• 핀이 100개인 자물쇠: 훨씬 더 다양한 열쇠를 구별할 수 있지만(표현력이 높지만), 올바른 열쇠를 찾으려면 더 많은 시도(데이터)가 필요하다.
• 핀이 무한한 자물쇠($\sin(\omega x)$ 분류기처럼 VC 차원이 무한인 경우): 어떤 열쇠 조합도 만들 수 있지만, 올바른 열쇠를 특정하는 것이 원리적으로 불가능해질 수 있다.

이 비유는 VC 이론의 핵심 메시지를 담고 있다: 모델의 “구별 능력”이 높을수록 더 많은 증거(데이터)가 필요하다.

---

핵심 개념

1. 산산조각내기 (Shattering)

정의

가설 클래스 $H$가 점의 집합 $S = \{x_1, ..., x_m\}$를 산산조각낸다(shatters)는 것은:

$S$의 모든 가능한 레이블링 ($2^m$가지)에 대해, 그 레이블링을 완벽히 분류하는 $h \in H$가 존재한다는 것이다.

예시: 2D에서 선형 분류기와 3개의 점

3개 점에 대한 가능한 레이블링은 $2^3 = 8$가지이다. 일반 위치(general position)에 있는 3개 점에 대해 직선으로 모든 8가지 레이블링을 구현할 수 있다.

(+)(+)(+)  (+)(+)(-)  (+)(-)(+)  (-)(+)(+)
(+)(-)(-)  (-)(+)(-)  (-)(-)(+)  (-)(-)(-)

따라서 2D 선형 분류기는 3개의 점을 산산조각낼 수 있다.

4개의 점은?

2D에서 4개의 점 중 XOR 배치(대각 반대끼리 같은 레이블)를 직선으로 분류할 수 없다. 따라서 2D 선형 분류기는 4개의 점을 산산조각낼 수 없다.

숫자로 이해하기

2D 평면에서 직선(Linear Classifier)의 VC 차원을 구체적으로 확인해 보자.

• 2개 점: 가능한 레이블링(Labeling) = $2^2 = 4$가지. 직선으로 4가지 모두 분류 가능? 가능하다.
• 3개 점 (일반 위치(General Position)): 가능한 레이블링 = $2^3 = 8$가지. 직선으로 8가지 모두 분류 가능? 가능하다. → VC 차원 $\ge 3$
• 4개 점: 가능한 레이블링 = $2^4 = 16$가지. XOR 배치(대각선끼리 같은 레이블)를 직선으로 분류할 수 없다. → VC 차원 $< 4$

따라서 2D 직선의 VC 차원 = 3이다. 이는 공식 $d + 1 = 2 + 1 = 3$과 일치한다.

실무적 의미: 3D 공간의 평면이면 VC = 4, 50차원의 초평면(Hyperplane)이면 VC = 51. 모델의 파라미터(Parameter) 수가 늘어날수록 VC 차원이 커지고, 그만큼 더 많은 데이터가 필요하다.

---

2. VC 차원의 정의

$\text{VC}(H) = \text{가설 클래스 } H\text{가 산산조각낼 수 있는 점의 최대 개수 } m$

중요: VC 차원은 $m$개 점의 어떤 배치에서 산산조각냄이 가능하면 충분하다. 모든 $m$개 점의 배치에서 가능할 필요는 없다.

---

3. 주요 예시

가설 클래스	VC 차원	설명
$\mathbb{R}^d$에서의 선형 분류기	$d + 1$	2D 직선: 3, 3D 평면: 4
실수선 위의 구간	2	구간 내/외 분류
2D 볼록 다각형	$\infty$	임의의 볼록 다각형으로 무한 점 산산조각 가능
유한 가설 클래스 $\|H\|$	$\le \log_2\|H\|$	상한
신경망	$\approx$ 파라미터 수	정확한 계산은 복잡

선형 분류기의 VC 차원 = $d + 1$ 직관

• $d$차원 공간에서 선형 분류기는 $d+1$개의 파라미터($d$개 가중치 + 편향)를 가짐
• 일반 위치에 있는 $d+1$개의 점을 항상 산산조각낼 수 있음
• $d+2$개의 점은 어떤 배치에서도 항상 산산조각낼 수 없음 (라돈 정리)

---

4. 성장 함수 (Growth Function)

$\Pi_H(m) = \max_{S:|S|=m} |\{(h(x_1), ..., h(x_m)) : h \in H\}|$

$m$개 점에 대해 $H$가 만들 수 있는 서로 다른 분류의 최대 수이다.

• 산산조각낼 수 있으면: $\Pi_H(m) = 2^m$
• 산산조각낼 수 없으면: $\Pi_H(m) < 2^m$

Sauer의 보조정리

VC 차원이 $d$이면:

$\Pi_H(m) \le \sum_{i=0}^{d}\binom{m}{i} \le \left(\frac{em}{d}\right)^d$

핵심: VC 차원 $d$ 이후, 성장 함수는 지수적($2^m$)에서 다항적($m^d$)으로 전환된다.

---

5. 일반화 바운드 (Generalization Bound)

VC 바운드

확률 $\ge 1 - \delta$로:

$|\text{훈련 오류} - \text{실제 오류}| \le \sqrt{\frac{d\left(\ln\frac{2m}{d} + 1\right) + \ln\frac{4}{\delta}}{m}}$

해석

• 일반화 격차는 $\sqrt{d/m}$에 비례: VC 차원($d$) 대비 데이터 양($m$)이 클수록 격차 감소
• $m/d$가 커질수록 훈련 오류가 실제 오류에 가까워짐

실무적 관점

사실	의미
VC 바운드는 매우 느슨	직접적인 숫자보다 정성적 통찰이 가치 있음
$d$가 클수록 더 많은 데이터 필요	복잡한 모델은 더 많은 훈련 데이터 필요
경험 법칙	모델이 잘 동작하려면 $m \gg d$

---

6. Rademacher 복잡도 (간략 소개)

VC 차원의 대안으로, 데이터 의존적 복잡도 척도이다:

$\hat{R}_m(H) = E_{\boldsymbol{\sigma}}\left[\sup_{h \in H} \frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i)\right]$

여기서 $\sigma_i \in \{-1, +1\}$은 균일 랜덤 변수(Rademacher 변수)이다.

VC 차원	Rademacher 복잡도
데이터 독립적	데이터 의존적
최악의 경우 분석	실제 데이터 분포 반영
느슨한 바운드	더 타이트한 바운드
계산 용이 (많은 경우)	계산 어려울 수 있음

---

상세 내용

산산조각냄(Shattering) 시각화

VC 차원 결정 과정: $m$개 점을 산산조각낼 수 있는 배치가 하나라도 존재하면 $\text{VC}(H) \ge m$이다. $m+1$개 점은 어떤 배치에서도 산산조각낼 수 없으면 $\text{VC}(H) = m$이다.

성장 함수와 상전이 (Growth Function Phase Transition)

성장 함수 $\Pi_H(m)$의 핵심적 성질은 VC 차원 $d$ 전후로 급격한 전환이 일어난다는 것이다:

$m$ 범위	$\Pi_H(m)$ 행태	의미
$m \le d$	$= 2^m$ (지수적)	모든 레이블링 가능, 완전한 표현력
$m > d$	$\le \left(\frac{em}{d}\right)^d$ (다항적)	표현 불가능한 레이블링 존재

이 상전이가 일반화 가능성의 열쇠이다. 성장 함수가 다항적으로 제한되어야만 균일 수렴(Uniform Convergence)이 보장되고, 이에 따라 훈련 오류가 실제 오류의 좋은 추정이 된다.

Sauer-Shelah 보조정리 증명의 핵심 아이디어

수학적 귀납법을 사용한다:

1. $m = 1$일 때 자명
2. 데이터 점 하나를 제거하여 두 개의 부분 문제로 분해
3. 두 부분 문제의 성장 함수의 합이 이항 계수의 합으로 바운드됨

주요 모델의 VC 차원 비교

모델	VC 차원	근거
$\mathbb{R}^d$ 선형 분류기	$d + 1$	가중치 $d$개 + 편향 1개, 라돈 정리로 상한 증명
$k$차 다항식 분류기 ($\mathbb{R}^1$)	$k + 1$	$k$차 다항식은 최대 $k$개 영점 → $k+1$개 구간으로 분할
$\mathbb{R}^d$에서 $k$차 다항식 분류기	$\binom{d+k}{k}$	특성 공간으로 매핑 후 선형 분류기의 VC 차원
결정 트리 (깊이 $D$, 이진 특성)	$2^D$	리프 노드 수에 비례
$\sin(\omega x)$ 분류기	$\infty$	주파수 $\omega$를 조절하여 임의 점을 분류 가능
ReLU 신경망 ($W$개 파라미터, $L$개 층)	$O(WL\log W)$	파라미터 수의 거의 선형, 깊이에도 의존

신경망의 VC 차원에 대한 주의사항

• 이론적 VC 차원은 파라미터 수에 거의 비례하지만, 실제 딥러닝 모델은 파라미터 수가 데이터 수보다 훨씬 많아도 잘 일반화한다.
• 이는 VC 차원이 최악의 경우(worst-case) 분석이기 때문이다. 실제로 SGD가 찾는 가설은 가설 공간의 작은 부분집합에 속하며, 암묵적 정규화(implicit regularization)가 효과적 복잡도를 줄인다.
• 이 간극은 현대 학습 이론의 주요 연구 주제이다.

---

언제 사용하는가

VC 차원은 알고리즘이 아니라 이론적 도구이다:

• 모델 복잡도 비교 시 (어떤 모델이 더 표현력이 높은가?)
• 필요한 데이터 양의 대략적 가이드라인
• 과적합의 이론적 이해
• 학습 이론 연구의 기초

---

실전 사례: ImageNet과 VC 차원

ImageNet 데이터셋이 왜 1,400만 장이나 되는 이미지를 필요로 했는지, VC 차원 관점에서 이해할 수 있다.

ImageNet 분류에 사용되는 딥러닝 모델(예: ResNet-50)은 약 2,500만 개의 파라미터를 가진다. VC 차원은 파라미터 수에 거의 비례하므로($O(WL\log W)$), 이론적으로 수천만 이상의 데이터가 필요하다는 것이 VC 바운드의 예측이다.

실제로 초기 ImageNet 대회에서 관찰된 현상들은 이 이론과 잘 부합한다:

• 데이터셋 크기의 중요성: CIFAR-10(6만 장)에서는 단순한 모델도 높은 성능을 보이지만, 1,000개 클래스의 ImageNet에서는 대규모 모델과 대규모 데이터가 동시에 필요했다
• 전이 학습(Transfer Learning)의 성공: ImageNet으로 사전 학습한 모델이 소규모 데이터셋에서도 잘 동작하는 이유는, 사전 학습이 효과적 VC 차원을 줄이는 것으로 해석할 수 있다. 가설 공간 전체를 탐색하는 대신, 이미 유용한 표현을 학습한 부분 공간만 탐색하기 때문이다
• 데이터 증강의 효과: 회전, 뒤집기 등의 데이터 증강은 효과적 데이터 수 $m$을 늘려 $m/d$ 비율을 개선하는 것과 같다

물론 VC 바운드 자체는 매우 느슨하여 “1,400만 장이 필요하다”는 정확한 숫자를 예측하지는 못한다. 하지만 “모델이 복잡할수록 더 많은 데이터가 필요하다”는 정성적 통찰은, ImageNet 규모의 데이터셋이 왜 딥러닝 혁명의 전제 조건이었는지를 설명해 준다.

---

직접 해보기

import numpy as np
from itertools import product
# 2차원 점 3개를 직선으로 산산조각낼 수 있는가?
pts = np.array([[0,0],[1,0],[0,1]], float)
def separable(pts, labels):
    from sklearn.svm import LinearSVC
    if len(set(labels)) == 1: return True
    clf = LinearSVC(C=1e6, max_iter=100000).fit(pts, labels)
    return (clf.predict(pts) == np.array(labels)).all()
ok = all(separable(pts, list(l)) for l in product([0,1], repeat=3))
print(f"3개 점, 2^3={2**3}가지 라벨링 모두 분리 가능? {ok}")
# 4개 점 (XOR 배치)
pts4 = np.array([[0,0],[1,1],[1,0],[0,1]], float)
xor = [0,0,1,1]
print(f"4개 점 XOR 배치 분리 가능? {separable(pts4, xor)}")
print("\n-> 2차원 선형 분류기의 VC 차원 = 3")

# 실행 결과:
# 3개 점, 2^3=8가지 라벨링 모두 분리 가능? True
# 4개 점 XOR 배치 분리 가능? False

3개 점은 8가지 라벨링을 전부 직선으로 나눌 수 있지만, 4개 점의 XOR 배치는 불가능하다. 그래서 2차원 선형 분류기의 VC 차원은 정확히 3이다.

---

흔한 오해와 함정

1. “VC 차원 = 파라미터 수”

• 항상 그런 것은 아니다. 예를 들어 $\sin(\omega x)$는 하나의 파라미터 $\omega$만 있지만 VC 차원이 무한이다. 하지만 실무에서는 대략적인 근사로 사용된다.

2. “VC 바운드가 느슨하므로 VC 차원은 쓸모없다”

• 바운드가 느슨해도, “파라미터가 많으면 더 많은 데이터가 필요하다”는 정성적 메시지는 매우 가치 있다.

3. “VC 차원이 높은 모델은 항상 과적합한다”

• VC 차원이 높아도 정규화나 알고리즘의 귀납적 편향으로 효과적으로 학습할 수 있다. 딥러닝이 대표적 사례이다.

4. “산산조각내려면 모든 점 배치에서 가능해야 한다”

• 아니다. 어떤 하나의 배치에서 가능하면 충분하다. 산산조각낼 수 없음을 보이려면 모든 배치에서 불가능함을 보여야 한다.

---

스스로 점검하기

1. 2차원 평면에서 직선 분류기의 VC 차원이 3인 이유는?

정답 보기

일반 위치의 점 3개는 $2^3=8$가지 라벨링을 전부 직선으로 나눌 수 있지만, 4개 점에서는 XOR 배치를 나눌 수 없다. 그래서 최대값이 3이다.

2. VC 차원이 무한대인 모델은 학습이 불가능한가?

정답 보기

그렇지 않다. 1-NN은 VC 차원이 무한대지만 실무에서 잘 작동한다. VC 이론은 최악의 경우를 다루며, 실제 데이터 분포에는 구조가 있다. Rademacher 복잡도 같은 데이터 의존적 척도가 더 현실적이다.

3. 산산조각내기(shattering)의 정확한 정의는?

정답 보기

$m$개 점에 대해 가능한 $2^m$가지 라벨링을 전부 그 가설 클래스로 구현할 수 있는 것이다. 단, 어떤 배치 하나에서만 가능하면 충분하고 모든 배치에서 될 필요는 없다.

---

다른 주제와의 연결

• PAC 학습: VC 차원은 무한 가설 클래스에서의 PAC 학습 가능성을 결정
• 정규화 이론: 정규화는 효과적 VC 차원을 줄임
• 과적합과 과소적합: VC 차원과 일반화 격차의 관계
• 오컴의 면도날: VC 차원이 낮은(단순한) 모델 선호의 이론적 근거
• 선형 모델: VC 차원 = $d+1$인 대표적 사례

---

자주 묻는 면접 질문

1. $d$차원 선형 분류기의 VC 차원은?

   • $d + 1$

2. 4개의 동일 선상 점을 선형 분류기로 산산조각낼 수 있는가?

   • 아니다. 동일 선상이든 일반 위치이든, 2D 선형 분류기로 4개 점은 산산조각낼 수 없다 (XOR 배치)

3. VC 차원이 과적합과 어떤 관계가 있는가?

   • VC 차원이 높으면 일반화 바운드가 느슨해져 과적합 위험 증가. $m/d$가 작으면 훈련 오류와 실제 오류의 격차가 큼.

4. VC 바운드가 느슨한데도 VC 차원이 중요한 이유는?

   • 정량적 값보다 “모델 복잡도와 필요 데이터의 관계”라는 정성적 통찰이 ML의 기본 원리를 이해하는 데 핵심적

---

용어 정리

영어	한국어
VC Dimension	VC 차원
Shattering	산산조각냄
Growth Function	성장 함수
Sauer’s Lemma	사우어의 보조정리
Generalization Bound	일반화 바운드
Rademacher Complexity	라데마허 복잡도
Hypothesis Class	가설 클래스
General Position	일반 위치

---

참고 자료

• Vapnik & Chervonenkis (1971) - “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”
• Shalev-Shwartz & Ben-David (2014) - Understanding Machine Learning (Ch. 6)
• Abu-Mostafa, Magdon-Ismail, Lin (2012) - Learning from Data (Ch. 7)
• Bartlett, Harvey, Liaw, Mehrabian (2019) - “Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks”