VC(Vapnik–Chervonenkis) Dimension의 정의와 의미, bound

기계학습은 데이터가 주어졌을 때 데이터와 타겟값 사이의 관계를 어떤 모델 $f$로 표현하는 것이 목적이다. 선형회귀모델, SVM, 의사결정나무 등의 여러모델이 있다. 각각의 모델이 몇개의 데이터까지 구분할 수 있는지? 수많은 데이터를 표현할 수 있는 complexity(혹은 power)를 갖고 있는지를 알면 모델마다 성능차이를 가늠할 수 있고 어떤 모델을 사용할 때 이 모델의 complexity와 한계에 맞게 모델을 사용할 수 있다. 이번 글에서는 앞서 말한 모델의 complexity(혹은 power라고 부름)을 측정하는 방법으로써 VC(Vapnik–Chervonenkis) Dimension을 소개하겠다.

VC(Vapnik-Chervonenkis) dimension의 정의

이중 분류(Binary Classification) 모델 $f:X \to Y$이 완전히 분류,구분(Shattering)할 수 있는 데이터의 최대 개수 $h$를 의미한다.

사실 위의 정의를 보면 이해하기 어려우니 예시를 보도록 하자.

VC dimension 예시

선형모델 $f(x;w,b) = sgn(w^Tx+b)$

직선을 기준으로 한쪽은 class + 다른 한쪽은 class -을 주는 경우다.

위와 같이 점이 세개인 경우 모두 분류가 된다. 그렇지만 아래와 같이 점이 네개일 경우는 직선으로 분류가 안된다.

2차원 상의 선형 모델의 VC Dimension h는 3이다.

매개변수가 두개인 원형모델(?) $f(x;b) = sgn(x^Tx+b)$

원을 만들고 원 바깥은 class + 다른 한쪽은 class -을 주는 경우다.

점이 두개 일 경우 분류가 되지 않는다.

2차원 상의 VC Dimension h는 1이다.

선형 모델과 마찬가지로 3개까지는 분류가 된다. 그런데 아래와 같이 네개는 분류가 안된다.

2차원 상의 VC Dimension h는 3이다.

여기서 잠깐 아래와 같은 경우에는 분류가 안된다고 볼 수 있다. 점 세개가 있고 이 점 세개가 직선상에 있는 경우에 선형 모델로 구분하려는 경우다.

사실 이 경우는 데이터가 직선상에 있기 때문에 이 데이터는 1차원 데이터로 볼 수 있다. 그래서 이 경우에는 선형모델을 1차원 데이터에 적용한 경우라 생각해서 vc dimension을 구한다.

위와 같이 VC를 이용하여 모델이 구분할 수 있는 데이터의 총갯수를 알 수 있다.

주요 모델의 VC dimension

주요 모델의 VC dimension은 아래와 같다.

선형 모델 : d+1 (d는 feature space의 차원)

신경망 : parameter의 갯수

k=1인 kNN : 무한대

그 이외의 모델의 VC dimension을 구하려는 시도가 있다는데 여기까진 찾아보진 않았다.

VC dimension을 이용하여 테스트 Error의 bound를 구할 수 있음

$$\displaystyle \Pr \left({\text{test error}}\leqslant {\text{training error}}+{\sqrt {{\frac {1}{N}}\left[h\left(\log \left({\tfrac {2N}{h}}\right)+1\right)-\log \left({\tfrac {\eta }{4}}\right)\right]}}\,\right)=1-\eta \tag{1}\label{1}$$

여기서 $N$은 training 데이터의 갯수 $h$는 VC dimension $\eta$는 0과 1사이의 숫자이다.

(\ref{1})의 의미는 VC Dimension $h$를 안다면 testerror의 바운드를 확률적으로 구할 수 있다는 얘기이다. 이는 모델의 성능을 평가하는 척도가 될 수 있다는 의미이다.