[출처] - http://trip2ee.tistory.com/52
패턴인식에서 Neural Network 매우 많이 사용되고 있는 알고리즘 중 하나이다. 하지만 Neural Network 는 학습데이터를 가장 적은 에러로 분리할 수 있는 수많은 decision boundary 중 하나를 선택할 뿐이다. 따라서 학습데이터 외의 데이터를 얼마나 잘 분류할 것인가 하는 generalization 성능의 관점에서 보면 optimal 한 결과는 아니다.
그렇기 때문에 decision boundary 와 학습데이터 간의 거리를 최대한으로 만드는 Support Vector Machine (SVM) 이 나왔다. SVM 에서는 분류에러를 최소화 하는 수식을 Lagrange Multiplier 를 이용해 계산하고 Quadratic Programming (QP) 문제를 풀어서 가장 optimal 한 decision boundary를 찾는 방법이라고 많은 책과 자료들에 설명되어 있다.
하지만 QP 문제를 어떻게 풀 것인가? 이것이 가장 어려운 문제였지만 어느 자료에서도 그것을 설명해 주지는 않았다. SVM을 알게 된게 작년 이맘때이며 이 QP 문제를 풀기 위한 방법을 지금까지 틈틈히 찾아봤지만 명확한 답을 얻지 못했다.
그러다 Numerical Recipes 3rd edition 에 pattern classification 에 대한 항목이 추가되었으며 여기에 SVM 에 대한 부분이 있음을 알았다. Numerical Recipes 3rd edition 은 이미 인터넷 상에서는 절판되어 구할 수 없는 것이었으나 강남 교보문고에 단 하나 남아있던 책을 구입할 수 있었다.
이 책에는 Successive Overrelaxation (SOR) 을 이용하여 SVM의 QP 문제를 푸는 다음 논문의 방법을 이용한 C 소스코드를 제공한다.
Olvi L. Mangasarian and David R. Musicant. Successive overrelaxation for support vector machines. IEEE Trans on Neural Networks, 1999, 10(5): 1032-1037.
이 논문은 다음 링크를 통해 다운받을 수 있다.
다음은 Numerical Recipes 3rd edition 에 나오는 C 코드를 MATLAB으로 구현한 결과이다. 저작권 등의 문제가 생길 수 있기 때문에 MATLAB코드는 공개하지 않도록 하겠다.
Linearly Separable 한 경우
Linearly non-separable 한 경우
하지만 아무래도 Numerical Recipes 에서도 이야기 하듯이 SVM-Light와 같은 SVM 라이브러리를 이용하는 편이 분류 결과나 학습 시간을 생각한다면 더 좋을것 같다. 최적화된 SVM을 구현하기엔 아직 수학적 알고리즘 부분에서 공부해야 할 부분이 너무 많을것 같다.
