9. 서포트 벡터 머신 (Support Vector Machine: SVM)

서포트 벡터 머신은 딥러닝 이전에 가장 일반적이고 뛰어난 성능을 보였던 지도학습 모델이다.
주로 분류 문제에 많이 사용되지만, 회귀 문제에도 사용할 수 있다.

SVM은 두 데이터 집합을 나누는 결정 경계의 마진이 최대화 되도록 학습한다. 마진이란, 결정 경계와 데이터의 거리를 의미한다.

용어

• 결정 경계: 결정 경계는 두 클래스의 데이터를 분류하는 기준이 되는 경계로, Linear SVM의 결정 경계는 데이터의 feature $n$차원의 초평면^Hyperplane이 된다.
• 서포트 벡터^{Support Vector}: 결정 경계에 가장 가까이 있는 각 클래스의 데이터를 의미한다.
• 마진^Margin: 어떤 데이터도 포함하지 않는 영역. 서포트 벡터와 결정 경계의 거리.

Linear SVM

결정 경계를 이루는 초평면 $H$는 다음과 같이 정의된다. 

$$H= W^TX+b = 0$$

이때, $W^T$는 결정 경계의 법선 벡터이다. (즉, 법선 벡터의 크기가 0 이므로 위 $H$는 결정 경계가 된다.)

클래스 A, B의 서포트 벡터는 각각 $W^TX+b =1$ 평면과 $W^TX+b = -1$평면을 지나는 벡터로 표현할 수 있으며, $W^TX+b$가 1보다 크면 클래스 A, -1보다 작으면 클래스 B로 분류가 가능하다.

이때, 두 서로 다른 클래스에 속한 데이터의 관계는 $X_+ = X_- + \lambda W, \lambda = \frac{2}{W^TW}$가 된다.

SVM의 목적 함수^Objective와 제약 함수^Constraints

즉, 마진은 두 서포트 벡터 간의 거리이므로, L2 norm으로 나타낼 수 있는데

$$\begin{align*} \text{Margin} &= ||X_+-X_-||_2 \\ &= ||(X_-+\lambda W)+X_-||_2\\ &= ||\lambda W||_2\\ &= \frac{2}{||W||_2} \end{align*}$$

위와 같다.

마진의 최대화는, 마진의 역수의 최소화로 나타낼 수 있다. 즉, SVM의 목적함수는 다음과 같다.

$$\text{minimizing}(\frac{||W||_2}{2})$$

또한, L2 Norm의 계산상의 편의를 위해, 제곱해주면 아래와 같다.

$$\text{minimizing}(\frac{||W||^2_2}{2})$$

이때, 아래 제약 함수가 성립해야한다.

$$y_i (W^Tx_i+b) \geq 1, i=1,2, \cdots , n$$

목적식과 제약식 합치기

라그랑지 승수를 통해 목적식과 제약식을 합쳐보자.

제약 함수는 다음과 같이 변형될 수 있다.

$$y_i(W^Tx_i+b) - 1\geq0, i=1,2,\cdots, n$$

이제 위 식의 좌변을 목적식에서 빼보자.

$$\max_a\min_{W, b}(\frac{1}{2}||W||^2_2 - \sum_{i=1}^n a_i(y_i(W^Tx_i + b)-1))$$

$$a_i \geq 0, i=1, 2, \cdots , n$$

이렇게 합쳐진 식을 Primal Problem이라 한다. 이를 유사하게 다시금 변환하면 Dual Problem이 된다.

$$\max_a \sum_{i=1}^na_i - \sum_{i=1}^n \sum_{j=1}^n a_ia_jy_iy_jx_i^Tx_j \\ \sum_{i=1}^n a_iy_i = 0, a_i \geq 0 , i=1,2,\cdots, n$$

이제 문제는 W와 b를 설정하는 문제에서 a를 설정하는 단순한 문제로 변환되었다.

Complementary Slackness

이제 식 $a_i(y_i(W^Tx_i+b)-1) = 0$을 보자. 해당 식이 성립하려면, $a_i$나 뒷부분이 0이어야 한다.

• $x_i$가 서포트 벡터인 경우: 식의 뒷부분이 0이 되어, $a_i$는 0이 아니다.
• $x_i$가 서포트 벡터가 아닌 경우: 식의 뒷부분이 0이 아니므로, $a_i$가 0이 되야 한다.

이는 결정 경계의 결정, 즉 학습과정에서 서포트 벡터가 아닌 데이터의 영향을 배제시킨다. 이로인해 SVM은 outlier에 굉장히 강건하다.

SVM의 학습

그래서, 결정 경계의 $W,b$는 도대체 어떻게 구할까?

$$W = \sum_{i=1}^n a_iy_ix_i = \sum_{i\in SV} a_iy_ix_i$$

기울기는 서포트 벡터를 가져다 쓴다. 얼핏보면 모든 데이터를 참조하는 것 같지만, 서포트 벡터가 아닌 데이터에서 $a_i=0$이기 때문이다.

$$b = y_{SV} - \sum_{i=1}^n a_iy_ix_i^Tx_{SV}$$

SVM의 추론

이제 마침내 추론이다! 추론 과정은 다음과 같다.

$$\text{pred} = \text{sign}(W^Tx+b)$$

sign 함수는 값이 0보다 크면 클래스 A, 작으면 B를 매핑한다.

Soft Margin SVM

지금까지 배운 SVM은 서포트 벡터가 구성하는 결정 경계 사이에 데이터를 허용하지 않는, Hard Margin SVM이었다.
반면, 결정 경계 사이에도 데이터를 허용하는 SVM을 Soft Margin SVM이라 한다.

소프트 마진 SVM

소프트 마진 SVM은 데이터에 어느 정도 에러가 있음을 인정하기 때문에, 선형 분리가 불가능한 문제에도 적용할 수 있다. 이때, 데이터의 에러를 설명하는 변수로 프사이($\psi$)를 도입한다.

$$\min_{W,b,\psi} \frac{1}{2} ||W||_2^2 + C\sum^n_{i=1}\psi _i$$

SVM은 기존 마진을 최대화함과 동시에 뒤에 추가된 패널티 항을 최소화 해야한다.

이때, 사용자가 패널티 계수 $C$를 얼마로 해주느냐에 따라 에러의 허용범위가 달라진다.
(클 수록 강한 규제 -> 오버피팅)

위 식을 Duel Problem으로 정리하면 아래와 같다.

$$\max_{a}\sum_{i=1}^na_i - \sum_{i=1}^n \sum_{j=1}^n a_ia_jy_iy_jx_i^Tx_j\\ \sum_{i=1}^n a_iy_i = 0, 0\leq a_i \leq C, i=1,2,\cdots, n$$

기본적으로 하드 마진 SVM과 식이 같으나, $a_i$에 $C$로 상한이 생겼다.