VC 차원은 왜 신경망을 설명하지 못하는가

유한한 가설공간에서는 샘플 복잡도가 $O(\log|\mathcal{H}|)$에 비례한다는 것을 PAC Learning이 보여준다. 그런데 신경망의 가설공간은 연속 매개변수 때문에 무한하다. 그렇다면 무한 $\mathcal{H}$를 어떻게 분석할 것인가? VC 차원은 이 질문에 대한 고전적 답이다 — 그리고 현대 딥러닝은 그 답이 틀렸음을 증명한다.

Shattering — 가설공간의 표현력을 측정하는 방법

$m$개 점의 집합 $C = \{x_1, \ldots, x_m\}$에 대해, 각 점을 양/음으로 분류하는 방법은 최대 $2^m$가지다. 이 각각을 dichotomy라 부른다. 가설공간 $\mathcal{H}$가 $C$를 shatter한다는 것은 이 $2^m$가지를 모두 구현할 수 있다는 뜻이다.

$\mathcal{H}|_C := \{(h(x_1), \ldots, h(x_m)) : h \in \mathcal{H}\}, \quad |\mathcal{H}|_C| = 2^{|C|}$

VC 차원은 이를 기반으로 정의된다.

몇 가지 예시를 보면 직관이 선다. $\mathbb{R}$ 위의 threshold classifier $h_\theta(x) = \mathbb{1}[x \geq \theta]$는 VC = 1이다 — 1개 점은 shatter할 수 있지만, 2개 점에서 “왼쪽만 양”인 dichotomy를 만들 수 없다. Interval classifier $h_{a,b}(x) = \mathbb{1}[a \leq x \leq b]$는 VC = 2다. $\mathbb{R}^d$의 선형 분류기(반공간)는 VC = $d+1$이다.

성장함수와 Sauer-Shelah — 지수에서 다항으로

VC 차원은 “복잡도를 나타내는 단일 정수”지만, 일반화 경계를 유도하려면 고정 샘플 크기 $m$에서 가설공간이 실제로 얼마나 많은 dichotomy를 만드는지 알아야 한다. 이것이 성장함수다.

$\Pi_\mathcal{H}(m) := \max_{|C|=m} |\mathcal{H}|_C|$

$\text{VC}(\mathcal{H}) = d$이면 $m \leq d$에서 $\Pi(m) = 2^m$이고, $m > d$에서는 지수보다 작아진다. 얼마나 작아지는가?

Pajor의 귀납법으로 증명한다. $m$번째 점 $x^*$를 추가할 때, 나머지 $m-1$개 점의 dichotomy 중 “$x^*$의 라벨이 양/음 둘 다 가능한 것”과 “고정된 것”으로 나눈다. 고정된 dichotomy는 자유도가 1 줄어든 가설공간(VC $\leq d-1$)에서 오므로, Pascal의 항등식과 귀납 가정으로 원하는 부등식이 나온다.

기하학적 도형의 VC도 같은 틀로 이해된다. $\mathbb{R}^2$의 축정렬 직사각형은 VC = 4 ($\mathbb{R}^d$에서는 $2d$), 원판은 VC = 3, convex 집합은 VC = $\infty$다. 각 차원마다 독립적인 “interval” 2개씩 조합하므로 직사각형의 VC가 $2d$가 된다는 점이 흥미롭다.

VC 경계의 유도 — ghost sample과 union bound

Sauer-Shelah가 확보되면 무한 $\mathcal{H}$에서도 uniform convergence를 증명할 수 있다. 핵심 아이디어는 symmetrization — ghost sample $S'$를 도입해 분포 $\mathcal{D}$에 대한 의존을 제거하는 것이다.

$\mathbb{E}_{S'}[L_{S'}(h)] = L_\mathcal{D}(h)$

이므로 $|L_S(h) - L_\mathcal{D}(h)|$를 $|L_S(h) - L_{S'}(h)|$로 근사할 수 있다. 이제 $S \cup S'$ ($2n$개 점) 위에서 실현되는 dichotomy만 고려하면 되는데, 그 수는 $|\mathcal{H}|_{S \cup S'}| \leq \Pi_\mathcal{H}(2n)$으로 유한하다. 유한한 집합 위에서 Hoeffding을 적용하고 상수를 정리하면:

$\mathbb{P}_S\!\left(\sup_{h \in \mathcal{H}} |L_\mathcal{D}(h) - L_S(h)| \geq \epsilon\right) \leq 4\,\Pi_\mathcal{H}(2n)\,e^{-n\epsilon^2/8}$

Sauer-Shelah를 대입하면 샘플 복잡도가 나온다.

$m = O\!\left(\frac{d \log(1/\epsilon) + \log(1/\delta)}{\epsilon^2}\right)$

“VC 유한 $\Leftrightarrow$ PAC 학습 가능”이라는 Fundamental Theorem의 핵심 방향이 이렇게 완성된다.

현대 딥러닝과 vacuous bound

이 아름다운 이론이 현대 딥러닝 앞에서 무너진다.

ReLU 신경망의 VC 차원은 width $W$, depth $L$에 대해 $\Theta(WL \log W)$다 (Bartlett et al. 2019). ResNet-50의 경우 $W \approx 25 \times 10^6$, $L \approx 50$이므로 VC $\sim 10^9$ 수준이다. ImageNet 훈련 샘플은 $n = 1.2 \times 10^6$. 따라서 $n/\text{VC} \approx 10^{-3} \ll 1$.

$4\left(\frac{2en}{d}\right)^d e^{-n\epsilon^2/8} \gg 1 \quad \text{(ResNet-50 기준)}$

경계가 1 이상이면 “일반화 gap은 1 이하”라는 자명한 사실 이상을 말하지 못한다. Vacuous bound다.

Zhang et al. (2017)이 이 문제를 실험적으로 확인했다. ResNet은 ImageNet 랜덤 라벨 전체를 외울 수 있다 — 즉 VC $\geq 1.2 \times 10^6$. 그런데 실제 라벨로 훈련하면 test error 약 10%까지 일반화한다. VC 이론은 “random label도 외울 수 있는 모델”이 왜 “real label은 일반화하는가”를 설명하지 못한다.

돌파구는 복수의 방향에서 나왔다. Norm-based Rademacher (Bartlett, Foster, Telgarsky 2017)는 파라미터 수 대신 가중치 norm의 곱을 복잡도 척도로 쓴다. SGD stability (Hardt, Recht, Singer 2016)는 알고리즘이 implicit regularization을 수행한다는 것을 보인다 — step size와 iteration 수가 effective 복잡도를 제어한다. Neural Tangent Kernel과 double descent는 overparameterized regime을 새로운 이론적 틀로 다룬다.

정리

• Shattering은 가설공간이 점집합의 모든 $2^m$가지 dichotomy를 구현할 수 있음이고, VC 차원은 그 최대 크기다 — 선형 분류기는 $d+1$, Radon 정리가 상한을 준다.
• Sauer-Shelah Lemma는 지수 $2^m$을 다항 $(em/d)^d$로 압축한다. 이것이 무한 $\mathcal{H}$의 일반화를 가능하게 한다.