[ML개론] (14) dual SVM with Kernel

이전글을 통해 dual SVM을 풀어내는 방식은 알아냈다. 그러나 여전히 trend가 존재하는, nonlinear한 형태의 data를 어떻게 분류할지에 대해선 모른다. 그 방법인 Kernel fn에 대해 알아보자. 

 

우리는 좌측그림과 같은 XOR문제를 2차원상에서 해결할 수 없다. 따라서 이를 특정 standard basis 위로 옮겨 3차원 상에 mapping(L -> H)하여 classification을 진행할 수 있다. 그러나 feature의 갯수가 많아질수록 Φ(x) 또한 무한히 커지게 되어 연산과정에 부담이 된다. 

 

따라서 이를 보완하기 위해 등장한 것이 kernel이다. 솔직히 아직도 그 방식을 완벽히 이해하진 못하겠지만 추후 실습코드와 함께 보충을 기약하며 이해한 것을 정리해보겠다. 

mapping fn의 경우 같은 공간에 위치한 서로 다른 두 벡터 x=<x1, x2>, y=<y1,y2>를 3차원 상에 mapping한다. 

그러나 kernel 기법의 경우 K(<x1,x2>,<y1,y2>)=<x1^2, root(2)x1x2, x2^2>·<y1^2, root(2)y1,y2, y2^2>이고 그 결과값은 (x1y1+x2y2)^2 = (x·y)^2이다. 따라서 모든 벡터를 mapping 시키지 않고 Kernel함수를 씌어주기만 함으로써 차원을 유지하면서 문제를 해결할 수 있다. 

즉 다시말해 기존 <x1,x2>와 <y1,y2>를 내적한뒤 n차만큼 곱하기만해도 이들을 mapping fn에 대입하여 차원을 늘린 후 내적한 값과 동일하다는 것이다. 계산이 훨씬 간편해진다. 

 

다시 dual problem으로 돌아와서, 우리는 nonlinear한 x들을 다루고 있으니 이들을 Kernel fn에 대입해줄 필요가 있다. 

mapping fn에 옮겨진 xi, xj의 내적값이 Kernel(xi,xj)와 같으니 대신하여 채택한다. 이 때 위 식을 maximize해주는 labmda가 존재할텐데 이를 다시 w=sigmasum(lambda*y*x)에 대입하고, b에도 대입하여 w*, b를 찾는다. 

 

polynomial kernel을 예시로 들었으나 NLP를 제외하곤 그리 선호되지 않는다. RBF가 가장 많이 선호되는 방식인데 이는 dataset의 분포에 따라 multivariate gaussian distribution을 형성하고, y<0이면 Kernel fn의 반환값으로 0을 y>0이면 1을 반환한다. 이런 방식으로 신규 data에 대해 판독을 내린다. 관련해서는 실습코드와 함께 상술할 계획이다. 

 

lambda를 구해서 w와 b를 구했다면, 새로 들어오는 data x에 대해 classification을 진행해야한다. 이 때 Kernel fn을 사용함으로 인해 사소한 문제가 발생한다. 사실 Kernel fn은 d차원에서의 벡터들을 d+a차원으로 옮겨 linearly discriminate해준 값을 다시 돌려주는 것이다. 따라서 기존의 linear한 classification line과는 달리 2,3차원에서 표현이 어렵다.

그러나 w*Φ(x)+b의 부호는 여전히 알 수 계산할 수 있기 때문에 이를 classification 해줄 수는 있다. 위 예시처럼 i,j에 대해 연산한 Kernel mtx와 많이 겹치는 쪽으로 부호가 판가름난다. 

 

위 그림을 살펴보면 label에 맞게 비선형적으로 잘 분류되었음을 확인할 수 있다. 좌측 그림을 살펴보면 4차 polynomial K를 활용하여 비선형적으로 분류한 것이다. 우측은 RBF를 사용한 결과다.