Support Vector Machine (1)
24 Jul 2022
해당 포스트는 Kaist 문일철 교수님의 기계학습개론 1의 강의를 정리한 내용입니다. (해당 강의를 기반으로 기계학습 관련하여 스터디를 진행하고 있습니다.)
(아직 글을 작성하지 않았지만) 나이브 베이지 분류기(Naive Bayes Classifier)와 로지스틱 회귀(Logistic regression) 을 지난번 수업들에서 배웠고, 해당 방법들은 확률 기반의 결정경계(Decision Boundary)를 설정하는 모델 이었습니다. 서포트 벡터 머신(Support Vector Machine)은 확률 기반이 아닌 결정경계(decision boundary)와 가장 가까운 데이터 사이의 거리인 Margin을 최대화 하는 방향으로 결정경계를 설정합니다.
SVM은 크게 세가지로 나눌 수 있습니다.
-
SVM with Hard Margin : 어떠한 error도 허용하지 않는 SVM.
-
SVM with Soft margin : error 존재하는 경우를 다루는 robust한 SVM. Error에 대해서 penalty를 부여하는 방식으로 고려합니다.
-
kernel trick을 이용한 SVM : 꼬불 꼬불한 decision boundary를 설정하는 SVM
SVM 관련하여 총 3파트로 나눠 작성 해보려 합니다.
Decision Boundary
결정경계(Decision Boundary)가 무엇인지 부터 짚고 넘어가려 합니다.
위 그림처럼 인스턴스들에 대해 각 클래스로 분류하는 평면 혹은 선 (또는 hyperplane)을 결정 경계라고 합니다. 분류 문제에서 이러한 결정경계를 어떻게 설정하는 지에 따라 모델의 유연도(Flexibility) 혹은 성능이 결정됩니다.
Support Vector Machine with hard margin
(위의 사진은 위키피디아의 서포트 벡터 이미지입니다.)
서포트 벡터 머신은 다음과 같이 결정경계를 찾습니다.
- 각 클래스에서 서로 가까운 3개의 벡터를 찾습니다.이때 3개의 벡터가 Support Vector Machine에서의 Support vector입니다.
- 먼저 각 클래스 별로, 가장 앞쪽에 위치한 벡터를 하나씩 찾습니다.
- 그 다음, 나머지 하나의 벡터는 클래스에 상관없이 가장 앞쪽에 위치한 것을 선택 합니다.
- 3개의 벡터를 찾았다면, 같은 클래스에 속한 2개의 벡터(흰 점)를 연결하여 하나의 직선을 긋습니다.
- 2번에서 그은 직선과 평행한 직선 중 나머지 벡터(검정 점)을 지나는 직선을 긋습니다.
- 2번과 3번에서 그은 직선들의 중점을 지나는 평행한 직선(실선)을 긋습니다. 이 실선 직선이 서포트 벡터 머신의 결정 경계 입니다.
마진은 결정경계에서 가장 가까운 점에서 수선의 발을 내렸을 때의 거리(Perpendicular distance)을 의미합니다. 위의 사진에서, 양쪽 점선에서 실선까지의 거리를 뜻합니다.
Decision Boundary 식을 다음과 같이 나타내 봅시다. $w$는 법선 벡터, $b$는 절편을 의미합니다.
\[w\cdot X+b = 0\]해당 결정 경계의 법선 방향쪽 (주황색 점 방향) 을 positive라고 하고, 반대편을 negative라고 하면 다음과 같이 표현할 수 있습니다.
- Positive case : $w\cdot X+b >0$
- Negative case : $w\cdot X+b < 0$
임의의 양수 클래스를 나타내는 $a$가 있다고 가정하고, positive case 일 때의 클래스를 $a$, negative일 때를 $-a$이라고 가정해봅시다.
그렇다면 다음 식은 항상 양수가 됩니다. 이때 $y_j$는 클래스를 의미합니다.
- Confidence level : $(w\cdot X+b)y_j >0$
이 신뢰도(Confidence level)를 최대화 하는 것이 서포트 벡터 머신의 목표입니다.
\[argmax \sum_j(w\cdot x +b)y_j\]위의 식에서 $y_j$는 클래스에 대한 임의의 상수이기 때문에, 결정 경계와 무관합니다. 즉 마진 $r$에 해당하는 $w\cdot x +b$를 최대화 하는 것이 중요합니다.
결정 경계를 $f(x)$라 하고 임의의 점 $x$와 결정 경계 위의 임의의 점 $x_p$가 있다고 할때, 두 점 사이의 관계는 다음과 같이 표현할 수 있습니다.
\[x= x_p+r{w\over \mid\mid w\mid \mid}\] \[f(x_p)=0\] \[f(x) = a\] \[f(x)=w\cdot x +b = w(x_p+r{w\over\mid \mid w \mid \mid})+b = w\cdot x_p+b+r{w\cdot w\over \mid\mid w\mid\mid} = r\mid\mid w\mid\mid =a\]그러면 마진(margin) $r$을 다음과 같이 표현할 수 있습니다.
\[r={f(x)\over\mid\mid w\mid\mid} = {a\over\mid\mid w\mid\mid}\]$r$을 최대화 해 봅시다. 이때, 양쪽 방향에 대해 모두 고려해야 합니다.
\[\therefore max_{w,b}2r = {2a\over\mid\mid w\mid\mid}\] \[s.t.(w\cdot x_j+b)y_j \ge a\]위의 식에서 $a$는 임의의 양수 값이 이므로 1이라고 하면, 마진 $r$을 최대화하는 것은 $\mid\mid w\mid\mid$을 최소화 하는 것으로 생각할 수 있습니다.
\[max_{w,b}2r=max_{w,b}{2\over\mid\mid w\mid\mid}=min_{w,b}\mid \mid w \mid\mid\] \[s.t.(w\cdot x_j+b)y_j \ge 1\]여기서 $\mid \mid w \mid \mid$에 대한 최소값을 찾는것은 $w$에 대해 다음과 같이 표현할 수 있으므로 Quadratic Programming (QP)으로 볼 수 있습니다.
\[argmin\mid\mid w \mid\mid = argmin \sqrt{w_1^2+w_2^2+..+w_i^2}\]수업에서도 QP에 대해서 자세하게 다루지 않기 때문에 이 부분은 나중에 optimization을 공부할 때 다시 다뤄보도록 하겠습니다.
Conclusion
- 서포트 벡터 머신은 가장 가까운 학습 점들(training data point)에 대해 가장 거리가 먼 초평면(hyperplane)의 집합을 구성한다.
- Hard margin은 어떠한 에러도 허용하지 않는 마진이다.
다음 글에서는 Support Vector Machine with soft margin에 대해 다뤄보겠습니다.