SVM intro

Introduction

---

Support Vector Machine는 이진 분류 기법입니다. 기본 Idea는 두 분류 사이에 존재하는 선형 구분선hyperplane을 찾는 것입니다.

분류대상의 값을 -1, 1이라 가정합니다. 두 분류를 구분하는 직선은 무수히 많지만, 두 분류에서 가장 멀리 떨어진 구분선을 최적 선형 구분자라할 수 있습니다.

구분 가능한 두 분류 o, x가 주어졌을 때 두 분류를 구분하는 선형 구분 방정식을 찾고자 합니다.

왼쪽 그림을 보면 두 분류를 구분하는 여러 직선이 존재한다는 것을 알 수 있습니다. 오른쪽 그림은 분류 사이이의 magin을 최대로 하는 유일한 직선을 나타낸 것입니다.

마진의 폭은 $\frac{2}{llAll}$ 입니다.

초평면은 다음 방정식으로 표현할 수 있습니다.$$Ax-b=0$$

A는 기울기를 나태는 벡터고, $x$는 입력 벡터입니다. 최대 margin의 폭은 A L2 norm 값으로 나눈 값이 됩니다. 기하학적으로 2차원상의 한점에서 직선까지의 거리를 구하는 상황입니다.

선형적으로 구분 가능한 이진 분류 데이터의 경우 margin을 최대화 하려면 A의 L2 norm값을 최소화해야 합니다. 이 최솟값은 다음 제약도 만족해야 합니다.

$$y_{i}(Ax_{i}-b)\ge 1\forall i$$

이 제한을 만족해야만 한 분류에 속하는 모든 점이 구분선의 같은 편에 족재하게 됩니다.

모든 데이터셋을 선형적으로 구분할 수 있는 것은 아니기 때문에 선을 넘어가는 점을 대상으로 한 cost function을 도입할 수 있습니다. n개의 데이터 지점에 대해 soft margin cost function은 다음과 같이 정의합니다.

$$\frac{1}{n}\sum^{n}_{i=1}max \left(0,1 - y_{i}(Ax_{i}-b) \right) +a\parallel A \parallel ^{2}$$

데이터 포인트가 올바른 자리에 있으면 $y_{i}(Ax_{i}-b)$의 값은 항상 1보다 클 것입니다. 그러면 cost function의 좌측항은 0이 되어 cont function에 영향을 미치는 부분은

$a\parallel A\parallel ^{2}$인 margin의 크기만 남게 됩니다.

이 cost function을 사용하면 데이터 포인트가 margin line 을 넘어가는 경우를 허용하는 선형 구분 직선을 찾을 수 있습니다.

$a$ 값에 따라 허용하는 정도가 느슨할 수 있고, 엄격할 수 있습니다. 

$a$ 값이 클수록 margin의 폭이 늘어나고 작을 수록 엄격한 margin을 적용하게 됩니다.