Support Vector Machine(SVM) Kernel trick

https://medium.com/@kushaldps1996/a-complete-guide-to-support-vector-machines-svms-501e71aec19e

A Complete Guide To Support Vector Machines(SVMs)

https://towardsdatascience.com/support-vector-machines-dual-formulation-quadratic-programming-sequential-minimal-optimization-57f4387ce4dd

Support Vector Machines, Dual Formulation, Quadratic Programming & Sequential Minimal Optimization

 

 

 

SVM은 두 클래스를 나누는 하이퍼플레인이 support vector들을 기준으로 최대한 큰 margin을 갖도록 하는 알고리즘이다.

 

약간의 오차(잘못 분류된 데이터포인트)를 허용하기 위해 Soft Margin SVM이 사용된다.

Soft Margin SVM

 

마진 $ \frac{2}{||w||} $을 최대화하는 문제는 dual form 유도과정을 통해 아래와 같이 $ \alpha $를 최대화하는 문제로 표현할 수 있다.

 

위 문제에서 $ \alpha $는 Sequential Minimal Optimization (SMO) 알고리즘을 통해 구해진다.

 

Kernel trick

선형 회귀 알고리즘에 비선형 회귀를 적용하기 위해 kernel이 사용된다.

kernel은 데이터를 보다 높은 차원으로의 변환을 통해 선형적으로 구분할 수 없던 것을 구분할 수 있게 만드는 개념이다.

 

Kernel trick은 kernel 행렬을 통해 변환과 내적을 동시에 처리하는 방법인데, $ x_i, x_j $ 데이터를 피쳐 공간으로 변환하는 동시에 내적한 결과를 gram 행렬로 계산하여 사용한다. (변환과 내적이 동시에 일어나므로, 실제로 피쳐 공간을 거치지는 않음)

 

scikit-learn에서는 (LIBSVM에 구현된) 다음 커널 함수들이 제공된다.

• linear: $ <x, x'> $.
• polynomial: $ (\gamma <x, x'> + r)^d $, where $d$ is specified by parameter degree, $r$ by coef0.
• rbf: $ exp⁡(−\gamma ||x - x'||^2) $ , where $\gamma$ is specified by parameter gamma must be greater than 0.
• sigmoid: $ tanh⁡(\gamma <x, x'> + r) $, where $r$ is specified by coef0.