머신러닝: SVM이란? Linear classifiers, Dual form 공부하기!

SVM이란?

 

 

SVM이 무엇인지 알아보기 위해 다음과 같은 예를 먼저 들어보자

 

 

가로세로 축이 무게와 속도이고, 검은점은 거북이, 흰점은 토끼라 하자 

 

거북이와 토끼의 그룹을 직선하나로 나누고 싶다.

(이과정을 dicision plane을 찾는다고 한다)

 

하지만 이 그룹을 나눌 수 있는 직선은 수 없이 많고 

 

어떤 직선이 최적의 직선인지 알고 싶다.

 

여기서 최적의 직선을 구하는 방법이 바로 SVM이다.

 

 

 

 

 

 

최적의 직선을 구하기 위해서 기준을 먼저 정해야 한다.

 

우선 margin이라는 것을 생각해보자

 

margin = 직선에서 가장 가까운 점(Data point)까지의 거리

 

그렇다면 이러한 margin이 최대가 되게 하는 직선을 찾는다면 기준을

 

만족하는 직선들 중에서 최적의 직선을 찾을 수 있게 된다.

 

 

위 조건을 만족하는 w(기울기), b(y절편)를 찾아 

 

f(x, w, b) = sign(w, x-b)를 만족하는 직선을 찾는 방법이

 

Linear SVM이다.

 

 

 

 

 

그렇다면 저 직선을 찾기 위해서는 마진이 최대가 되어야 하고

 

마진은 직선에서 가장 가까운 세 점(Support Vectors)을 까지의 거리 x 2이다.

 

그렇다면 마진은 W에 대한 어떤식으로 표현될 것이다. 

 

그렇다면 저 세 점까지와 직선까지의 거리를 구해보자

 

우선 직선의 방정식은 wx +b = 0을 만족하는 x들의 집합이라 할 수 있고 

 

어떤 임의의점 x와 위 직선까지의 거리는 다음과 같이 표현된다.

 

 

 

 

 

마진 값이 다음과 같다고 하자

 

wx+b = 1이되는 직선과 wx + b = - 1이 되는 직선을 두어

 

마진을 m = 2/||w|| 이라 하자 

 

 

 

이 때 최대가 되는 margin을 찾기 위해서는 다음과 같은 조건을 만족해야 한다.

 

 

 

 

 

 

위와 같은 과정을 거쳐 최적의 직선을 찾을 수 있지만 실제로 계산이 복잡하기 때문에

 

Dual form이라는 방법을 사용한다.

 

유도과정은 생략하고 결론부터 보면

 

최대가 되는 알파는 다음과 같이 구한다.

 

 

 

 

Quadratic programming(QP)를 통해 알파를 구한다

(support vectors를 제외한 알파 값들이 0이기 때문에 계산량이 많지 않다)

 

 

알파를 구한 후 다음과 같은 과정을 통해 w를 구한다.

 

 

 

 

 

 

지금까지 linear decision boundary를 갖는 경우에서만 가능했는데

 

일반적으로 non-linear한 경우 훨씬 많다.

 

그래서 nonlinear한 경우에는 커널을 이용해 high-dimentional한 경우로 맵핑해준다.

 

 

 

맵핑하기 위해서는 커널이라는 것을 이용해야 하는데 

 

다음과 같다.

 

 

 

사실상 맵핑없이도 다음과 같이 커널(K)가 나오므로 

이를 커널 트릭(Kernal trick)이라 한다.

 

그래서 non-linear한 경우 커널 트릭을 통해 알파 값들을 구한 후

최대가 되는 W값을 구한다. 

 

후에 w를 구하고 원래 차원의 좌표를 통해 b를 구함으로써

decision plane을 찾는다.

 

 

 

 

 

 

 

출처입니다!