Scalable Kernel Methods via Doubly Stochastic Gradients
해리s2015. 9. 25. 13:18
http://arxiv.org/abs/1407.5599
원래 논문이 나온건 NIPS 2014였는데, 그 뒤에 워크샵 내용도 추가된 저널 버젼은 한 이주 전에 나왔다.
이 논문은 올해 본 논문 중에서 가장 수학적으로 아름다운 논문이다. 이 논문을 이해하기 위해선 몇 가지 기본 지식이 필요한데, 이런 내용부터 간단히 설명을 해보겠다.
가장 중요하게 알아야될 것은 커널이다. 커널, 옥수수, 리눅스 등이 생각날 수 있지만, 수학적으로 커널은 데이터 두 개를 받아서 실수로 바꿔주는 함수이다. 기계 학습 수업들에서는 데이터를 임의의 고차원 공간으로 보낸 후에 해당 공간에서 내적을 해주는 것이라고 설명을 하기도 한다. 물론 맞는 말이지만 이것 보다는 좀 더 복잡한 내용들이 존재한다. 예를 들면 과연 고차원 공간으로 보내주는 매핑이 존재하는가? 이런 것 말이다.
두 번째는 kernel method를 바라보는 다른 관점이다. 논문을 설명하면서도 나오겠지만, 많은 커널 방법론들은 데이터가 살고 있는 공간이 아닌 커널들로 만들어진 새로운 공간에서 convex optimization으로 표현될 수 있다. 이 공간을 reproduction kernel Hilbert space (RKHS)라 한다.
Duality between Kernels and Random Processes
커널 방법론은 커널 함수를 사용해서 커널 방법론이라 불린다. 당연하다. -_- 이들은 '$k(x, x') : X \times X \to R$' 이고, symmetric이고 positive definite하다. PD의 정의는 넘어가겠다. 여기에 한가지 재밌는 성질이 있는데
커널과 랜덤 프로세스 사이에는 duality가 있다.
논문의 Theorem 1은 다음과 같다.
위의 식에서 '$\phi_w(x)$'가 우리의 입력 '$x$'를 다른 공간으로 보내주는 함수이다. 랜덤 프로세스라는 용어가 나온 이유는 '$\phi_w(x)$'를 랜덤 프로세스라고 볼 수 있기 때문이다. 랜덤 프로세스를 수학적으로 정의하면 임의의 sample space에서 하나를 뽑으면, 그 뽑은게 어떤 함수를 나타나게 되는 것이다. 여기서 sample space가 '$\Omega$'이고, 여기서 '$w$'를 뽑으면 어떤 함수 '$\phi_w(x)$'가 생성되므로 랜덤 프로스세가 되는 것이다. (여기까지는 커널을 좀 공부하면 다들 알고 있는 사실일텐데 이 논문에서는 이 성질을 사용하여서 알고리즘을 만들어 내었다는 점에서 수학적 아름다움이 있다.)
뛰어난 수학 잘하시는 분들께선 많은 커널 함수에 대해서 '$\phi_w(x)$'와 '$p(w)$'를 구해놓으셨다. (세상엔 수학 잘하는 사람이 왜이리 많은가..) 아래 표를 참고하도록 하자.
문제는 많은 경우에 허수를 포함한다. 무슨 말인고 하니.. 직접 써먹기가 힘들다. 하지만 역시나 우리의 뛰어난 수학자이신 Bocher 님께선 다음과 같은 사실을 발견하셨다.
여기엔 허수가 없다. 좋다! 게다가 위의 theorem에서 if and only if가 있다. 이는 수학적으로 동치 혹은 정의를 나타내고, 우리가 갖고 있는 함수가 real-valued, symmetric, 그리고 shift-invariant하면 (즉 커널 함수가 두 입력의 차로 표현될 수 있으면) 항상 커널과 랜덤 프로세스 사이의 듀얼리티 관계를 사용할 수 있는 것이다. (개인적으로 Bochner theorem은 익숙한데, 내가 제안한 커널 함수의 positive definiteness를 증명하는데 이를 사용했기 때문이다.)
여기에 몇가지 중요한 성질들을 나열하겠다. 출처는 Gaussian process for machine learning이란 책으로 공짜로 받을 수 있다.
우리가 소위 말하는 매핑된 고차원 벡터들이 살고 있는 공간을 RKHS라 하고, 이 공간의 존재성을 보이는 것이 Moore-Aronszajn theorem이다. 바꿔 말하면 우리가 사용하는 커널 함수가 positive definite하면, 해당 매핑이 있음을 보이는 것과 같다.
RKHS에 살고 있는 고차원 벡터들은 사실 함수이다. 수학적으로 함수는 무한차원의 벡터와 같다.
자 이제 이 논문에서 제안하는 doubly stochastic functional gradient를 설명해보자.
Doubly Stochastic Functional Gradients
많은 커널 방법론들은 RKHS 공간에 살고 있는 함수들의 convex optimization으로 나타낼 수 있다. 그리고 이 성질은 이 논문에서 제안하는 방법론을 유도하는데 가장 중요한 성질이다.
이게 직관적으로 잘 안와드을 수 있는데 다음의 예를 통해서 좀 더 명확히 알아보자. (이 내용 역시 Gaussian process for machine learning에 있는 내용이다.)
먼저 representer theorem이란 것을 이용하면 우리가 찾고 싶은 함수 f는 다음의 꼴로 나타내질 수 있다.
$$f(x) = \sum_i \alpha_i k(x, x_i)$$
그리고 이 성질을 이용하면 Gaussian process의 mean function은 다음과 같이 유도될 수 있다.
즉 Gaussian process regression은 위의 식에서 (6.19)와 같이 함수 f에 대한 convex optimization으로 치환될 수 있는 것이다. 상당히 흥미롭다. (이 내용 역시 최근 논문에서 제안한 커널 함수를 사용한 GPR을 해석하는데 사용되었다.)
이러한 성질을 이용하면 함수 f에 대한 gradient를 다음과 같이 구할 수 있다. 여기서 stochastic functional gradient라는 것이 나오는데 이는 흔히 알고 있는 SGD와 같다. 즉 데이터를 전부 보는 것이 아니라 하나씩 보겠다는 것이다.
여기까지 왔으면 절반은 왔다. 이제 doubly stochastic에서 남은 하나의 stochastic을 설명해보자. 우리가 앞에서 커널 함수와 랜덤 프로세스 사이의 duality를 보였었는데, 이 성질을 사용하지 않았다.
위의 (3) 식에서 커널 함수를 위의 적분식을 이용해서 근사하면 된다. 무슨 말인고 하니 우리가 '$w$'의 분포를 알고 있으니 '$w$'를 뽑고, 여기서 '$\phi_w(x)$'를 만들어내면 SGD와 같이 stochastic approximation이 되고, 이를 이용해서 Doubly stochastic functional gradient를 구할 수 있다.
이제 위의 doubly stochastic functional gradient를 이용한 학습과 검증 알고리즘은 다음과 같다.
여기까지가 끝이다. 이 논문에선 여러 커널 방법론들에 대해서 '$f$'관점에서 loss function과 gradient를 설명해놓고 있다. 설명이 간단하니 논문을 참고하기 바란다.
구현에 있어서 약간의 휴리스틱이 들어갔는데 다음과 같다. (사실 이거 빼면 안돌아간다..)
We note that our algorithm can also take a mini-batch of points and random features at each step, and estimate an empirical covariance for preconditioning to achieve potentially better performance
