ML [5] Support Vector Machine(2)

본 포스팅은 카이스트 산업및시스템공학과 문일철 교수님의 Introduction to Artificial Intelligence/Machine Learning(https://aai.kaist.ac.kr/xe2/courses) 강의에 대한 학습 정리입니다.

이전의 ML [5] Support Vector Machine(1)의 SVM은 에러가 있음을 인정하고 패널티를 주는 방식의 Linear의 형태지만 decision boundary를 complex하게 만들기 위해 모델을 complex하게 만들어 아래 그림 처럼 non-linear하게 만들 수 있다. 그때 필요한 것이 kernel trick이다.

Kernel Trick

• nonlinear하게 만드는 방법으로, x1,x2의 interaction을 더욱 복잡하게 표현하여(차원을 높여) 표현 할 수 있다.
  • $\varphi(<x_1,x_2>) = <x_1,x_2,x^2_1,x^2_2,x_1 x_2, x_1^3,x^3_2,x_1^2 x_2,x_1 x_2^2>$
• 이때 위 식 처럼 3차로 표현할 수 있는데, 무한대로 표현하면 더 잘 표현할 수 있을 것이고, 그때 필요한 것이 kernel trick이다.

Lagrange Method and Duality

: kernel을 도입하기 위해서 SVM의 primal 문제를 dual문제로 바꿔야하는데, 그때 사용하는 방법이 lagrange method이다.

• SVM은 classification문제를 constrained quadratic programming으로 바꾼다.
  • Constrained optimization
    • $min_x f(x)$
    • $s.t. \ g(x) \leq{0},h(x) = 0$
• Lagrange method
  • Lagrange Prime Function: $L(x,\alpha,\beta)=f(x)-\alpha g(x)+\beta{h(x)}$
  • Lagrange Multiplier: $\alpha\geq0,\beta$
  • Lagrange Dual Function: $d(\alpha,\beta)={inf}_{x\in{X}}L(x,\alpha,\beta)=min_x L(x,\alpha,\beta)$
  • $max_{\alpha\geq0,\beta}L(x,\alpha,\beta)=f(x):if \ x \ is \ feasible, \ \infty:otherwise$
    = $min_x{f(x)}\rarr min_x max_{\alpha\geq0,\beta}L(x,\alpha,\beta)$
• Strong Duality
  • primal solution와 dual solution이 같을때를 의미
    

• 필요한 조건: KKT(Karush-Kunh-Trucker) condition
• KKT condition
  • $\nabla L(x^*,\alpha^*,\beta^*)=0$
  • $\alpha^*\geq0$
  • $g(x^*)\leq0$
  • $h(x^*)=0$
  • $\alpha^*g(x^*)=0$
• SVM의 dual 표현:
  • 
  • 위의 표현은 또 다시 quadratic programming이 된다.
  • 그렇다면 $\alpha$만 안다면, $w$값을 구할 수 있게 된다.

Kernel

• Kernel: 두 벡터의 다른 공간에서의 inner product(내적)을 계산
• $K(x_i,x_j)=\varphi(x_i)\varphi(x_j)$

Dual SVM with Kernel Trick

• $max_{\alpha\geq0}\sum_j{\alpha_j}-\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_j y_i y_j \varphi(x_i)\varphi(x_j)$
• => $max_{\alpha\geq0}\sum_j{\alpha_j}-\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_j y_i y_j K(x_i,x_j)$
  • $\alpha_i((wx_j+b)y_j-1)=0, C>\alpha>0$
    • $w=\sum_{i=1}^N\alpha_i y_i\varphi(x_i)$
    • $b=y_j-\sum_{i=1}^N \alpha_i y_i\varphi(x_i)\varphi(x_j)$
  • $\sum_{i=1}^N\alpha_i y_i=0$
  • $C\geq\alpha_i\geq0,\forall i$
• 따라서, 위의 식(kernel)을 통해서 classification할 수 있다