서포트 벡터 머신
업데이트:
서포트 벡터 머신
서포트 벡터 머신(SVM)은 클래스를 분리하기 위해 feature space에서 선형 또는 선형 의사결정 경계를 학습하는 판별적 모델이다. 실습 코드는 링크로 가면 된다.
1. 분리 초평면에 대해
클래스들을 분리하는 초평면(hyperplane)은 다음과 같이 쓴다.
\[w^Tx+b=0\]※ x는 feature를 뜻하고, w,b는 초평면의 파라미터이다.
w는 초평면에 수직한 법선 벡터이다. 증명하는 방법은 다음과 같다.
초평면 위에 두 점 $x_1,x_2$가 있다고 해보자. 그럼 $w^Tx_1+b =0,w^Tx_2+b =0$이 되고, 두 식을 빼면 $w^T(x_2-x_1)=0$ 이 된다. 내적의 원리에 의해, 초평면과 평행한 벡터인 $x_1x_2$와 w는 수직하다. 따라서 w는 초평면에 수직한 법선 벡터가 된다.
데이터 $x_i$는 $w^T+b$의 부호에 따라서 초평면의 양쪽에 속할 수 있다. 그래서 우리의 목적은 데이터를 분류해주는 기준인 초평면의 파라미터들을 찾는 것이다! 초평면으로 전체 데이터를 완벽하게 분리할 수 있으면, 데이터 집합을 선형으로 분리할 수 있다고 얘기할 수 있다. 그러나 클래스들을 분리해주는 초평면은 무수히 많다. 그림 1을 보자.
 |
|---|
| 그림 1 |
초평면을 어떻게 결정하느냐에 따라서, 우리는 데이터들을 분리하는 것의 일반화 성능을 최대치로 이끌어낼 수 있다. 이것은 마진(margin) 개념을 사용함으로써 가능해진다.
 |
|---|
| 그림 2 |
그림 2를 보면, $B_1,B_2$의 초평면들이 보인다. 그리고 각각 $b_{i1},b_{i2}$의 평행한 초평면들을 갖는다. 그리고 평행한 서브 초평면들의 거리를 초평면 $B_i$의 거리, 마진 초평면라고 부른다. 그림 2에서 $B_1$은 가장 긴 초평면 거리를 가지므로, 이것을 최대 마진 초평면(maximum margin hyperplane)을 가진 분리 초평면이라고 부른다.
최대 마진의 이론적 근거
만약 그림 2에서 $B_2$를 분리 초평면으로 선택해보자. 그러면 조금만 feature가 변하면 클래스가 바뀌는 취약한 상황에 놓일 것이다. 따라서 가장 긴 초평면 거리를 갖는 분리 초평면을 찾아야 일반화 성능이 뛰어나다.
2. 선형 SVM(linear SVM) : Separable
선형 SVM은 최대 마진을 갖는 분리 초평면을 사용하는 분류기를 뜻한다. 기본적으로 다음 식으로 클래스 $y_i$를 결정한다.
\[\begin{cases} w^Tx_i+b>0 & if \;y_i=1 \\ w^Tx_i+b<0 & if \;y_i=-1 \end{cases}\]초평면과 데이터 x와의 거리는 점과 직선의 거리 방정식을 통해 다음과 같이 얻을 수 있다.
\[D(x)=\frac{|w^Tx+b|}{||w||}\]이제 $k_+,k_-$를 다음과 같이 가정하자.
- $k_+$는 y=1인 클래스 중 분리 초평면과 가장 가까운 점과의 거리
- $k_-$는 y=-1인 클래스 중 분리 초평면과 가장 가까운 점과의 거리
그러면 기존의 linear SVM 식은 다음과 같이 바꿔쓸 수 있다.
\[\begin{cases} w^Tx_i+b>k_+ & if\;y_i=1 \\ w^Tx_i+b<k_- & if\;y_i=-1 \end{cases}\]조금만 생각해보면 너무나 당연한 식이다. 머릿속으로 상상해보자. $k_+$가 분리 초평면과 클래스 y=1 중 가장 가까운 점의 거리이니, 이 값보다 더 긴 거리를 갖는 데이터들은 전부 클래스 y=1에 속하게 될 것이다. $k_-$도 마찬가지다.
Margin of a Linear Classifier
여기서 마진 서브 초평면들 $b_{i1},b_{i2}$를 원래의 분리 초평면의 파라미터들을 rescale해서 다음과 같이 설정했다고 하자.
\[\begin{align*} b_{i1} &: w\cdot x + b = 1, \\ b_{i2} &: w\cdot x + b = -1 \end{align*}\] |
|---|
| 그림 3 |
각각의 모습은 그림 3에서 볼 수 있다. 두 서브 초평면들의 마진 초평면을 구하기 위해, 각각의 초평면들에 $x_1,x_2$가 놓여있다고 하자. 위 식은 다음과 같이 바뀐다.
\[\begin{align*} b_{i1} &: w\cdot x_1 + b = 1, \\ b_{i2} &: w\cdot x_2 + b = -1 \end{align*}\]두 식을 빼면, $w\cdot(x_1-x_2)=2$를 얻게 된다. 그럼 여기서 마진 초평면 $d$는 어떻게 구할까? 여기서 벡터의 개념을 잘 생각해야한다. 두 데이터들간의 벡터 $(x_1-x_2)$는 2개의 방향으로 쪼개질 수 있다. w와 평행한 방향과 w와 수직한 방향으로. 그럼 $w\cdot(x_1-x_2)=2$는 다음과 같이 쪼개진다.
\[w\cdot(x_1-x_2)_{w^{\parallel}} + w\cdot(x_1-x_2)_{w^{\bot}} = 2\]그럼 수직한 방향은 내적에 의해 0이되고, 평행한 방향 즉, 서브 초평면들의 거리인 마진 초평면 $d$만 남게된다. 그래서 위 식은 다음과 같이 정리된다.
\[||w||d = 2, \; \therefore \; d=\frac{2}{||w||}\]선형 SVM 학습하기
SVM을 학습한다는 것은 파라미터 $w,b$를 학습 데이터들을 사용해서 예측하는 것이다. 파라미터들은 다음의 두 조건을 만족하는 방법으로 선택된다.
\[\begin{cases} w^Tx_i+b>=1 & if\;y_i=1 \\ w^Tx_i+b<=1 & if\;y_i=-1 \end{cases}\]이 조건들은 y=1인 모든 학습 데이터들이 $w\cdot x+b=1$의 서브 초평면에 있거나 더 위에 있어야 함을 보이고, 반대로 y=-1인 모든 학습 데이터들이 $w\cdot x+b=-1$의 서브 초평면에 있거나 더 아래에 있어야 함을 보인다. 이 두 이야기를 하나의 식으로 묶어서 표현하면 다음과 같다.
\[y_i(w\cdot x_i + b) >= 1 , \; i=1,2,...N\]i번째 데이터에 따라 클래스 $y_i$가 1 또는 -1로 바뀔 것이니 이해가 될 것이다.
그러나 SVM은 여기에 추가적으로 의사결정 경계의 마진이 최대가 되야한다는 조건을 붙여야한다. 즉, 위에서 우리가 구했던 마진 초평면 $d$를 최대화시켜야한다는 것이다. $d$는 파라미터 $w$를 변수로 가지므로, 함수 $1/f(w)$로 표현하면 다음과 같다.
\[d=\frac{1}{f(w)}=\frac{2}{||w||^2}\]그럼 우린 d를 최대화 해야하므로 말을 바꿔서 $f(w)$를 최소화시킨다는 목적을 갖게 된다. 따라서 선형 SVM의 constrainted optimization problem은 다음과 같이 정의된다.
\[\begin{align*} \min_w \quad & \frac{||w||^2}{2} \\ \text{subject to} \quad & y_i(w\cdot x_i+b)>=1,\;i=1,2,...N \end{align*}\]목적 함수가 2차식이고, constraint가 linear하기 때문에, 이것은 convex opimization problem이고 라그랑주 상수 방법을 통해 풀 수 있다! 라그랑주 상수 $\lambda_i$를 사용한 최적화 문제를 통해 새로운 목적함수를 만들 수 있다.
\[L_P= \frac{1}{2}||w||^2-\sum_{i=1}^N \lambda_i(y_i(w\cdot x_i+b)-1)\]왜 이런 식이 만들어졌는지는, 원래 식을 생각해보자. 원래 목적함수를 최소로 만드는 $w$는 사실 $w$의 모든 components가 0일 때 이다. 그러나 $w$가 영벡터가 되면, contraint를 위반하게 된다. b에 대한 실현 가능한 해가 없기 때문이다. 라그랑주는 이 contraint를 원래의 목적함수에서 뺌으로써 포함시킨다. 라그랑주 상수가 0 이상이라고 가정하면, 어떤 실현 불가능한 해도 라그랑주의 값을 증가시키는 것만 못하다. (?)
어쨌든, 라그랑주를 최소화 하기 위해서, $L_P$를 $w,b$에 대해 미분을 하고 =0을 설정하자. 이것을 primary Lagrangian 라고 한다.
\[\begin{align*} \frac{\partial L_P}{\partial w} = 0 &-> w=\sum_{i=1}^N \lambda_iy_ix_i \frac{\partial L_P}{\partial b} = 0 &-> \sum_{i=1}^N \lambda_iy_i = 0 \end{align*}\]지금까지 아직 우린 라그랑주 상수를 모르기 때문에, w와 b에 대해 답을 내놓을 수 없다. 여기서 만약 inequality contraints가 equality만을 생각한다면, 우린 위 식에 따라 w,b,$\lambda_i$를 얻을 수 있다. 그러나 우리는 inequality contraint를 갖고 있다. 그래서 이것을 equality contraint로 바꾸는 작업을 해야한다. 이 작업은 라그랑주 상수가 음의 값이 아닐 때만 가능하다. KKT condition에 의해, 우리는 이 제약으로 equality contraint를 가질 수 있다.
\[\lambda_i[y_i(w\cdot w_i+b)-1] = 0\]위 식을 무조건 만족하려면, $\lambda_i$가 0이면 될 것이다. 다른 방법으로, $\lambda_i$가 0보다 크다면 $y_i(w\cdot w_i+b)=1$을 만족해야 할 것이다. 그렇게 되면 학습 데이터들이 서브 초평면 $b_{i1},b_{i2}$에 놓여있을 것이고, 이것을 support vector라고 한다. 만약 학습 데이터들이 서브 초평면에 놓여있지 않다면, $\lambda_i=0$이 되면 된다. 그렇다보니, $ w=\sum_{i=1}^N \lambda_iy_ix_i$에서 $\lambda_i$가 0일 때 즉, 학습 데이터가 서브 초평면에 있지 않는 것들은 $w$에 영향을 미치지 않음을 알 수 있고, 서브 초평면에 놓인 데이터들 즉, 서포트 벡터들만 관여하게 된다. 이것이 바로 이 분류기가 서포트 벡터 머신이라고 불리우는 이유이다.
미분으로 얻었던 식들을 원래의 목적함수에 넣게되면, 다음의 식으로 정리가 가능하다.
\[L_D=\sum_{i=1}^N\lambda_i - \frac{1}{2}\sum_{i,j}\lambda_i\lambda_j y_i y_j x_i\cdot x_j\]위 식을 dual formulation of the optimization problem 이라고 한다.
dual과 primary의 차이점은 다음과 같다.
- 서로 포함되어 있는 파라미터들이 다르지만, 답은 같다.
- dual의 2차항의 부호가 음수다. 이것은 primary Lagrangian $L_P$을 갖는 원래의 최소화 문제가 dual에선 최대화 문제로 바뀜을 뜻한다.
후의 더 자세한 풀이는 이 책의 범주에서 벗어나기 때문에, 생략하자.
선형 SVM : Nonseparable, 비선형 SVM
두 개념들은 급하게 배우지 않아도 되므로, 일단 보류한 상태로 이 글을 끝맺음 짓자.
읽어볼 사이트들
나중에 SVM에 대해 좀 더 자세히 파고싶다면, 아래의 사이트들에 들어가보자.
- 서포트 벡터 머신 : https://ratsgo.github.io/machine%20learning/2017/05/23/SVM/
- 라그랑주 : https://untitledtblog.tistory.com/96
- KKT 조건 : https://ratsgo.github.io/convex%20optimization/2018/01/26/KKT/
- https://hleecaster.com/ml-svm-concept/