Help us understand the problem. What is going on with this article?

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

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つの定義を心置きなく乱用できますね^^^^

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした