PRMLの6章はカーネル関数が主役の章です。この章では、2つのカーネル関数の定義があり、この2つの定義は等価であることがPRML本文中(式(6.12)の下らへん)で述べられています。ただし証明はありませんので、この記事で2つの定義が等価であることを証明をします。
そのカーネル関数の定義の1つ目は、関数$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$が以下のような形で書けるとき、その関数$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$をカーネル関数という、というものです。

k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})=\boldsymbol{\phi}(\boldsymbol{\mathrm{x}})^{\mathrm{T}}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}^{\prime}}) \tag{*}

ここで、$\boldsymbol{\mathrm{x}}$と$\boldsymbol{\mathrm{x}}^{\prime}$はそれぞれ$D$次元の入力ベクトルとして、$\boldsymbol{\phi}$は$M$次元のベクトル関数で、入力ベクトルを特徴空間に写像する関数です。
カーネル関数の定義の2つ目は、$N$個の任意の入力ベクトルの集合{ $\boldsymbol{\mathrm{x}}_{n}$}に対して、要素が$k(\boldsymbol{\mathrm{x}}_{n}, \boldsymbol{\mathrm{x}}_{m})$であるグラム行列$K$が半正定値行列であるとき、$k(\boldsymbol{\mathrm{x}}_{n}, \boldsymbol{\mathrm{x}}_{m})$がカーネル関数である、というものです。
これらの2つのカーネル関数の定義が等価な定義であることを示していきます。

参考文献

PRML本文中でも参照されてますが、以下のJohn Shawe-Taylor and Nello Cristianini著の"Kernel Methods for Pattern Analysis"という参考書の3章を参考にしました。
https://dl.acm.org/citation.cfm?id=975545

やること

結局やることは、以下の同値関係を示すことである。

関数$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$が式(*)を満たす⇔ 上で定義したグラム行列$K$が半正定値行列である

本題の前に半正定値行列について

PRML本文でも登場するので詳しくは書きませんが、行列$A$が半正定値行列であるということは、任意のベクトル$\boldsymbol{v}$に対して、以下の性質を満たす$A$のことである。

\boldsymbol{v}^{\mathrm{T}}A\boldsymbol{v} \geq  0

ちなみに、半正定値行列$A$の固有値は全て非負です。

⇒の証明

まずは、

関数$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$が式(*)を満たす⇒ 上で定義したグラム行列$K$が半正定値行列である

を証明します。
(証明開始)
$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$が式(*)を満たすので、グラム行列$K$の要素$K_{nm}$は

K_{nm}=k(\boldsymbol{\mathrm{x}}_{n}, \boldsymbol{\mathrm{x}}_{m})=\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})^{\mathrm{T}}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}_{m}})

となる。よって、$\boldsymbol{v}$を任意のベクトルとすると、$\boldsymbol{v}^{\mathrm{T}}K\boldsymbol{v}$は

\boldsymbol{v}^{\mathrm{T}}K\boldsymbol{v}=\sum_{n=1}^{N}\sum_{m=1}^{N}v_{n}v_{m}K_{nm}=\sum_{n=1}^{N}\sum_{m=1}^{N}v_{n}v_{m}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})^{\mathrm{T}}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}_{m}})\\
=\bigg(\sum_{n=1}^{N}v_{n}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})\bigg)^{\mathrm{T}}\bigg(\sum_{m=1}^{N}v_{m}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}_{m}})\bigg)\\
=\Bigg\| \sum_{n=1}^{N}v_{n}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})\Bigg\|^{2}  \geq  0

となり、$\boldsymbol{v}^{\mathrm{T}}K\boldsymbol{v} \geq 0$より、グラム行列$K$が半正定値行列である。
(証明終了)

⇐の証明

次に、

関数$k(\boldsymbol{\mathrm{x}}, \boldsymbol{\mathrm{x}}^{\prime})$が式(*)を満たす⇐ 上で定義したグラム行列$K$が半正定値行列である

を証明します。
この証明には、任意の半正定値行列$P$は正方行列$Q$とその転置行列$Q^{\mathrm{T}}$によって、

P=Q^{\mathrm{T}}Q

と分解できることを使用します。(証明はこちらのページを参考にしてください。)
(証明開始)
この補題を利用すると、半正定値行列$K$は適当な正方行列$Q$を用いて、

K=Q^{\mathrm{T}}Q

と分解できる。ここで、$K$は$N×N$行列なので、$Q$も$N×N$行列である。
また、以下の性質を満たす$M×N$の行列$P$を導入する。

P^{\mathrm{T}}P = I

$M×N$の行列$B$を

B = PQ

と定義したら、$K$は

K=Q^{\mathrm{T}}Q=Q^{\mathrm{T}}P^{\mathrm{T}}PQ=(PQ)^{\mathrm{T}}PQ=B^{\mathrm{T}}B

と書ける。
この行列$B$を適当な$N$個の$M$成分ベクトルの集合{$\boldsymbol{b}_{n}$}を用いて、$B=(\boldsymbol{b}_{1},\boldsymbol{b}_{2},\cdots, \boldsymbol{b}_{N})$とすると、$K=B^{\mathrm{T}}B$の$(n,m)$成分$K_{nm}$は

K_{nm}=\boldsymbol{b}^{\mathrm{T}}_{n}\boldsymbol{b}_{m}

となる。
ここで、{$\boldsymbol{\mathrm{x}}_{n}$}に対して

\boldsymbol{b}_{n}=\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})

を満たすようなベクトル関数$\boldsymbol{\phi}$を定義すれば、グラム行列の成分$K_{nm}=k(\boldsymbol{\mathrm{x}}_{n}, \boldsymbol{\mathrm{x}}_{m})$は

k(\boldsymbol{\mathrm{x}}_{n}, \boldsymbol{\mathrm{x}}_{m})=\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{n})^{\mathrm{T}}\boldsymbol{\phi}(\boldsymbol{\mathrm{x}}_{m})

となる。
(証明終了)

最後に

これで、2つの定義を心置きなく乱用できますね^^^^