[Yongggg's] Support Vector Machine
오늘은 Support Vector Machine에 대해 알아보겠습니다. 딥러닝이 나오기 전에는 이 SVM이 가장 주목을 받았던 Mahine Learning Technique 중에 하나였습니다. 이 내용은 고려대학교 대학원에서 김성범 교수님과 강필성 교수님의 강의 자료와 ratsgo's blog내용을 바탕으로 정리했습니다.
1. 목적
Classification performance를 최대화 하는 작업에서, trainging error와 testing error는 모두 중요하다. 이를 해결하기 위해, SVM의 모델이 개발됐다. SVM은 기존 Classification Model들 보다 일반화 능력이 좋다. ( trainging error가 줄어들면 testing error 또한 줄어든다. )
2. 개념
범주를 나누기 위해서 Logistic Regression 처럼 일정한 threshold를 정해 분류하는 것이 아닌, 각 Support Vector를 기준으로 "margin"을 최대화 하는 초평면을 찾아 그 초평면을 기준으로 분류한다.
[그림 1]에서 두 Class를 나누는 초평면(Hyper Palne)은 무수히 많을 것이다. 이 때, '어떤 초평면이 가장 좋은 초평면인가?' 또 '"좋다"라는 기준은 무엇인가?'의 물음에 SVM을 시작한다.
[그림 1]에서는 빨간점과 파란점을 분류하기에 가장 적당한 초평면을 고르라하면, 빨간색 선이 아마 가장 좋은 분류면일 것이다. 이유는 초평면보다 두 범주의 사이의 거리가 넓기 때문이다. 이 거리를 'margin'이라 하고 이 margin을 최대화 하는 방향으로 학습이 진행된다.
3. 원리
Margin의 정의
[그림 2]에서 표현된 margin을 최대화하는 초평면을 찾는다.
support vector와 margin등을 찾는 원리에 대해 설명하겠다.
우리가 찾고자 하는 (초평면)경계면을 $ w^{T}x+b$라고 하면, 벡터 $w$는 이 초평면과 수직인 법선벡터가 된다. 예를들어 $w$가 2차원 벡터($w=(w_{1}, w_{2})^{T}$)라고 하면, 법선벡터가 $w$ 벡터인 원점과의 거리가 b인 직선의 방정식은 $ w^{T}x+b=w_{1}x_{1}+w_{2}x_{2}+b=0 $이 된다. 이 직선의 기울기는 $-w_{1}/w_{2}$이고, 법선벡터 $w$의 기울기는 $ w_{2}/w_{1}$이기 때문에 두 직선은 수직을 이룬다. [그림 3]과 같이 차원을 확장해도 마찬가지로 적용된다.
plus plane과 minus plane은 평행이기 때문에, plus plane위의 벡터 $x^{+}$와 minus plane 위의 $x^{-}$의 관계식은 (수식 1)과 같이 얻어낼 수 있다.
$$ x^{+} = x^{-} + \lambda w \quad (수식 1) $$
이 때, $\lambda$의 값은 support vector $x^{+}$가 plus plane, $x^{-}$가 munus plane위에 있다는 점과, (수식 1)의 관계식으로 (수식 2)와 같이 유도할 수 있다.
$$ w^{T}x^{+} + b=1 \\ w^{T}(x^{-}+ \lambda w)+b=1 \\ w^{T}x^{-}+b+ \lambda w^{T}w =1 \\ -1 + \lambda w^{T}w =1 \\ \lambda = {2 \over w^{T}w} \quad (수식 2)$$
그리고, margin은 plus plane과 minus plane의 수직 거리이다. 따라서 distance는 (수식 3)과 같이 유도할 수 있다.
$$distance(x^{+}, x^{-}) \\ = || x^{+} - x^{-}||_{2} \\ = ||x^{-} + \lambda w - x^{-} ||_{2} \\ = || \lambda w ||_{2} \\ = \lambda \sqrt{w^{T}w} \\ = {2 \over w^{T}w} \sqrt{w^{T}w} \\ = {2 \over \sqrt{w^{T}w}} \\ = {2 \over || w||_{2}} \quad (수식 3)$$
목적식 및 제약식 정의
SVM의 목적은 위에서 정의한 margin을 최대화하는 초평면을 찾는 것이다. (수식 4)와 같이 목적식을 최대화하는 문제에서 역수를 취해줌으로써 목적식을 최소화하는 문제로 바꾸었다.
$$ max \; margin = max {2 \over ||w||_{2}} \Longleftrightarrow min {1 \over 2} ||w||_{2} \quad (수식 4)$$
그리고, $w$의 $L_{2} norm$이 제곱근을 포함하고 있기 때문에 계산이 어렵다는 문제때문에, (수식 5)와 같은 형태로 목적함수를 변경하였다.
$$ min {1 \over 2 ||w||_{2}} \Longleftrightarrow min {1 \over 2} ||w||^{2}_{2} \quad (수식 5)$$
이 (수식 5)에서는 training data가 linearly separable한 경우에만 해가 존재한다. (그렇지 않은 경우는 목적식에 규제항을 추가함으로써 이를 해결할 수 있다.)
그리고 이 목적식에 대한 제약조건은 (수식 6)과 같이 관측치 개수만큼 붙는 것을 확인할 수 있다. plus plane보다 위에 있는 관측치들은 $class=1$이고 $w^{T}x+b$가 1보다 크다. 반대로 minus plane보다 아래에 있는 점은 $class=-1$이고 $w^{T}x+b$가 -1보다 작다. 이 두 조건을 한꺼번에 쓰면, (수식 6)과 같이 나타낼 수 있다. 이는 training data를 완벽하게 separating하는 조건으로 이해할 수 있다.
$$ y_{i}(w^{T}x_{i} +b \ge 1) \quad (수식 6) $$
Lagrangian 문제로 변환
라그랑지안 승수법(Lagrange multiplier method)는 승수를 곱한 항을 최적화하려는 목적식에 제약식을 더하여 문제를 풀어내는 방법이다.
(수식 5)와 (수식 6)을 라그랑지안 문제로 식을 바꾸면 (수식 7)과 같다.
$$ min L_{p}(w, b, \alpha_{i}) = {1 \over 2} ||w||^{2}_{2} - \sum_{i=1}^{n} \alpha_{i} ( y_{i} ( w^{T} x_{i} + b ) -1 ) \quad (수식 7) $$
원래의 목적식 (수식 5)의 범위가 0이상이기 때문에, $L_{p}$의 제약은 $ \alpha_{i} \le 0, 1, \cdots, n$이다.
Dual 문제로 변환
KKT 조건에서는 $L_{p}$를 미지수로 하여 각각 편미분한 식이 0이 되는 지점에서 최소값을 갖는다.
$$ {\partial L(w,b, \alpha_{i}) \over \partial w} =0 \rightarrow w= \sum_{i=1}^{n} \alpha_{i}y_{i}x_{i} $$
$$ {\partial L(w,b, \alpha_{i}) \over \partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_{i}y_{i} =0 $$
이 식을 L에 넣어 정리를 해보자.
첫 번째 Term :
$$ \begin{align} {1 \over 2} ||w||^{2}_{2} &= {1 \over 2} w^{T}w \\ &= {1 \over 2} w^{T} \sum^{n}_{j=1} \alpha_{j} y_{j} x_{j} \\ &= {1 \over 2} \sum_{j=1}^{n} \alpha_{j} y_{j} (w^{T}x_{j} ) \\ &= {1 \over 2} \sum_{j=1}^{n} \alpha_{j} y_{j} ( \sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}^{T} x^{j} ) \\ &= {1 \over 2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x^{T}_{i} x_{j} \end{align}$$
두 번째 Term :
$$ \begin{align} - \sum_{i=1}^{n} \alpha_{i} ( y_{i} (w^{T} x_{i} + b ) -1 ) &= - \sum_{i=1}^{n} \alpha_{i} y_{i} ( w^{T} x_{i} +b ) + \sum_{i=1}^{n} \alpha_{i} \\ &= - \sum_{i=1}^{n} \alpha_{i} y_{i} w^{T} x_{i} -b \sum_{i=1}^{n} \alpha_{i} y_{i} + \sum_{i=1}^{n} \alpha_{i} \\ &= - \sum^{n}_{i=1} \sum^{n}_{j=1} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} + \sum_{i=1}^{n} \alpha_{i} \end{align} $$
첫 번째 Term과 두 번째 Term을 더해 최종 목적식을 쓰면, (수식 8)과 같다.
$$ max L_{D}( \alpha_{i} ) = \sum_{i=1}^{n} \alpha_{i} - {1 \over 2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} (수식 8)$$
여기에서도 KKT 조건에 의하여 $L_{D}$의 제약식은 다음과 같다.
$$ \sum_{i=1}^{n} \alpha_{i} y_{i} =0 \\ \alpha_{i} \ge 0, i=1, \cdots, n $$
SVM의 해 도출
위에서 언급했듯이, 우리가 최종적으로 찾고자 하는 것은 margin을 최대화하는 분류경계면 $w^{T} x+b$ 이다. 여기에서 $w$와 $b$를 찾는 것이 SVM의 해를 구하는 것과 동일하다.
(수식 8)에서, 두 번째 Term은 Quadratic Form의 형태로 볼 수 있다. 이 말은 전역 최적해가 존재한다는 것이다.
Lagrangian Dual problem의 최적해가 되기 위한 KKT(Karush-Kuhn-Tucker)의 Stationarity 조건(Dual 문제로 변환 부분) 에서$w$는 ${\partial L(w,b, \alpha_{i}) \over \partial w} = 0 \rightarrow w= \sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}$로 구할 수 있었고, $x_{i}$와 $y_{i}$는 학습데이터이므로 알고 있다. 따라서 $ \alpha $값들만 알면 $w$를 구할 수 있다.
$ \alpha_{i} $가 0일 때에는 관측치 값이 어느 값이라도 구하고자 하는 초평면의 기울기에는 영향을 끼칠 수 없다. 이는 $ \alpha_{i} $가 0보다 커야 Margin을 결정하는데 관여를 한다는 것이다.
여기서 KKT의 Complementary slackness 조건은 $ \alpha_{i} (y_{i} (w^{T}x_{i} +b )-1) =0$을 만족해야 한다.
이 때 이 조건을 만족하려면,
- $\alpha_{i}$ > 0 and $y_{i} ( w^{T} x_{i} +b ) -1 =0 \quad (1)$ 또는
- $\alpha_{i}$ = 0 and $y_{i} (w^{T} x_{i} +b ) -1 \neq 0 \quad (2)$을 만족해야한다.
(1)의 경우 $x_{i}$가 plus-plane 또는 minus-plane (margin)위에 있다는 말이고 이를 Support vector라 표현한다. ( 해당 $\alpha_{i} >0 $)
(2)의 경우 plus-plane 또는 minus-plane 위에 있지 않다는 것이다. (해당 $\alpha_{i} = 0$), 이는 Hyper plane을 구축하는데 영향을 미치지 않는다는 말이기 때문에, SVM이 outlier에 robust하다는 것이다.
$b$는 위에서 구한 w와 학습데이터 샘플로 $y_{i}(w^{T}x_{i} +b -1) =0 $식을 이용하여 구할 수 있다.
새로운 데이터 샘플이 들어왔을 때, $y_{i} (w^{T}x_{i} +b -1)$식에 대입하여 0보다 크면 1, 0보다 작으면 -1로 예측하게 되는 것이다.
위의 SVM 외에도 original 목적식에 규제항을 추가하여, training error를 허용하여 완벽하게 linearly separable하지 않아도 SVM 평면을 찾을 수 있고 Kernel function을 이용하여 space를 옮긴 뒤 SVM을 분류하는 방법이 있다.
이렇게 SVM에 대하여 알아보았습니다. 이번 SVM을 정리하면서 KKT 조건이나, Lagrangian 문제 등은 자세하게 다루진 못했습니다. 저 또한 이런 조건들을 사용하는구나 정도로 공부를 했기 때문에 자세히 설명 못드린 점 양해 부탁드립니다. 그 외, 내용의 오류나 오타가 있다면 댓글에 남겨주시면 감사하겠습니다!