​이번시간에는 서포트 벡터 머신(support vector machine, SVM)에 대하여 알아보겠습니다.

SVM은 분류나 회귀분석에 쓰일 수 있는 지도학습 모델입니다. 

​두가지 범주로 나눌 수 있는 학습데이터로 만들어지며 새로운 데이터가 들어왔을 때 비확률적 이진 선형 분류를 합니다. p차원 공간속의 점으로 데이터들을 표현하고 이 점들이 각각 두개의 클래스 중 하나에 속할 때 다음과 같이 점들을 분리하는 (p-1)차원의 분리 초평면(hyperplane)을 찾는 것이 기본적인 목적입니다.

Margin

 하지만 단순히 데이터포인트들을 분리만 하는 hyperplane은 무수히 많습니다.

최적의 분리 초평면을 구하기 위해 마진이라는 직관적인 개념을 이해해야 합니다. 마진은 hyperplane과 가장 가까운 데이터포인트까지의 거리를 뜻합니다. SVM은 최대마진을 가지는 hyperplane을 구하는 것입니다. 그리고 이때 hyperplane을 결정하는 데이터포인트들이 바로 SVM에서 SV가 의미하는 Support Vector가 됩니다.

Hard margin SVM

Hard margin SVM은 단어 그대로 hard하게 분류를 하는 SVM이라고 할 수 있습니다. hard는 선형판별을 할 때 오차, 즉 마진의 안이나 밖에 기준과 맞지 않는 데이터를 절대 허용하지 않을 정도로 유연하지 않다는 뜻으로 풀어서 해석할 수 있습니다. Hard margin SVM은 다음과 같은 결정경계식을 가집니다.

여기서 는 초평면의 법선벡터이고 는 원점까지의 거리를 결정하는 값입니다. 이런 결졍경계식에서 d의 부호로 데이터를 구분할 수 있습니다. 예를 들어 다음과 같이 0보다 크면  로, 0보다 작으면 로 분류합니다.

초평면의 양쪽 영역의 서포트벡터들 까지의 거리가 같아야 하며 계산의 편의를 위해 거리를 1로 하면 결정경계식을 다음과 같이 나타낼 수 있습니다.

두 영역의 서포트벡터에서 초평면까지 거리를 절대값으로 변환하여 더하면 다음과 같은 식으로 표현되고 이는 마진의 크기와 같습니다.

따라서 마진을 최대로 하기 위해서는  를 최소화하는 목적함수를 구하면 됩니다. 목적함수는 계산상의 편의성을 위해 다음과 같이 나타냅니다.

 하지만 이 목적함수만 가지고는 데이터들을 완벽히 분류할 수 없습니다. 따라서 다음과 같은 제약식이 필요합니다.

목적함수와 제약식을 한꺼번에 두고 계산하기 위해 라그랑주 승수법을 사용합니다. 라그랑주 승수법은 제약조건이 있는 최적화 문제를 다룰 때 사용하는 방법이지만 자세한 설명은 생략하겠습니다.

라그랑주 승수법을 사용하여 목적함수와 제약조건을 결합하면 제약이 사라진 새로운 형태의 목적함수가 만들어집니다. (단, 라그랑주변수에 대한 조건은 만족해야 합니다.)

새롭게 구한 목적함수를 통해  과 를 구하여 기존의 결정경계식에 대입하면 다음과 같은 최종 판별함수식이 나오게 됩니다.

새로운 데이터가 들어왔을 때 판별함수식에 대입하여 0보다 크면 +1로, 0보다 작으면 -1로 분류하는 것 입니다.

Soft margin SVM

하지만 선형으로 정확하게 분류되는 데이터들은 극히 드물기 때문에 약간의 오분류를 허용하여 모델을 구축하는 Soft margin SVM이 나오게 됩니다. 모든 학습데이터에 대해 완벽하게 분류되는 것을 제약조건으로 가지는 기존의 Hard한 방법에서 약간의 오분류를 허용하고 전체적인 성능을 높이는 Soft한 방법으로 발전 된 형태입니다.

Soft margin SVM에서는 잘못 분류된 데이터포인트부터 해당결정경계까지의 거리를 나타내는 슬랙변수 가 사용됩니다. 슬랙변수의 크기만큼 초평면의 위 또는 아래로 오분류를 허용하는 것입니다. 따라서 가 클수록 오분류의 허용범위가 넓어지는 것을 의미합니다. 슬랙변수를 추가하면 다음과 같은 목적함수와 조건식이 나오게 됩니다.

Hard margin SVM에서와 마찬가지로 라그랑주 승수법을 이용하여 최적화된 파라미터를 구할 수 있습니다. 마찬가지로 분류함수에 구한 매개변수들을 대입하면 새로운 데이터의 분류를 할 수 있게 됩니다.

Kernel trick

Soft margin을 통해 약간의 오분류를 허용하는 선형분류의 유연성이 생기긴 했지만 애초에 선형으로 분류가 불가능한 위 그림과 같은 데이터는 Kernel trick을 이용한 SVM을 통해 분류가 가능합니다.

위의 그림처럼 저차원의 비선형 분류경계를 가지는 데이터를 고차원으로 매핑 시킨 후 분류 초평면을 찾기 위해 차원 매핑에 커널함수를 사용하게 됩니다. 하지만 데이터들을 고차원으로 매핑하고 이를 다시 내적하는 과정에서 연산이 매우 크게 늘어나는 단점이 있습니다.

그래서 나오게 된 방법이 Kernel trick입니다. 매핑함수를 라고 할 때 는 =Ax 같이 선형변환이 가능하다고 가정합니다. 선형변환이 가능하다면 내적도 선형변환을 통해 가능 할 것입니다. 따라서 선형변환이 이루어지는 두 내적공간만 정의 해주면 매핑과 내적을 동시에 하는 다음과 같은 커널함수를 만들 수 있습니다.

고차원에서의 복잡한 연산없이 저차원에서 함수계산만으로 원하는 풀이를 할 수 있는 커널 함수를 사용하여 증가한 연산량의 문제를 해결하는 것입니다. 이 뒤로의 판별경계를 구하는 과정은 앞에서의 과정과 같습니다. 커널함수의 종류로는 기본적인 Linear커널과 다음과 같은 종류들이 있습니다.

마치며

오늘은 분류모형으로 많이 쓰이는 SVM에대해 알아보았습니다. SVM은 선형결정경계를 사용하여 이진분류를 하는 것을 기본으로 하는 모델이지만 데이터에 따라 유연하게 대처할 수 있는 여러가지 방법들이 있습니다. 오늘 소개해드린 Soft margin을 사용하여 데이터의 noise를 해결 할 수도 있고 Kernel trick을 사용하여 비선형 분류도 수행할 수도 있습니다. 이 외에 데이터에 라벨이 지정되어 있지 않다면 클러스터링기법을 통해 그룹화를 진행하여 SVM을 가능케 할 수도 있습니다. 또한 다범주 문제도 다중 바이너리분류로 접근하면 1대 전체, 혹은 모든 범주를 1대1로 비교하는 방법 등을 통해 해결 할 수 있다고 알려져있습니다.

Reference

https://dev.datasift.com/blog/building-better-machine-learned-classifiers-faster-active-learning

https://docs.opencv.org/2.4/doc/tutorials/ml/introduction_to_svm/introduction_to_svm.html

http://gentlej90.tistory.com/43

https://en.wikipedia.org/wiki/Support_vector_machine

https://www.slideshare.net/kambliruta/event-classification-prediction-using-support-vector-machine

http://blog.hackerearth.com/simple-tutorial-svm-parameter-tuning-python-r

http://www.cogsys.wiai.uni-bamberg.de/teaching/ss06/hs_svm/slides/SVM_and_Kernels.pdf