[ML][Classification] Soft Margin SVM, Nonlinear SVM(비선형 서포트 벡터 머신), Kernel Trick, Multiclass SVM

 

 

 

[ML][Classification] Support Vector Machine(SVM, SVD)

 

앞선 글에서 Support Vector Machine에 대해서 공부해보았습니다

이번 글에서는 SVM의 심화주제인 Soft Margin SVM, Nonlinear SVM에 대해 공부해보도록 하겠습니다

---

Soft Margin SVM

앞선 글에서 SVM은 이상치에 민감하게 반응하기 때문에 이상치 처리가 중요하다고 언급하였습니다.

Outlier를 허용하지 않는 것을 Hard Margin, 어느 정도의 Outlier들을 Margin 안에 포함되는 것을 허용한다면 Sort Margin이라고 합니다

이는 SVM에서 선형경계로는 완벽히 나눌 수 없는 경우 혹은 나눌 수 있지만 Noisy한 데이터 때문에 비효율적인 경계가 형성되는 경우 Slack Variable $\epsilon_i$를 도입하여 해결하는 방법입니다

알고리즘

$$
{\large
\begin{aligned}
&\underset{w, b, \epsilon}{\max} \frac{||w||^2}{2} + C \sum \limits_{i=1}^{N} \epsilon_i\\
&subject\;to\; y_i(w x_i + b) \ge 1 - \epsilon_i , \quad \epsilon_i \ge 0
\end{aligned}
}
$$

 

Soft Margin SVM도 SVM과 동일한 방식으로 계산합니다(라그랑주 승수법 이용)

 

$$
{\normalsize
\begin{aligned}
&\underset{\alpha, \beta}{\max} \Big[ \underset{w, b, \epsilon}{\min}\frac{||w||^2}{2} + C \sum \limits_{i=1}^{N} \epsilon_i - \sum \limits_{i=1}^{N} \alpha_i \big\{y_i(w \cdot x_i + b) -1 + \epsilon_i \big\} - \sum \limits_{i=1}^{N} \beta_i \epsilon_i\Big]\\
&subject\;to\; \alpha_i \ge 0,\; \beta_i \ge 0 \; for\; all\; i=1,\;\cdots,\;N
\end{aligned}
}
$$

이 때 Stationary Condition에 따라 Primal Problem의 parameter에 대한 편미분 값이 0이 됩니다

$$\frac{\partial L}{\partial w}=0, \quad \frac{\partial L}{\partial b}, \quad \frac{\partial L}{\partial \epsilon_i} = 0$$

편미분 결과에 따라 식을 정리하면 아래와 같은 결과를 얻을 수 있습니다

$$w = \sum \limits_{i=1}^{N} \alpha_i y_i x_i, \quad \sum \limits_{i=1}^{N} \alpha_i y_i =0, \quad \alpha_i = C - \beta_i$$

 

이제 Dual Problem에 대해 풀이를 해보면 아래와 같습니다

 

$$
\begin{aligned}
&\underset{\alpha}{\max} \sum \limits_{i=1}^{N} \alpha_i - \frac{1}{2}\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j {x_i}^T x_j\\
&subject\;to\; C \ge \alpha_i \ge 0,\; \sum \limits_{i=1}^{N}\alpha_i y_i = 0\quad for\;i = 1,\cdots, N
\end{aligned}
$$

 

여기서 KKT Condition(Complementary Slackness Condtiion)에 따라 두 가지의 Support Vector가 존재하게 됩니다

• Unbounded SV : $C \gt \alpha_i \gt 0$의 margin 위에 있는 샘플
  • 결정경계 위에 있으며, $w^T x_i + b = y_i$를 만족합니다
  • 따라서 이로부터 $b$를 계산할 수 있다 
• Bounded SV : $C = \alpha_i $의 margin 위에 있는 샘플
  • 결정경계 밖에 있는 샘플입니다

Unbounded Support Vector를 사용하여 결정 경계 Paramete $w, b$를 구한 결과입니다

$$w = \sum \limits_{i=1}^{N} \alpha_i y_i x_i, \quad b = \frac{1}{N_{USV}} \sum \limits_{i=1}^{N_{USV}} (y_i - w^T x_i)$$

 

※ Hyperparameter in C in SVM

• C 값이 커지면 :
  • $\epsilon$의 영향이 커져 0으로 보내며, Margin의 폭이 줄어든다
  • Support Vector의 수가 줄어들어, 적은 샘플로 결정 경계를 찾는다(Over fitting 이슈)
  • Bias 감소, Variance 증가
• C 값이 작아지면 :
  • Margin의 폭이 커진다
  • 모든 샘플이 Support Verctor가 된다(Under fitting 이슈)
  • Bias 증가, Variance 감소

---

Nonlinear SVM

선형 결정 경계로 데이터를 효과적으로 분류할 수 없을 경우 필요하면 SVM입니다

Kernel Trick을 활용하여 저차원의 데이터를 고차원으로 Mapping함으로써 선형분류가 가능하도록 만들어줍니다

 

Mapping Function

비선형 구조의 데이터를 고차원으로 옮겨주는 Fucntion($\phi$)입니다

Input space에 존재하는 데이터를 Feature space로 Mapping

Kernel Trick

Mapping Function 함수 도입시 는 단점이 있습니다 ($\phi (x_i)^T \cdot \phi(x_j)$)

만약 Mapping Function을 사용한다면 아래 식에서 고차원 Mapping($\phi(x)$)과 내적($\phi(x_i)^T \cdot \phi(x_j)$)을 수행해야 합니다(많은 연산이 필요합니다)

$$\underset{\lambda}{\max} \sum \limits_{i=1}^{N} \lambda_i - \frac{1}{2}\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N}\lambda_i \lambda_j y_i y_j \phi({x_i}^T) \phi(x_j)$$

 

이러한 단점을 개선하고 고차원 Mapping과 내적을 한번에 해결하기 위해 Kernel(커널)을 도입합니다

Ex) $K(x_i, x_j) = \phi(x_i)^T \phi(x_j) = (Ax_i)^T (Ax_j) = {x_i}^T A^T A x_j$

$ {x_i}^T A^T A x_j\;Dimension\;:\;(1 \times m) (m \times n) (n \times m) (m \times 1) \rightarrow (1 \times 1)$

 

여기서 $ \phi(x_i) \rightarrow Ax_i$는 Affine Transformation을 의미합니다(행렬 $A$는 m차원에서 n차원으로의 변환을 수행하는 행렬)

 

요약하자면, Kernel Trick을 통해 실제 데이터($x_i$, $x_j$)를 고차원으로 변환하지 않고도 고차원 공간의 내적을 직접 계산할 수 있게 되고 이는 계산의 효율성을 높이는 이점을 가져다 주게 됩니다

※ Mercer's Theorem 

아래 두 조건을 만족시, $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$를 만족시키는 어떤 $\phi$가 존재함

• Positive semi definite matix 조건 : $K(x_i, x_i)$의 경우 항상 0
• 대칭 행렬 조건 : $K(x_i, x_j) = K(x_j, x_i)$

※ 커널 함수로 사용 가능한 함수들

• Linear :  $K(x_i, x_j) = {x_i}^T x_j$
• Polynomial : $K(x_i, x_j) = ( {x_i}^T x_j  + c)^d$
• Gaussian : $K(x_i, x_j) = \exp{\Big\{ \frac{-||x_i - x_j||_{2}^{2} }{2 \sigma^2} \Big\}}$
• Radial : $K(x_i, x_j) = \exp{\big\{ - \gamma \sum \limits_{k=1}^{p} (x_{ik} - x_{jk})^2\big\}}$

---

그럼 이제 Kernel Trick을 이용한 Support Vector Machine의 식을 보도록 하겠습니다 

 

SVM with Kernel Trick

$$
\begin{aligned}
&\underset{\lambda}{\max} \sum \limits_{i=1}^{N} \lambda_i - \frac{1}{2}\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N}\lambda_i \lambda_j y_i y_j K(x_i, x_j)\\
&subject\;to\; \lambda_i \ge 0,\; \sum \limits_{i=1}^{N}\lambda_i y_i = 0\quad for\;i = 1,\cdots, N
\end{aligned}
$$

$$w = \sum \limits_{i=1}^{N} \lambda_i y_i \phi(x_i), \quad b = \frac{1}{N_{SV}} \sum \limits_{i=1}^{N_{SV}} (y_i -(\sum \limits_{j=1}^{N_{SV}} \lambda_j y_j K(x_i, x_j)))$$

---

Multiclass SVM

OVA(One Versus All)

K개의 2-class SVM을 학습하며 각자의 class와 나머지 클래스로 나눈다

$\hat{f}(x)$의 값이 가장 큰 클래스로 분류

 

OVO(One Versus One) 

$\begin{pmatrix}K\\2\end{pmatrix}$ 개의 pairwise classifier($\hat{f}_{kl}(x)$)를 학습한다

Pairwise Competition을 가장 많이 이긴 클래스로 분류