PRML第6章の2つのカーネルの定義の等価性を証明する

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})$をカーネル関数という、というものです。

```math
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})$が式(*)を満たす&hArr; 上で定義したグラム行列$K$が半正定値行列である

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

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

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

## &rArr;の証明
まずは、

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

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

```math
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}$は

```math
\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$が半正定値行列である。
(証明終了)

## &lArr;の証明
次に、

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

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

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

と分解できることを使用します。(証明は[こちら](https://risalc.info/src/positive-semi-definite-decomposition.html)のページを参考にしてください。)
(証明開始)
この補題を利用すると、半正定値行列$K$は適当な正方行列$Q$を用いて、

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

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

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

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

```math
B = PQ
```

と定義したら、$K$は

```math
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}$は

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

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

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

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

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

となる。
(証明終了)

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