Kernel machine basic

Random Fourier Feature가 뭔지 궁금해서 개념만 간단히 정리. Reference에서 아주 잘 설명되어있다.

Reference

Random Features for Large-Scale Kernel Machines (Ali Rahimi, Benjamin Recht / NIPS 2007)
https://gregorygundersen.com/blog/2019/12/10/kernel-trick/
https://gregorygundersen.com/blog/2019/12/23/random-fourier-features/#a1-gaussian-kernel-derivation

Kernel machine

RFF를 이해하려면 먼저 kernel machine을 간단히 알고 있어야 한다.

어떤 input space의 데이터 $(x_n,y_n)$의 classification 문제를 linear model로 풀고자 한다면 이는 어떤 적당한 hyperplane $f(x)=w^Tx$를 찾는 문제일 것이다. 하지만 위의 그림처럼 data가 linear하게 separable하지 않은 경우에는 non-linear function을 도입하여 해결할 수도 있겠다.

조금 다른 관점에서는, input domain space ($x \in \mathcal X$)을 선형적인 특성을 가지는 또 다른 더 높은 차원의 space ($\phi(x) \in \mathcal V$)로 mapping시켜서 linear model을 통해 구분하는 방식을 생각해볼 수 있다.

여기서 사용하는 함수 $\phi$가 basis function 혹은 feature map이다.

(예시) data point $x$를 polynomial kernel을 사용해 $\phi(x)$로 옮긴 경우

출처: https://gregorygundersen.com/blog/2019/12/10/kernel-trick

그런데 실제로는 이 $\phi$를 explicit하게 적용하는 것이 매우 복잡하기 때문에 (모든 data point에 preprocessing), kernel trick을 이용하여 어떤 kernel function을 통해 computationally cheap하게 연산을 수행하고자 한다.

여기서 SVM의 loss function을 한번 생각해보자.

이 식이 어떻게 나왔는지는 따로 공부하는 것으로 하고, 결론적으로 SVM은 data point들의 내적 연산을 필요로 한다. 바로 위의 그림 A와 같은 data를 분류하려 한다면 똑같이 polynomial kernel로 데이터를 옮길 수 있다.

그럼 뒤의 내적 항은 아래와 같이 계산되고 모든 데이터 포인트에 대해서 이것을 계산하면 된다.

그런데 한번 이렇게 계산해보자.

각 data point를 고차원으로 이동시킨 후 내적을 연산하지 않고, 내적을 계산하고 제곱을 취했다. 여기서는 문자를 써서 별로 연산에 차이가 많이 나보이지는 않지만 실제로는 내적 연산을 더 낮은 차원에서 한다는 것이 곱셈과 덧셈을 훨씬 덜 하고, 내적 후에는 그냥 scalar 제곱이기 때문에 훨씬 computational cost가 낮다.

즉, kernel trick은 더 높은 차원에서의 내적 연산과 같은 결과를 낼 수 있는 어떤 적당한 kernel function $k(x_n,x_m)$을 찾아 사용함으로써 더 높은 차원에서 expensive한 연산을 줄이는 방법이다. (방금전 예시에서는 $k(x_n,x_m)=(x_n^Tx_m)^2$이고, 다양한 kernel function이 이미 많이 정의되어 있다.)

Kernel trick에 대한 mathmatical basis는 Mercer’s theorem를 더 공부해보면 좋을 것 같다. (symetric function, positive semidefinite)

그런데 이런 Kernel trick도 $N*N$의 covariance matrix $K$를 기반으로 연산되기 때문에, data point $N$이 너무 큰 경우 여전히 비효율적일 수 있다.

Random Fourier Feature (RFF)

Random Features for Large-Scale Kernel Machines에서는 이러한 내적값을 low dimensional random feature $z$를 이용하여 approxiamte하여 computational cost를 더 낮추고자 하였다.

즉, 어떤 random projection $z$를 잘 찾아내서 data를 projection시키고, 이를 간단한 linear model로 분류하는 것이다.

Random $D$차원의 vector $w \sim \mathcal N_D(0,I)$를 이용해 $h:x \to exp(iw^Tx)$를 정의하면 아래와 같이 gaussian kernel을 approximate할 수 있다. (*는 켤레복소수)

어떤 non-negative measure $p(w)$의 fourier transform은 아래와 같은데,

위의 observation과 Bochner's theorem을 바탕으로 fourier transform을 이용한 shift-invariant kernel의 approximation이 가능해진다.

Bochner’s theorem: A continuous kernel $k(x,y)=k(x−y)$ on $\mathbb R^D$ is positive definite if and only if $k(\Delta)$ is the Fourier transform of a non-negative measure.

위 식에서 1은 Monte Carlo approximation이고, 2는 random map $h$의 정의를 의미한다.

실제로는 $w$의 분포 $\mathcal N_D(0,I)$와 kernel $k(\Delta)$가 모두 real value이므로, 허수부를 제외하고 $z_w(x)$를 정의할 수 있다.

그러면 random feature map $z:\mathbb R^D \to \mathbb R^R$을 정의할 수 있다.

그러므로 이것을 통해 shift-invariant, positive definite kernel을 쉽게 estimate할 수 있다.

Gaussian Kernel approximation

수학은 예시가 없으면 이해가 참 안간다. 예시로 gaussian kernel을 random fourier feature로 approximate해보자.

그냥 R개의 iid $w$를 spherical Gaussian으로부터 sampling해서 아래를 계산하면 된다.

N개의 모든 데이터 pair ($x,y$)에 대해 계산을 하면 바로 gaussian kernel function을 estimation하는 $N*N$ 공분산 행렬을 얻을 수 있다.

위 그림에서 볼 수 있다시피 sampling하는 fourier feature의 수 R이 커질수록 더욱 정확한 approximation을 해내는 것을 볼 수 있다.

Discussion

다른 논문을 읽다가 Random fourier feature라는 내용을 이해하고 싶어서 조금 공부해봤다. 결론적으로는 어떤 task를 잘 수행하기 위해서 data point를 더 높은 차원으로 mapping하고 싶은데, 이를 mapping하는 function을 찾기 위해 kernel trick을 사용할 수 있고, 이러한 kernel 자체를 더 간단히 estimation하기 위해 fourier base feature의 combination을 사용할 수 있다라는 내용이었다.