SVM (Support Vector Machines)

하이퍼플레인

Label에 따라 벡터들을 구분하기 위한 면(선)

n 차원 공간에 대한 하이퍼플레인: b0 + b1x1 + ... + bnxn = 0

 

서포트 벡터

벡터들을 구분하는 하이퍼플레인과 가장 가까이 있는 벡터

 

마진(margin)

하이퍼플레인과 서포트 벡터 사이의 거리

 

* 목표: margin을 최대화하는 b0, b1 ... bn 값을 찾는 것

1. 점과 선 사이의 거리를 찾는 공식을 알아보자

* 법선 벡터(normal vector)란 한 평면이나 직선에 대해 수직인 벡터를 의미한다.

* ax + by = c의 법선 벡터 N은 (a, b) <내적이 0이면 서로 수직임>

** 법선 벡터를 활용하여 점(x0, y0)과 직선(ax + by + c = 0)의 거리를 구하면 absolute(ax0 + by0 + c) / root(a^2 + b^2)

 

2. ax0 + by0 + c = k로 동일하므로 margin을 최대화하기 위해서는 root(a^2 + b^2)을 최소화해야 한다.

* argmin root(a^2 + b^2)

 

3. k = 1이라고 가정하고 yi가 {-1, 1}에 속한다고 가정했을 때, yi * f(xi) >= 1이어야 한다.

* argmin root(a^2 + b^2) subjet to yi * f(xi) >= 1

* constrained optimization 사용

 

 

Not linearly separable cases

그런데 실제 데이터에 적용할 경우, hyperplane에 의해 데이터가 완벽하게 구분되는 경우는 거의 없을 것이다. 따라서 Slack 변수를 사용하거나 데이터 포인트들을 고차원 공간으로 이동시켜 분리하는 방법을 통해 해당 문제를 해결한다.

 

1. Slack 변수 사용하기 

slack 변수는 각 관측치의 에러 정도를 나타내는 역할을 한다. slack 변수를 사용함으로 최적의 hyperplane을 찾을 때, 잘못 labeling 되는 관측치의 발생을 어느 정도 허용할 수 있다. 이때 error 값은 y=1의 경우 f(x)=1과의 거리를, y=-1의 경우 f(x)=-1과의 거리를 의미한다.

 

Slack 변수까지 포함할 경우 다음과 같은 식이 도출된다. ξ(자이)는 slack 변수의 값을 의미한다.

해당 식은 margin을 되도록 크게 하면서 에러의 정도를 최소화하는 hyperplane을 찾는다는 것을 의미한다.

이때, C의 값이 커지면 slack 변수의 값이 작아져야 하므로, error를 덜 허용하게 되고 과적합이 발생할 수 있다.

 

2. 벡터를 고차원으로 이동하기

저차원의 데이터 포인트들을 고차원으로 이동시킨 후 해당 공간에서 hyperplane을 찾기 위해서는 다음 두 과정이 필요하다.

1) 데이터 포인트들을 고차원으로 이동시키기

2) 고차원에서 데이터 포인트들 사이의 내적 계산하기

 

A = [[1, 1], [1, 1], [1, 1]]이고 v = [1, 1]일 경우 Av = [2, 2, 2]가 되는데 2차원(v)에서 3차원(Av)으로 증가한 모습을 확인할 수 있다.

 

위 예시와 같이 데이터 포인트들을 고차원으로 이동시킨 후 데이터 포인트들 사이의 내적을 계산하는 방법은 시간이 오래 걸린다. 따라서 kernel function(kernel trick)을 사용하여 점들을 직접적으로 고차원으로 보내지 않고도 간단하게 고차원에서의 내적을 계산한 결과를 얻는 방법을 사용한다. 

 

Polynomial kernal function

* d의 값이 증가할수록 더 높은 차원에서의 내적값을 얻게 된다

* γ(감마) 값이 증가할수록 두 벡터의 내적값이 커지고, 두 벡터 사이의 유사도가 증가하며, 따라서 boundary의 형태가 단순해진다. 반대로 γ 값이 감소할수록 두 벡터의 내적값이 작아지고, 두 벡터 사이의 유사도가 감소하여, boundary의 형태가 복잡해진다. boundary 형태가 너무 단순하면 underfitting problem 너무 복잡하면 overfitting problem에 봉착할 수 있다.

 

 RBF(Radial Basis Function) kerel

RBF kernel은 저차원 공간의 벡터를 무한 차원(infinite dimension)으로 보내고 그곳에서의 내적을 구하는 효과가 있다.

* γ = 1/(2σ^2)이고 γ를 제외한 RBF kernel 함수에 -가 붙어 있기 때문에 γ 값이 클수록 내적값이 작아져서, Polynomial kernel function에서의 γ와 반대의 방향으로 효과를 낸다.