[ML] 수식과 함께 SVM 이론 파헤치기

이번 글은 SVM에 대한 내용입니다. 이 강의는 순천향대학교 정영섭 교수님의 강의와 핸즈온 머신러닝을 참고하여 정리했음을 먼저 밝힙니다.

 

순서

1. SVM Motivation

2. 특징

3. 비선형 SVM

4.1. 수식으로 보는 SVM

4.2. Lagrangian multiplier method

4.3. Dual 문제로 변환

5. 장단점

 

1. SVM Motivation

SVM은 Support Vector Machine의 줄임말입니다. 이 모델은 매우 강력하고 선형, 비선형 분류, 회귀, 이상치 탐색에 사용할 수 있습니다. 아래 그림에서 +,- 두 범주를 나누는 분류 문제를 푼다고 가정할 때 가장 잘 분류하는 선을 긋는다면 빨간색 선을 그을 수 있을 것입니다. 이렇게 두 범주를 나누는 선을 decision boundary라고 합니다. decision boundary와 데이터의 거리를 margin이라 하고 margin을 최대화하는 decision boundary 찾는 것이 SVM의 목표입니다. decision boundary는 두 개의 경계(노란 선)의 중간선이 되고 유일한 두 개의 경계선을 만족하려면 feature의 개수와 상관없이 최소 2개 이상의 데이터가 노란 선에 위치해야 합니다. 이렇게 노란색 위에 위치하는 데이터들을 support vector라고 합니다. -쪽의 hyperplane을 negative hyperplane, +쪽의 hyperplane을 positive hyperplane이라고 합니다. 

S

2. 특징

SVM은 feature 스케일에 민감합니다. 모든 샘플이 negative hyperplane과 positive hyperplane 바깥쪽에 올바르고 분류되어 있다면 이를 하드 마진 분류라고 합니다. 하드 마진 분류는 데이터가 선형적으로 구분될 수 있어야 제대로 작동하고 이상치에 민감합니다. 이 문제를 피하기 위해서는 마진을 최대화하려는 것과 마진 오류 사이에 적절한 균형을 잡습니다. 이러한 분류 방법을 소프트 마진 분류라고 합니다. 마진 오류는 일반적으로 적은 것이 좋고 모델이 과대적합이라면 마진 오류를 증가시켜 모델을 규제할 수 있습니다. 즉, 마진 오류를 하나도 발생하지 않는 것을 하드 마진, 제한적인 마진 오류를 가지는 것을 소프트 마진이라고 합니다.  

 

3. 비선형 SVM

비선형 SVM 분류기는 다항 특성과 같은 특성을 더 추가하는 것입니다. 다항식 특성을 추가할 때 낮은 차수의 다항식은 복잡한 데이터셋을 잘 표현하지 못하고 높은 차수의 다항식은 많은 특성을 추가하므로 모델을 느리게 만듭니다. 커널 트릭을 이용하면 실제로 특성을 추가하지 않으면서 특성을 많이 추가한 것과 같은 결과를 얻을 수 있습니다. 모델이 과대적합이라면 다항식의 차수를 줄이고 과소적합이라면 다항식의 차수를 늘려서 좋은 모델을 만들어냅니다.

 

비선형 특성을 다루는 두번째 방법은 각 샘플이 랜드마크와 얼마나 닮았는지를 측정하는 유사도 함수로 계산한 특성을 추가하는 것입니다. 이때 가우시안 RBF(방사 기저 함수)를 이용할 수 있습니다. 이 함수는 랜드마크에서 아주 멀릴 떨어지면 0, 같은 위치이면 1까지 변화하며 종 모양입니다. 랜드마크는 데이터셋에 있는 모든 샘플 위치에 설정합니다. 이 방법은 차원이 매우 커지고 변환된 훈련 세트가 선형적으로 구분될 가능성이 높습니다.

 

4.1. 수식으로 보는 SVM

Decision boundary 수식을 $W^TX+b=0$의 수식을 따른다고 할 때, 가중치 벡터 W는 decision boundary와 직교해야 합니다. 계산상의 편의를 위해 b=0으로 가정하여 원점을 지난다고 할 때 $w^TX=0$을 decision boundary라고 정의할 수 있고 2개 벡터 내적의 결과가 0이 되는 각도는 90이기 때문입니다. 

 

노란색 선의 수식은 +쪽이 가지는 class 값을 +1, -쪽에서 가지는 class값을 -1이라고 한다면 +쪽에 있는 노란 선 경계선을 $w^Tx+b=1$, -쪽에 있는 노란색 경계선을  $w^Tx+b=-1$로 나타낼 수 있습니다. 각 데이터들은  $w^Txi+b>1$, $w^Txi+b>-1$에 해당하는 점들이 여러 개 모여있는 것입니다. 이 사실을 바탕으로 $x^+$ (+1에 해당하는 데이터)는 $x^-$(-1에 해당하는 데이터)의 λ 폭 만큼 w방향으로 평행 이동한다고 정의할 수 있습니다.

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

 

그리고 $\lambda$에 의한 수식으로 정의를 하면 아래와 같이 유도됩니다.

 

$$w^Tx^++b=1$$

$$w^T(x^-+\lambda w) +b=1$$

$$w^Tx^-+\lambda w^Tw +b=1$$

$$-1+\lambda w^Tw = 1$$

$$\lambda = {2 \over w^Tw}$$

 

 

margin은 $x^+$, $x^-$의 차이로 수식을 작성하면 다음과 같습니다.

 

 

$$Margin = distance(x^+, x^-)$$

$$=||x^+-x^-||_2$$

$$=||x^-+\lambda w-x^-||_2$$

$$=||\lambda w||_2$$

$$=\lambda \sqrt{w^Tw}$$

$$={2\over w^Tw}* \sqrt {w^Tw}$$

$$={2 \over \sqrt {w^Tw}}={2 \over ||w||_2}$$

 

 

margin은 ${2 \over w L2 norm}$라고 표현됩니다. L2 norm은  $||W||_2$ $w_i$제곱의 합에 제곱근을 씌운 것으로 즉, 각 elemenent 제곱의 합에 제곱근을 씌운 것입니다. L2 norm은 제곱근을 포함하고 있기 때문에 계산이 어렵기 때문에 계산상의 편의를 위해 목적함수를 다음과 같이 변형합니다.

 

$$max ({2 \over ||w||_2}) \to min({1 \over 2}||w||_2^2)$$

 

목적식은 위와 같고 제약식은 margin을 적어도 1보다 크게 하는 w, b를 찾자는 다음과 같은 수식을 갖게 됩니다.

$$y_i(w^Tx_i + b) \geq1$$  

 

이와 같은 수식들을 통해 w는 decision boundary의 기울기의 계수 값으로 max-margin을 구하는 것은 w라는 weight matrix에 대한 최소화를 푸는 문제가 됩니다.

 

목적 식이 w의 제곱으로 이차식, 제약식은 linear 한 형태로 되어있는데 이런 형식을 최적화해서는 quadratic programming(2차 계획법)으로 부릅니다. quadratic programming은 최솟값 또는 최댓값이 1개로 도출되는 convex optimization이기 때문에 이미 개발된 해결법을 이용하여 쉽게 w, b를 찾아낼 수 있습니다.

 

4.2. Lagrangian multiplier method

Lagrangian multiplier method(라그랑주 승수법)을 이용하여 목적식과 제약식을 하나로 표현할 수 있습니다. 라그랑주 승수법은 제약식이 존재하는 문제를 제약이 없는 문제로 바꾸는 기법으로 제약식에 신경 쓰지 않을 수 있습니다.

 

$$minL_p(w, b, \alpha_i) = {1 \over 2}||w||_2^2-\sum_{i=1}^{n}\alpha_i[y_i(w^Tx_i+b)-1]$$

4.3. Dual 문제로 변환

KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 W는 최솟값을 가집니다. 미분한 식은 다음과 같습니다.

 

w에 대한 미분

$${dLp \over dw}=0$$

$$w = \sum_{i=1}^{n}{a_iy_ix_i}$$

 

b에 대한 미분 

$${dLp \over db}=0$$

$$0 = \sum_{i=1}^{n}{a_iy_i}  (a_i \geq 0)$$

 

 

w를 찾기 위해서는 Lagrangian multiplier인 $\alpha$를 알아야 합니다. $\alpha$는 위 식을 $L$식에 대입하여 유도할 수 있습니다.

 

첫 번째 항

$${1 \over 2}||w||_2^2={1 \over 2}w^Tw$$

$$={1 \over 2}w^T \sum_{j=1}^{n}\alpha_jy_jx_j$$

$$={1 \over 2} \sum_{j=1}^{n}\alpha_jy_j(w^Tx_j)$$

$$={1 \over 2} \sum_{j=1}^{n}\alpha_jy_j(\sum_{i=1}^{n}\alpha_jy_jx_i^Tx_j)$$

$$={1 \over 2} \sum_{j=1}^{n}\sum_{i=1}^{n} \alpha_i \alpha_jy_iy_jx_i^Tx_j$$

 

두 번째 항

$$-\sum_{i=1}^{n}\alpha_i[y_i(w^Tx_i+b)-1] = -\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j y_iy_jx_i^Tx_j+ \sum_{i=1}^{n}\alpha_i$$

 

이 결과를 정리하면 

 

$$maxL_p(\alpha_i)=\sum_{i=1}^{n}\alpha_i-{1 \over 2} \sum_{j=1}^{n}\sum_{i=1}^{n} \alpha_i \alpha_jy_iy_jx_i^Tx_j$$

 

KKT 조건에 의해 $L_p$의 제약식은 $\sum_{i=1}^{n}\alpha_iy_i = 0$ 입니다.

 

max, min 문제에서 alpha에 의해 정의되었기 때문에 alpha만 구하면 되는 dual문제로 변환되었습니다. 결국 max-margin은 w를 최소화한다는 것, 즉 $\alpha$를 최대화한다는 것을 뜻합니다. 

 

KKT 조건에 의해 $\alpha_i=0$ 이거나 $y_i(w^Tx_i+b)=1$이 반드시 성립되어야합니다. 따라서 $x_i$는 노란 경계선 위에 있는 벡터가 됩니다. b는 이미 구한 w와 학습데이터를 이용하여 구할 수 있기 때문에 새로운 데이터가 입력되었을 때 $y_i(w^Tx_i + b -1)$ 수식을 통해 범주를 예측할 수 있습니다. 

 

5. 장단점

SVM은 feature dimension이 커질수록 내적 시간이 커지기 때문에 큰 문제는 없고 과적합 되는 경우가 적다는 장점이 있지만 최적의 모델을 찾기 위해서 커널과 모델에서 다양한 테스트를 필요로 하기 때문에 데이터가 많아질수록 연산량 증가로 학습속도가 저하된다는 단점이 존재합니다. 또한 해석도 어렵다는 단점이 있습니다.

 

 

 

참고

파이썬으로 실습하는 SVM(Github)

[핵심 머신러닝] SVM 모델 1(Margin, Hard Margin Linear SVM)