Support Vector Machine (SVM) - Soft margin

02_3 : Kernel based learning : Support Vector Machine (SVM) - Soft margin

이전 글에서는 Hard margin을 사용하는 SVM에 대하여 알아보았다. 이번에는 Soft margin을 사용하는 경우를 알아보자. 

SVM - Case 2 : Linear case & Soft margin

지금까지는 분류경계면에 대하여 margin을 넘어가는 객체가 없다고 가정하고 Hard margin을 적용하였다. 하지만 실제 데이터에는 noise가 존재하기 때문에 위와 같은 경우가 발생하기 마련이다. 위의 경우에 Hard margin을 사용하면 분류경계면의 생성이 불가능하다.

그래서 모든 객체가 margin의 밖에 존재해야 한다는 제약을 제거하고 margin 안쪽에도 존재할 수 있도록 예외를 허용해주는 방법이 Soft margin이다. 물론 margin 안쪽에 존재하는 경우를 그냥 허용하는 것이 아니라 Penalty를 준다. 

위 예시에서 $\xi$에 해당하는 값이 error 객체에 대한 Penalty이다. Penalty를 부여하는 방법에 따라 C-SVM과 nu-SVM으로 나뉘는데, 이 글에서는 C-SVM에 대하여 알아볼 것이다.

  • Optimization problem (C-SVM)
- Objective function
$$ min\;\;\;\;\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i $$
- Constraints
$$ s.t.\;\;\;\;y_i(\textbf{w}^T\textbf{x}_i+b)\geq 1-\xi_i,\;\;\;\xi_i\geq 0,\;\;\forall i$$
Objective function의 $\frac{1}{2}||\textbf{w}||^2$은 기존의 Hard margin에서 사용했던 Margin이 최대화 되도록 한다. 그리고 위에서 말했던 Penalty를 주는 부분이 $C\sum_{i=1}^N\xi_i$식이다. 이 식을 통해 예외를 허용하지만 되도록 Margin을 벗어나지 않도록 하는 것이다. 여기서 $C$는 Margin을 최대화 하는 Term과 예외를 허용하는 Penalty term사이의 trade-off를 조절하는 Hyperparameter이다.

Constraint를 보면, 제약식에 $\xi_i$가 있다. $\xi_i$는 margin을 벗어나지 않는 객체에 대해서는 0이고, margin을 벗어나는 경우에만 양의 값이 주어진다. margin을 벗어나는 객체가 제약식을 만족할 수 있도록 $\xi_i$를 추가해 주었다.
  • Given data (알고있는 값) : $x,\;y$
  • Parameter (찾아야 하는 값) : $w,\;b,\;\xi$
  • Hyperparameter : $C$
이제 위의 최적화 문제를 라그랑주 승수법을 사용하여 풀어보자.
  • Lagrangian problem
$$min\;\;\;L_P(\textbf{w},b,\alpha_i)=\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i$$
$$s.t.\;\;\;\alpha_i\geq 0,\;\;\;\mu_i\geq 0$$
KKT Condition을 만족하는 최적해를 구해보자. Stationary 조건에 의해 모든 미지수에 대한 미분값은 0이어야 한다. 이 조건에 따라 아래의 3개 조건을 도출할 수 있다.
$$\frac{\partial L_P}{\partial \textbf{w}} = \textbf{w} - \sum_{i=1}^N\alpha_iy_i\textbf{x}_i = 0$$
$$\textbf{w} = \sum_{i=1}^N\alpha_iy_i\textbf{x}_i\;\;\;\;(1)$$
$$\frac{\partial L_P}{\partial b} = \sum_{i=1}^N\alpha_iy_i = 0$$
$$\sum_{i=1}^N\alpha_iy_i = 0\;\;\;\;(2)$$
$$\frac{\partial L_P}{\partial \xi_i} = C - \alpha_i-\mu_i= 0$$
$$C - \alpha_i-\mu_i= 0\;\;\;\;(3)$$
이제 $\textbf{w} = \sum_{i=1}^N\alpha_iy_i\textbf{x}_i$식을 $L_P$에 대입하여 Primal problem을 Dual problem으로 바꿔보자.
$$L_P = \frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i$$
$$\begin{align*}L_D &= \frac{1}{2}||\sum_{i=1}^N\alpha_iy_i\textbf{x}_i||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i((\sum_{i=1}^N\alpha_iy_i\textbf{x}_i)\textbf{x}_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i\\&=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+C\sum_{i = 1}^N\xi_i - \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j- b\sum_{i=1}^N\alpha_iy_i\\&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{i=1}^N\alpha_i-\sum_{i=1}^N\alpha_i\xi_i-\sum_{i=1}^N\mu_i\xi_i\\&=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i+\sum_{i=1}^N(C-\alpha_i-\mu_i)\xi_i\\&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(\sum_{i=1}^N\alpha_iy_i = 0)\\&=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i\qquad\qquad(C-\alpha_i-\mu_i = 0)\end{align*}$$
$$ s.t.\qquad C-\alpha_i - \mu_i = 0$$
제약조건을 살펴보면, 미지수 $\alpha_i$에 대한 조건만 남는다. 이 조건은 $\alpha_i\geq 0,\;\;\mu_i\geq 0$조건에 의해서 미지수 $\alpha_i$만을 표현하는 제약식으로 바꿀 수 있다. $\alpha_i$는 여전히 0보다 커야 하는데, $\alpha_i$가 최대인 경우는 $\mu_i$가 0인 경우이다. 따라서 $\alpha_i$만을 사용하여 제약식으로 표현가능하다. 
$$s.t.\qquad 0\leq \alpha_i \leq C$$
정리해보자.
  • Dual problem
$$max\;\;\; L_D(\alpha_i)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\textbf{x}_i^T\textbf{x}_j$$
$$s.t.\qquad\sum_{i = 0}^N\alpha_iy_i = 0\quad and \quad 0\leq \alpha_i \leq C$$
Soft margin의 특징으로 $\alpha_i$가 $C$로 bound 되는 제약조건이 추가되었음을 확인할 수 있다.

Dual problem은 항상 Convex problem임으로 그 최적해를 찾을 수 있음이 보장된다. 최적해인 극대값 $\alpha$를 찾고나면, 임의의 $\textbf{x}_{new}$가 주어졌을 때 아래의 분류기를 사용해 분류 가능하다.
  • Solution
$$f(\textbf{x}_{new}) = sign\bigg(\sum_{i=1}^N \alpha_iy_ix_i^T\textbf{x}_{new}+b\bigg)$$




SVM - Case 2 : Linear case & Soft margin (Add.)

앞서 Hard margin에서 이야기 했듯, SVM에서 Lagrangian multiplier와 제약식의 곱은 항상 0이어야 하고, 동시에 둘다 0이면 안된다. 
$$\alpha_i(y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i) = 0$$
$$\mu_i\xi_i = 0$$
그리고 추가적으로 도출한 조건이 있다. 
$$\;\qquad C-\alpha_i - \mu_i = 0\qquad(3)$$
이 조건들을 사용하여 Soft margin을 분석해보자.
  • Case 1 : $\alpha_i = 0$  $\Rightarrow$  non-support vectors
$\alpha_i = 0$ 인 경우, $y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i \neq 0$ 이어야 한다. 그리고 $C-\alpha_i - \mu_i = 0$ 조건으로부터 $\mu_i = C$ 임을 알 수 있다. 

$\mu_i = C$ 임으로 $\mu_i\xi_i = 0$ 조건으로 인해 $\xi = 0$ 임을 알 수 있다. $y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i \neq 0$ 에 $\xi = 0$ 을 대입하면 아래 식이 구해진다.
$$y_i(\textbf{w}^T\textbf{x}_i+b)-1 \neq 0$$
즉 $\alpha_i = 0$인 Case 1은 margin 밖에 존재하는 경우이다.

  • Case 2 : $0\leq\alpha_i \leq C$  $\Rightarrow$  support vectors on the margin
$0\leq\alpha_i \leq C$ 인 경우, $C-\alpha_i - \mu_i = 0$ 조건을 만족하기 위해 $\mu_i > 0$이어야 한다. $\mu_i \neq 0$ 임으로 $\mu_i\xi_i = 0$ 조건으로 인해 $\xi = 0$ 임을 알 수 있다.

그리고 $\alpha_i \neq 0$ 임으로 $y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i = 0$ 이어야 한다. 위 식에 $\xi = 0$ 을 대입하면 $y_i(\textbf{w}^T\textbf{x}_i+b)-1= 0$ 임을 알 수 있다.
$$y_i(\textbf{w}^T\textbf{x}_i+b)=1$$
즉, $0\leq\alpha_i \leq C$ 인 Case 2는 margin위에 존재하는 경우이다.

  • Case 3 : $\alpha_i = C$  $\Rightarrow$  support vectors outside the margin
$\alpha_i = C$ 인 경우, $C-\alpha_i - \mu_i = 0$ 조건을 만족하기 위해 $\mu_i = 0$이어야 한다. $\mu_i = 0$ 임으로 $\mu_i\xi_i = 0$ 조건으로 인해 $\xi_i > 0$ 임을 알 수 있다.

그리고 $\alpha_i \neq 0$ 임으로 $y_i(\textbf{w}^T\textbf{x}_i+b)-1+\xi_i = 0$ 이어야 한다.
$$y_i(\textbf{w}^T\textbf{x}_i+b)=1-\xi_i,\;\;\;\;\xi_i > 0$$
$\xi_i > 0$임으로 이 경우는 Penalty를 받는 원소를 의미한다.

여기서 Case 2Case 3Support vector로 사용한다.



SVM - Case 2 : Linear case & Soft margin (Cont.)

이제 Soft margin에서 Regularization cost $C$를 살펴보자. C-SVM의 Objective function을 살펴보자.
$$ min\;\;\;\;\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i $$
$C$는 margin을 최대화 하는 term $\frac{1}{2}||\textbf{w}||^2$과 penalty term $C\sum_{i=1}^N\xi_i $의 trade-off를 설정하는 Hyperparameter이다.
  • Large $C$
$C$가 크다면, $\xi_i$에 대한 penalty를 크게하여 $\xi_i$가 최대한 작아지게 한다. 이는 예외를 최대한 허용하지 않겠다는 의미이다. 이렇게 되면 margin의 크기가 작아질 것이다.
  • Small $C$
$C$가 작다면, $\xi_i$에 대한 penalty를 적게하여 $\xi_i$를 어느정도 커질 수 있게 한다. 이는 예외를 어느정도 허용하겠다는 의미이다. 이렇게 되면 margin의 크기가 커질 것이다.



SVM - Case 3 : Non-linear case & Soft margin

지금까지 선형 분리가 가능하다고 가정하고 SVM을 구성하였다. 하지만 현실의 문제상황에는 선형 분리가 불가능한 Non-linear 문제들이 더 많다. (ex. XOR Problem) 우리는 이러한 상황을 mapping function을 사용하여 해결하려고 한다.
$$mapping\;function\;:\;\Phi(x_1,x_2)\rightarrow(x_1^2,x_2^2,\sqrt{2}x_1,\sqrt{2}x_2,\sqrt{2}x_1x_2,1)$$
Mapping function $\Phi(x)$는 저차원 상의 input vector를 mapping 하여 고차원의 feature vector로 바꾸어준다. 위의 예시처럼 mapping function을 통해 기존에 선형 분리가 불가능한 data를 선형 분리가 가능하게 만들어 줄 수 있다.
우리의 목표는 margin을 최대화 하면서 오류를 최소화 하는 최적의 Hyperplane을 찾는 것이다. 하지만 Non-linear인 문제는 해결이 불가능하다. 이러한 단점을 해결하기 위해 mapping function을 사용해 Non-linear 문제도 해결이 가능하게, 더 Flexible하게 만든다.

이제 Mapping function을 사용한 Optimization problem을 정의해보자.
  • Objective function
$$ min\;\;\;\;\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i $$
  • Constraints
$$ s.t.\;\;\;\;y_i(\textbf{w}^T\Phi(\textbf{x}_i)+b)\geq 1-\xi_i,\;\;\;\xi_i\geq 0,\;\;\forall i$$
위에서 살펴본 Case 2의 SVM과 거의 동일하다. 유일하게 추가된 것은 제약식에 $\Phi$ 함수가 추가된 부분이다. 즉 변환된 feature space에서 Optimization problem을 푸는 것이다. 위에서 했던 것처럼 라그랑주 승수법을 사용해 Lagrangian problem을 정의해보자.
  • Lagrangian problem
$$min\;\;\;L_P(\textbf{w},b,\alpha_i)=\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(\textbf{w}^T\Phi(\textbf{x}_i)+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i$$
$$s.t.\;\;\;\alpha_i\geq 0,\;\;\;\mu_i\geq 0$$
식을 보면 $\textbf{x}$항에 대하여 $\Phi$함수가 추가되었다는 점을 제외하면, 위의 Case 2와 크게 다르지 않다. 이 문제를 KKT Condition을 사용하여 Dual 문제로 바꿔보자. (계산과정이 Case 2와 유사함으로 생략)
  • Dual problem
$$max\;\;\; L_D(\alpha_i)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\Phi(\textbf{x}_i)^T\Phi(\textbf{x}_j)$$
$$s.t.\qquad\sum_{i = 0}^N\alpha_iy_i = 0\quad and \quad 0\leq \alpha_i \leq C$$
Dual 문제 또한 $\textbf{x}$항에 대하여 $\Phi$함수가 추가되었다는 점을 제외하면, 위의 Case 2와 크게 다르지 않다.

Dual 문제의 $\Phi(\textbf{x}_i)^T\Phi(\textbf{x}_j)$항을 보면 Feature space로 mapping된 $x_i$와 $x_j$에 대하여 내적을 수행한다. 이 계산과정은 굉장히 소모적일 수 있는데, 이를 효율적으로 해결하는 방법이 Kernel trick이다.



Kernel Trick

핵심 아이디어는 $\Phi(x_i)^T\Phi(x_j)$의 계산을 위해 $\Phi(x_i)$과 $\Phi(x_j)$를 각각 계산하여 내적하지 말고, 처음부터 $x_i, x_j$를 입력으로 받아, $\Phi(x_i)^T\Phi(x_j)$를 반환하는 $K(x_i,x_j)$ 함수를 사용하자는 것이다. 즉 위의 Dual 문제는 아래와 같이 바뀔 것이다.
$$max\;\;\; L_D(\alpha_i)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j \textbf{K}(\textbf{x}_i^T,\textbf{x}_j)$$
$$s.t.\qquad\sum_{i = 0}^N\alpha_iy_i = 0\quad and \quad 0\leq \alpha_i \leq C$$

이제 Kernal 함수 $\textbf{K}$를 알아보자.

Given two points $x,\;x^\prime\in X$, we need $z^Tz^\prime$
which $z = \Phi(x)$ and $z^\prime = \Phi(x^\prime)$
Let $z^Tz^\prime = K(x,x^\prime)$ $K$ is the kernel

Kernal 함수 $\textbf{K}$의 정의에 따라 아래의 예시를 만들어볼 수 있다.

<Example>
$$x = (x_1,x_2),\;\;\;z = \Phi(x) = (1,x_1,x_2,x_1^2,x_2^2,x_1x_2)$$
$$K(x,x^\prime) = z^Tz^\prime = 1+x_1x_1^\prime + x_2x_2^\prime+x_1^2x_1^{\prime 2} + x_2^2x_2^{\prime 2} + x_1x_1^\prime x_2x_2^\prime$$

하지만 매번 $\Phi$ 함수를 설정하고 이에 따라 $K$ 함수를 만들어 주는 것은 매우 소모적이다. 다행이 여러 경우에서 범용적으로 사용 가능한 Kernel 함수들이 있다. 이 함수들을 알아보자.
  • Polynomial Kernel
$\Phi$ 함수가 임의의 $d$차원으로 mapping을 한다고 할 때, 이 결과의 내적을 한번에 계산해주는 Kernel 함수는 아래와 같다.
$X\in \mathbb{R}^d$ and $\Phi\,:\,X\rightarrow Z$ is polynomial of order $Q$
The equivalent kernel function $K$ is, 
$$K(x,x^\prime) = (1+x^Tx^\prime)^Q = (1+x_1x_1^\prime+x_2x_2^\prime+\cdots+x_dx_d^\prime)^Q$$
$Q$ 를 크게 할 수록 더 고차원으로 mapping이 가능하다. 만약 크기를 조정하고 싶다면, 아래와 같이 정의하면 된다.
 $$K(x,x^\prime) = (ax^Tx^\prime+b)^Q$$

  • Gaussian (RBF) Kernel
Polynomial kernel을 더 확장한 RBF kernel은 가장 범용적으로 사용되는 Kernel 함수이다.

If $K(x,x^\prime)$ is an inner product in some space $Z$, 
$$K(x,x^\prime) = exp(-\gamma ||x-x^\prime||^2)$$
여기서 $\gamma$는 가우시안 함수 $exp(-\frac{||x-x^\prime||^2}{\sigma^2})$에서 $\frac{1}{\sigma^2} = \gamma$로 치환한 것이다.
Exponential 함수 $exp$는 테일러 급수를 사용하여 나타내어진다. 
- Taylor expansion of exponential function
$$e^x = \sum_{n = 0}^\infty \frac{x^n}{n!} = 1 + x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\;\;\;for\;all\;x$$

테일러 급수를 사용하여 RBF 함수를 표현해보자.
$$\begin{align*}K(x,x^\prime) &= exp(-(x-x^\prime)^2)\\&= exp(-x^2)exp(-x^{\prime 2})exp(2xx^\prime)\\ &= exp(-x^2)exp(-x^{\prime 2})\sum_{k = 0}^\infty \frac{2^kx^kx^{\prime 2}}{k!}\end{align*}$$
위와 같이 테일러 급수를 사용해 $x^\infty$까지 차원의 확장이 가능하다. 때문에 이론적으로 RBF Kernel은 유한 차원의 vector를 무한 차원의 vector로 mapping 하여 내적한 결과까지 계산이 가능하다.

Shatter 개념에서 배운 내용을 상기해보자. d차원 data는 선형 분류기에 의해 최대 d+1개를 Shatter 가능하다. RBF Kernel로 표현 가능한 차원이 $\infty$임으로 무한개의 객체를 shatter 가능하다.

이렇게 Shatter할 수 있는 객체가 무한한 경우라면 VC-dimension이 너무 커지는 것이 아닐까? 다행이도 margin이 VC-dimension을 줄여주기 때문에 이런 문제는 발생하지 않는다.

Kernel trick을 사용함으로써 얻을 수 있는 이점은 크게 2가지이다.
  • Efficiency : 일반적으로 $Phi$를 계산해서 내적하는 것 보다. Kernel 함수 $K$ 를 사용하여 한번에 결과를 얻는 것이 더 효율적이다.
  • Flexibility : 아래에서 알아볼 Mercer's condition을 만족하는 모든 함수는 Kernel 함수로 사용할 수 있음으로, 모델이 좀더 유연해진다.



Kernel Trick (Cont.)

  • Mercer's condition
For any symmetric function $K\,:\,X\times X \rightarrow R$ which is square integrable($L_2$-space) in $X\times X$ and which satisfies
$$\int_{X\times X} f(x)K(x,x^\prime)f(x^\prime)dxdx^\prime\;\;\geq 0\;\;for\;all\;f\in L_2(X)$$
There exist functions $\phi_i\,:\,X\rightarrow R$ and numbers $\lambda_i\geq 0$ such that
$$K(x,x^\prime)=\sum_i\lambda_i\phi_i(x)\phi_i(x^\prime)\;\;for\;all\;x,x^\prime \in X$$
Mercer's condition에 따르면, 어떠한 Symmetric function $K$가 $L_2$-space에서 적분이 가능할 때, 위의 두 조건을 만족하면 Kernel function으로 사용이 가능하다고 한다.
위의 적분에 대한 해석이 좀 어려운데, 적분은 아래 행렬 곱셈의 Continuous한 version이라고 볼 수 있다.
$$\sum_i\sum_jK(x_i,x_j)\alpha_i\alpha_j \geq 0$$
이에 기반하여 위의 Mercer's condition을 행렬의 관점에서 살펴보자.

$K(x,x^\prime)$ is a valid kernel iff (if and only if)
  • It is symmetric (1)
$\Phi(x_i)^T\Phi(x_j) = \Phi(x_j)^T\Phi(x_i)$ 임으로, $K(x_i,x_j) = K(x_j,x_i)$이어야 한다.
  • the matrix $M$ is positive semi-definite (2)
$$M = \begin{equation*} \begin{bmatrix} K(x_1,x_1) & K(x_1,x_2) & \cdots &K(x_1,x_N)\\ K(x_2,x_1) & K(x_2,x_2) & \cdots &K(x_2,x_N)\\\cdots & \cdots& \cdots &\cdots\\K(x_N,x_1) & K(x_N,x_2) & \cdots &K(x_N,x_N)\end{bmatrix}\end{equation*}$$
$$positive\;semi-definite\;:\;x_i^TMx_i\geq 0\;\;\;for\;all\;i=0,1,2,\cdots,N$$

위 두 조건을 만족하는 함수는 Kernel 함수로 사용 가능하다. 조건을 만족하는 대표적인 kernel 함수로는 위에서 살펴본 Polynomial, Gaussian(RBF), Sigmoid 함수가 있다.
  • Polynomial 
$$K(x,y) = (x\cdot y+c)^d,\;\;\;c\geq 0$$
  • Gaussian (RBF)
$$K(x,y) = exp(-\gamma ||x-y||^2),\;\;\;\gamma=\frac{1}{2\sigma^2},\;\;\;\sigma \neq 0$$
  • Sigmoid
$$K(x,y) = tanh(a(x\cdot y)+b),\;\;\;a,b \geq 0$$



Effects of different kernel 

동일한 data에 SVM을 수행할 때 각기 다른 Kernel 함수를 사용한 경우들을 비교해보자.
  • Linear kernel
별 다른 Kernel 동작을 수행하지 않는 Case 2와 같은 경우, 일반적으로 기대되는 선형의 분류경계면을 생성하였다.
  • Polynomial (degree 2)
Kernel 함수를 통해 고차원으로 mapping하였다. 이 경우 앞의 Linear kernel 경우보다 margin을 벗어나는 case가 적은 비선형의 분류경계면을 생성하였다.
  • Polynomial (degree 5)
위의 경우보다 더더욱 고차원으로 Mapping 하였다. 앞의 경우보다 margin을 벗어나는 case가 거의 없는, 더 최적화 된 비선형의 분류경계면을 생성하였다.


이번에는 Hyperparameter $C$에 따라서 RBF kernel을 사용한 SVM의 결과가 어떻게 달라지는지 살펴보자. 
$C$가 커질수록 Margin을 벗어나는 경우에 부여하는 penalty가 커진다. 때문에 분류경계면이 더욱 구불구불한 모양으로 형성됨을 확인할 수 있다. 


RBF kernel을 사용하는 경우 Hyperparameter $\gamma$의 설정이 중요하다. $\gamma$는 $\gamma=\frac{1}{2\sigma^2}$ 로 정의되는데, $\sigma$가 클수록 Gaussian 함수가 넓게 퍼져서 분포하는 모양을 띈다. 따라서 $\gamma$가 크다면 $\sigma$가 작다는 뜻이고, 저차원의 data를 mapping 할 때, 두 객체의 거리의 차이가 고차원 상에서 크게 작용할 것이다. (동일한 거리의 두 객체에 대하여 $\gamma$가 다를 때 Gaussian Kernel함수의 결과를 비교해보면 직관적이다) 때문에 분류 경계면이 더 구불구불한 모양으로 형성된다.
반면, $\gamma$가 작다면 $\sigma$가 크다는 뜻이고, 저차원의 data를 mapping 할 때, 두 객체의 거리의 차이가 고차원 상에서 덜 차이나게 될 것이다. 때문에 분류 경계면이 좀더 선형으로 형성된다.
정리하자면, $\gamma$가 커질수록, 분류 경계면(decision boundary)의 복잡도가 높아지고, $C$가 커질수록, Margin이 작아지고 분류 경계면의 복잡도 또한 높아진다. 이러한 Hyperparameter의 적절한 설정이 SVM의 성능과 직결된다. 일반적으로 Grid-search 같은 방법을 사용해 Hyperparameter를 설정한다.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 참고하여 작성되었습니다.

댓글

이 블로그의 인기 게시물

One-Class SVM & SVDD

Self-Training & Co-Training

Support Vector Regression (SVR)