지난 포스팅에서 보았던 교차검증은 일반화 오차를 추정하는 데 강력한 도구로 활용할 수 있지만 단점은 느리다는 점 입니다. 왜냐하면 모델을 여러 번 학습시켜야하기 때문이죠. 그래서 더 빠른 대안으로 모집단 리스크를 직접 근사하거나 상계(Upper Bound)를 구하는 방법이 연구됩니다. 이것이 바로 통계적 학습 이론(Statistical Learning Theory; SLT)의 핵심입니다.
SLT의 목적은 일반화 오차에 대한 확률적 상계를 구하는 것 입니다. 즉, 어떤 확률로 "경험적 위험을 최소화한 가설이 모집단에서도 낮은 위험을 가진다"는 보장을 주는 것이죠. 이렇게 하면 데이터에 대해 ERM을 적용했을 때 그 결과가 실제 분포에서도 잘 작동할 것이라고 수학적으로 신뢰할 수 있게 됩니다. 이진 분류기의 경우 이는 "가설이 올바른 예측을 한다는 것"을 의미합니다. 이 경우 가설은 아마도 대략적으로 정확할 것이며, 가설 클래스는 PAC 학습(Probably Approximately Correct learning) 가능하다고 합니다. 이는 쉽게 말하면 데이터가 충분히 많으면 그 가설이 새로운 데이터에서도 거의 맞게 예측한다는 것을 수학적으로 정의한 것 입니다.
1. 일반화 오차의 상계(Bounding the Generalization Error)
이제 가설 클래스가 PAC 학습 가능함을 증명할 수 있는 조건들을 정립하도록 하겠습니다. 우선 가설 공간이 유한한 경우를 가정해보겠습니다. 즉, $\text{dim}(\mathcal{H}) = |\mathcal{H}|$인 경우를 고려해보겠습니다. 다시 말해, 실제값 파라미터를 최적화하는 대신 유한한 가설의 리스트 중 하나의 가설을 선택하는 경우입니다. 이 경우, 다음과 같은 정리를 고려할 수 있습니다.
정리1. 임의의 데이터 분포 $p^{*}$와 $p^{*}$로부터 추출된 크기 $N$의 데이터셋 $\mathcal{D}$에 대해 이진 분류기의 일반화 오차가 최악의 경우보다 $\epsilon$보다 클 확률은 다음과 같이 상계된다.
$$P(\text{max}_{h \in \mathcal{H}} |R(h) - R(h, \mathcal{D})| > \epsilon) \le 2 \text{dim}(\mathcal{H})e^{-2N\epsilon^{2}}$$
여기서 $R(h, \mathcal{D}) = \frac{1}{N} \sum_{i = 1}^{N} \mathbb{I}(f(x_{i} \neq y^{*}_{i}))$는 경험적 위험이고 $R(h) = \mathbb{E} \left[ \mathbb{I}(f(x) \neq y^{*}) \right]$는 모집단의 위험이다.
증명: 이를 증명하기 전에 두 가지 중요한 보조정리를 활용해야한다. 첫번째인 Hoeffding 부등식은 $E_{1}, \dots, E_{N} \sim \text{Ber}(\theta)$일 때 임의의 $\epsilon$에 대해서 $P(|E - \theta| > \epsilon) \le 2e^{-2N\epsilon^{2}}$가 성립함을 말한다. 여기서 $E = \frac{1}{N} \sum_{i = 1}^{N} E_{i}$는 경험적 오류율이고 $\theta$는 실제 오류율이다. 두번째는 사건 $A_{1}, \dots, A_{d}$가 있을 때 $P\left( \cup_{i = 1}^{d} A_{i} \right) \le \sum_{i = 1}^{d} P(A_{i})$이다. 이 결과들을 이용하면 다음과 같이 식을 전개하면 쉽게 증명할 수 있다.
$$\begin{align} P \left(\text{max}_{h \in \mathcal{H}} |R(h) - R(h, \mathcal{D})| > \epsilon \right) &= P \left( \cup_{h \in \mathcal{H}} \{ | R(h) - R(h, \mathcal{D}) | > \epsilon \} \right) \\ &\le \sum_{h \in \mathcal{H}} P(|R(h) - R(h, \mathcal{D})| > \epsilon) \\ &\le \sum_{h \in \mathcal{H}} 2e^{-N\epsilon^{2}} = 2\text{dim}(\mathcal{H}) e^{-2N\epsilon^{2}} \end{align}$$
이 결과는 훈련 오류가 가설 공간의 크기 $\text{dim}(\mathcal{H})$가 커질수록 증가하지만 데이터의 개수 $N = |\mathcal{D}|$가 많아질수록 감소한다는 점을 보여줍니다.
2. Vapnik-Chervonenkis 차원(VC Dimension)
만약 가설 공간 $\mathcal{H}$가 무한하다면 $\text{dim}(\mathcal{H}) = |\mathcal{H}|$를 사용할 수 없습니다. 대신 Vapnik-Chervonenkis 차원(VC Dimension)이라는 양을 사용할 수 있습니다. 이는 Vapnik와 Chervonenkis의 이름을 딴 개념으로 가설 클래스의 자유도(효과적인 파라미터의 개수)를 측정하는 방식입니다.
하지만, 많은 모델들에 대해서는 VC 차원을 계산하는 것은 매우 어려운 일입니다. 또한, 상계 역시 보통 매우 느슨하기 때문에 이 접근법은 실제적으로는 제한적입니다. 그러나 최근에는 특히 심층신경망을 위해 보다 실용적인 일반화 오차 추정 방법론들이 많이 제안되어왔습니다.
