Mathematics of Support Vector Machine

• Key Questions
• Key Synopsis
• SVM Mathematically
  • Preliminary concepts
    • Length of a vector
    • Direction of a vector
    • Dot product (inner product)
    • Hyperplane
    • Classifier
• Explained Visually
• Optimization for SVM
  • Metrics to compare hyperplanes
    • Defining functional margin
  • Derivation of SVM optimization problem
  • Optimization by Wolfe duality
  • Compute w and b
  • Limitation
    • 데이터에 노이즈가 있을 경우
    • 데이터 자체가 선형으로 분리되지 않을 경우
• Soft Margin SVM
  • What is C
  • Kernel Trick
• Resource

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

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

$$ \Vert {\bf x} \Vert = \sqrt{x_1^2 + x_2^2 + \dotsc + x_n^2} $$

Direction of a vector

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

$$ \mathbf{w} = \left( \dfrac{x_1}{ \Vert \bf x \Vert }, \dfrac{x_2}{ \Vert \bf x \Vert } \right) $$

그림으로 나타내보자.

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

Dot product (inner product)

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

$$ \begin{aligned} \cos \theta & = \cos (\beta -\alpha) \\\\ & = \cos \beta \cos \alpha + \sin \beta \ \sin \alpha \\\\ & = \dfrac{x_1}{\Vert \rm x \Vert} \dfrac{y_1}{\Vert \rm y \Vert} + \dfrac{x_2}{\Vert \rm x \Vert} \dfrac{y_2}{\Vert \rm y \Vert} \\\\ & = \dfrac{x_1 y_1 + x_2 y_2}{\Vert \rm x \Vert \Vert \rm y \Vert} \end{aligned} $$

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

$$ \rm x \cdot \rm y = \Vert \rm x \Vert \Vert \rm y \Vert \cos \theta $$

Hyperplane

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

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

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

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

Classifier

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

$$ h({\bf x}) = \begin{cases} +1\hspace{3em} & \text{if} \hspace{1em} \mathbf{w} \cdot {\bf x} + b \geq 0 \\\\ -1 \hspace{3em} & \text{if} \hspace{1em} \mathbf{w} \cdot {\bf x} + b < 0 \end{cases} $$

Explained Visually

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

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

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

$$ \text{Proj}_\mathbf{w} {\bf x}_i = \dfrac{\mathbf{w} \cdot{\bf x}_i}{\Vert \bf w \Vert} $$

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

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

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

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

$$ y_i ( \mathbf{w} \cdot {\bf x}_ i + b) - 1 \geq 0 $$

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

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

$$ \cos \theta = \dfrac{({\bf x} _ {\rm svr} - {\bf x} _ {\rm svl}) \cdot \bf w}{\Vert {\bf x} _ {\rm svr} - {\bf x} _ {\rm svl} \Vert \Vert \mathbf{w} \Vert} $$

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

$$ \dfrac{ \Delta _ {\bf x} }{\Vert {\bf x} _ {\rm svr} - {\bf x} _ {\rm svl} \Vert } = \cos \theta = \dfrac{({\bf x} _ {\rm svr} - {\bf x} _ {\rm svl}) \cdot \bf w}{\Vert {\bf x} _ {\rm svr} - {\bf x} _ {\rm svl} \Vert \Vert \mathbf{w} \Vert} $$

따라서

$$ \Delta _ {\bf x} = \dfrac{({\bf x} _ {\rm svr} - {\bf x} _ {\rm svl}) \cdot \bf w}{\Vert \mathbf{w} \Vert} $$

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

$$ \begin{aligned} {\bf x}_ {\rm svr} \cdot \mathbf{w} + b & = 1 \\ {\bf x}_ {\rm svl} \cdot \mathbf{w} + b & = -1 \end{aligned} $$

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

Optimization for SVM

Metrics to compare hyperplanes

Defining functional margin

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

$$ D = \left\lbrace ({\bf x}_i, y_i) \mid {\bf x}_ i \in \mathbb R^n,~y_ i \in \lbrace -1, 1\rbrace \right\rbrace_{i=1}^m $$

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

$$ F = \min_{i = 1, \dotsc, m} y_i( \mathbf{w} \cdot {\bf x} _i + b ) $$

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

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

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

Derivation of SVM optimization problem

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

$$ \max_{\mathbf{w} , b} M\hspace{1em}\text{s.t.}\hspace{1em}\gamma_i \geq M\hspace{1em}\text{for}\hspace{1em}i = 1,\dotsc, m $$

where

$$ \gamma_i = y_i \left( \dfrac{\mathbf{w} }{\Vert \mathbf{w} \Vert} \cdot {\bf x}_i + \dfrac{b}{\Vert \mathbf{w} \Vert} \right) $$

$$ M = \min_{i=1, \dotsc, m} \gamma_i $$

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

$$ \max_{\mathbf{w} , b} \dfrac{F}{\Vert w \Vert}\hspace{1em}\text{s.t.}\hspace{1em}f_i \geq F \hspace{1em}\text{for}\hspace{1em}i = 1,2, \dotsc, m $$

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

$$ \max_{\mathbf{w} , b} \dfrac{1}{\Vert w \Vert}\hspace{1em}\text{s.t.}\hspace{1em}f_i \geq 1\hspace{1em}\text{for}\hspace{1em}i = 1,2, \dotsc, m $$

$$ \min_{\mathbf{w} , b} {\Vert w \Vert}\hspace{1em}\text{s.t.}\hspace{1em}f_i \geq 1\hspace{1em}\text{for}\hspace{1em}i = 1,2, \dotsc, m $$

$$ \min_{\mathbf{w} , b} \dfrac{1}{2}{\Vert w \Vert}^2\hspace{1em}\text{s.t.}\hspace{1em}f_i \geq 1\hspace{1em}\text{for}\hspace{1em}i = 1,2, \dotsc, m $$

Optimization by Wolfe duality

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

$$ {\mathcal L}(\mathbf{w} , b, {\boldsymbol \alpha}) = \frac{1}{2} \mathbf{w} \cdot \mathbf{w} - \sum_{i=1}^m \alpha_i \left [ y_i (\mathbf{w} \cdot {\bf x} + b) -1 \right] $$

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

$$ \begin{aligned} \nabla_\mathbf{w} {\mathcal L}( {\mathbf{w}, b, \boldsymbol \alpha} ) & = \mathbf{w} - \sum_{i}^{m} {\alpha_i} {y_i} {x_i} = 0 \\ \nabla_{b} {\mathcal L}({\mathbf{w}, b, \boldsymbol \alpha}) & = - \sum_{i}^{m} \alpha_i y_i = 0 \end{aligned} $$

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

$$ W(\boldsymbol \alpha) = \sum_{i=1}^m \alpha_i - \dfrac{1}{2}\sum_{i=1}^{m} \sum_{j=1}^m \alpha_i \alpha_j y_i y_j {\bf x}_i \cdot {\bf y}_j $$

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

$$ \max_{\boldsymbol \alpha} W( {\boldsymbol \alpha} )\hspace{1em}\text{s.t.}\hspace{1em}{\alpha_i} \geq 0, \sum_{i=1}^m \alpha_i { \left( y_i ( \mathbf{w} \cdot {\bf x}^* + b) -1 \right)} = 0 $$

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

$$ \alpha_i \left[ y_i (\mathbf{w} \cdot {\bf x}^* + b) -1 \right] = 0 $$

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

Compute w and b

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

$$ \mathbf{w} - \sum_{i=1}^m \alpha_i y_i {\bf x} _i = 0 $$

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

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

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

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

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

$$ b = \dfrac{1}{S} \sum_{i=1}^S \left( y_i - \mathbf{w} \cdot {\bf x}^*_i \right) $$

Limitation

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

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

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

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

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

Soft Margin SVM

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

$$ \min_{\mathbf{w}, b, {\boldsymbol \zeta}} \dfrac{1}{2} \Vert \mathbf{w} \Vert^2 + C \sum_{i=1}^m \zeta_i~\text{s.t}~ y_i ( \mathbf{w} \cdot {\bf x}_i + b) \geq 1 - \zeta_i~\text{for}~ i = 1,2,\dotsc, m $$

문제를 풀면

$$ \max_{\boldsymbol \alpha} \sum_{i=1}^m \alpha_i - \dfrac{1}{2} \sum_{i=1}^m \sum_{j=1}^{m} \alpha_i \alpha_j {y_i} {y_j} {\bf x}_i \cdot {\bf x}_j \hspace{1em} \text{s.t.} $$

$$ 0 \leq \alpha_i \leq C\hspace{1em}\text{for}\hspace{1em}i=1,2,\dotsc, m $$

$$ \sum_{i=1}^m \alpha_i y_i = 0 $$

What is C

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

Kernel Trick

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

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

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

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

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

Resource

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

• Basic: LINK
• Illustration: LINK

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

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