Kernel

 

데이터를 공이라고 생각하고 공을 공중에 던져보면 구분 경계를 쉽게 찾을 수 있다. 이 과정을 kernel trick 이라고 한다.

 

왼쪽의 그림에서는 주황색 또는 파란색 선을 그어도 missclassification 이 포함되게 된다. 여기에 한 차원들 더해서 2차원으로 만들면 적당한 구분선을 그을 수 있다. Kernel function 은 데이터를 고차원 공간으로 매핑하는 역할을 한다.

 

참고로 Kernel 은 SVM 에만 사용되는 것이 아니라 내적 ⟨x,z⟩형태로 표현되는 다양한 알고리즘에 적용할 수 있다. Dimension 을 증가시키는 다양한 경우에 활용될 수 있다. 

 

Kernel trick 적용하기

Step 1: 알고리즘을 두 입력 벡터의 내적 형태 로 작성하기
예: ⟨x,z⟩ 

SVM 같은 경우, 결정 경계를 학습하는 과정에서 데이터 포인트 간 내적이 사용된다. 

 

Step 2: Kernel 함수를 적용하기

 

Step 3: Kernel 함수의 구체적인 형태 정의하기

 Kernel 함수를 결정한다. 예를 들어, RBF 커널, 다항 커널 등 다양한 Kernel 함수가 여기에 사용될 수 있다.

 

Step 4: 알고리즘의 내적을 Kernel 함수로 대체하기
<x,z> 를 K(x,z) 로 대체

 

Kernel trick 필요성

x와 z가 원래 차원이 n인 벡터라고 가정하면, 이들을 고차원 공간으로 사상하면 각 원소의 곱으로 구성된 새로운 벡터 ϕ(x)와 ϕ(z)가 만들어진다. 이렇게 하면 차원이 $O(n^2)$으로 증가한다.

고차원 공간에서의 두 벡터 ϕ(x)와 ϕ(z) 간의 내적 $\phi(x)^T \phi(z)$ 를 계산하려면 $O(n^2)$의 연산이 필요하다. 이는 계산 복잡도가 높아 비용이 많이 든다. 

 

이때 Kernel Trick을 사용하면 고차원 벡터 ϕ(x)를 직접 계산하지 않고도 고차원 공간에서의 내적 결과를 얻을 수 있다.

 

 

가운데 부분을 계산할 필요가 없는 것이다. 각각의 점을 고차원으로 매핑할 필요 없이 두 점의 내적만 계산해주면 된다. 그러면 계산 복잡도가 $O(n)$ 밖에 되지 않는다. 자세한 증명은 아래와 같다. 

 

 

 

 

Polynomial kernel

 

 

c와 d 에 값을 넣어 계산을 해보면 두 점의 내적 형태로 정리되게 된다. 분류를 잘 하는 c와 d 값을 찾아내는 것이 관건이다. 

 

c=1/2, d=2 일 때의 9와 14 두 데이터 포인트의 관계를 계산할 수 있다. 16002.xx 는 polynomil function 을 이용해서 고차원으로 map 했을 때, 새로운 차원에서 두 점 사이의 거리를 의미한다. 

 

만약 c=0 이라면, 새로운 차원이 더해지지 않는다. 다만 데이터들끼리의 거리가 조금 더 멀어지는 rescaling 은 일어난다. 

 

Gaussian kernel

Gaussian Kernel은 무한 차원으로 데이터를 매핑할 수 있다. 

 

Gaussian Kernel 에서는 $\Gamma$ 값이 중요하다. 높은 분류 정확도를 보이는 $\Gamma$ 값을 실험적으로 찾아내야 한다.

 

2.5와 4 데이터를 예시로 들어 설명하자면, $\Gamma=1$ 일 때 가우시안 커널의 값은 0.11 이다. $\Gamma=2$ 일때는 값이 0.01 로 감소한다. 즉, $\Gamma$ 값이 커지면 새로운 차원에서 두 점 사이의 거리가 줄어든다. 

 

이번에는 $\Gamma=1$ 로 고정하고 2.5와 4 데이터가 아닌 2.5와 16 데이터를 계산해보자. 커널값은 거의 0이다. 즉, 멀리 떨어져 있는 점일수록 커널값은 작아지고, 가까운 이웃일수록 영향이 크다. 

 

 

Gaussian kernel 공식을 전개해보자. $e^xz$ 를 taylor series expansion 을 이용해서 계산하면, 두 개의 데이터 포인트를 내적한 모양으로 표현이 된다. Infinite dimension 이라고 계산이 복잡해지는 것이 아니라 똑같이 내적만 계산하면 되는 것이다. 

Mercer's therorem

 

Mercer's Theorem은 어떤 함수가 유효한 Kernel 함수로 사용될 수 있는지 판별하는 기준을 제공하는 정리이다. Kernel function 을 적용한 수의 Kernel matrix 는 아래의 조건을 만족해야 한다. 

 

주어진 데이터 포인트들 $x_1, x_2, \dots, x_d$ 에 대해 구성한 Kernel 행렬 K가 대칭(symmetric)이어야 하며, positive semi-definite이어야 한다.

Positive semi-definite 는

- K>=0 : 모든 교유값이 0 이상이다. 

- diag(K) >= 0 : 대각 성분이 항상 0 이상이다. 

 

정리

그렇다면 어떤 상황에서 어떤 커널을 사용해야 할까? 정답은 없지만 데이터셋을 고려하면 좋다. 

- 데이터에 대한 사전 정보가 없다 -> 기본적인 Gaussain kernel

- 데이터가 선형적으로 분리 가능하다 -> Linear kernel

- decision boundary 에 대한 아이디어가 있고 경계가 부드러워야 한다. -> Gaussian kernel

 

실제 분석에서는 교차 검증 (cross-validation)을 통해 다양한 Kernel을 시도해보고, 가장 좋은 성능을 내는 Kernel을 선택하는 것이 일반적이다.