ML 101 : 서포트 벡터 머신(Support Vector Machine, SVM) - Margin

서포트 벡터 머신 (Support Vector Machine, SVM)

서포트 벡터 머신은 Linear Classification, 즉 선형 분류 중 하나 입니다. 위의 그림과 같이 별모양과 동그라미가 있을 때 두 도형을 나누는 가장 좋은 boundary 를 찾아야 한다고 할 때 사용되는 머신 러닝 기법 중 하나 입니다. 그림 처럼 2차원일 경우 이 boundary 를 선으로 표현할 수 있지만 더 고차원으로 가게 될 경우 단순히 선형이라 표현하지 않고 hyperplane 이라 부르게 됩니다.

서포트 벡터 머신을 알기 위해서 중요한 기본 개념으로 3가지와 이에 따르는 몇가지 서브 개념들이 있습니다.

1. Margin ( VC Dimension, Shattering, Dichotomy )

2. Support Vector

3. Kernel

그럼 각각이 무엇인지 이론적으로 먼저 살펴보도록 하겠습니다. 

• Margin - VC Dimension, Shattering, Dichotomy

안드로이드 개발자 분들이라면 margin 에 대해서 많이 보셨을 것 같습니다. 안드로이드를 하다보면 UI 를 그릴 때 각 View 간의 거리를 정할 때 margin 값을 주곤 합니다. 서포트 벡터 머신에서의 margin 도 사실상 동일한 개념 입니다. 위의 예제 그림에서 Class1 과 Class2 를 나누기 위한 선은 무수히 많이 그릴 수 있습니다. 그런데 어떤 선을 가장 잘 분류한 선이라고 표현할 수 있을 까요?

두 클래스 사이을 분류하는 무수히 많은 선, 고차원에서는 hyperplane, 중 margin 을 가장 크게 하는 hyperplane 을 찾는 것이 서포트 벡터 머신 분류를 잘 표현한 것이라고 할 수 있습니다.  

사실 직관적으로 생각해 보면 당연히 분류되는 아이템들 과의 margin 이 가장 큰 hyperplane 을 찾는 것이 가장 잘 분류하는 방법일 것 같긴 합니다. 그런데 왜 그럴까요?

이를 증명하는 개념 중 하나가 VC Dimension 입니다. VC Dimension 은 데이터를 분류하는 SVM 분류기가 얼마나 복잡한 데이터를 분류할 수 있는지를 나타내는 속성 입니다. 

그럼 이제 VC Dimension 을 좀 더 설명하기 위해 Dichotomy 란 개념을 추가적으로 설명해 보겠습니다. Dichotomy 란 어떤 집합이 있다면 이 집합을 둘로 나눈 다는 것 입니다. 예를 들어 A, B, C 라는 점이 있다면 { A }, { B, C} 혹은 { A, B, C}, { } 등으로 총 8 종류로 나누는 것이 가능 할 것 입니다. 이처럼 8 종류로 나누는 것을 Dichotomy 라고 부릅니다. 

그럼 Shattering 은 무엇일까요? 

Shattering 은 SVM 분류기가 Dichotomy 를 모두 표현할 수 있느냐 입니다. 위의 그림 중 마지막 그림을 보시면 + 와 - 를 나누는 선 하나를 표현할 수 있는 방법은 없습니다. 해당 경우의 Dichotomy 는 표현할 수 없는 것 입니다.

결론적으로 VC Dimension, 즉 SVM 분류기가 얼마나 복잡한 데이터를 표현할 수 있느냐의 여부는 Shattering 할 수 있는 가장 많은 데이터의 갯수라고 보실 수 있을 것 같습니다. 

일반적으로 N 차원의 hyperplane 의 VC Dimension 은 N+1 이라고 합니다. 또한 VC Dimension 이 높으면 안 좋다고 합니다. 그리고 Margin 을 최대화 한다는 말의 동치는 VC Dimension 을 줄인다는 말과 동일하다고 합니다.

이상 이론적인 부분에서의 SVM 의 Margin 에 관련된 부분들을 살펴 보았습니다. 다음 글에서 그럼 어떻게 Maximum Margin 을 찾을 수 있을지에 대해서 살펴보도록 하겠습니다.