[딥러닝] 서포트 벡터 머신 (SVM)

서포트 벡터 머신 (Support Vector Machine; SVM)

고차원 데이터의 분류 문제에서 좋은 성능을 나타내는 분류 방법

분류 오차를 줄이면서 동시에 여백을 최대로 하는 결정 경계를 갖는 이진 분류기

 

결정 경계 (decision boundary): $w^Tx+b=0$으로 나타낼 수 있다.

여백(margin): 결정 경계와 가장 가까이에 있는 학습 데이터까지의 거리. 기울기로 표현 가능하다.

서포트 벡터(support vector): 결정 경계로부터 가장 가까이에 있는 학습 데이터들

출처 https://velog.io/@shlee0125/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-%EC%A0%95%EB%A6%AC-%EC%84%9C%ED%8F%AC%ED%8A%B8-%EB%B2%A1%ED%84%B0-%EB%A8%B8%EC%8B%A0Support-Vector-Machine-06.-Soft-margin-SVM-1

$x^+$: plus plane 위의 점, $x^-$: minus plane 위의 점이라 하자.

$x^+=x^-+\lambda w$라 하면 $w^Tx^++b=1$은 $w^T(x^-+\lambda w )+b=1 $로 표현된다.

이를 전개하면 $w^Tx^- +b + \lambda w^Tw=1$,

$-1+ \lambda w^Tw=1, \; 따라서 \; \lambda = \frac{2}{w^Tw}$

 

$Margin=distance(x^+,x^-)=\left\| x^+-x^- \right\|_2=\left\| \lambda w \right\|_2 = \lambda \sqrt{w^Tw}$

$ \lambda = \frac{2}{w^Tw}$를 대입하면 $\frac{2}{w^Tw} \cdot \sqrt{w^Tw}=\frac{2}{\sqrt{w^Tw}}=\frac{2}{\left\| w \right\|_2}$

 

즉 여백을 최고로 하는 목적함수는 다음과 같다. $$max Margin = max \frac{2}{\left\| w \right\|_2} \leftrightarrow min \frac{1}{2}\left\| w \right\|_2$$

그런데 위 식은 제곱근을 포함하고 있기 때문에 계산이 어려워, 계산상의 편의를 위해 다음과 같이 목적함수를 변경한다.

$$ min \frac{1}{2}\left\| w \right\|_2 \leftrightarrow min \frac{1}{2}\left\| w \right\|_2 ^2$$ $$학습조건 \; subject \, to \, y_i(w^Tx_i) \geq 1, \; i=1,2,...,n$$

 

위 문제를 Lagrangian multiplier를 이용하여 Lagrangian primal 문제로 변환한다.

$$max_{\alpha} \, min_{w,b} \, L(w,b,\alpha)=\frac{1}{2} \left\|w\right\|_2^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i+b)-1)$$ $$ subject \, to \, y_i(w^Tx_i) \geq 1, \; i=1,2,...,n$$

 

대상 함수가 미분가능이고 연속이므로 미분=0에서 최솟값을 가진다.

1. $\frac{\partial L(w,b,\alpha)}{\partial w}=0 \overset{}{\rightarrow} w=\sum_{i=1}^{n}\alpha _iy_ix_i$
2. $\frac{\partial L(w,b,\alpha)}{\partial b}=0 \overset{}{\rightarrow} \sum_{i=1}^{n}\alpha _iy_i=0$

위 1, 2번을 이용해 $min_{w,b} \, L(w,b,\alpha)=\frac{1}{2} \left\|w\right\|_2^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i+b)-1)$를 다음과 같이 바꿀 수 있다. $$\sum_{i=1}^{n}\alpha_i - \frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j x_i^T x_j$$ $$where \; \sum_{i=1}^{n}\alpha_iy_i = 0$$

 

---

SVM을 이용한 비선형 문제

$$minimize_{w,b,\xi} \frac{1}{2} \left\| w \right\|_2^2 + C \sum_{i=1}^{n}\xi_i$$ $$ subject \, to \, y_i(w^Tx_i+b) \geq 1-\xi, \; \xi \geq 0 \; i=1,2,...,n$$

이때 $C$는 margin과 training error에 대한 트레이드 오프를 결정하는 turnning paramter (크면 오버피팅, 작으면 언더피팅)

 

데이터가 직선으로 구분되지 않을 경우에도 해가 존재하며, 이런 경우 커널을 이용한다.

SVM Kernal

관측치 x들을 더 높은 차원으로 변환시켜 분류하자는 아이디어로부터 출발.

변환: $x=(x_1,x_2,...,x_n) \rightarrow \phi (x) =z=(z_1,z_2,...,z_n)$

 

SVM을 원래 데이터(비선형 결정 경계)가 아닌 feature space(선형 결정 경계)에서 학습시킨다.

왜? 고차원 feature space에서는 관측치 분류가 더 쉬울 수 있고 효율적으로 계산할 수 있는 방법이 있기 때문

$$\sum_{i=1}^{n}\alpha_i - \frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j x_i^T x_j$$ $$where \; \sum_{i=1}^{n}\alpha_iy_i = 0$$ 여기서 $x_i$를 $\phi(x_i)$로 바꾸면 아래와 같다.

$$\sum_{i=1}^{n}\alpha_i - \frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j \phi (x_i)^T \phi (x_j)$$ $$where \; \sum_{i=1}^{n}\alpha_iy_i = 0$$ $$0 \leq \alpha_i\leq C, \; i=1,2,....n$$

 

커널 함수

• Linear Kernal: $K \left< x_1, x_2 \right > = \left< x_2, x_2 \right>$
• Polynomial Kernal: $K \left< x_1, x_2 \right > = (a \left< x_1, x_2 \right> + b)^d$
• Sigmoid Kernal(Hyperbolic tangent Kernal): $K \left< x_1, x_2 \right > = tanh( a \left< x_1, x_2 \right> + b )$
• Gaussian Kernal(Radial basis function Kernal): $K \left< x_1, x_2 \right > = exp(\frac{-\left\| x_1 - x_2 \right\|_2^2}{2\sigma^2})$