6.2. Constructing Kernels

6.1에서 Gram matrix를 정의할 때엔 $\phi(x)$의 내적을 사용했고, Gram matrix를 kernel function으로 확장할 수 있음을 언급했다. 6.2에서는 kernel function이 무엇이고, 어떤 성질을 만족해야 하는지 알아보려 한다.

 

kernel function의 수학적인 정의는 다음과 같다.

Def. For an input space $\mathcal{X}$, a kernel is a bivariate function $k: \mathcal{X}\times \mathcal{X} \rightarrow \mathbb{R}$ s.t. $\forall x, x' \in \mathcal{X}$,

   1. $k(x, x') = k(x', x)$ (symmetric)

   2. $k(x, x') \geq 0$ (non-negative)

 

즉, kernel은 어떠한 input space에서 $\mathbb{R}$로의 연산을 하는 함수인데, 대칭성과 음수가 아님을 만족해야한다..

 

참고로, machine learning에서 사용하게 될 kernel은 Mercer kernel이다. Mercer kernel은 Gram matrix가 항상 positive-semidefinite한 kernel을 말한다.

 

kernel function의 가장 대표적인 형태는 6.1에서 보았던 $\phi(x)$의 내적이다. Gram matrix를 형성할 때 쓰였다.

$k(x, x') = \phi(x)^T \phi(x') = \displaystyle \sum_{i=1}^M \phi_i (x) \phi_i (x')$

내적은 어떠한 vector space(여기선 $\mathbb{R}^M$)에서 $\mathbb{R}$로의 연산으로, symmetric하고 non-negative하다. 게다가 내적 연산은 Mercer kernel이다.(증명은 알아서)

 

그렇다면 또 다른 kernel은 무엇이 있을까? 물론 엄청난 아이디어를 통해 만들어낸 함수가 kernel이라는 것을 직접 증명할 수도 있다. 그러나 더 쉬운 방법은 kernel이 만족하는 성질들을 이용해서 kernel function을 확장하는 것이다.

 

Properties. Given Mercer kernel $k_1 (x, x')$ and $k_2 (x, x')$, the following new kernels will also be Mercer kernel.

  1. $k(x, x') = ck_1 (x, x')$, $c >0$

  2. $k(x, x') = f(x) k_1 (x, x') f(x')$, $f: \mathcal{X} \rightarrow \mathbb{R}$

  3. $k(x, x') = q(k_1 (x, x'))$, $q$ is a polynomial with nonnegative coefficients

  4. $k(x, x') = $exp$(k_1(x, x'))$

  5. $k(x, x') = k_1 (x, x') + k_2 (x, x')$

  6. $k(x, x') = k_1 (x, x') k_2 (x, x')$

  7. $k(x, x') = k_3 (\phi(x), \phi(x'))$, $k_3$ is a valid kernel in $\mathbb{R}^M$, $\phi: x \mapsto a_x \in \mathbb{R}^M$

  8. $k(x, x') = x^T A x'$, $A$ is a symmetric positive semidefinite matrix

  9. $k(x, x') = k_a (x_a, x_a ') + k_b (x_b, x_b '), $x = (x_a, x_b)$, $k_a, k_b$ is valid kernel

  10. $k(x, x') = k_a (x_a, x_a ') k_b(x_b, x_b ')$

 

예를 들어, 우리는 $||x - x' ||^2 = x^T x + (x')T x' - 2x^T x'$이 kernel임을 1, 5번 property를 통해 알 수 있다.

또한 이렇게 얻은 새로운 kernel을 이용해서 $exp(- {{||x-x'||^2} \over {2\sigma^2}})$(Gaussian kernel) 또한 kernel임을 1, 4번 property를 통해 알 수 있다.

* 참고로 Gaussian kernel은 infinite-dimensional vector의 내적으로 표현될 수 있다. 즉 kernel을 도입한 덕분에 finite한 vector 뿐 아니라 infinite한 vector까지도 사용할 수 있다.

 

kernel function의 응용을 한 가지 살펴보자.

머신러닝은 probabilistic generative model과 discriminative model로 크게 분류할 수 있다. 이 두 model의 자세한 설명은 다음에 다루기로 하자. 여기서 중요한 것은, generative model은 uncertainty를 표현할 수 있는 장점이 있지만 performance는 discriminative model보다 떨어진다. 그 반대로 discriminative model은 performance가 높지만 uncertainty를 표현하는 데에는 한계가 있다.

 

kernel function의 중요성 중 하나는 generative model과 discriminative model의 접근을 연결하는 것이다.

 

1. $p(x)$ 라는 generative model이 주어졌을 때, 우리는 $k(x, x') = p(x) p(x')$로 kernel을 정의할 수 있다.(1-dimension inner product)

이 정의를 확장하여 latent variable의 개념을 도입하면, $k(x, x')=\displaystyle\sum_{i}{p(x|i)p(x'|i)p(i)}$이 되는데, 이 또한 1, 5번 property에 의해 kernel임을 알 수 있다.

*latent variable이란, 간단하게 말해서 $x$, $x'$의 feature을 담고 있는 variable이다. 직접적으로 $x$, $x'$의 distribution을 파악하는 것이 아니라, $x$, $x'$의 특징을 담은 variable의 distribution을 찾아내고, 그러한 특징을 바탕으로 한 $x$와 $x'$의 분포$(p(x|i)$, $p(x'|i)$에 관심을 가진다.

 

latent variable을 포함하는 kernel function은 infinite sum으로도 확장 가능하다: $k(x, x') = \displaystyle\int {p(x|z)p(x'|z)p(z)dz}$. 여기서 $z$는 continuous latent variable이다.

 

2. $p(x|\theta)$라는 parametric generative model이 주어졌을 때,우리는 fisher kernel이라는 kernel을 정의할 수 있다.

Fisher kernel은 다음과 같이 나타낼 수 있다: $k(x, x') = g(\theta, x)^T F^{-1} g(\theta, x')$, where

$g(\theta, x) = \nabla_\theta \ln p(x|\theta)$ (Fisher score) and

$F=\mathbb{E}_x [g(\theta, x)g(\theta, x)^T] \approx {1 \over N} \displaystyle\sum_{n=1}^N{g(\theta, x_n)g(\theta, x_n )^T}$ (Fisher information matrix)

 

Fisher score와 Fisher information matrix에 대한 자세한 설명은 수리통계학에서 다룬다.