[인공지능 기초] 7. SVM(Support Vector Machine)

이번에는 분류기(classifier)로 매우 유명한 Support Vector Machine에 대해서 알아보겠다. CNN이전에 가장 많이 쓰였던 classifier이고, 지금까지도 사용되고 연구도 진행되고 있는 방식이다.

---

SVM은 Maximum Margin Classifier라고도 불린다. 말 그대로 margin을 최대화시키도록 학습이 되기 때문이다. 

 

SVM은 데이터를 비선형 매핑을 통해서 고차원으로 변환하는 과정을 거친다. 이 새로운 차원에서 데이터들을 잘 분리하는 선형 boundary(decision boundary)를 찾는 것이 SVM의 목적이다.

 

1. 왜 고차원으로 변환해야 할까?

간단한 예제를 한번 보자. 개념은 MLP와 비슷하다. 2차원에서 A=[a, d], B=[b, c]는 non-linearly seperable하지만, 이를 $\phi (x)$를 통해 3차원으로 매핑하면 linearly seperable한 것을 볼 수 있다.

 

즉, 충분히 큰 차원으로 적절한 비선형 매핑을 한다면, 데이터를 hyperplane으로 분리할 수 있다는 것이다.

 

2. Hyperplane은 어떻게 정해야할까?

좌측 그림과 같이 데이터와 hyperlane이 너무 가까우면 이상치(noise)에 대해 모델이 매우 민감해진다는 단점이 있다. 이러한 부분을 보완하기 위해서 오른쪽과 같이 margin을 두어서 hyperplane과 데이터 간에 어느정도 거리를 두게 된다.

 

두 초평면 간 거리

positive hyperplane 위에 있는 벡터 $x^+$와 negative hyperplane위에 있는 벡터 $x^-$ 사이의 관계는 다음과 같이 표현할 수 있다.

$$ x^+ \ = \ x^- + \lambda w$$

즉, $x^-$를 $w$방향으로 $\lambda$ 폭 만큼 평행이동 시킨다는 의미이다.

 

지금부터 수학 유도식이 나오니 긴장하자.....

 

이동 폭인 $\lambda$는 다음과 같이 유도가 가능하다.

$$w^T w^+ + b = 1$$

$$w^T (x^-+\lambda w ) + b = 1$$

$$w^T x^- + b + \lambda w^T w = 1$$

$$ - 1 + \lambda w^T w = 1$$

$$ \lambda = \frac{2}{w^T w}$$

 

Margin 구하기

margin은 positive hyperplane과 negative hyperplane 사이의 거리를 의미하고, 이것은 $x^+$와 $x^-$사이의 거리와 같다. $\lambda$ 값과 둘 사이의 관계식을 이용해 다음과 같이 유도가 가능하다!

 

$$Margin \ = \ distance(x^+, x^-)$$

$$\ = \ ||x^+ - x^- ||_2$$

$$\ = \ ||x^- + \lambda w - x^- ||_2$$

$$\ = \ ||\lambda w ||_2$$

$$\ = \ \lambda \sqrt{w^T w}$$

$$\ = \ \frac{2}{w^T w} \sqrt{w^T w}$$

$$\ = \ \frac{2}{\sqrt{w^T w}}$$

$$\ = \ \frac{2}{||w||_2}$$

 

3. 목적식과 제약식 정의

SVM의 목적은 마진을 최대화하는 경계면을 찾는 것이다. 계산상 편의를 위해 마진식에 제곱을 해주고 역수를 취해 최소화 식으로 바꾸면 다음과 같이 나타낼 수 있다.

$$max\frac{2}{||\omega||_2} \to min\frac{1}{2}||\omega||^2_2$$

 

추가로 제약식은 다음과 같이 정의할 수 있다.

첫번째로 positive hyperplane보다 위에 있는 관측치들에 대해서 y=1이고 $w^Tx +b$가 1보다 크다라는 조건식이고 이는,

$$w^Tx+b \gt 1 \ and \ y_i=+1$$

두번째는 negative hyperplance보다 아래에 있는 관측치들에 대해서 y=-1이고 $w^Tx+b$가 -1보다 작다라는 조건식이다.

$$w^Tx+b \le -1 \ and \ y_i=-1$$

이제 이 두 조건식을 합치면 다음과 같은 제약식으로 표현할 수 있다.

$$y_i(\omega^Tx_i+b) \ge 1$$

 

라그랑지안 문제로 변환

라그랑지안 승수법은 제약식에 라그랑지안 승수($\alpha_i$)를 곱한 항을 목적식에 더함으로써, 제약이 있는 문제를 제약 없는 문제로 바꾸는 기법이다. 여기서는 목적함수와 제약식을 한꺼번에 두고 계산하기 위해 사용된다.

$$min \ L_p(\omega, b, \alpha_i) = \frac{1}{2} ||\omega||^2_2 - \sum^n_{i=1} \alpha_i(y_i(w^Tx_i+b)-1)$$

$$=\frac{1}{2}||\omega||^2_2 + \sum^n_{i=1} \alpha_i(1-y_i(\omega^Tx_i+b)) \ \ \alpha_i \gt 0, \ \ i=1, \dots, n$$

 

3. Soft Margin SVM

위에서 설명한 SVM방식을 Hard Margin SVM이라고 한다. Hard margin이란, 두 개의 클래스를 분리하는 hyper-plane을 매우 엄격하게 구하는 방법으로 모든 입력 데이터들이 이 hyper-plane 사이인 마진 내부에 존재하면 안되고, 무조건 한 클래스에 속해야만 한다.

 

Hard Margin SVM은 노이즈로 인해 두 그룹을 구별하는 hyper-plane을 잘못 찾을 수도 있고, 최악의 경우에는 아예 찾지 못할 수도 있다. 이러한 단점을 완화하기 위해서 Soft Margin이 나오게 된다.

 

Soft Margin 방법은 기본적으로 Hard margin과 같은데 여유 변수(Slack Variable)이란 개념만 추가 되었다.

$$y_i(\omega^Tx_i+b) \ge 1 - \xi, \ \ \xi_i \ge 0 \ \ for \  \forall i$$

 

이는 Support Vector가 위치한 hyper-plane을 두고 $\xi$만큼의 오류를 인정한다는 의미이다. 이때 margin M을 최대화 하는 목적함수는 다음과 같아진다.

$$min_{\omega, b, \xi}\frac{1}{2}||\omega||^2 + C\sum \xi_i$$

 

 

여기서 C값은, 여유변수에 어느 정도의 가중치를 줄 것인가를 정하는 계수이다. 

즉, C값이 작으면 margin을 최대화 시키는 목적함수의 비중이 높고 제약식의 비중은 낮아지기 때문에 margin은 커지나 어느정도의 오류가 생길 수 있고,

C값이 크면 목적함수의 비중이 낮고, 제약식의 비중이 높아지기 때문에 마진이 작아지더라도 오류가 생기지 않도록 hyper-plane이 생성되게 된다

 

4. Non-linear SVM

현실에서는 선형으로는 분리하기 힘든 문제가 더 많다. 이러한 경우에는 liner SVM을 확장함으로써 non-linear SVM으로 만들 수 있다.

 

간단하게 그 과정을 살펴보자!

먼저 원 데이터를 비선형 매핑을 통해 고차원 공간으로 변환한다. 하지만 이렇게 고차원 매핑을 하게 되면 Maximum Marginal Hyperplane을 구하기 위한 계산 비용이 매우 많이 들게 된다.

 

이를 해결하기 위해 여기서 Kernel Trick 이란 방법을 사용한다. Kernel Trick의 원리는 데이터 튜플을 고차원으로 보낸 뒤에 벡터의 내적을 계산하는 것과 내적을 한 뒤에 고차원으로 보내는 것의 결과 값이 결과적으로 같다는  것을 이용한다.

 

따라서 커널함수와 벡터 내적은 다음과 같이 표현가능하다.

$$K(X_i, X_j) = \Phi(X_i) \cdot \Phi(X_j)$$

즉, 알고리즘에서 $ \Phi(X_i) \cdot \Phi(X_j)$를 Kernel Function $K(X_i, X_j)$로 대체할 수 있게 되어 내적에 대한 계산량 문제를 어느정도 해결해준다.

 

대표적인 Kernel Function으로는 다음 3가지가 있다.

• Polynomial Kernel of Degree h : $(X_i \cdot X_j + 1)^h$
• Gaussian Radia basis Function Kernel : $e^{-||X_i \cdot X_j||^2 / 2 \sigma^2}$
• Sigmoid Kernel : $tanh(\kappa X_i \cdot X_j - \delta)$

 

---

이렇게 SVM에 대해서 살펴보았다. 이후에도 기존 SVM에서 파생된 여러 알고리즘들이 나왔고, 아직까지 연구되고 있는 분야니까 잘 알아두면 언젠가 도움이 되지 않을까 한다. 인공지능 기초이기 때문에 너무 자세한 내용은 다루지 않았고, 이후에 심층학습 책을 정리할 때 Kernel function과 같은 부분은 더 깊게 다뤄볼 예정이다.