SVM (Support Vector machine)

1980년대 이전에는 Linear한 방법으로만 학습을하고, 분류하는 것이 이루어졌다. 그 이후인 1980년대에는 비선형기법으로 Decision Tree와 NN을 이용하여 비선형인 방법을 이용하려고 했지만, 학습하는데 있어 local minima등이 해결이 안되어 모델에 제한이 있었다. 그이후 컴퓨터학습이론이 개발되면서 효율적으로 학습이가능한 비선형 머신러닝기법이 생겨났다.

앞에서 언급한것처럼, 1980년전에는 2차원에서는 선형방법은 데이터가 있을 때, Postive / Negative와 같이 두 분류로 결정된다. SVM은 유사하게 2차원에서의 선을 한 차원 더 올려서 3차원에서 plane 형태로 만들어거 분류하고자 하는게 가장 핵심적인 컨셉이다. 

SVM을 이해하기 위해서는 3가지의 개념을 이해해야하는데, Margin, Support vector, Kernels이 그 3가지이다.

Support Vector는 Decision surface(Hyperplane)에 가장 가까운 데이터포인트(인스턴스)이다.

Margin은 이 Support 로부터의 거리이며, SVM은 margin이 가장 큰 평면을 구하는 알고리즘이다.

VC dimension: 모델이 분류가능한 경우의 수(=shattering 할 수 있는 가장 많은 수의 데이터의 수)

예를, 들어 2가지로 분류하는 경우(이를 dichotomy라고 한다),  데이터 개수가 n개라고하면  2^{n}이다. 예를 들어서, 3 개의 데이터가 2차평면에 있다고 가정하면, 

1. {}, {A,B,C} 

2. {A}, {B,C} 

...

등으로 나눌 수 있는데, 그래서 2가지를 분류하는 경우를 일반화하면, 2^{n}개이다. 그렇게, n차원에서 최대로 shatter할 수 있는 데이터 서브세트를 VC dimension이라고 한다. 2차원에서는 최대 많아봤자 3개의 데이터세트를 분류할 수 있다. 2차원에서 4개의 데이터를 다 분류할 수는 없다. 

(Source: http://www.ehu.eus/ccwintco/uploads/e/e2/Svm.pdf)

이를 일반화하면

특징: VC dimension (H) = 차원(n) +1 이다.

parmeter의 증가하면, 모델이 분류할 수 있는 경우의 수 (VC-dimension)이 증가한다. 

Margin & VC-Dimension

SVM에서 margin을 최대로해서 분류해야 한다고 한다. 이유는 데이터들이 있을 때, 그룹간의 거리가 클수록 뚜렷하게 그룹이 보일것이다. 예를 들어서, 남/북한이 구분짓는다고 가정했을 때, 38경계선을 1mm두께로하는것보다 DMZ처럼 넓게 하는 것이 좋은 분류가 될 것이다. 마찬가지로, 그 그룹안에 선을 그을 때, 중앙에 그어서, 두 집단간간의 거리, 그리고 집단과 선의 거리가 최대가 되었을 때, 잘 분류했다고 직관적으로 생각 할 수 있는데, 마찬가지로 마진을 최대로 해서 분류해야한다는게 SVM을 선택하는 기준이다. 이 Margin을 최대화 한다는 것은 VC dimension을 최소로 한다는 이야기인데, 

마진을 최대로하는 w찾기. 3차원에서의 vector은 바라보고 있는 방향의 vector와 같다. 즉, 이를 w vector라고 하면, 초평면은 다음의 수식을 따른다. wT라고 쓴 이유는 3차원의 (x,y,z)와 계산을 위해서 전치행렬(transpose)을 하기 위함이다. 즉, 다음의 식(1)에서 우리가 구해야하는 파라미터는 w, b만 있으면 된다. w는 정규화된 결정 초평면 벡터이며, x는 데이터, =을 0으로 했지만,  =y로 둔다면 , y는 데이터 포인터의 클레스이다. 

 (1)

(1)번은 초평변을 의미했다면, 분류기의 형식(표현방식)은 (2)로 설명할 수 있다.  여기서 sign함수가 나오는데, 삼각함수의 사인함수(sin)이 아니라, sign함수이다. 아래의 그레프를 보면 이해가 될텐데, 이런 형식과 유사하게 f(x)가 1보다 크면 y=+1을 출력하고, f(x)가 -1보다 작으면 -1을 출력하는 형식이다. 즉, 수의 부호를 판별하는 함수처럼 생각하면 된다. (2)번의 식에 각 x들을 넣어서 계산했을 때 1보다 크고 작은 것을 이용해서 분류할 수 있다는 말이다.

 (2)

참고로, (1)에서 0은 어짜피 상수이므로 , 정규화하여 하여서 조건을 줄 수 있는데, 이는백터의 각 요소의 크기를 1로 맞춘다는 것을 의미한다. 그렇게 조건을 주어 다음의 식을 생각해서 , 각 w와 b을 계산할 수 있게된다. 이것을 직관적으로 이해하기위해서, 2차평면에서 1차함수를 생각해보면, 1차함수 cx2= ax1+b라고 했을 때, 각 a,b,c만 알면 이 수식을 다 알 수 있다. 이 a,b,c에 2배를 하든 3배를하든 라인은 똑같은 설명을 가지게된다 유사하게, 크기를 1인 형식으로 맞춘다고 생각하면 된다. 

 (3)

Margin Maximization

조건식이 아닌 하이퍼플레인 식(1)에서 임의에 x1, x2이 하이퍼플레인 위에 있을 때,  다음의 식을 따른다.(4) 이 4번식에서 위아래의 차를 구하면 (5)식을 따르는데 이는 x1-x2벡터가 (즉 하이퍼플레인으로 뻗어있는 방향)은 w벡터와 Orthgonal(수직?)하다라는 것이다. 이것을 알면 가장가까운점 Xn과 하이퍼플레인과 거리를 구할 수 있다. 그리고 서포트벡터(가장 가까운점. Xn)과 분류기의 거리를 구하는게 중요한데 이를 d라고하면, W벡터에 Xn-x1벡터를 projection하면 Xn과 hyperplane의 거리를 측정할 수 있다(수학에서 정사영(그림자))을 구하듯이 구한 다는 것이다. 

 (4)

(5)

Xn-X1(녹색선)에 대해서 W벡터(검은색선, 거리)쪽으로 햇볕을 쪼였다고 생각했을 때, Xn과 하이퍼플레인과의 거리가 되는 것이다. 이 계산을 위해서, Xn-X1에다가 w벡터 방향에 unit벡터와 inner product을 해주면되는데, w방향의 unit vector(크기가 1인벡터)을 w hat이라고 했을 때, w벡터의 각각의 길이를 정규화(w벡터의 norm)한것이다. 이는 방향에 따라서 -가 될수도있기 때문에 W hat *(Xn-X10) = Distnace이다. 

Optimization problem

margin maximzing =max(1/||w||)= 

Hyperplane을 아래와 같이 H1은 y=1 일때라고 생각하면 빨간 점들은 wx+b >= 1인 점들이고, H2은 y=-1이라고 생각하면 wx+b<=-1인 경우이다. 서포트 벡터를 통과하고, 우리가 구하고자하는 H와 평행한 평면을각각 H1, H2라고 한다면, H1: xw+b = 1, x

H2: xi•w+b = -1

w는 weight vector이고, 하이퍼플레인을 경정한다. 

Soft margin & Hard margin

---

우리는 최적화문제를 해결하기위해서 , 보통 하드마진을 생각한다. 하드마진이란, SVM의 하이퍼플레인의 모든 분류가 완벽하게 분류해놓은 것을 이야기한다. 위의 그림처럼 모든 결과가 깔끔하게 분리된 경우를 의미한다. 그러나 이러한 경우는 Real world에서 거의 발견되지 않아, 조금은 잘못된 분류를 포함한 분류기(하이퍼플레인)가 필요한데, 이를 Soft margin(소프트 마진)이라고 한다.

이러한 소프트 마진을 고려하기위해서는 C와 gamma의 두 가지의 하이퍼 파라미터를 이해할 필요가 있다.