[ML] SVM(Support Vector Machine)서포트 벡터 머신

※해당 게시물에 사용된 일부 자료는 순천향대학교 빅데이터공학과 정영섭 교수님의 머신러닝 전공수업 자료에 기반하였음을 알려드립니다.

 

이번 포스팅에서는 머신러닝 모델 중 Classification에 활용되며 Supervised Learning의 종류인 SVM(Support Vector Machine)에 대해 알아보려고 한다. 2019년 2학기에 DSC 활동을 하면서 SVM에 대해서 처음 알게되었고 그 때 당시에는 얕은 깊이의 공부를 했던 기억이 난다. 하지만 이번엔 SVM을 머신러닝 전공 수업에서 다루는 만큼 깊이 있게 공부하고 넘어가야 겠다. 목차는 다음과 같다.

 

1. SVM의 기원은 무엇일까?

2. Margin의 maximum을 구하는 방법

3. 비선형 분류를 하기 위한 Slack Variable

4. 비선형 분류를 하기 위한 Kernel Trick

5. Structural SVM이란?

 

1. SVM의 기원은 무엇일까?

SVM의 풀어쓴 이름은 Support Vector Machine이다. 이름 그대로 '지지하는 벡터?' 라는 의미부터 생각이 나게 되는데 이게 무슨 의미인지 살펴보자. 먼저 그림을 보면서 직관적으로 이해해보자.

 

SVM의 기원

 

위와 같이 빨간색, 파란색 label을 분류하는 선형(Linear)을 찾는다고 가정해보자. 기본적으로 SVM은 두 개의 다른 클래스를 분류할 수 있는 여러가지의 선형식이 있을테지만 이 중에서 가장 잘 분류할 수 있는 하나의(Unique) 선형식을 찾으려고 한다. 그렇다면 가장 잘 분류할 수 있는 기준은 무엇일까?

 

바로 위 그림에서 Separating Hyperplane이라고 적혀있는 일종의 Decision boundary가 두 개의 클래스를 가장 잘 분류할 수 있는 선형이다. 이 Decision boundary를 찾기 위한 조건이 있다. 이를 살펴보기 전에 우선 Support Vector의 개념부터 살펴보자. Support Vector란, 위 그림 속에서 점선으로 되어 있는 선형위에 존재하는 벡터들을 뜻한다. 

 

가장 최고로 잘 분류할 수 있는 Decision boundary를 찾기 위해서 여러가지의 선형식 후보들이 존재할텐데 이 중 Support Vector들과의 Margin이 가장 Maximium이 되게 해야 한다. 이 때 Support Vector는 반드시 최소 2개 이상의 데이터가 존재해야 한다. 

 

2. Margin의 maximum을 구하는 방법

Margin을 최대화시키전에 Margin을 구하는 방법부터 알아야 최대화를 시킬 수 있지 않을까? 다음 그림을 보면서 법선벡터를 이용해 Margin을 구하는 방법을 차근차근 알아가 보자.

 

Margin을 구하는 방법

 

SVM은 Wx+b=0이라는 Unique한 Decision boundary를 찾은 후에 x에 데이터가 input으로 들어간 후 양수/음수에 따라 클래스를 분류하게 된다. 그렇다면 우리는 Wx+b=0이라는 g(x)의 법선(직교)벡터를 활용하여 Margin(그림 속에서는 'r'값)을 구할 수 있게 된다. 

 

이제 그럼 이 Margin(r값)의 maximum(최대값)을 찾아야 한다. 이 때 Lagrange Multiplier(라그랑지 함수)를 사용하게 되는데 '라그랑지 함수'의 정의는 다음과 같다. "라그랑지란, 어떤 함수가 제약식 조건을 만족하면서 해당 '어떤 함수'가 갖는 최대값 또는 최소값을 찾고자 할 때 사용하는 함수이다."  따라서 우리는 이 라그랑지 함수를 이용할 것이다. 밑의 그림 속 필기 내용을 보면서 이해해보자.

 

Margin을 구하기 위해 1,2,3번식을 하나의 식으로!

 

이제 Margin의 일반화된 식을 도출해내기 위해서 위 그림과 같이 두 클래스를 분류하는 선형식 3개(Decision boundary, Support Vector가 자리잡고 있는 두 개의 경계선)가 일반화 과정을 거치게 된다. 이 때 Wx+b = 1 or Wx+b = -1을 만족하는 x 데이터들은 바로 Support Vector가 되는 것이다.

 

이제 거리(width)를 구해보자. 이 때 앞서 말했던 것처럼 선형식의 법선벡터를 활용해서 구한다. 

 

Margin을 구하고 Margin을 최대화 시키자.

 

Margin을 구하는 식은 위와 같은 계산과정을 거치면 'width = 2/ ||w벡터||' 라는 식이 나오게 된다. 이 식으로 부터 알 수 있는 사실은 w벡터값이 분모에 있기 때문에 width(거리) 값 자체를 최대화시키기 위해서는 w벡터값을 최소화시켜야 함을 알 수 있다. 따라서 결국 '거리를 최대화' 문제에서 'w값을 최소화' 하는 문제로 변한됨을 알 수 있다. 이번에도 '최소화' 문제이다. 

 

여기서 알아두어야 할 점은 w값을 최소화 하기 위해서 위에서 언급했던 Lagrange Multiplier( L( ) )를 이용해야 한다. 그래서 만들어진 식은 위 그림의 L(w,b,α) 로 정의된 식이다. 따라서 우리는 L(w,b,α)가 최소값을 갖도록 해주어야 한다. 이제 우리는 본격적인 '최소화' 과정을 실현시키기 위해서 L(w,b,α)식을 변수 w,b값 각각에 대해 편미분을 수행한다. 편미분을 수행한 후 도출된 w,b의 각 최적화값을 원래 함수인 Lagrange함수에다가 대입을 한다. 이 때 우리는 KKT Condition 을 고려해야 한다.

 

KKT Condition 이란, α값이 0인지 아닌지에 따라 나뉘게 된다. KKT 조건에서 알파값이 0이 아니라는 것은 [1-yi ~ ] 부분이 0이되는 의미이고 이는 (yi~ ) 이 부분(거리)의 값이 1이 되며 결국 이 때의 x(데이터)는 Support Vector라는 의미인 것이다.

 

 이제 다시 Lagrange함수에다가 w,b의 최적화값을 대입하게 되면 알파값으로만 이루어진 Q(α)함수로 변환이 되는데, 이는 또 'w값을 최소화' 하는 문제에서 '알파값을 최대화' 하는 문제로 바뀌게 된다. 왜냐하면 L(w,b,α)식을 보게 되면 최소화해야 할 목적함수 1/2*||w||^2에서 시그마+알파값으로 이루어진 부분을 '빼게'되어 있기 때문이다. 즉, 1/2*||w||^2 에서 알파의 최대값을 빼주어야 전체적인 값(w값)은 최소화 되기 때문이다.

 

그렇다면 L(w,b,α)인 함수를 최소화함으로써 Global Optimum을 구할 수 있을까? 답은 '구할 수 있다' 이다. 왜냐하면 위에서 구해주었던 Q(α)함수가 이차항으로 이루어져있고 이차항으로 이루어져있다는 것은 Convex 함수를 의미하며 결국 Global Optimum을 구할 수 있음을 의미하게 된다.

(사실 애초에 SVM이 Unique한 Decision Boundary를 구할 수 있음에서 Global Optimum을 구할 수 있다는 것이 전제되어 있는 상태이긴 하다.)

 

Convex Function은 Global Optimum을 구할 수 있다.

 

이제 Q(α)함수를 최대화시키기 위해 Quadratic Programming을 이용하고 최대의 알파값을 찾아내게 된다. 그리고 우리는 최적의 w값과 b값을 알파값과 x,y값을 사용하여 나타낼 수 있다.

 

알파의 최대값을 찾아줌으로써 최적의 w,b값을 정의할 수 있다.

 

결론적으로 Optimal W값은 weighted sum값으로 나타내줄 수 있다. 이 때 만약에 알파값=0이 되게 된다면 Support Vector가 아닌 값들을 고려한다는 의미이고 심지어 알파값이 0이기 때문에 Weighted sum값은 0이 되게 된다. 이 말은 결국 Support Vector만 고려한다는 의미이기도 하다.

 

3. 비선형 분류를 하기 위한 Slack Variable

다음은 이제 SVM모델을 비선형 분류를 위해 사용하는 방법 중 하나이다. Slack Variable 이란 우리가 직관적으로 쉽게 풀어쓰자면 "조금 오분류하는 건 내가 좀 그냥 봐주고 넘어갈게!" 라고 이해하면 될 것 같다. 다음 그림을 보면서 Slack Variable이 무엇이며 Slack Variable을 얼마나 허용해줄지(얼마나 관대하게 넘어가줄지)를 설정하는 파라미터값 'C'에 대해서도 알아보자.

 

Slack Variable이란?

 

하이퍼파라미터로서 'C'는 Slack Varable을 얼마나 봐줄지에 대한 척도이며 크기에 따른 의미는 다음과 같다.

 

• C값을 크게 준다 -> 분류 기준이 까다롭다 -> 정확히 분류하려고 노력(하지만 Overfitting문제 유도..)
• C값을 작게 준다 -> 분류 기준이 관대하다 -> 대충 분류하려고 함.

4. 비선형 분류를 하기 위한 Kernel Trick

비선형 분류를 하기 위한 또 다른 방법으로 Kernel Trick이 있다. Kernel Trick은 쉽게 말해서 "지금 공간에서 비선형 분류가 불가능한데 그렇다면 공간 자체를 바꿔 버리자" 라고 이해하면 되겠다. Kernel 종류에도 여러가지가 있지만 가장 많이 사용되는 것은 RBF(Radial Basis Function)커널이라고 한다. 주요 학습알고리즘에는 SMO(Sequential Minimal Optimization), Cutting-plane이 있으며 라이브러리에는 LIBSVM, SVMLight가 있다고 한다.

 

SVM은 Kernel Trick을 활용해 비선형 분류를 한다.

#참고로 SMO는 일일이 업데이트 하는 방식이기 때문에 대용량 데이터에는 적합하지 않다고 알려져 있다.

 

5. Structural SVM이란?

마지막으로는 Strucural SVM이다. 그렇다면 우리가 그동안 배웠던 SVM은 뭔가? 우리가 지금까지 배웠던 SVM은 'Regular SVM'이라고 할 수 있겠다. 그러면 두 개의 차이는 무엇일까?

 

• Regular SVM : 보통 Univariate(일변량) 분류, 회귀분석에 사용된다. input 데이터를 집어 넣었을 때 output으로 벡터, Scalar값(실수값)으로 mapping이 된다.
• Structural SVM : 다중분류나 Multi-label Classification에 사용된다. Multi-label Classification은 하나의 데이터가 동시에 여러개의 Label을 가질 수 있음을 의미한다. input 데이터를 집어 넣었을 때 output으로 'Set of class labels'가 mapping 된다. 즉, '여러개의 Label들'을 가리킨다. 'Set of class labels'은 'Structured output labels'이라고도 하며 이 단어에서 Structural SVM 용어가 나오게 된 것 같다.

 

#Hinge Loss에 대한 추가 정보

 

Hinge Loss를 사용하는 이유