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

1. Support Vector Machine, SVM이란?

Support Vector Machine(SVM)은 원 훈련(또는 학습)데이터를 비선형 매핑(Mapping)을 통해 고차원으로 변환한다. 이 새로운 차원에서 초평면(hyperplane)을 최적으로 분리하는 선형분리를 찾는다. 즉, 최적의 Decision Boundary(의사결정 영역)를 찾는다. 

그렇다면 왜 데이터를 고차원으로 보내는 것일까? 예를 들어, 아래의 [그림1]과 같이 A=[a, d], B=[b, c]는 2차원에서 non-linearly separable(비선형 분리)하다. 이를 통해 한 차원 높은 3차원으로 Mapping하게 되면 linearly separable(선형 분리)하게 된다. 따라서, 충분히 큰 차원으로 적절한 비선형 매핑을 이요하면, 두 개의 클래스를 가진 데이터는 초평면(hyperplane)에서 항상 분리될 수 있다.

SVM은 복잡한 비선형 의사결정 영역을 모형화 할 수 있기 때문에 매우 정확하며, 다른 모델들 보다 Over Fitting되는 경향이 적다.

[그림 1]

2. 데이터가 선형으로 분리되는 경우

두 개의 클래스가 선형으로 분리된 경우를 통해 SVM에 대해서 자세히 알아 보겠다. 

데이터 집합 는 와 같이 주어졌다고 가정한다. 여기서 는 클래스 에 대한 훈련용 투플(tuple)이다. 각 는 buys_computer = yes, buys_computer = no에 대응하는 +1, -1 둘 중 하나의 값을 갖는다. 아래의 [그림2]는 같이 특정 속성값 에 대한 Vector의 분포이다. 그림에서 알다시피 2차원 데이터는 선형적으로 분리가 가능하다(linearly separable). 분리할 수 있는 직선은 무수히 많이 존재하지만 최적의 직선, 훈련 데이터 외의 데이터에 대한 분류 오류를 최소로한느 직선을 찾아야 한다. 2차원이 아닌 3차원 이상에서는 직선이 아닌 최적의 평면(plane)을 찾아야한다. 즉, n-차원으로 일반화를 하게되면, 최적의 초평면(hyperplane)을 찾아야한다. 이 초평면이 Decision Boundary가 된다. 

SVM은 MMH(Maximum Marginal Hyperplane, 최대 마진 초평면)을 찾아 분리하는 방법이다.

[그림 2]

아래의 [그림3]에서는 두 그림 모두 데이터를 분리하고 있지만, 직관적으로 봐도 미래의 데이터를 분류하는데 있어서 오른쪽 그림의 초평면이 더 정확하게 분류할 것이라는 것을 알 수 있다. 

[그림3]

분리 초평면은 다음과 같이 나타낸다.

        (1)

여기서 는 가중치 벡터다. 즉, 이다. 은 속성의 수이며, 는 스칼라이며 편향값(bias)라고도 한다. [그림3]에서는 두 개의 속성값 에 대한 2차원이다. 예를 들어,  이고 과 는 속성 의 값이다. 를 추가적인 가중치 이라고 하면,  위의 식(1)을 다음과 같이 쓸 수 있다.

        (2)

분리 평면(Decision Boundary) 위에 있는 모든 값들은 아래의 식을 만족한다.

        (3)

마찬가지로 분리 평면 아래에 있는 모든 값들은 다음을 만족한다.

        (4)

가중치는 수정될 수 있고, 마진(margin)의 면(side)를 정의하는 초평면은 다음과 같이 쓸 수 있다.

        (5, 6)

즉, 의 윗 쪽에 위치하게 되는 모든 투플은 +1 클래스에 속하게 되고, 의 아랫쪽에 있는 투플들은 -1 클래스에 속하게 된다. 

식(5), (6)을 결합하게되면 다음의 식을 얻게된다.

        (7)

초평면 ,  위에 위치하는 모든 투플은 식(7)을 만족하고 이를 바로 서포트 벡터라고 한다. 아래의 [그림4]에서 빨간 테두리의 원들이 서포트 벡터이다. 서포트 벡터는 분류하기가 가장 어려운 투플이며 분류에 대해 가장 많은 정보를 준다. 

분리 초평면으로 부터 위의 점까지의 거리는 이고, 이며 의 유클리드 norm이다. 마찬가지로, 위의 점까지 거리 또한 이다. 따라서 최대 마진(margin)은 이다.

[그림 4]

자, 그렇다면 SVM은 어떻게 MMH와 서포트 벡터를 찾는것일 까? KKT(Karush-Kunh-Tucker)조건과 라그랑지 방법을 이용하여 구할 수 있다. (이 부분은 현재의 나로써는 너무 어려워서 추후에 공부하게 되면 다시 포스팅 하겠다...ㅜㅜ)

3. 소프트 마진(Soft Margin)

위에서 설명한 SVM 방식은 하드마진(Hard Margin) 방법이라고 한다. 하드마진 방식은 매우 엄격하게 두 개의 클래스를 분리하는 분리초평면을 구하는 방법으로, 모든 입력 투플은 이 초평면을 사이에 두고 무조건 한 클래스에 속해야 한다. 그렇게 되면 몇개의 노이즈로 인해  두 그룹을 구별하는 분리초평면을 잘 못 구할 수도 있고, 경우에 따라서는 찾지 못하는 문제가 발생한다. 따라서, 현실세계에서는 하드마진 방법을 적용하기 힘들다.

이를 해결하기 위해 소프트마진(Soft Margin) 방식이 개발되었다. 소프트 마진 방법은 SVM을 창안했던 러시아 배프니크(Vapnik)가 하드마진 방식의 단점을 극복하고자 코테스(Cortes)와 함께 제안한 방법이다.

소프트 마진 방법은 기본적으로 하드마진 방법을 기반으로 하는데 차이점은 서프토 벡터가 위치한 경계선에 약간의 여유 변수(Slack Variable)을 두는 것이다. 이를 수식으로 표현하면 다음과 같다.

위 식의 의미는 서포트 벡터가 위치한 경계선을 두고 만큼의 오류를 인정한다는 의미이다. 이때 마진 을 최대화하는 목적함수는 다음과 같다.

여기서 값은 얼마만큼 여유를 가지고 오류를 인정할 것인지 판단하여 결정해 주는 값이다.

4. 데이터가 선형으로 분리되지 않는 경우

위에서 계속해서 설명한 부분은 선형적으로 분리 가능한(Linearly Separable) 데이터에 SVM을 구하는 것에 대해 설명했다. 하지만, 현실에서는 선형으로 분리되지 않는(non-linearly separable) 즉, 비선형 SVM이 많다. 이러한 비선형 SVM은 선형 SVM의 확장을 통해 비선현 SVM을 만들 수 있다. 

[그림 5]

원 데이터를 비선형 매핑(Mapping)을 통해 고차원 공간으로 변환한다. 위의 [그림5] 처럼 를 통해 2차원에서 3차원으로 한 차원 높게 변환하였을 때 선형 분리 초평면을 가지게 된다. 하지만, 이렇게 고차원으로 비선형 매핑을 하게 되면 MMH를 구하기 위한 계산비용이 많이 들게 된다. 이를 해결하기 위해 커널 트릭(Kernel Trick)을 사용한다. 커널 트릭의 원리는 수학적 기교를 사용하는 것인데, 데이터 투플을 고차원으로 보낸 뒤 벡터의 내적을 계산하는 것과 내적을 한 뒤 고차원으로 보내는 것은 결과적으로 같은 값이기 때문이다. 따라서 커널함수(Kernel Function)과 벡터 내적은 다음과 같이 표현할 수 있다.

따라서, 알고리즘에서 이 있는 모든 곳에 로 대체할 수 있다. 이러한 커널 트릭을 이용하여 모든 계산은 원 데이터의 차원에서 이루어지게 된다. 대표적인 커널함수는 다음과 같다.