Mathematics of Support Vector Machine

SVM의 수학

Key Questions

• Support Vector Machine (SVM)의 알고리듬을 수학적으로 어떻게 도출할 수 있을까?
• 보다 직관적으로 이해할 수 있는 방법은 없을까?

Key Synopsis

• SVM은 기본적으로 최소화(minimize)를 한 후 이를 다시 극대화(maximize)를 하는 최대최소(maxmin) 형태의 최적화 문제이다.
  • 최소화: 분류(classification)의 기준이 되는 두 영역을 나누는 하이퍼플레인을 찾은 후 이 하이퍼플레인과 가장 가깝게 위치하는 두 영역의 벡터(서포트 벡터)를 찾는다.
  • 최대화: 분류 기준이 되는 하이퍼플레인과 평행한 두 서포트 벡터를 지나는 하이플레인의 거리를 최대화 한다.
• 이 maxmin 문제를 풀면 목적함수에는 training set에 속한 벡터들의 닷 프로덕트만 남게 되고, 덕분에 최적화 문제가 단순해진다.
• 이 닷 프로덕트들로 구성된 부분을 다른 함수 형태로 바꿔서 SVM 알고리듬의 ’커널’을 유연하게 바꿀 수 있다. 이것이 커널 트릭 (Kernel trick)이다.

SVM Mathematically

Preliminary concepts

Length of a vector

벡터 $\mathbf{x}=(x_1,x_2,\dots ,x_n)$ 의 벡터의 길이, 즉 유클리드 노름(norm), 은 다음과 같이 정의된다.

$$\Vert \mathbf{x}\Vert =\sqrt{x_1^2+x_2^2+\dots +x_n^2}$$

Direction of a vector

벡터 $\mathbf{x}$의 방향성 $\mathbf{w}$는 다음과 같이 정의할 수 있다.

$$\mathbf{w}=({\displaystyle \frac{x_1}{\Vert \mathbf{x}\Vert }},{\displaystyle \frac{x_2}{\Vert \mathbf{x}\Vert }})$$

그림으로 나타내보자.

이는 다음과 같이 삼각함수로 표시할 수 있다. $$\mathbf{w}=(\cos \theta ,\cos \alpha )$$

Dot product (inner product)

내적은 벡터 연산의 일종으로, 이는 두 벡터를 스칼라 값으로 바꿔주는 일종의 함수다.

$$\begin{array}{rl}\cos \theta & =\cos (\beta -\alpha )\\ \\ & =\cos \beta \cos \alpha +\sin \beta \sin \alpha \\ \\ & ={\displaystyle \frac{x_1}{\Vert \mathrm{x}\Vert }}{\displaystyle \frac{y_1}{\Vert \mathrm{y}\Vert }}+{\displaystyle \frac{x_2}{\Vert \mathrm{x}\Vert }}{\displaystyle \frac{y_2}{\Vert \mathrm{y}\Vert }}\\ \\ & ={\displaystyle \frac{x_1{y}_1+x_2{y}_2}{\Vert \mathrm{x}\Vert \Vert \mathrm{y}\Vert }}\end{array}$$

이를 아래와 같이 정리할 수도 있다.

$$\mathrm{x}\cdot \mathrm{y}=\Vert \mathrm{x}\Vert \Vert \mathrm{y}\Vert \cos \theta$$

Hyperplane

$n$ 차원 공간을 가를 수 있는 해당 공간의 차원보다 하나 낮은 수학적 관계라고 풀어서 쓸 수 있다.

• 즉, $x_1$이나 $x_2$ 중 하나만 주어지면 나머지 위치가 주어진다.
  
• 쉽게 $y=x+1$의 직선을 생각하면 된다. 2차원 평면에서 $x$의 값이 주어지면 y값이 정해진다. 이 직선은 2차원 평면에 위치하지만 사실상 1차원의 속성을 지니게 된다.

$\mathbf{x}=(x_1,x_2)$의 벡터가 있다고 할 때, 하이퍼플레인은 벡터 $\mathbf{w}$와 $b$에 의해 정의된다. 즉,

$$\mathbf{w}\cdot \mathbf{x}+b=0$$

Classifier

하이퍼플레인을 기준으로 클래시파이어를 다음과 같이 정의한다. 특정한 관찰 벡터 $\mathbf{x}$가 있다고 하자. 이때 분류 $h$의 정의는 아래와 같다.

$$h(\mathbf{x})=\{\begin{array}{ll}+1& \text{if}\mathbf{w}\cdot \mathbf{x}+b\ge 0\\ \\ -1& \text{if}\mathbf{w}\cdot \mathbf{x}+b<0\end{array}$$

Explained Visually

그림으로 보다 직관적으로 이해해보자.

어떤 원점을 기준으로 training example까지의 벡터를 ${\mathbf{x}}_i$라고 하자. 이때 둘을 가르는 하이퍼플레인이 있을 때 이와 직교하는 벡터 (orthogonal vector) $ $를 생각해보자. 왜 orthogonal해야 하는가? 잠시 후 그 이유를 알 수 있다. 하이퍼플레인은 기본적으로는 두 벡터 사이의 닷 프로덕트다. 닷 프로덕트를 그림으로 나타낼 수 있는 방법은 이를 projection으로 생각해보는 것이다.

내적이라고 번역되기도 하지만 여기서는 그냥 ’닷 프로덕트’라고 쓰리고 하겠다.

즉, ${\mathbf{x}}_i$를 $ $로 프로젝션을 한다면(projection of ${\mathbf{x}}_i$ on $ $), 이는

$${\text{Proj}}_{\mathbf{w}}{\mathbf{x}}_i={\displaystyle \frac{\mathbf{w}\cdot {\mathbf{x}}_i}{\Vert \mathbf{w}\Vert }}$$

닷 프로덕트의 부분이 시각적으로는 projection 결과 곱하기 $\Vert \mathbf{w}\Vert$로 나타난다. 즉, ${\mathbf{x}}_i$에서 $\mathbf{w}$를 향해 내린 선분이 프로젝션이고 이를 $\Vert \mathbf{w}\Vert$로 스케일링 한 $\mathbf{w}$ 위에서의 길이가 닷 프로덕트를 시각적으로 나타낸 것이다. 이 프로젝션의 길이에 따라서 해당 트레이닝 샘플이 어떤 것으로 분류될지에 관해서 파악할 수 있다. $\Vert \mathbf{w}\Vert$가 고정되어 있다고 하면, 프로젝션의 크기가 일정 숫자보다 크면 분류의 오른쪽에 작으면 분류의 왼쪽에 위치하는 것이다. 이를 아래와 같이 표시해보자.

$$\mathbf{w}\cdot {\mathbf{x}}_{\mathrm{r}}+b\ge 1$$

$$\mathbf{w}\cdot {\mathbf{x}}_{\mathrm{l}}+b\le 1$$

프로젝션의 길이가 일정한 기준보다 길면 오른쪽에 짧으면 왼쪽에 위치한 것으로 분류할 수 있다. 이 조건을 $y_i$와 함께 나타내보자. 즉,

$$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\ge 0$$

앞서 분류기에서 해당 값이 0보다 크면 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\ge 0$가 성립한다. 반면, 해당 값이 0보다 작으면 음수를 곱하는 것이 되어 부등호가 바뀌게 되고, 이 경우 역시 위의 식이 성립한다.

이제 $\cos \theta$를 벡터 ${\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}}$와 $\mathbf{w}$가 이루는 각이라고 생각하자. 이때 $\mathbf{w}$는 하이퍼플레인과 orthogonal하며 적절한 training sample 즉, 적절한 하나의 서포트 벡터를 지난다. 이때 $\cos \theta$는 다음과 같이 쉽게 정의된다.

벡터의 방향에 대해서 약간 갸우뚱하는 분들이 있을지 모르겠다. $\cos \theta$를 제대로 정의하기 위해서는 $-({\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}})$, $-\mathbf{w}$라고 쓰는 것이 맞을 것이다. 하지만, 둘의 닷 프로덕트를 구하면 서로 상쇄되어 아래 적은 것과 동일하다.

$$\cos \theta ={\displaystyle \frac{({\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}})\cdot \mathbf{w}}{\Vert {\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}}\Vert \Vert \mathbf{w}\Vert }}$$

한편, 하이퍼플레인과 평행하면서 서포트 벡터를 지나가는 하이퍼플레인의 거리 ${\mathrm{\Delta }}_{\mathbf{x}}$는 다음과 같다.

$${\displaystyle \frac{{\mathrm{\Delta }}_{\mathbf{x}}}{\Vert {\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}}\Vert }}=\cos \theta ={\displaystyle \frac{({\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}})\cdot \mathbf{w}}{\Vert {\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}}\Vert \Vert \mathbf{w}\Vert }}$$

따라서

$${\mathrm{\Delta }}_{\mathbf{x}}={\displaystyle \frac{({\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}})\cdot \mathbf{w}}{\Vert \mathbf{w}\Vert }}$$

$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1=0$의 양변에 $y_i$를 곱하면, $y_i^2(\mathbf{w}\cdot {\mathbf{x}}_i+b)=y_i$가 된다. $y_i^2=1$이므로,

$$\begin{array}{rl}{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}\cdot \mathbf{w}+b& =1\\ {\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}}\cdot \mathbf{w}+b& =-1\end{array}$$

여기서 $({\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{r}}-{\mathbf{x}}_{\mathrm{s}\mathrm{v}\mathrm{l}})\cdot \mathbf{w}=2$를 쉽게 도출할 수 있다. 결론적으로 두 서포트 벡터 사이의 거리를 최대화하는 문제는 $\Vert \mathbf{w}\Vert$를 최소화하는 문제와 같다.

Optimization for SVM

Metrics to compare hyperplanes

Defining functional margin

$f_i=y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)$가 있다고 하자. 이때 분류가 제대로 이루어졌다면, $f_i$의 부호는 언제나 양수다. 위의 분류의 정의에 따르면 그렇다. 데이터 셋 $D$의 정의는 다음과 같다.

$$D={\{({\mathbf{x}}_i,y_i)\mid {\mathbf{x}}_i\in {\mathbb{R}}^n,y_i\in \{-1,1\}\}}_{i=1}^m$$

펑셔널 마진(functional margin)이라고 불리는 $F$ 는 다음과 같다.

$$F=\underset{i=1,\dots ,m}{min}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)$$

$\mathbf{w}$와 $b$로 정의되는 하이퍼플레인이 모든 트레이닝 셋을 잘 분류했다면, $f_i>0$가 성립한다. 이 $f_i$ 중 가장 작은 값이 functional margin이다. 그리고 두 번째로 서로 다른 하이퍼플레인 중에서 가장 큰 $F$를 지니는 하이퍼플레인이 최적이 하이퍼플레인이다.

1. $F$를 얻기 위한 과정에서 최소화 로직이 들어간다. 즉, 해당 하이퍼플레인과 가장 가깝게 위치한 관측치를 얻어내는 과정
2. 이렇게 얻어낸 $F$들을 서로 다른 하이퍼플레인들 사이에 비교하고, 가장 큰 $F$를 주는 하이퍼플레인을 채택한다.

표준화를 위해서 $\mathbf{w}$의 norm으로 $f_i$ 값을 나누고 극대화 문제를 정식화하면 아래와 같다.

Derivation of SVM optimization problem

표준화를 위해서 $\Vert \mathbf{w}\Vert$로 목적함수와 제약을 나누자.

$$\underset{\mathbf{w},b}{max}M\text{s.t.}{\gamma }_i\ge M\text{for}i=1,\dots ,m$$

where

$${\gamma }_i=y_i({\displaystyle \frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }}\cdot {\mathbf{x}}_i+{\displaystyle \frac{b}{\Vert \mathbf{w}\Vert }})$$

$$M=\underset{i=1,\dots ,m}{min}{\gamma }_i$$

표준화된 펑셔널 마진을 최대화하되, 트레이닝 샘플들이 이것보다 커야 한다는 조건(최소화)이 제약으로 들어간다. 즉, 아래의 식은 최소화 제약 하에서 $F$를 최대화한다는 이중 최적화 과정을 보여 준다.

$$\underset{\mathbf{w},b}{max}{\displaystyle \frac{F}{\Vert w\Vert }}\text{s.t.}{f}_i\ge F\text{for}i=1,2,\dots ,m$$

위 극대화 문제에서 모든 변수는 상대값으로 정의할 수 있으므로 $F$를 1로 제한해도 해는 바뀌지 않는다. 그리고 아래와 같은 차례로 정식화할 수 있다.

$$\underset{\mathbf{w},b}{max}{\displaystyle \frac{1}{\Vert w\Vert }}\text{s.t.}{f}_i\ge 1\text{for}i=1,2,\dots ,m$$

$$\underset{\mathbf{w},b}{min}\Vert w\Vert \text{s.t.}{f}_i\ge 1\text{for}i=1,2,\dots ,m$$

$$\underset{\mathbf{w},b}{min}{\displaystyle \frac{1}{2}}{\Vert w\Vert }^2\text{s.t.}{f}_i\ge 1\text{for}i=1,2,\dots ,m$$

Optimization by Wolfe duality

제약 하의 극대화 문제이므로 라그랑주 최적화로 바뀌서 볼 수 있다. 다음과 같이 라그랑주 방정식을 정의하자.

$$\mathcal{L}(\mathbf{w},b,\mathit{\alpha })=\frac{1}{2}\mathbf{w}\cdot \mathbf{w}-\sum _{i=1}^m{\alpha }_i[y_i(\mathbf{w}\cdot \mathbf{x}+b)-1]$$

여기서 벡터 $\mathit{\alpha }$는 라그랑주 최적화의 라그랑주 승수로 제약식을 반영하는 부분이다.
일단, ${\alpha }_i$를 무시하고 두 최적화 변수인 $\mathbf{w}$와 $b$ 에 대해서면 1계 조건을 풀면 다음과 같다.

$$\begin{array}{rl}{\mathrm{\nabla }}_{\mathbf{w}}\mathcal{L}(\mathbf{w},b,\mathit{\alpha })& =\mathbf{w}-\sum _i^m{\alpha }_i{y}_i{x}_i=0\\ {\mathrm{\nabla }}_b\mathcal{L}(\mathbf{w},b,\mathit{\alpha })& =-\sum _i^m{\alpha }_i{y}_i=0\end{array}$$

이 녀석들을 다시 라그랑주 방정식에 대입하면, $\mathit{\alpha }$로만 된 일종의 maximal function 혹은 라그랑주 방정식의 하한(infimum)을 만들 수 있다. Wolfe duality에 따르면, 최소화 최대화를 한 번에 푸는 것과 한 가지 문제를 먼저 푼 후 해당 결과를 목적 함수에 넣고 두 번째 문제를 순차적으로 푸는 것이 동일하다. 따라서 위의 일계 조건을 목적 함수에 넣은 목적함수는 구해보자.

$$W(\mathit{\alpha })=\sum _{i=1}^m{\alpha }_i-{\displaystyle \frac{1}{2}}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i\cdot {\mathbf{y}}_j$$

이제 문제는 $\mathit{\alpha }$에 관해서 극대화 문제를 푸는 것으로 바뀐다. 즉,

$$\underset{\mathit{\alpha }}{max}W(\mathit{\alpha })\text{s.t.}{\alpha }_i\ge 0,\sum _{i=1}^m{\alpha }_i(y_i(\mathbf{w}\cdot {\mathbf{x}}^{\ast }+b)-1)=0$$

제약 부분이 부등식이므로 KT(Kuhn-Tucker) 조건에 따라서 풀면 된다.

$${\alpha }_i[y_i(\mathbf{w}\cdot {\mathbf{x}}^{\ast }+b)-1]=0$$

KT 조건이란 부등식 제약을 푸는 테크닉이다. 즉, ${\alpha }_i>0$의 제약이 유효하다면 제약을 만족시키기 위해서는 $y_i(\mathbf{w}\cdot {\mathbf{x}}^{\ast }+b)-1=0$이 만족해야 한다. 이렇게 제약이 걸리는 경우에 위치한 $x^{\ast }$가 바로 ’서포트 벡터’다. 반면, ${\alpha }_i=0$는 제약이 등호로 걸릴 필요가 없는 트레이닝 셋의 관찰들이다. 이들은 분류 하이퍼플레인까지의 길이가 서포트 벡터의 길이보다 크다.

Compute w and b

$\mathbf{w}$ 의 경우 1계 조건에서 쉽게 얻을 수 있다.

$$\mathbf{w}-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i=0$$

한편, $b$의 경우 서포트 벡터의 경우 위에서 본 것 같이 제약 식의 등호가 성립한다. 즉, 서포트 벡터를 $x^{\ast }$라고 할 때,

$$y_i(\mathbf{w}\cdot {\mathbf{x}}^{\ast }+b)-1=0$$

• 양변에 $y_i$를 곱하면, $y_i^2=1$이므로,

$$b=y_i-\mathbf{w}\cdot {\mathbf{x}}^{\ast }$$

• 서포트 벡터가 S개 존재할 경우라면,

$$b={\displaystyle \frac{1}{S}}\sum _{i=1}^S(y_i-\mathbf{w}\cdot {\mathbf{x}}_i^{\ast })$$

Limitation

앞서 본 것을 이른바 hard margin SVM이다. 즉, 서포트 벡터 사이의 마진을 획일적으로 적용하는 분류 알고리듬이다. 하드 마진 SVM은 다음의 두가지 경우에 취약하다.

데이터에 노이즈가 있을 경우

하드 마진의 큰 문제는 아웃라이어에 취약할 수 밖에 없다는 것이다. 풀어서 말하면 제약이 선형이고 그 제약이 강력하다는 데 있다. 트레이닝 데이터에 이런 저런 노이즈가 있을 경우 하드 마진은 아예 계산이 불가능할 수 있다. 이때 사용하는 기법이 soft margin SVM이다.

데이터 자체가 선형으로 분리되지 않을 경우

애초부터 데이터 자체가 선형을 통한 분류를 허용하지 않을 경우에는 비선형 분류를 사용할 수 있다. 이때 동원하는 테크닉이 커널 트릭 (kernel trick)이다.

Soft Margin SVM

제약을 약간 풀어주는 $\zeta$를 도입하여 최적화 문제를 정식화하면 아래와 같다.

$$\underset{\mathbf{w},b,\mathit{\zeta }}{min}{\displaystyle \frac{1}{2}}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\zeta }_i\text{s.t}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1-{\zeta }_i\text{for}i=1,2,\dots ,m$$

문제를 풀면

$$\underset{\mathit{\alpha }}{max}\sum _{i=1}^m{\alpha }_i-{\displaystyle \frac{1}{2}}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i\cdot {\mathbf{x}}_j\text{s.t.}$$

$$0\le {\alpha }_i\le C\text{for}i=1,2,\dots ,m$$

$$\sum _{i=1}^m{\alpha }_i{y}_i=0$$

What is C

정규화 파라미터인 $C$를 어떻게 이해할까? 식 그대로 보면, $\mathit{\zeta }$를 얼마나 중요하게 최적화 문제에 반영할 것인지가 중요하다. 다시 말하면 이는 에러를 어떻게 볼 것인가와 연결되어 있다. 만일 $C$가 양의 무한대 값이라면 이는 하드 마진과 동일하다. 만일 $C=0$ 이라면 ${\alpha }_i=0$가 된다. 이는 사실상 선형 제약이 사라지게 되는 결과가 된다. 따라서 하이퍼플레인이 어떤 것도 분류하기 못하게 될 것이다. 즉, C는 하드 마진과 소프트 마진 사이를 적절하게 조절하는 역할을 수행한다.

Kernel Trick

마지막에 얻은 극대화 문제를 살펴보면, training set이 관련된 부분이 딱 하나 밖에 없다. ${\mathbf{x}}_i\cdot {\mathbf{x}}_j$ 뿐이다. 따라서 이 부분을 유연하게 조정해줌으로써 비선형적 형태의 분류를 만들 수 있는 것이다. 앞서 봤던 하드 마진 SVM은 선형 커널을 사용한다. 즉,

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i\cdot {\mathbf{x}}_j$$

이런 커널만 있을 형태는 없다. 여러가지 함수를 커널로 취할 수 있을 것이다. 가장 많이 사용되는 커널은 RBF(Radial Basis Function) 혹은 가우시안이라고 한다.

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert )$$

• $\gamma$ 값이 충분히 작으면 선형 커널과 비슷하게 작동한다.
• $\gamma$가 크면 서포트 벡터에게 크게 영향 받는다.

Resource

이 자료는 아래 내용을 바탕으로 만들어졌습니다.

• Basic: LINK
• Illustration: LINK