[Data Mining] Support Vector Machine

Support Vector Machine을 공부해보자. 이거 공부하느라 어제 하루 다 써서 어제는 포스팅 못 했다. 아무튼 지금 포스팅을 해보자. 우선 Support Vector Machine이 어떤 것인지 개념부터 알아보자. 개념은 아주 아주 간단하다. 그냥 나누면 된다. 책받침으로 나누듯이 나누면 된다. 문제는 어떻게 나누느냐이다. 아래와 같이 여러가지 방법이 있다.

그 중에 가장 안정적으로 나누는 방법은 아래와 같이 가장 정 가운데에서 나누는 것이다.

위와 같이 이렇게 가운데로 나누었을 때 양쪽의 data 들간의 거리는 같게 되고 동시에 거리도 가장 크게 된다.

위의 그림처럼 주황색 평면으로 나누어도 data는 나누어지는데 확실히 검은색 평면으로 나누는 것보다는 margin이 작다. 그래서 우리의 목표는 이제 정해졌다. margin을 최대로 만드는 것이다. 그 margin을 구하기 위해서 우리는 수학을 이용할 것이다. 우선 한 평면을 이루는 공식은 linear algebra에서 공부했듯이 아래와 같다.

평면 위의 data들은 당연히 0보다 큰 양수의 값을 가질 것이며 평면 아래의 data들은 당연히 0보다 작은 음수의 값을 가질 것이다. 그럼 이렇게 한번 정리해보자.

평면 위의 점을 평면 공식에 집어 넣으면 당연히 0이 나올 것이다. 그렇다면 평면 위의 점을 넣으면 뭔지는 모르지만 양수가 나올 것이고 평면  아래는 음수가 나오는데, 평면이랑 가장 가까운 위, 아래 점을 집어 넣었을 때, +1과 -1이 나온다고 해보자. (이렇게 가정해도 상관없다. 어짜피 우리가 구하는 b값에서 빼질 테니까) 이렇게 값을 집어 넣었을 때, +1과 -1이 나오는 vector 들을 우리는 support vector라고 부른다. 이것을 왜 support vector라고 부르냐면, 저 vector들이 margin을 구하는데 supporting을 하기 때문에 support vector라고 부르고 그래서 이것을 support vector machine이라고 부른다. 자 이제부터 조금 수학을 해보자. 점과 평면 사이의 구하는 공식을 이용해서 margin의 길이를 계산해보면 아래와 같다. 

우리가 구해야할 2/w^2의 최대값은 w^2/2의 최소값을 구하는 것과 같다. 갑자기 왜 이렇게 역수를 취하냐면.. 계산하기 편하게 하기 위해서이다. 아무튼 이리하여 w^2/2의 최소값을 구하긴 해야되는데 사실 조건이 있다. 모든 x와 y에 대해서 아래의 식이 만족해야 된다는 것!!

특정 조건을 가정한 상태에서 어떤 함수의 최소값을 구하는 방법이 lagrange multiplier라고 하는데, 우리는 여기서 이것을 이용할 것이다. 본격적으로 수식을 써 나아가기 앞서 lagrange multiplier의 예제를 한번 하고 넘어가자. 예를 들어, 아래와 같이 사용될 수 있다.

자 이제 예제를 통해 알아봤으니 실제 적용을 해보자. 적용할 식을 정리해보면 아래와 같다.

우와 복잡하다. 막 갑자기 다른거 하고 싶어지겠지만 저걸 공부하고 쓴 나는 또 얼마나 힘들었을까? 생각을 하면서 잘 읽어봐주세요.(갑지기 존대말) 위의 식에서 시그마는 i=0~N까지의 시그마이다. (N은 data의 개수) 위의 식만 이해하면 이제 거의 support vector machine의 핵심은 다 이해한 샘이다. 그러면 이제 우리는 실제 어떻게 적용하는지 예를 들어 설명해보자.

위에서 구한 평면을 이용하면 위의 세 점을 가장 중간에서 나누면서 margin을 최대로 유지할 수가 있다. 사실 Support Vector Machine은 이해하기 매우 쉬운 알고리즘이다. 그냥 직선이나 평면으로 data들을 나눈다라고 생각하면 되니까. 그런데 그것을 어떻게 mathematically 나누냐라고 물어보면 위와 같은 어마무시한 수학이 들어간다. 따라서 이번 포스팅은 증명과 예제로 만족하련다. 그런데 여기서 하나 더 이야기하고 넘어가야 할 부분이 있다. 바로 kernel function이다. 

왜 kernel function이 필요한지만 간단하게 집고 넘어가자. 왜냐하면 나도 자세한건 모르기 때문이다. 위의 예에서 우리는 너무나 간단하고 이상적인 example data point가지고 작업을 했다. 그런데 실제 데이터는 저렇게 나누어지지 않는다.

사실 위의 그림 역시 너무나도 이상적으로 나누어진 그림이다. 아무튼 요점은 나누는 선이 곡선일 수도 있다는 것이다. 곡선일 때는 위에서 설명한 평면 개념을 적용할 수 없다. 이 때 적용하는 것이 바로 Kernel Function인데, 아래의 식에서 xixj를 다른 kernel function으로 변경해주면 된다.

자 이제 마지막으로 하나만 이야기하고 포스팅을 마치도록 하자. soft margin이다. 지금까지 우리가 공부한 margin은 hard margin이다. 여태까지 제시한 예시는 모두 평면으로 완벽하게 나누어졌었는데, 사실 이런 아주 이상적인 예제는 실제 data에는 없다. 모든 data는 에러를 가지고 있다. 그래서 아래와 같은 soft margin이 있는 것이다.

그림 출처 : http://emilea-stat.stochastik.rwth-aachen.de/cgi-bin/WebObjects/EMILeAstat.woa/wa/module?module=384C2AD2-4504-714A-C17D-90C3A4EFEB82

선 위가 빨간 data, 선 아래가 파란 data이지만 가끔 보면 에러들이 있다. 저런 데이터는 못 나눈다. 그냥 에러로 가지고 가는게 낮다. 설령 곡선을 이용한 kernel function으로 완벽하게 나누었다고 해도 분명히 overfitting할 위험이 크다. 기본적으로 SVM은 margin을 크게 함으로서 overfitting의 위험을 줄일 수 있는 모델인 것을 감안하면, 위의 data를 억지로 나누는 것은 이 모델의 장점을 잃는 것으로 해석할 수도 있다.

아 몰라. Classification을 잘 설명했는지는 모르겠지만 아무튼 Classification은 다 설명했다. 하고자 하는 것들은 다 한 것 같다. 다음 포스팅부터는 조금 더 새로운 것!! Clustering을 공부해보도록 하자.