SVM은 분류 및 회귀 분석을 위한 지도 학습 모델.
큰 데이터 셋에 대해서는 작동하지 않아, 딥러닝에 밀리고 있는 추세.

---

Concept

복수의 클래스 벡터를 선형으로 분류하는 것이 기본.

Decision Boundary : 클래스를 분류해주는 경계
※ 차원의 관점에서 이는 Hyperplane

Supprot Vector : decision boundary에서 가장 가까운 최외곽 벡터

Margin (M) : decision boundary에서 support vector까지의 거리

Margin을 최대로 하는 경계를 찾는 것이 최종 목표.

---

Detail

$\bold{w}$ : normal vector of hyperplane
$\bold{x^+}$ : (support) vetor of positive class
$\bold{x^-}$ : (support) vetor of negative class

decision boundary를 결정하기 위해서는 hyperplane을 결정해야 함.

Hyperplane : $\bold{w^T}\bold{x}+b=0$

즉, $\bold{w}$와 $b$를 결정해야 함.

---

Hard Margin

거리 $\delta$에 대해서,
$\bold{w^Tx^+}+b\geq\delta,\ \bold{w^Tx^-}+b\le\delta$

Normalize by $\delta$,
$\bold{w^Tx^+}+b\geq1,\ \bold{w^Tx^-}+b\le-1$

For $t_i=1$ if $\bold{x^+}$ else $-1$ if $\bold{x^-}$,
$t_i(\bold{w^Tx}+b)-1\geq0$ (support vector를 지날 경우, 등호 성립)

Margin M : $(\bold{x^+}-\bold{x^-})·$$\bold{w}\over||\bold{w}||$$=$$2\over||\bold{w}||$

$∴maximize$ $2\over||\bold{w}||$ $⇔minimize$ $1\over2$$||\bold{w}||^2\ subject\ to\ t_i(\bold{w^Tx_i}+b)-1\geq0$

KKT (Karush-Kuhn-Tucker) Conditions
$optimize\ f(\bold{x})\ subject\ to\ g_i(\bold{x})\le0,\ h_j(\bold{x})=0$

1) Stationarity
$\nabla f(\bold{x^*})+\sum\mu_i\nabla g_i(\bold{x^*})+\sum\lambda_j\nabla h_j(\bold{x^*})=0$

2) Primal Feasibility
$g_i(\bold{x})\le0,\ h_j(\bold{x})=0$

3) Dual Feasibility
$\mu_i\geq0$

4) Complementary Slackness
$\mu_i g_i(\bold{x^*})=0$

KKT 조건을 적용해보면,
$minimize\ f(\bold{w})=$ $1\over2$$||\bold{w}||^2\ subject\ to\ g_i(\bold{w})=t_i(\bold{w^Tx_i}+b)-1\geq0$

1) $\nabla f(\bold{w^*})+\sum\alpha_i\nabla g_i(\bold{w^*})=0$

2) $g_i(\bold{w})=t_i(\bold{w^Tx_i^*}+b)-1\geq0$

3) $\alpha_i\geq0$

4) $\alpha_ig_i(\bold{w^*})=\alpha_i(t_i(\bold{w^{*^T}x_i^*}+b)-1=0$

Lagrangian에 의해,
$L(\bold{w},b,\alpha)=$ $1\over2$$||\bold{w}||^2-\sum\alpha_i[t_i(\bold{w^T}\bold{x_i}+b)-1]$

$∂L\over∂\bold{w}$ $=\bold{w^*}-\sum\alpha_it_i\bold{x_i}=0$
$∂L\over∂b$ $=\sum\alpha_it_i=0$

$∴L(\bold{w^*},b^*,\alpha)=\sum\alpha_i-$$1\over2$$\sum\sum\alpha_i\alpha_jt_it_j\bold{x_i^T}\bold{x_j}$

$minimize\ L(\bold{w},b,\alpha)\ ⇔\ maximize\ L(\bold{w^*},b^*,\alpha)\ ⇔\ maximize\ L_{dual}(\alpha)$
① 이를 통해 $\alpha$를 구함.

② $\bold{w^*}=\sum\alpha_it_i\bold{x_i}$
③ $b^*=$ $1\over N_s$$\sum(t_j-\sum\alpha_it_i\bold{x_i^T}\bold{x_j})$

---

Soft Margin

hyperplane에 의해 깔끔하게 분류되지 않음.
slack varialbe $\xi_i$를 통해 오류 허용을 조절.

$minimize\ f(\bold{w})=$ $1\over2$$||\bold{w}||^2+C\sum\xi_i$
$subject\ to\ g_i(\bold{w})=t_i(\bold{w^Tx_i}+b)\geq1-\xi_i,\ \xi_i\geq0$

$\xi_i=0$ : 분류 성공
$\xi_i>1$ : 분류 실패
$0<\xi_i<1$ : margin violation

Dual 문제를 적용하면
$maximize\ L_{dual}(\alpha)=\sum\alpha_i-$$1\over2$$\sum\sum\alpha_i\alpha_jt_it_j\bold{x_i^T}\bold{x_j}$
$subject\ to\ \sum\alpha_it_i=0\ for\ 0\le\alpha_i\le C$

$C$가 작을수록 margin은 커지고, 더 많은 오류 허용.
$C$가 클수록 margin은 작아지고, 더 적은 오류 허용.

---

Kernel

선형으로 분류하지 못할 경우, kernel 사용.

데이터를 더 높은 차원으로 mapping ($\Phi$)하여 hyperplane 결정.

$maximize\ L_{dual}(\alpha)=\sum\alpha_i-$$1\over2$$\sum\sum\alpha_i\alpha_jt_it_j\bold{\Phi(x_i)^T}\bold{\Phi(x_j)}$

$\bold{\Phi(x_i)^T}\bold{\Phi(x_j)}$을 kernel이라 함.

머서의 정리에 의해,
$maximize\ L_{dual}(\alpha)=\sum\alpha_i-$$1\over2$$\sum\sum\alpha_i\alpha_jt_it_jK(\bold{x_i},\bold{x_j})$

머서의 정리
함수 $K(\bold{a,b})$가 머서의 조건을 만족하면, $\bold{a}$와 $\bold{b}$를 더 높은 차원으로 mapping하는 $K(\bold{a,b})=\Phi(\bold{a})^T\Phi(\bold{b})$를 만족하는 함수 $\Phi$
가 존재.
따라서 $\Phi$를 계산하지 않더라도 존재함을 알기 때문에, $K$를 커널로 사용.

커널 종류
Linear : $K(\bold{a,b})=\bold{a^T·b}$
Polynomial : $K(\bold{a,b})=(\gamma\bold{a^T·b}+r)^d$
Gaussian RBF : $K(\bold{a,b})=exp(-\gamma||\bold{a-b}||^2)$
Sigmoid : $K(\bold{a,b})=tanh(\gamma\bold{a^T·b}+r)$

Gaussian Radial Bias Fnction
$K(\bold{a,b})=exp(-\gamma||\bold{a-b}||^2)$
2차원의 점을 무한한 차원의 점으로 mapping.

$\gamma$가 작을수록 표준편차가 커져서, decision boundary가 단조로움. ⇒ Underfitting
$\gamma$가 클수록 표준편차가 작아져서, decision boundary가 복잡해짐. ⇒ Overfitting

---

Reference
[학부생의 머신러닝] | General | SVM : Support Vector Machine
SVM(Support Vector Machine) 원리
[머신러닝] 9. 머신러닝 학습 방법(part 4) - SVM(1)
서포트 벡터 머신(Support Vector Machine) 쉽게 이해하기
Kernel/Kernel trick(커널과 커널트릭)