Ch.6 「カーネル法」の章末問題の解答例　パターン認識と機械学習 6.1〜6.15

当記事は「パターン認識と機械学習」の読解サポートにあたってChapter.$6$の「カーネル法」の章末問題の解説について行います。
基本的には書籍の購入者向けの解説なので、まだ入手されていない方は下記より入手をご検討ください。また、解説はあくまでサイト運営者が独自に作成したものであり、書籍の公式ページではないことにご注意ください。

・参考
パターン認識と機械学習 解答まとめ
https://www.hello-statisticians.com/answer_textbook#prml

解答まとめ

問題$6.1$

問題$6.2$

問題$6.3$

問題$6.4$

$$
\large
\begin{align}
A = \left( \begin{array}{cc} a & b \\ c & d \end{array} \right)
\end{align}
$$

上記のように定めた行列$A$が「固有値が正」かつ「少なくとも$1$つの要素が負」である条件を調べ、条件に基づいて例示を行う。固有値を$\lambda$とおくと、下記が成立する。
$$
\large
\begin{align}
\det(A – \lambda I) &= 0 \\
\left| \begin{array}{cc} a – \lambda & b \\ c & d – \lambda \end{array} \right| &= 0 \\
(a – \lambda)(d – \lambda) – bc &= 0 \\
\lambda^2 – (a+b) \lambda + ad – bc &= 0 \quad (1)
\end{align}
$$

ここで$(1)$式を$\lambda$に関して解くと二次方程式の解の公式より下記が得られる。
$$
\large
\begin{align}
\lambda = \frac{(a+d) \pm \sqrt{(a+d)^2 – 4(ad-bc)}}{2}
\end{align}
$$

ここで下記の二つの条件が成立すれば全ての固有値が正の値になる。
$$
\large
\begin{align}
a+d > \sqrt{(a+d)^2 – 4(ad-bc)} \quad (2) \\
(a+d)^2 – 4(ad-bc) > 0 \quad (3)
\end{align}
$$

$(2)$式は全ての固有値が正であることに対応し、$(3)$式は方程式が実数解を持つことに対応する。以下、$(2)$式の変形を行い、解釈可能な形に変形する。

・$(2)$式に関する変形
$$
\large
\begin{align}
a+d &> \sqrt{(a+d)^2 – 4(ad-bc)} \quad (2) \\
(a+d)^2 &> (a+d)^2 – 4(ad-bc) \\
ad &> bc \quad (2)’
\end{align}
$$

よって、$(2)’$式に基づいて行列を例示し、$(3)$式が成立するかを確認すれば良い。下記に一例を挙げる。
$$
\large
\begin{align}
A = \left( \begin{array}{cc} 2 & -1 \\ -1 & 2 \end{array} \right)
\end{align}
$$

・考察
$(2)’$式が成立する一方で$(3)$式が成立しない場合を以下に例示する。
$$
\large
\begin{align}
A’ = \left( \begin{array}{cc} 2 & -1 \\ 1 & 2 \end{array} \right)
\end{align}
$$

上記の行列$A’$に関する方程式$\det(A – \lambda I) = 0$は実数解を持たない。このように単に$ad > bc$に基づいて値を設定すると実数解を持たない場合があるので注意が必要である。

問題$6.5$

・$(6.13)$式の証明
$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるので、$k_{1}(\mathbf{x},\mathbf{x}’)$は下記のように表せる。
$$
\large
\begin{align}
k_{1}(\mathbf{x},\mathbf{x}’) = \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’)
\end{align}
$$

このとき$ck_{1}(\mathbf{x},\mathbf{x}’)$は下記のように変形できる。
$$
\large
\begin{align}
ck_{1}(\mathbf{x},\mathbf{x}’) &= c \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’) \\
&= (\sqrt{c}\boldsymbol{\phi}(\mathbf{x}))^\mathrm{T} (\sqrt{c}\boldsymbol{\phi}(\mathbf{x}’)) \\
&= \mathbf{u}(\mathbf{x})^\mathrm{T}\mathbf{u}(\mathbf{x}’)
\end{align}
$$

途中式で$\mathbf{u}(\mathbf{x})=\sqrt{c}\boldsymbol{\phi}(\mathbf{x}’)$のようにおいた。上記より$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき、$k(\mathbf{x},\mathbf{x}’)=ck_{1}(\mathbf{x},\mathbf{x}’)$も有効なカーネルであることが示される。

・$(6.14)$式の証明
$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるので、$k_{1}(\mathbf{x},\mathbf{x}’)$は下記のように表せる。
$$
\large
\begin{align}
k_{1}(\mathbf{x},\mathbf{x}’) = \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’)
\end{align}
$$

このとき$f(\mathbf{x})k_{1}(\mathbf{x},\mathbf{x}’)f(\mathbf{x}’)$は下記のように変形できる。
$$
\large
\begin{align}
f(\mathbf{x})k_{1}(\mathbf{x},\mathbf{x}’)f(\mathbf{x}’) &= f(\mathbf{x}) \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’) f(\mathbf{x}’) \\
&= (f(\mathbf{x})\boldsymbol{\phi}(\mathbf{x}))^\mathrm{T} (f(\mathbf{x}’)\boldsymbol{\phi}(\mathbf{x}’)) \\
&= \mathbf{v}(\mathbf{x})^\mathrm{T}\mathbf{v}(\mathbf{x}’)
\end{align}
$$

途中式で$\mathbf{v}(\mathbf{x})=f(\mathbf{x})\boldsymbol{\phi}(\mathbf{x}’)$のようにおいた。上記より$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき、$k(\mathbf{x},\mathbf{x}’)=ck_{1}(\mathbf{x},\mathbf{x}’)$も有効なカーネルであることが示される。

問題$6.6$

・$(6.15)$式の証明
$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき、$k_{1}(\mathbf{x},\mathbf{x}’)^{n}$が有効なカーネルであることが示せれば$(6.13)$式と$(6.17)$式より多項式関数$q(k_{1}(\mathbf{x},\mathbf{x}’))$が有効なカーネルであることが示せる。

ここで$k_{1}(\mathbf{x},\mathbf{x}’)^{n}$が有効なカーネルであることは$(6.18)$式より帰納法的に示すことができる。よって、$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき多項式関数$q(k_{1}(\mathbf{x},\mathbf{x}’)^{n})$も有効なカーネルである。

・$(6.16)$式の証明
マクローリン展開より$\exp(k_{1}(\mathbf{x},\mathbf{x}’))$は下記のように変形できる。
$$
\large
\begin{align}
\exp(k_{1}(\mathbf{x},\mathbf{x}’)) = \sum_{n=0}^{\infty} \frac{1}{n!} k_{1}(\mathbf{x},\mathbf{x}’)^{n}
\end{align}
$$

上記より、$\exp(k_{1}(\mathbf{x},\mathbf{x}’))=q(k_{1}(\mathbf{x},\mathbf{x}’))$と表すことができ、$(6.15)$式より$k_{1}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき、$\exp(k_{1}(\mathbf{x},\mathbf{x}’))$も有効なカーネルであると考えられる。

問題$6.7$

・$(6.17)$式の証明
$k_{1}(\mathbf{x},\mathbf{x}’)$と$k_{2}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるので、ベクトル集合${\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_n}$に対してこれらに対応するグラム行列を$\mathbf{K}_1, \mathbf{K}_2$とおくと、$\mathbf{K}_1, \mathbf{K}_2$は半正定値行列である。

$\mathbf{K}_1, \mathbf{K}_2$がそれぞれ半正定値行列であることは任意のベクトル$\mathbf{a}$に関して下記が成立することに対応する。
$$
\large
\begin{align}
\mathbf{a}^\mathrm{T}\mathbf{K}_{1}\mathbf{a} \geq 0, \quad \mathbf{a}^\mathrm{T}\mathbf{K}_{2}\mathbf{a} \geq 0
\end{align}
$$

上記より$\mathbf{a}^\mathrm{T}(\mathbf{K}_{1}+\mathbf{K}_{2})\mathbf{a}$に関して下記が成立する。
$$
\large
\begin{align}
\mathbf{a}^\mathrm{T}(\mathbf{K}_{1}+\mathbf{K}_{2})\mathbf{a} = \mathbf{a}^\mathrm{T}\mathbf{K}_{1}\mathbf{a} + \mathbf{a}^\mathrm{T}\mathbf{K}_{2}\mathbf{a} \geq 0
\end{align}
$$

上記より$k_{1}(\mathbf{x},\mathbf{x}’)$と$k_{2}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき$k_{1}(\mathbf{x},\mathbf{x}’)+k_{2}(\mathbf{x},\mathbf{x}’)$も有効なカーネルであることを示すことができる。

・$(6.18)$式の証明
$k_{1}(\mathbf{x},\mathbf{x}’)$と$k_{2}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるので、ベクトル$\mathbf{x},\mathbf{x}’$を用いて下記のようにそれぞれ表すことができる。
$$
\large
\begin{align}
k_{1}(\mathbf{x},\mathbf{x}’) &= \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’) \\
k_{2}(\mathbf{x},\mathbf{x}’) &= \boldsymbol{\psi}(\mathbf{x})^\mathrm{T}\boldsymbol{\psi}(\mathbf{x}’)
\end{align}
$$

このとき$k_{1}(\mathbf{x},\mathbf{x}’)k_{2}(\mathbf{x},\mathbf{x}’)$は下記のように計算を行える。
$$
\large
\begin{align}
k_{1}(\mathbf{x},\mathbf{x}’)k_{2}(\mathbf{x},\mathbf{x}’) &= \boldsymbol{\phi}(\mathbf{x})^\mathrm{T}\boldsymbol{\phi}(\mathbf{x}’)\boldsymbol{\psi}(\mathbf{x})^\mathrm{T}\boldsymbol{\psi}(\mathbf{x}’) \\
&= \sum_{m=1}^{M} \phi_{m}(\mathbf{x})\phi_{m}(\mathbf{x}’) \sum_{n=1}^{N} \psi_{n}(\mathbf{x})\phi_{n}(\mathbf{x}’) \\
&= \sum_{m=1}^{M} \sum_{n=1}^{N} \phi_{m}(\mathbf{x}) \phi_{m}(\mathbf{x}’) \psi_{n}(\mathbf{x}) \psi_{n}(\mathbf{x}’) \\
&= \sum_{k=1}^{MN} \phi_{((k-1) \oslash N)+1}(\mathbf{x}) \psi_{((k-1) \odot N)+1}(\mathbf{x}) \phi_{((k-1) \oslash N)+1}(\mathbf{x}’) \psi_{((k-1) \odot N)+1}(\mathbf{x}’) \\
&= \sum_{k=1}^{K} \varphi_{k}(\mathbf{x}) \varphi_{k}(\mathbf{x}’) \\
&= \boldsymbol{\varphi}_{k}(\mathbf{x})^{\mathrm{T}} \boldsymbol{\varphi}_{k}(\mathbf{x}’) \\
K &= MN, \quad \varphi_{k}(\mathbf{x}) = \phi_{((k-1) \oslash N)+1}(\mathbf{x}) \psi_{((k-1) \odot N)+1}(\mathbf{x})
\end{align}
$$

ここで$A \oslash N$は$A$を$N$で割った商、$A \odot N$は$A$を$N$で割った余りにそれぞれ対応する。

上記より$k_{1}(\mathbf{x},\mathbf{x}’)$と$k_{2}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであるとき、$k(\mathbf{x},\mathbf{x}’)=k_{1}(\mathbf{x},\mathbf{x}’)k_{2}(\mathbf{x},\mathbf{x}’)$も有効なカーネルであることが示される。

問題$6.8$

・$(6.19)$式の証明
$k_{3}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであることより、$k_{3}(\boldsymbol{\phi}(\mathbf{x}),\boldsymbol{\phi}(\mathbf{x}’))$は下記のように変形できる。
$$
\large
\begin{align}
k_{3}(\boldsymbol{\phi}(\mathbf{x}),\boldsymbol{\phi}(\mathbf{x}’)) &= \boldsymbol{\psi}(\boldsymbol{\phi}(\mathbf{x}))^\mathrm{T} \boldsymbol{\psi}(\boldsymbol{\phi}(\mathbf{x}’)) \\
&= \mathbf{u}(\mathbf{x})^\mathrm{T} \mathbf{u}(\mathbf{x}’) \\
\mathbf{u}(\mathbf{x}) &= \boldsymbol{\psi}(\boldsymbol{\phi}(\mathbf{x}))
\end{align}
$$

上記より、$k_{3}(\mathbf{x},\mathbf{x}’)$が有効なカーネルであれば、$k(\mathbf{x},\mathbf{x}’) = k_{3}(\boldsymbol{\phi}(\mathbf{x}),\boldsymbol{\phi}(\mathbf{x}’))$も有効なカーネルであることが示される。

・$(6.20)$式の証明
$\mathbf{A}$に対して「エッカート・ヤング分解」を行い、$\mathbf{A}=\mathbf{Z}\mathbf{Z}^{\mathrm{T}}$が得られたと考える。このとき、$\mathbf{x}^{\mathrm{T}}\mathbf{A}\mathbf{x}’$は下記のように変形できる。
$$
\large
\begin{align}
\mathbf{x}^{\mathrm{T}}\mathbf{A}\mathbf{x}’ &= \mathbf{x}^{\mathrm{T}}\mathbf{Z}\mathbf{Z}^{\mathrm{T}}\mathbf{x}’ \\
&= (\mathbf{Z}^{\mathrm{T}} \mathbf{x})^{\mathrm{T}} (\mathbf{Z}^{\mathrm{T}}\mathbf{x}’) \\
&= \boldsymbol{\phi}(\mathbf{x})^{\mathrm{T}} \boldsymbol{\phi}(\mathbf{x}’)
\end{align}
$$

上記より$k(\mathbf{x},\mathbf{x}’) = \mathbf{x}^{\mathrm{T}}\mathbf{A}\mathbf{x}’$が有効なカーネルであることが示される。

問題$6.9$

問題$6.10$

問題$6.11$

$$
\large
\begin{align}
k(\mathbf{x},\mathbf{x}’) &= \exp \left( -\frac{||\mathbf{x}-\mathbf{x}’||^2}{2 \sigma^2} \right) \quad (6.23) \\
&= \exp \left( -\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}+(\mathbf{x}’)^{\mathrm{T}}\mathbf{x}’-2\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{2 \sigma^2} \right) \\
&= \exp \left( -\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}}{2 \sigma^2} \right) \exp \left( \frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2} \right) \exp \left( -\frac{(\mathbf{x}’)^{\mathrm{T}}\mathbf{x}’}{2 \sigma^2} \right) \quad (6.25)
\end{align}
$$

ここで$\displaystyle \frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2}$に関して下記が成立する。
$$
\large
\begin{align}
\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2} &= \left( \frac{1}{\sigma}\mathbf{x}^{\mathrm{T}} \right) \left( \frac{1}{\sigma} \mathbf{x}’ \right) \\
&= v(\mathbf{x})^{\mathrm{T}} v(\mathbf{x}’) \\
v(\mathbf{x}) &= \frac{1}{\sigma}\mathbf{x}
\end{align}
$$

上記より$\displaystyle \frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2}$はカーネル関数$\displaystyle k_1(\mathbf{x},\mathbf{x}’)=\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2}$のように表せる。このとき、$\displaystyle \exp \left( \frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2} \right) = \exp ( k_1(\mathbf{x},\mathbf{x}’) )$に関して、下記のようにマクローリン展開を行うことができる。
$$
\large
\begin{align}
\exp ( k_1(\mathbf{x},\mathbf{x}’) ) = \sum_{n=0}^{\infty} \frac{1}{n!} k_1(\mathbf{x},\mathbf{x}’)^{n}
\end{align}
$$

上記では無限次元の特徴ベクトルを考えているが、$(6.15), (6.16)$式より$\exp(k_1(\mathbf{x},\mathbf{x}’))$はカーネル関数であることが示されるので$k_2(\mathbf{x},\mathbf{x}’)=\exp(k_1(\mathbf{x},\mathbf{x}’))$とおくと、$k_2(\mathbf{x},\mathbf{x}’)$は無限次元の特徴量の内積の形式で表すことができる。また、ここで$\displaystyle f(\mathbf{x}) = \exp \left( -\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}}{2 \sigma^2} \right)$とおくと、$(6.25)$式は下記のように変形できる。
$$
\large
\begin{align}
k(\mathbf{x},\mathbf{x}’) &= \exp \left( -\frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}}{2 \sigma^2} \right) \exp \left( \frac{\mathbf{x}^{\mathrm{T}}\mathbf{x}’}{\sigma^2} \right) \exp \left( -\frac{(\mathbf{x}’)^{\mathrm{T}}\mathbf{x}’}{2 \sigma^2} \right) \quad (6.25) \\
&= f(\mathbf{x}) k_2(\mathbf{x},\mathbf{x}’) f(\mathbf{x}’)
\end{align}
$$

上記に対し、$(6.14)$式を適用することで$(6.25)$式が有効なカーネル関数であることが示せる。よって、$(6.23)$式で表されるガウシアンカーネルは無限次元の特徴量を持つ有効なカーネル関数であると考えられる。

問題$6.12$

問題$6.13$

問題$6.14$

問題$6.15$

グラム行列を$K$とおくと、$2$次元正方行列の$K$は下記のように定められる。
$$
\large
\begin{align}
K = \left( \begin{array}{cc} k(x_1,x_1) & k(x_1,x_2) \\ k(x_2,x_1) & k(x_2,x_2) \end{array} \right)
\end{align}
$$

上記に対して$\det K \geq 0$かつ$k(x_1,x_2)=k(x_2,x_1)$より下記が成立する。
$$
\large
\begin{align}
\det K &= k(x_1,x_1)k(x_2,x_2) – k(x_1,x_2)k(x_2,x_1) \geq 0 \\
k(x_1,x_2)k(x_2,x_1) & \leq k(x_1,x_1)k(x_2,x_2) \\
k(x_1,x_2)^2 & \leq k(x_1,x_1)k(x_2,x_2)
\end{align}
$$