VC 차원 (VC Dimension)¶

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

개요¶

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

직관적으로: 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개의 점을 산산조각낼 수 없다.

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) 시각화¶

flowchart LR
    subgraph H["가설 공간 H"]
        h1["h₁"]
        h2["h₂"]
        h3["h₃"]
        h4["h₄"]
        hdots["..."]
        h8["h₈"]
    end

    subgraph S["데이터 점 3개"]
        direction TB
        p1(("x₁"))
        p2(("x₂"))
        p3(("x₃"))
    end

    subgraph L["가능한 레이블링 2³ = 8가지"]
        l1["+,+,+"]
        l2["+,+,−"]
        l3["+,−,+"]
        l4["−,+,+"]
        l5["+,−,−"]
        l6["−,+,−"]
        l7["−,−,+"]
        l8["−,−,−"]
    end

    H -->|"각 가설이\n하나의 레이블링을\n구현"| L
    S -->|"모든 레이블링이\n실현 가능하면\nShattering 성공"| L

    style H fill:#e3f2fd
    style S fill:#fff3e0
    style L fill:#e8f5e9

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 차원은 알고리즘이 아니라 이론적 도구이다:

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

흔한 오해와 함정¶

1. "VC 차원 = 파라미터 수"¶

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

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

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

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

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

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

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

다른 주제와의 연결¶

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

자주 묻는 면접 질문¶

\(d\)차원 선형 분류기의 VC 차원은?
\(d + 1\)
4개의 동일 선상 점을 선형 분류기로 산산조각낼 수 있는가?
아니다. 동일 선상이든 일반 위치이든, 2D 선형 분류기로 4개 점은 산산조각낼 수 없다 (XOR 배치)
VC 차원이 과적합과 어떤 관계가 있는가?
VC 차원이 높으면 일반화 바운드가 느슨해져 과적합 위험 증가. \(m/d\)가 작으면 훈련 오류와 실제 오류의 격차가 큼.
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"