DAY58 - 서포트 벡터 머신

데이터를 분류하는 선형판별함수를 생각해낸다고 했을 때 데이터를 완벽히 분류하는 단 하나의 선형판별함수가 아닌 여러 개의 선형판별함수가 나올 수 있습니다.

 

이렇게 여러 선형판별함수가 나올 수 있다고 하였을 때 가장 안정적인 선형판별함수를 만들어 내는 방법이 바로 서포트 벡터 머신입니다.

 

SVM

서포트벡터머신에 대해 설명하기 전에 먼저 "가장 안정적인 선형판별함수"를 찾는 것은 무슨 의미일까요?

안정적이라는 것은 판별함수가 한 쪽의 데이터그룹으로 너무 붙지 않고 양 그룹의 중간 즈음에 적당히 위치하면서도, 판별선과 그룹간의 거리가 최대한 멀리 떨어진 함수를 찾겠다는 의미입니다.

 

위의 그림에서 만약 판별함수가 O쪽으로 바싹 붙어있게 되면 O근처에 새로운 데이터가 들어오더라도 X라고 분류하게 되는 결과를 야기할 수 있기 때문입니다.

 

서포트벡터머신에서는 $y$값으로 $1$ 또는 $-1$을 갖게 됩니다.

보유 중인 데이터 중에서 $1$을 갖는 입력 데이터들을 $x_{+}$, $-1$을 갖는 입력 데이터들을 $x_{-}$라고 하겠습니다.

 

$f(x) = w^Tx - w_0$가 판별함수라고 하였을 때 $x_{+}$과 $x_{-1}$는 다음과 같은 식을 만족하게 됩니다.

$$ f(x_{+}) = w^Tx_{+} - w_0 \gt 0 $$

$$ f(x_{-}) = w^Tx_{-} - w_0 \lt 0 $$

 

그리고 $x_{+}$ 중에서 가장 판별함수값이 작은($y=1$인 데이터 중 가장 초평면과 가까운) 데이터를 $x^{+}$, $x_{-}$ 중에서 가장 판별함수 값이 큰($y=-1$인 데이터 중 가장 초평면과 가까운) 데이터를 $x^{-}$라고 하겠습니다.

 

이 두 데이터들이 바로 서포트 벡터라고 하는 것이 됩니다.

 

서포트벡터머신에서는 위 처럼 모든 데이터들을 잘 분류해내는 선형판별함수 중 다음을 만족하는 함수를 후보군으로 선정합니다.

$$ f(x^{+}) = 1 $$

$$ f(x^{-}) = -1 $$

 

이 때 $f(x)$와 각 점 $x^{+}$, $x^{-}$ 사이의 거리는 각각 $\frac{1}{||w||}$, $\frac{1}{||w||}$가 되고 이 거리의 합을 "마진(margin)"이라고 부릅니다.

$$ \text{margin} = \frac{2}{||w||} $$

 

서포트벡터머신은 마진을 최대화하는 $w$값을 찾아 최종 선형판별함수로 결정하는 것입니다.

$\frac{2}{||w||}$ 값을 최대화한다는 것은 반대로 생각하면 다음과 같은 값을 최소화하는 문제이기도 합니다.

$$ L = \frac{1}{2} ||w||^2 = \frac{1}{2}w^Tw$$

 

단 모든 데이터들을 잘 분류해내야하기 때문에 다음과 같은 제약식을 만족해야 합니다.

$$ y_i f(x_i) \ge 1 $$

 

여기에 라그랑주 승수법을 적용하면 다음을 최소화하는 문제가 됩니다.

$$ L = \frac{1}{2}w^Tw - \sum_{i=1}^N \lambda_i \{y_i(w^Tx_i - w_0) - 1\} $$

 

부등식 제약조건이 있는 최적화 문제에서 라그랑주 문제를 해결하는 것이 원래의 풀고자 했던 문제와 동일한 결과가 나오기 위해서는 KKT조건을 따라야 합니다.

 

KKT조건 (1)에 의하면 $w$로 미분한 값은 0이 되어야합니다.

$$ \dfrac{\partial L}{\partial w} = w - \sum_{i=1}^N \lambda_i y_i x_i = 0$$

$$ w = \sum_{i=1}^N \lambda_i y_i x_i $$

 

KKT조건 (2)에 의하면 $\lambda_i \{ y_i(w^Tx_i - w_0)\} = 0$

이 되어야 하는데 여기서 $\lambda_i = 0$이 되는 경우는 부등식 제약조건이 필요가 없는 경우에 0이 됩니다.

 

$x^{+}$와 $x^{-}$는 각 그룹에서 초평면과 가장 가까운 데이터들입니다. 따라서 이 두 개의 데이터만 부등식 제약조건을 만족하면 나머지는 자동으로 부등식 제약조건을 만족하게 되므로 $x_i = x^{+}$일 때와 $x_i = x^{-}$를 제외하고는 $\lambda_i = 0$이 됩니다.

 

$$ L = \frac{1}{2}w^Tw - \left( \lambda^{+}\{ y^{+}(w^Tx^{+} - w_0) \} \right) - \left( \lambda^{-}\{ y^{-}(w^Tx^{-} - w_0) \} \right) $$

 

다시 한 번 $w$로 미분해서 0이 되어야한다는 조건을 대입시켜 보면

$$ \dfrac{\partial L}{\partial w} = w - \lambda^{+}x^{+} + \lambda^{-}x^{-} = 0$$

$$ w = \lambda^{+}x^{+} - \lambda^{-}x^{-} $$

 

이렇게 구해진 $w$를 $f(x) = w^Tx - w_0$에 대입하면 SVM에서 최종적으로 선정하는 선형판별함수는

$$ f(x) = \lambda^{+}x^Tx^{+} - \lambda^{-}x^Tx^{-} - w_0 $$

 

$w_0$ 값은 $f(x^{+}) = 1$, $f(x^{-1}) = -1$이라는 사실을 통해서 구할 수 있습니다.

 

 

SVM with Python

from sklearn.svm import SVC
model = SVC(kernel='linear', C=1e10)