SVM을 시작해보자! SVM이 수행하는 작업은 분류다. 데이터를 가장 잘 분류하는 hyperplane을 찾는 것이다.
이해를 돕기 위해 초반부는 논문과 약간 다르게 데이터마이닝 수업 내용과 비슷한 흐름으로 진행되며, 수학적인 디테일이 추가되었다고 생각하면 좋다.
위와 같은 2차원 평면 위의 데이터에 대해 두 클래스가 있다. 이때 두 클래스가 선형 분류기에 의해서 완벽히 분리되는 separable한 경우라고 가정한다. (= hard margin을 가짐) 만약 이와 같이 가정한다면 위처럼 두 클래스를 분류하는 선형 모델은 검은 선처럼 무수히 많이 존재할 것이다. 그렇다면 과연 이 모델(선)들 중 최적의 모델을 어떻게 찾을 수 있을까? 직관적으로 생각한다면, 두 클래스가 구분되는 지점에서 모델이 한쪽으로 치우쳐 있는 것이 아니라 정중앙에 위치한다면 새로운 데이터를 더 잘 분류할 수 있을 것이기에 최적의 모델이 된다. 최적의 모델을 찾기 위해 margin에 대한 개념이 등장한다.
빨간색 선이 우리가 찾고자 하는 모델 hyperplane이다. margin은 hyperplane에서 가장 가까운 데이터까지의 거리의 두 배이다. 최적의 모델은 이 margin을 최대화하는 모델이며, 해의 유일성을 위해 한 가지 제약 조건이 필요하다.
$$ w^Tx_i-b\ge+1 \quad \mathrm{for} \;\; y_i=+1 \quad \& \quad w^Tx_i-b \le -1 \quad \mathrm{for} \;\; y_i=-1 \\ \Leftrightarrow y_i(w^Tx_i-b)\ge+1 $$
즉 모든 데이터는 margin 바깥에 있어야 한다는 것이다. 이러한 제약 조건 하에 우리가 최대화 하고자 하는 margin $M$은 다음과 구할 수 있다.
$$ w^Tx_0-b=0 \;\; \mathrm{and} \;\; w^Tx_1-b=1 $$
라고 가정하면, $w$는 hyperplane의 법선벡터(normal vector)이므로
$$ \\ x_1=x_0+pw \;\;(p>0) \\ p=\frac{1}{w^Tw} \\ \therefore M= 2\cdot|x_0-x_1| = 2\cdot|pw| = \frac{2}{||w||_2} $$
가 성립한다. 우리는 이 margin $M$을 위의 제약 조건 하에 최대화해야 하므로, 역수를 취해 제곱해주면 최소화 문제와 동일해지며 다음과 같이 식을 세울 수 있다.
$$ \min_{w,b} \; \frac{1} {2}||w||_2^2 \quad\mathrm{subject\;to}\;\; y_i(w^Tx_i-b)\ge+1 $$
위 제약이 있는 최적화 문제를 라그랑지안 승수법을 이용해 제약이 없는 최적화 문제로 바꿀 수 있다.
※ 데마 수업에서 본 식과 약간 다르다. $\beta^T\beta$ = 1 이라는 조건이 없는데, 이는 margin을 계산할 때 positive/negative plane에서 볼 수 있듯이 Support vector들이 속하는 평면의 상수항 값을 1로 제한했기 때문이다.