[Machine Learning] Support Vector Machine (SVM) (1)

우리에게 Leanearly separable 한 두 개의 클래스 중 하나의 클래스에 속하는 데이터셋들이 있다.

우리의 데이터셋을 두 개의 class로 구분하는 decision boundary A와 B 중 어느 것이 더 좋은 decision boundary일까?

대충 감으로도 알 수 있듯 정답은 바로 A이다.

 

그 이유는 A가 B보다 일반적인 성능이 더 좋기 때문이다.

주어진 test data들에 대한 성능만 보는 것이 아니라, 미래에 들어올 data도 잘 분류할 가능성이 높은 A가 B보다 좋다.

 

다시 말해서, A가 B보다 각 클래스 데이터에 대해 높은 margin을 주는 분류기이기 때문이다.

 

Margin이란?

Margin이란, decision boundary와 decision boundary에서 가장 가까운 data point들과의 수직 거리를 의미한다.

높은 margin을 주는 분류기일수록 성능이 더 좋다고 할 수 있다.

 

 

아까와 같은 분류기이다. A가 B보다 가장 가까운 데이터들에 대해 마진이 크므로 일반적인 성능이 더 좋은 분류기라고 할 수 있다.

여기서 SVM의 아이디어가 나왔다.

 

SVM의 아이디어

두 클래스(혹은 더 많은 클래스)에 대해 가장 큰 margin을 주는 decision boundary(hyperplane)을 찾는것이다.

이 hyperplane을 Support Vector Machine이라고 부른다.

Support vector란 decision boundary에서 가장 가까운 data들이다. data 하나하나를 vector 취급한다.

data들이 decision boundary를 지탱, 즉 support 한다.

SVM은 support vector들로 인해 만들어진 decision boundary인 것이다.

 

SVM에 대해 깊이 설명하기 전에, 간단한 수학적인 이야기를 해보도록 하겠다.

 

$X$: data(열벡터)

$g(X)$ = $w^T$$x$ + b = 0: decision boundary

$w$: weight vector & hyperplane $g(X)$ = 0의 normal vector

b: bias

 

 

$X_p$가 decision boundary에 있다면, g($X_p$) = 0

$X_a$가 decision boundary보다 위에 존재한다면 g($X_a$) > 0

$X_b$가 decision boundary보다 아래에 존재한다면 g($X_b$) < 0

 

임의의 data point X가 존재한다.

$X$에서부터 decision boundary까지의 부호있는 거리 값 r은 다음과 같다.

$$r = \frac {g(X)}{||w||}$$

 

$X$ = $X_p$ + $r$$\frac {w}{||w||}$로 나타낼 수 있다.

$X_p$가 decisioin boundary에 존재하므로 $g(X_p)$ = 0이다.

 

$g(X)$

= $w^T$$X$ + b = $w^T$ ($X_p$ + $r$$\frac {w}{||w||}$) + b

= $w^T$$X_p$ + b + $w^T$($r$$\frac {w}{||w||}$)

= $w^T$$X_p$ + b + $r$$\frac {w^Tw}{||w||}$

= $g(X_p)$ + $r$$||w||$

= $r$$||w||$

 

따라서 특정 data point $X$에서 decision boundary로 내린 수선의 발의 길이 $r$ = $\frac {g(X)}{||w||}$ 이다.

 

SVM의 Objective Function

위에서도 언급했듯, SVM의 목표는 margin maximize하는 hyperplane을 찾는 것이다.

$y$ = 1, $y$ = -1 두 개의 class가 존재할 때,

$X_+$는 $y$ = 1에 속하는 support vector들이고,

$X_-$는 $y$ = -1에 속하는 support vector들이다.

Margin r = $\frac {g(X_+)}{||w||}$ = $\frac {g(X_-)}{||w||}$ 이다.

두 클래스의 support vector들과의 margin이 같아야 decision boundary가 두 클래스의 정 가운데에 속하게 된다.

 

 

들어가기에 앞서, $w$와 b를 조정하여 다음과 같아지도록 할 것이다.

$g(X_+)$ = +1

$g(X_-)$ = -1

 

$w$와 b를 조정한다는게 잘 와닿지 않을 것 같아 예시를 들어보도록 하겠다.

$g_1(X)$ = $x_1 + 2x_2 + 4$ ,

$g_2(X)$ = $2x_1 + 4x_2 + 8$ ,

$X$ = $(x_1, x_2)$ = (1, 1)일 때, $g_1(X)$ = 7, $g_2(X)$ = 14로 다른 값이 나온다.

$w$와 b에 따라 같은 직선이지만 다른 값이 나올 수 있다는 뜻이다.

따라서 $w$와 b를 조정해 함수 값이 1 또는 -1로 나오도록 조정한다.

 

 

이렇게 조정하면 Margin r = $\frac {±1}{||w||}$ 이다.

Margin은 |r|이지만, 두 클래스의 support vector들 사이의 거리는 2 * Margin이므로

2 * Margin = 2|r| = $\frac {2}{||w||}$ 이다.

 

이제 $\frac {2}{||w||}$을 maximize하고자 한다.

=> $||w||$을 minimize하는 것과 같다.

=> $\frac {1}{2}$$||w||^2$을 minimize하는 것과 같다.

따라서 우리의 cost function의 최적의 해 $w^*$ = $\underset{w}{argmin}$$\frac {1}{2}$$||w||^2$ 이다.

 

무언가 이상하지 않은가?

위의 설명에 따르면 $w^*$ = [$w^*_1$, $w^*_2$, ... , $w^*_d$] = [0, 0, ... , 0] 이다.

이는 최고의 정확도를 위해 아무 분류도 하지 않는 것과 같다.

 

따라서 우리는 제약조건이 필요하다.

 

 

제약조건 Constraints

다음과 같은 제약조건을 추가한다.

 

class +1인 data들의 제약조건

$g(X_{+1})$ ≥  1 또는 $w^TX_{+1}$ + b ≥ 1

 

class -1인 data들의 제약조건

$g(X_{-1})$ ≤ -1 또는 $w^TX_{-1}$ + b ≤ -1



test data들에는 data point와 정답이 포함되어 있다.

따라서 어떠한 data를 넣건 올바르게 분류해야 한다는 제약조건을 추가해 모든 data에 대해 정확히 분류하면서 margin을 maximize하는 decision boundary를 찾는다.

 

위 제약조건들을 하나의 제약조건으로 표시하면 다음과 같다.

$$y_i(w^TX_i + b) ≥ 1$$

이 조건은 ($X_1, y_1$)부터 ($X_N, y_N$)까지의 모든 data에 대해 성립해야한다.

 

제약조건이 추가된 SVM의 최종 objective function은 다음과 같다.

 

min $\frac{1}{2} ||w^2||$

subject to $y_i(w^TX_i + b) ≥ 1$, ∀$i$ ∈ [1, N]

 

처음에 언급했듯 현재 나는 linearly separable한 data에 대해서 solution이 있는 SVM에 대해 설명하고 있다.

이를 Hard margin SVM이라고 한다.

 

Hard margin SVM의 optimization problem을 푸는 방법은 다음 포스트에서 설명하도록 하겠다.

[Machine Learning] Support Vector Machine (SVM) (2)