[2-1] SVM

Theoretical Foundation

이번장에서는 SVM 의 이론적 배경을 말씀드리도록 하겠습니다. 먼저, Shatter 는 동사이며, 함수 F 가 N 개의 포인트를 Shatter 할 수 있다는 의미는 함수 F 에 의해 n 개의 포인트를 임의의 +1 -1을 Target Value 로 하는 분류 경계면의 생성이 가능하다는 의미입니다.

아래 그림을 보시면 2차원 상에서 직선 분류기는 점 2개, 3개가 Shatter 가 가능합니다.

하지만, 2차원 상 직선 분류기는 점 4개 Shatter 가 가능하냐는 질문에서는 XOR 문제에 등장하는 부분이 분류가 불가능하기때문에 2차원 상에서 직선 분류기는 3개까지 Shatter 가 가능하다고 할 수 있습니다. 따라서 VC Dimension 에 대해서 말씀드릴것인데, 2차원 직선 분류기 H 의 VC Dimension 은 3입니다.

VC Dimension 에 대해서 더 살펴보도록 하겠습니다.

VC(Vapnik-Chervonekis) Dimension

VC Dimension 은 분류기에 의해서 Split 될 수 있는 점의 최대 수 입니다. 2차원에서 직선 분류기는 최대 점 3개를 Shatter 할 수 있습니다. N 차원의 VC Dimension 은 N+1 입니다.

SRM : Structural Risk Minimization

구조적 위험 리스크는 경험적 리스크와 Capacity Term 으로 구성됩니다. Capacity Term 은 $n$ 이 클수록 감소하여 구조적 위험 리스크를 줄이며, $h$ 가 클수록 Capacity Term 이 증가하여 구조적 위험 리스크를 증가 시킵니다. $n$ 은 학습 데이터 수를 의미하므로 데이터 수가 많을수록 리스크가 감소하며, $h$는 VC Dimension 을 의미하므로, VC Dimension 이 증가하ㄹ수록 리스크가 커진다고 할 수 있습니다.

당시, VC Dimension 이 증가할수록 리스크가 올라가는 아래 그림은 진리로 생각되어왔지만, 딥러닝과 같은 VC Dimension 이 높아도 다양한 오버피팅을 방지하는 기법들을 활용하여 성능이 좋아지므로 아래 그림의 설명은 위협을 받고 있습니다.

모델의 복잡도가 증가할 수록 데이터의 노이즈까지 학습할 수 있으므로 훈련 데이터 셋의 오차는 줄더라도 일반화 성능은 오히려 퇴보할 수 있습니다.

SVM (Support Vector Machine)

가능하면, 좋은 분류기란 두 데이터의 간격을 최대로 하여 일반화 성능을 높인 분류기라고 할 수 있습니다. SVM 은 이진 분류에서 다른 클래스 사이의 거리인 마진을 최대로 하는 분류기를 구축하는 것이 목적입니다.

마진은 분류 경계면서부터 한쪽 경계면 사이까지의 거리를 마진이라고 정의합니다.

하늘색 분류 경계면의 점 $x_0$ 가 있었을 때 이를 한쪽 경계면으로 벡터를 만들면 점 $x_1$ 는 크기 $p$ 와 방향 벡터 $w$ w 를 사용하여 다음과 같이 표현될 수 있습니다. 이를 풀이하면, 마진을 정의할 수 있습니다.

$$x_1 = x_0 + wp$$

$$p(margin)=\frac{1}{||w||^2}$$

SVM Hard Margin

SVM 은 마진을 벗어나는 것을 허용하지 않는 엄격한 Hard Margin 과 패널티를 받더라도 마진을 벗어나는 것을 허용하는 Soft margin 으로 구분할 수 있습니다. 이번장에서는 Hard Margin 을 보도록 하겠습니다.

$$min \frac{1}{2}||w||^2$$

라그랑주 승수법 풀이입니다. SVM 의 제약조건인 데이터들이 마진 밖에 있다는 을 가지고 목적식을 만듭니다. 그리고 라그랑지 승수는 양수값이라는 제한조건을 갖습니다. 이를 통해 최적화 식이 0일때 극값을 가지므로 KKT Condition 을 찾으면 다음과 같습니다.

Primal 문제에서 Dual 문제로 변화하여 문제를 풀기 쉬운 방식으 변환합니다.