SVM과 Kernel 보기

쓰여진 날: by Creative Commons Licence

Intro

SVM은 기본적으로 지도 학습의 한 알고리즘으로 Classification과 Regression 모두 가능한 알고리즘입니다. 1963년에 Vladimir N. Vapnik, Alexey Ya. Chervonenkis가 개발한 이후로 꾸준히 발전된 모델이고 한때는 기계학습을 대표하는 알고리즘이었습니다. 특히 커널의 발명으로 말이죠.

Backpropagation의 등장으로 인공신경망 모델이 다시 뜨면서 한물간? 알고리즘이지만 여전히 SVM을 볼 가치는 충분하죠. 딥러닝이 여전히 대세이긴 하지만, 대부분의 많은 산업에선 여전히 SVM이 강력한 알고리즘입니다. 딥러닝에 비해 필요한 데이터가 매우 적기도 하며 가장 최적의 결과를 보인다는 것도 밝혀졌으니까요.

SVM

SVM이 기본적으로 하고자 하는 건 decision boundary을 가장 잘 찾으려는 것입니다. 아래와 두개의 클래스를 가진 데이터를 분류한다고 해봅시다. 데이터는 간단하니 linearly separation이 가능해 보입니다. 즉 선은 두 클래스 사이에 그어 분류를 하는건데 그릴 수 있는 선은 매우 많죠. svm은 여기서 가장 좋은 선은 찾아 긋는 알고리즘입니다. SVM은 가장 좋은 선은 두 클래스 사이를 반으로 나누는 것이 가장 좋다고 가정합니다.

그렇다면 아래의 두 점선은 좋은 분류 기준이 아닌거 같죠. 뭔가 한쪽으로 치우져 보이니까요.

아래 저 밑의 선이 가장 좋은 분류 기준이 됩니다. 이 직선을 수식으로 나타내면 이렇습니다. $\overrightarrow{w}^{T} \overrightarrow{x}+b = 0$ 이 직선은 기준으로 직선보다 위에 있으면 class 2 아래 있으면 class 1 으로 보는거죠. 일정거리는 직선에서 가장 가까운 데이터입니다. 점선에 걸쳐있는 점이 바로 그것이고 이것을 support vector 라고 부릅니다. 그래서 두 점선 사이의 거리를 m, margin 이라고 합니다. 그러면 이 margin이 최대일 때, 즉 두 점선 사이의 거리가 가장 클 때가 직선이 가장 좋은 분류 기준이 되는 것이죠.

이제 이것을 수식으로 봅시다.

class 2를 positive $x_+$, class 1을 negative $x_-$ 이라고 보면 각 데이터는 이렇게 표현할 수 있습니다.

그런데 사실 위의 두 식은 같습니다! 아래의 식을 한 번 보죠.

각 데이터를 표현한 식 양쪽에 $y_i$ 를 곱해준 식입니다. 오른쪽 항은 $y_i$ 대신 1, -1을 곱해주었죠. 계산을 해본다면 positive 일 때와 negative 일 때 모두 위의 식이 나옵니다. 그러면 SVM은 위의 식만 만족하는 분류 기준을 찾으면 되는 것입니다.

이번엔 margin 을 어떻게 최대화할까요? Margin 은 두 점선 사이의 거리라고 하였습니다. 가장 가까워 보이는 각 클래스의 점들 사이의 거리죠. 그러면 각 두 점 사이의 거리를 다음처럼 구해봅니다. 직선에 수직인 벡터를 $\overrightarrow{w}$ 라고 하면 두 점선 사이의 거리인 margin은 다음과 같습니다.

이 margin이 최대가 되는 점이 바로 support vector 가 되는 것입니다. $max ~ \frac{2}{|w|}$ 와 같은 형태는 최대값을 구하기 어렵습니다. 그래서 $min |w|$ 와 같은 형태로 최소값을 구하는 형태로 바꾸죠. 그리고 수학적인 편리를 위해 $min \frac{1}{2}|w| ^2$ 을 구하는 문제로 바꿔줍니다.

이제 SVM은 이런 최적화 문제로 바뀌었습니다.

이 최적화 문제는 답을 구하는 방법이 이미 밝혀졌죠. 이 최적화 문제는 lagrangian 식의 gradient 가 0인 것이 최적화 값입니다. lagrangian 은 $f(x) + \sum \alpha_i g_i(x)$ 의 형태를 띄는 식으로 $\alpha$ 는 lagrangian multiplier 입니다. 위의 해답을 svm의 문제에 적용하면, 먼저 lagrangian 은

Loss 가 아닌 Lagrangian 입니다. 이제 lagrangian의 $w, b$ 에 대한 gradient를 구해봅니다. 이 둘이 모두 0이 되어야 하죠.

위의 편미분을 통해 $\overrightarrow{w}$ 와 $\sum \alpha y$을 알아내었고 이것을 기존의 lagrangian에 대입시키면 다음의 결과를 얻습니다.

이제 lagrangian 은 $\alpha$ 에 대한 함수라는 걸 알았습니다. 그리고 이러한 문제는 Dual problem 으로 알려진 문제입니다. Dual problem은 간단하게 $\overrightarrow{w}$ 을 안다면 모든 $\alpha_i$ 를 아는 것이고 모든 $\alpha_i$ 를 안다면 $\overrightarrow{w}$ 를 안다는 것입니다. w 는 $\alpha$ 값에 의해 정해지니 그렇겠죠? 그래서 dual problem 은 다음처럼 정의됩니다.

하지만 Dual problem은 문제의 정확한 해를 찾는 것이 아니고 primal problem 의 하한을 찾는 방법입니다. 그렇다면 일반적으로 dual problem으로 찾는 답을 해 라고 할 순 없지만, Karush-Kuhn-Tucker 조건이라는걸 만족하면 dual의 해와 primal의 해가 같다는 정리가 있습니다. 그리고 SVM 문제는 KKT 조건을 만족해서 결국 dual로 구한 해를 정확한 해다!! 라고 할 수가 있는 것이죠.

또 Dual problem은 장점은 Dual problem으로 해를 찾는 방법을 써야 커널 트릭을 사용할 수 있게 되는 겁니다. 사실 엄청난 이점이죠.

이것은 또 quadratic programming problem 이고 이것은 $\alpha_i$, global maximum 을 항상 찾을 수 있다고 알려져 있습니다. Global maximum 을 항상 찾을 수 있다니 너무 좋죠. Quadratic programming 을 풀면 밑의 그림과 같이 $\alpha_i$ 를 찾을 수 있습니다.

그림을 보면 대부분의 데이터에서 $\alpha$ 는 0이고 점선에 걸친 데이터에서만 $\alpha$ 가 0이 아니죠. 즉 $\alpha \neq 0$ 인 데이터가 바로 support vector 입니다. 이렇게 $\alpha$ 를 구하면 $\overrightarrow{w} = \sum \alpha_i y_i x_i$ 에 대입하여 $\overrightarrow{w}$ 를 구합니다.

Non-linear Classifier

하지만 세상의 거의 모든 실제 데이터는 선형 분류로 간단하게 해결되지 않습니다. 선형으로 해결이 되는 데이터라면 사실 SVM을 쓸 필요도 없죠. 결국 우리가 풀어야하는건 비선형 분류입니다. 커널 트릭이라는 마법 같은 방법이 나오기 전까지는 그럼 어떻게 비선형 문제를 해결했을까요? 근본적인 해결책은 아니지만 Soft margin 이라는 방법을 사용했습니다.

Soft Margin

Soft margin 은 간단히 말해 에러를 어느 정도 봐주는 방법입니다. 이 에러를 봐주는 정도는 slack variable $\xi$ 를 통해 이루어집니다. $\xi$ 는 잘못 분류된 데이터와 아래 점선과의 거리를 계산합니다. 당연히 0 이상인 $\xi$ 만 고려를 합니다. 그럼 $\xi_i = 0$ 이라면 모든 데이터가 잘 분류되었고 선형 분류로만으로도 충분하다는 이야기겠죠?

다시 Soft margin에서 분류가 어떻게 되는지 봅시다. Slack variable을 도입한 후 식을 이렇게 됩니다.

다음 최적화 문제는 이렇습니다.

여기서 C 라는 hyperparameter가 생깁니다. margin과 error 사이의 trade-off를 하는 파라미터이죠. 이후 계속해서 같은 방식으로 전개가 됩니다.

하지만 이 방법은 비선형 분류에 대한 근본적인 해결책이 아닙니다. 일단 XOR을 못푸니까요.

Kernel

XOR은 본질적으로 linear 하게 분류를 할 수가 없습니다. 한 때 MLP도 무너뜨리고 AI의 겨울을 가져온 무시무시한 녀석입니다. 하지만 1992년에 커널 트이 등장하게 됩니다. 커널 트릭이 바로 svm 을 기계학습 분야에 대세로 만든 방법이죠.

Basic Idea

커널은 쉽게 말해 더 높은 차원에서 데이터를 바라보는 것입니다. 차원이 높아지면 전 차원에서는 볼 수 없었던 것들을 쉽게 바라볼 수 있게 되죠. 이게 무슨 말인지 봅시다.

이 미로가 5cm의 벽으로 만들어졌다고 해봅니다. 만약 개미가 이런 미로를 통과한다고 하면 매우 어렵겠죠. 자기가 가는 길을 모두 기억해야 하니까요. 하지만 사람이 책상에 앉아 미로를 보면 금세 미로를 빠져나갈 길을 찾을 수 있습니다. 적어도 개미보다는 빨리요.

개미에게는 왜 미로가 어렵고 사람한테는 쉬울까요?

바로 사람은 한차원 높은 공간에서 미로를 바라보기 때문입니다. 개미는 미로 속을 돌며 2차원의 공간에서 답을 찾지만 사람은 그 위인 3차원에서 답을 찾습니다. 단지 차원이 하나만 높아졌지만 답을 찾기는 훨씬 쉬워졌죠.

영화 '인터스텔라'에서도 위기에 빠진 인류를 5차원의 존재가 도와준다고 하죠. 5차원의 존재는 인류가 절대 이해하지 못할 존재로 나옵니다.

이것이 바로 커널의 원리입니다. 데이터를 높은 차원으로 이동시켜 그 공간에서 분류를 하는 것이죠.

이 그림은 2차원에 있던 데이터를 3차원으로 바라보았습니다. 2차원에서는 불가능하던 linear 분류를 3차원에서는 면을 중간에 그음으로 가능하게 되었죠.

이해하기 쉬운 영상

이 영상을 9분부터 보시는걸 추천합니다.

Mapping

커널은 input space 에 존재하는 데이터들을 feature space 로 옮겨주는 역할을 하는 mapping 입니다. 보통은 $\phi$ 로 표기하죠. Feature space 에서의 선형 분류는 input space 에서는 비선형 분류가 됩니다. 위의 비디오에서 보았듯이요.

위 그림처럼 모든 데이터를 $\phi$ 로 mapping 하는 것입니다.

그런데 모든 데이터를 mapping 하는건 계산량이 어마어마하게 증가합니다. 또 차원을 높인다는 건, 한두 차원이 아니라 무한차원까지도 가능하죠. 높은 차원에서 또 분류를 해야하는 건 물론이고요.

Kernel

커널 트릭이 뭔지 보기 전에 커널이 뭔지 알고 갑시다.

커널은 연속함수 $K(x, y)$ 로 실수, 함수나 벡터 등등을 $x, ~ y$ 인자로 받고 실수를 내뱉는 symmetric한 함수입니다. $(K(x, y) = K(y, x)) \in {\cal R}$

그럼 SVM에서는 mapping $\phi(x)^T, \phi(x)$ 를 인자로 받고 내적하여 실수를 출력하는 것이죠. 즉 직접 mapping을 하지 않아도 될 뿐더러 몰라도 됩니다. 그냥 커널을 하나 정해서 계산하기만 하면 되죠.

그런데 여기서 궁금증이 생깁니다. 아무 커널 $K(\phi(x)^T , \phi(X))$ 를 사용한다면, 인자로 받는 mapping이 진짜 존재하는지 어떻게 알 수 있을까요? Mapping 이 존재하지 않는다면 커널의 계산은 의미가 없는 것이 되니까요. 그런데 mercer theorem 덕분에 그런 mapping 이 있다고 말할 수 있습니다.

mercer theorem

Mercer theorem: 커널 $K : [a,b]^2 \rightarrow {\cal R}$ 이 symmetric, positive-definite, continuous function 이라면, countable sequence of functions ${ \phi_i }{i \in N}$ 이 존재하고 $K(s, t) = \sum \lambda \phi(s) \phi(t)$ 를 만족하는 양수인 실수 ${ \lambda_i }{i \in N}$ 도 존재한다.

증명은 너무 길고 어렵네요…

아무튼 mercer 덕분에, 커널이 mercer condition을 만족하면, $K(x_i, x_j) = <\phi(x_i) , \phi(x_j)>$ 를 만족하는 mapping $\phi$ 가 무조건 존재합니다. 그래서 무한 차원의 feature space를 갖는 mapping도 맘껏 사용해도 됩니다. Gaussian 커널이 그 예죠.

Kernel Trick

커널 트릭이 트릭인 이유는 모든 데이터를 mapping 하지 않고 꼼수를 이용해 같은 효과를 내게 만들었기 때문입니다.

위에서 보았던 lagrangian 을 다시 한 번 봅니다.

여기서 데이터는 $x^T_ix_j$ 인데 우리는 데이터가 자체가 필요한게 아니고 데이터의 내적이 필요합니다. 이것이 무슨 말이 되냐면, feature space 에서 내적을 계산할 수 있다면 데이터의 mapping 은 굳이 구할 필요가 없다는 것입니다. $\phi(x)$ 를 구하지 않고 바로 $\phi(x_i)^T \phi(x_j)$ 를 구하면 되는 겁니다.

고차원의 각 점들을 구하는 것보다 고차원에서 내적을 바로 구해버리는 지름길 같은 trick 입니다. 그럼 이제 커널 함수를 다음 처럼 정의합니다.

커널 함수를 적용한 lagrangian 은 다음처럼 되죠.

또 똑같이 최적화 문제를 풀면 됩니다.

However…

하지만 feature space가 무한 차원이라고 해도 데이터를 항상 100% 선형 분류할 수 있다고 말할 수는 없습니다. 물론 그러니까 SVM의 정확도가 100%가 아니겠죠. 그래도 무한 차원이라는 도구는 굉장히 강력하고 잘 작동하고 있습니다. 그리고 위에서 보았던 soft margin 방법 역시 무한 차원에서도 계속 적용하기 때문에 svm은 강력한 힘을 보여주는 것입니다.

Example of Kernels

물론 커널은 정의하기에 따라 무한히 많기도 하지만, 자주 쓰이는 커널들은 정해져 있습니다.

  • Polynomial kernel $K(x,y) = (x^T y+1)^d$
  • Radial kernel $K(x,y) = exp(-|x-y|^2/(2 \sigma^2))$
  • Sigmoid kernel $K(x, y) = tanh(kx^T y + \theta)$

Reference

Ali Ghodsi

MIT 6.034 Artificial Intelligence, Fall 2010

CSE