Gaussian kernelが正定値性をみたすことの証明

Introduction : 正定値なkernel

Gaussian kernel（動径基底関数カーネル, RBF kernel）とは、

\begin{eqnarray*}
k(x,y) &:=& \exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right)
\end{eqnarray*}

と数式で定義されます。機械学習においてkernel法（例えば、SVMやkernel PCAなど）で主に用いられる関数の一つです。

kernel法では、正定値性 (positive definite) を持つkernelを考えることが自然です。正定値なkernelとは、以下の2条件をみたすような関数$k:\Omega\times\Omega\rightarrow\mathbb{R}$のことをいいます。
(1) 対称性 : $k(x,y)=k(y,x)$
(2) 正定値性 : どんな正の整数$n$および$\Omega$の要素$x_1,\cdots,x_n$に対しても、行列$K=(k(x_i,x_j))$が半正定値である。要するに、どんな実ベクトル$v\in\mathbb{R}^n$に対しても、$v^TKv\geq0$になる。この$K$をGram行列といいます。

Gaussian kernelは、$\Omega=\mathbb{R}^m$における正定値なkernelの代表例として知られています。そこで、今回の記事では次の問題を考えてみましょう。

問題 : Gaussian kernelが正定値なkernelであることを証明せよ。

1. 解答1

以下に示す4つの命題を組み合わることで、この問題の証明を与えることが出来ます。

命題 : $x,y$は$m$次元のベクトルであるとする。
(1) $k(x,y)=x^Ty$は正定値なkernelである。
(2) $c>0$とする。$k(x,y)$が正定値なkernelならば、$ck(x,y)$もまた正定値なkernelになる。
(3) $k(x,y)$が正定値なkernelのとき、$\exp(k(x,y))$もまた正定値なkernelになる。
(4) $k(x,y)$が正定値なkernelのとき、どんな関数$f:\mathbb{R}^m\rightarrow\mathbb{R}$に対しても$k'(x,y)=f(x)k(x,y)f(y)$は正定値なkernelになる。

命題の主張を認めて、問題の証明を与えてみましょう。なお、命題の証明もまた後ほど与えます。

問題の証明 : $x^Ty$が正定値なkernelであることから、$x^Ty/\sigma^2$は正定値なkernel、さらに$\exp(x^Ty/\sigma^2)$もまた正定値なkernelとわかります。Gaussian kernelは

\begin{eqnarray*}
\exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right) &=& \exp\left(-\frac{\|x\|^2}{2\sigma^2}\right)\exp\left(\frac{x^Ty}{\sigma^2}\right)\exp\left(-\frac{\|y\|^2}{2\sigma^2}\right)
\end{eqnarray*}

なので、命題(5)からGaussian kernelが正定値なkernelであることが分かります。■

命題の証明を行いましょう。対称性の証明は難しくないので、正定値性のみを示します。

命題(1)の証明 : $x_1,\cdots,x_n$を$m$次元のベクトルであるとします。このとき、行列$K=(x_i^Tx_j)$は行列$A=\begin{pmatrix}x_1&x_2&\cdots&x_n\end{pmatrix}$を用いて$K=A^TA$と書けます。ゆえに、どんな$n$次元のベクトル$v$に対しても、$v^TKv=||Av||^2\geq0$が成り立ち、$k(x,y)=x^Ty$が正定値なkernelであることが分かります。■

命題(2)の証明 : $k(x,y)$のGram行列を$K$, $ck(x,y)$のGram行列を$K'$と書くとき、$K'=cK$となります。また$k(x,y)$が正定値なので、行列$K$はどんな$m$次元のベクトル$v$に対しても$v^TKv\geq0$を満たします。ゆえに、$v^TK'v=c(v^TKv)\geq0$が成り立ち$cK(x,y)$の正定値性がわかります。■

命題(3)の証明 : $\exp$の$x=0$まわりのTaylor展開を用いれば

\begin{eqnarray*}
\exp(k(x,y)) &=& \sum_{m=0}^{\infty}\frac{1}{m!}k(x,y)^m
\end{eqnarray*}

ですが、正定値なkernelの和と積はまた正定値なkernelになる（ここでは証明しません）ことから、$\exp(k(x,y))$もまた正定値なkernelであることがわかります。■

命題(4)の証明 : $k(x,y)$のGram行列を$K$, $f(x)k(x,y)f(y)$のGram行列を$K'$と書くことにします。また、このベクトル$x_1,\cdots,x_n$と$n$次元のベクトル$v=(v_i)$に対して、$v'=(f(x_i)v_i)$と書くことにします。$k(x,y)$の正定値性から、行列$K$がどんな$m$次元のベクトル$v$に対しても$v^TKv\geq0$をみたすことに注意すれば、

\begin{eqnarray*}
v^TK'v &=& v'^TKv' &\geq& 0
\end{eqnarray*}

が成り立つので、$f(x)k(x,y)f(y)$が正定値であることが分かります。■

2. 解答2

解答1は、正定値なkernelの基本的な例である$k(x,y)=x^Ty$を出発点に、正定値なkernelが持つ一般的な性質を用いてGaussian kernelが正定値性をもつことを示すものでした。解答2では、より直接的に問題の証明を与えることを目指します。

問題の証明 : $m$次元の正規分布$N\left(0,\sigma^2E_{m}\right)$の特性関数が$\phi(t)=\exp(-t^Tt/2\sigma^2)$, $t\in\mathbb{R}^m$であることに注意します。特性関数の定義から、Gaussian kernelは$k(x,y)=\phi(x-y)$と書き換えることが出来ます。$v$を$n$次元の実ベクトル, $K$をGaussian kernelのGram行列, $Z$を$n$次元の正規分布$N\left(0,\sigma^2E_{m}\right)$に従う確率変数とするとき以下の式変形が成り立ちます。

\begin{eqnarray*}
v^TKv &=& \sum_{i,j=1}^{n}v_iv_j\phi(x_i-x_j)\\
&=& \sum_{i,j=1}^{n}\mathbb{E}\left[v_iv_j\exp(i(x_i-x_j)^TZ)\right]\\
&=& \mathbb{E}\left[\sum_{i,j=1}^{n}v_i\exp(ix_i^TZ)v_j\exp(-ix_j^TZ)\right]\\
&=& \mathbb{E}\left[\left(\sum_{i=1}^{n}v_{i}\exp(ix_i^TZ)\right)\left(\sum_{j=1}^{n}v_{j}\exp(-ix_j^TZ)\right)\right]\\
&=& \mathbb{E}\left[\left|\sum_{i=1}^{n}v_{i}\exp(ix_i^TZ)\right|^2\right]\\
&\geq& 0
\end{eqnarray*}

なお、式変形の5段目は、複素数$z$の大きさに対して$|z|^2=z\bar{z}$が成り立つことを用いました。以上により、Gaussian kernelが正定値なkernelであるとわかります。■

Acknowledgement

昨日は、ついに記事の更新が出来ずに終わってしまいましたが、今日は無事に書くことが出来ました。twitterやfacebookで温かいコメント, RT, いいねを下さる皆さまに感謝申し上げます。