Ch3. SVM(Support Vector Machine)

<SVM 이란>

binary classification 에서 두 class를 분리하는 최적의 경계를 찾는 과정을 SVM이라 한다

 

SVM

 

 

위 그림처럼 $ wx-b\geq +1 $ 혹은 $ wx-b\leq -1 $ 로 데이터를 분류 하는 것이 목표이다 

 

SVM에 대해 알아볼 것은 다음과 같다

1. Margin 계산 방법
2. Soft Margin & Hard Margin
3. Kernel trick

 

<Margin 계산 방법>

SVM의 baseline은 $ wx-b=0 $ 의 해집합이다따라서, 법선벡터$ (v) $는 $ w $의 row space가 된다

$$ v=(w_1, ..., w_n)=w $$

 

원점을 지나는 법선벡터를 직선으로 나타내면 $ y=tv $ 이다

 

$ wx-b=0 $ 과 $ y=tv $ 의 교점을 $ t_1v $ 라고 하며 다음의 식을 만족시킨다

$$ wt_1v-b=0 $$

$$ t_1v=\frac{b}{w} $$

 

마찬가지로 $ wx-b=1 $ 과 $ y=tv $ 의 교점을 $ t_2v $ 라고 하며 다음의 식을 만족시킨다

$$ wt_2v-b=1 $$

$$ t_2v=\frac{b+1}{w} $$

 

두 점 사이의 거리

$$ t_2v-t_1v=\frac{1}{w} $$

 

따라서 margin은 $ \frac{2}{w} $ 이다

위 방법 말고, 점과 직선사이의 거리를 구하는 공식

$$ d=\frac{|wx_1-b|}{|w|} $$

를 이용해도 된다

 

 

 

<Hard margin & Soft margin>

hard margin과 soft margin은 이름에서 알 수 있듯

margin을 유하게 관리하냐, 강하게 관리하냐에 차이가 있다

 

Hard margin vs Soft margin

 

 

그림만 보면, Hard margin이 데이터를 더 정확하게 분류하고 더 좋은 결과를 낼 것이라고 추측할 수 있다

하지만 다음의 상황을 생각해보자

Soft margin vs Hard margin

 

 

너무 엄격하게 margin을 관리하면 분류기가 안정적이지 못하게 될 수 있다

따라서 다음의 식을 통해 적절하게 margin을 관리해야 한다

 

$$ L(w,b)=\min\frac{||w||^2}{2}+C\sum^N_{i=1}\xi_i $$

$$ s.t.\; y_i(wx_i+b)\geq 1-\xi_i $$

 

두 식을 하나로 나타내면

 

$$ \min\frac{||w||^2}{2}+C\sum^N_{i=1}\max(0,1-y_if(x_i)) $$

 

$ C $ 를 통해 soft 혹은 hard margin을 조절할 수 있으며

$ C $ 가 클 수록 hard margin에 가까워 진다

 

 

 

<Kernel Trick>

SVM은 선형분리를 위해 데이터를 고차원으로 옮긴다

데이터를 고차원으로 옮기면 선형분리 가능한 초평면을 찾을 수 있다!

 

SVM using Kernel map

 

 

그 식은 soft margin loss 식에서 라그랑주 승수법을 적용하면 찾을 수 있으며, 다음과 같다

$$ \max L_D(\alpha_i)=\sum^N_{i=1}\alpha_i-\frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j) $$

 

고차원으로 옮긴 데이터는 위의 Loss 식을 풀기 위해 내적 $ \phi(x_i)^T\phi(x_j) $ 을 해야함을 알 수 있다

 

 

여기서 아주 큰 문제가 발생한다

 

적절한 $ \phi(x) $를 찾는 것이 첫 번째 문제이며

내적 계산에 많은 시간이 소요된다는 것이다

 

여기서 두 가지 문제를 동시에 해결하기 위해 kernel trick이 등장한다

고차원의 내적 값을 미리 저장하는데, 그 값을 빠르게 계산하는 방식이다

$$ K(x_i,x_j)=\phi(x_i)\times\phi(x_j) $$

 

 

여기서 $ K $ 함수는 여러가지를 사용할 수 있다

 

1. linear kernel

$$ K(x_i,x_j)=x_i^Tx_j $$

 

2. polynomial kernel

$$ K(x_i,x_j)=(r+x_ix_j)^d $$

 

3. gaussian kernel

$$ K(x_i,x_j)=e^{-\gamma(x_i-x_j)^T(x_i-x_j)} $$