[ML개론] (11) Support Vector Machine(SVM)

이전까지 Logistic Regression, Naive Bayes Classifier를 살펴봤다.

이들 Classification Model은 확률에 기반하여 Class Variable Y를 결정짓는다. 

 

그렇다면 확률을 기반으로 분류하지 않는 SVM 모형을 이제 살펴보자.

이는 independent variable X를 input data로 받고 이를 특정 class variable Y로 분류해준다. SVM은 이 평면 위에서 Decision Boundary를 가장 효과적으로 설정할 수 있도록 돕는다.

 

그 방법은 다음과 같다.

우선 특정 class variable Y에 속하는 instance 중 최전선에 위치한 두 instance를 선택하고 선을 긋는다.

그리고 나서 이 선과 평행한 선을 움직이면서 가장 먼저 이 선과 만나는 다른 class variable Y에 속하는 instance를 찾는다. 마지막으로 이 두 선을 등분하는 위치에 놓인 선을 구한다. 이 선이 바로 SVM 모형이 제시하는 Decision Boundary다. 이처럼 SVM은 그 이름처럼 Decision Boundary를 Support하는 Vector를 찾는 것이 핵심이다. 

 

그럼 단계별로 Decision Boundary를 찾는 과정을 살펴보자.

WX + b = 0이 Decision Boundary라 가정했을 때, 이 선을 기준으로 WX + b > 0이 되는 X에 대해선 blue, <0이 되는 X는 red로 설정한다. blue인 경우 class variable Y가 +1, red인 경우 Y가 -1이다.

 

그렇다면 우리는 (WX+b)Y를 confidence level로 설정할 수 있다. 이 confidence level은 (WX+b)<0이라면 Y=-1이고, (WX+b)>0이면 Y=1이기 때문에 confidence level 자체는 0 이상이다. 이 것을 극대화하는 것이 우리의 목적이라 할 수 있겠다. 

아래 그림의 (2,2)와 (3,3)은 (WX+b)Y값이 (1.5,4)나 (2.5,5)에 비해 낮을 수 밖에 없다. Decision Boundary로부터 멀어질수록 Confidence level이 높아지기 때문에 우리는 이를 높임으로서 판정을 더 '자신있게' 할 수 있는 것이다. 

 

정리하자면 Confidence level의 극대화가 더 효과적인 모델을 위한 필요조건이며, 이 Confidence level은 Decision Boundary에서 얼마나 instance들이 벗어나있는지, 즉 둘 사이의 거리에 의존한다. 

특정 instance X는 다음과 같이 정의할 수 있다. X = Xp + r(w/||w||)

이 때 Xp는 decision boundary 위의 벡터이다. Xp와 unit direction vector인 w * r(거리)를 더해주면 decision boundary와 X와의 수직거리가 도출된다. instance 중 수직거리가 가장 작은 것을 우린 margin이라 부른다.

 

f(x) = wx+b 가 decision boundary일 때, margin 거리에 위치한 vector를 넣을 반환되는 함수값을 a라고 가정하자. 

이 경우 식이 다음과 같이 전개되어 ||w||r = a가 된다. r = f(x) / ||w||이며 이 r은 margin, 즉 boundary로부터의 수직거리가 된다. 

 

그렇다면 SVM이 마주하는 optimization problem은 margin을 최대화하는 것이다. 그래야지 분류가 안전하게 되니까.

margin이 위로 하나 아래로 하나 있으니 이는 2r(r=margin)이고, 이는 모든 training instance에 대해 (wx+b)y >= a 라는 는 constraints에 종속된다. 가장 decision boundary에 근접한 x_j를 wx+b에 대입할 경우 +-a가 도출된다는 점에서, 그리고 y_j는 항상 +-1이라는 점에서 a보다 작은 (wx+b)y는 존재할 수 없다. 

 

편의를 위해 f(x)=a=1로 설정하자. 그러면 2r, 즉 2a/ ||w||를 최대화하는 문제는 1/||w||를 최대화하는 문제로 변한다. 역수를 취해주면 ||w||를 최소화해야만 하는 것이다. 

이 경우에는 variable x가 <x1,x2>로 구성된 vector였기 때문에 weight 또한 <w1, w2>가 존재하며 이들의 norm은 root(w1^2 + w2^2)와 같다. 차피 최소화문제이기 때문에 root는 걷어주어도 괜찮다.

 

자 그럼 최적의 decision boundary를 찾기 위해 필요한 variable이 w1, w2, b 그리고 x_j로 압축된다. 

constraint와 optimization의 수식은 우측상단과 같다. 

 

그런데 여기서 질문이 생긴다. 만약 decision boundary를 통해 classification을 해낼 수 없다면?

위 그림과 같이 decision boundary가 나머지 instance를 잘 분류했지만 아래의 파란점은 분류해낼 수 없었다. 이처럼 우리의 instance는 대게 fit하게 들어맞지 않는데 이런 instance의 존재 때문에 decision boundary가 이상하게 형성될 수 있다. 

 

가령 위쪽의 두 파란점은 decision boundary를 좀 더 tight하게 형성하면 분류가 되긴 하지만,

아래의 파란점은 decision boundary로 분류할 수 없는 instance다. 이를 infeasible solution이라 부르고 우리는 이러한 error를 다루기 위한 두가지 방법을 도입한다.