「統計的機械学習」では、すでにYoutubeを公開しています。今回、「機械学習のためのカーネル」のテキストを使った15回の講義の録画を公開しました。2024年4月から8月にかけて、大阪大学の大学院生(と学部の一部)を対象にした「機械学習の数理」という15回の講義をYoutube「ぜうちゃねる(辛口データサイエンス)」で公開しています。各回のリンクは、こちらから見れます。

カーネルを数学のコアの部分(関数解析)から学ぶ講義は、世界広しといえどこの講義以外にはないと自負しています。カーネルの使い方だけを知ったとしても、意味がわからないままデータをパッケージにほうりこむことになり、不安になります。

関数解析は、線形代数のベクトルを関数に一般化したものと思えば、さほど苦にはならないと思います。そうは言っても、作用素や完備化などで違和感が生じるかもしれません。そこを乗り越えていただければ、カーネルトリックなど難しく感じない思います。

Youtubeをぜひお役立ていただきたいと思っています。ちゃんねる登録と、いいねをお願いできたらと思っています。

$(\Omega,{\cal F},P)$を確率空間とします。$\mathbb R$に値をとるいわゆる確率変数は、$\Omega\ni \omega \mapsto X(\omega)\in {\mathbb R}$が可測であることが定義になります。同様に、Hilbert空間$H$について、$\Omega\ni \omega \mapsto F(\omega)\in H$が可測であるとき、$F$をランダム要素とよびます。ランダムな関数という言い方をしてもよいでしょう。ランダム要素は、$g\in H$と$r>0$について、$\{\omega\in \Omega\mid \|F(\omega)-g\|_H<r\}$が$\cal F$の要素ということができます。ここでは、「${\cal F}$がランダム要素であることと、任意の$f\in H$について$\langle F,f\rangle_H$が確率変数であることが同値」であることを示します。

以下では、$h\in H$と$a>0$を用いて$\{g\in H\mid \|g-h\|_H<a\}$とかける集合によって生成される$\sigma$集合体を$\sigma$、$h\in H$と$a\in {\mathbb R}$を用いて$\{g\in H\mid \langle g,h\rangle_H<a\}$とかける集合によって生成される$\sigma$集合体を$\sigma’$と書くものとします。このとき、$\sigma=\sigma’$が成立します(T. Hsing and R. Eubank, 2015)。その証明は最後に行うとして、認めて議論をすすめます。

まず、各$f\in H$について、$\varphi: H\ni g\rightarrow \langle g,f\rangle_H\in {\mathbb R}$は連続($|g-g’|<\epsilon \Longrightarrow |\langle g,f\rangle-\langle g’,f\rangle|\leq |g-g’|\cdot|f|<|f|\epsilon$)なので、$\langle F,f\rangle$は可測になります。逆に各$f\in H$について$\langle F,f\rangle$が可測であれば、各$a\in {\mathbb R}$について
$$F^{-1}\{g\in H\mid \langle g, f\rangle <a\}=\{\omega\in\Omega \mid \langle F(\omega),f\rangle <a\}\in {\cal F}$$となり、$\sigma=\sigma’$から$F$は可測、すなわち$H$のランダム要素になります。

このことから$f: \Omega\times E\rightarrow {\mathbb R}$が可測であって各$\omega\in \Omega$で$f(\omega,\cdot)\in H$であれば、$\Omega\ni\omega \mapsto f(\omega,\cdot)$は$H$のランダム要素になります。実際、各$h\in H$で$\langle f(\omega,\cdot),h\rangle $が可測になるので、$f(\omega,\cdot)\in H$, $\omega\in \Omega$であれば、ランダム要素になります。

$\sigma=\sigma’$の証明:
各$f\in H$について、$\varphi: H\ni g\rightarrow \langle g,f\rangle_H\in {\mathbb R}$は連続なので、${\mathbb R}$の任意の開集合$B$の逆像$\varphi^{-1}(B)\subseteq H$も開集合となります。したがって、$\sigma’\subseteq \sigma$が成立します。次に、逆方向の包含関係を示します。$\{e_i\}$を$H$の正規直交基底として、
\begin{eqnarray*}
&&\{g\in H\mid \langle g, e_1\rangle^2+\langle g,e_2\rangle^2<\epsilon\}\\
&=&\cup_{q\in {\mathbb Q}}\left(\{g\in H\mid \langle g,e_1\rangle^2<q\}\cap \{g\in H\mid \langle g,e_2\rangle^2<\epsilon^2-q\}\right)\in \sigma’\\
&&\{g\in H\mid \sum_{j=1}{i-1}\langle g, e_j\rangle^2+\langle g,e_i\rangle^2<\epsilon\}\\
&=&\cup_{q\in {\mathbb Q}}\left(\{g\in H\mid \langle g,\sum_{j=1}^{i-1}e_j\rangle^2<q\}\cap \{g\in H\mid \langle g,e_i\rangle^2<\epsilon^2-q\}\right)\in \sigma’\end{eqnarray*}より、帰納法から以下が得られます。
$$\{g\in H\mid \|g|<\epsilon\}=\cup_{j=1}^\infty \left\{g\in H\mid \sum_{k=1}^j\langle g,e_k\rangle^2<\epsilon^2 \right\}\in \sigma’$$ したがって、任意の$\{g\in H\mid \|g-h\|<\epsilon\}\in \sigma$が以下のようにかけます。
$$\cup_{q\in {\mathbb Q}} \left(
\{g\in H\mid \|g\|^2<q\}\cup\{g\in H\mid 2\langle g,h\rangle>q-\epsilon^2+\|h\|^2
\}\right)$$ここで、$\{g\in H\mid \|g\|^2<q\}$はこれまでの議論から$\sigma’$の要素、第2項はもともと$\sigma’$ですから、全体として$\sigma’$の要素です。したがって、$\sigma\subseteq \sigma’$が成立します。

$E$を距離空間として、$k: E\times E\times E \rightarrow {\mathbb R}$として、$x,y\in E$の距離を$z$としたときに、\begin{equation}\label{eq6-11}
\varphi_\nu(z):=\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\frac{\sqrt{2\nu}z}{l}\right)^\nu K_\nu(\frac{\sqrt{2\nu}z}{l})
\end{equation}によって定義される正定値カーネル$k(x,y)=\varphi_\nu(z)$をMaternカーネルといいます。ただし、$\nu,l>0$はカーネルのパラメータ、$K_\nu$は第2種変形Bessel関数です。$$K_\nu(x):=\frac{\pi}{2}\frac{I_{-\nu}(x)-I_\nu(x)}{\sin(\nu x)}, \hspace{10mm}I_\nu(x):=\sum_{m=0}^\infty \frac{1}{m!\Gamma(m+\nu+1)}\left(\frac{x}{2}\right)^{2m+\nu}$$

Maternカーネルは$\nu$を切り上げした整数の回数だけ微分でき、$\nu\rightarrow\infty$でGaussカーネル$$\varphi_\infty(z)=\exp(-\frac{z^2}{2l^2})$$に収束します。

以下では、$p$を非負整数として$\nu=p+1/2$とかけるとき、
$$\varphi_\nu(z)=\exp\left(-\frac{\sqrt{2\nu }z}{l}\right)\frac{\Gamma(p+1)}{\Gamma(2p+1)}\sum_{i=0}^p \frac{(p+i)!}{i!(p-i)!}\left(\frac{\sqrt{8\nu}z}{l}\right)^{p-i}$$となることを示します。この公式はよく使われていますが、証明を載せている文献やネットの記事などが少ないので、メモのために書いておきました。

具体的には、以下の2式を示します。$$K_{\nu}(\frac{\sqrt{2\nu}z}{l})=\sqrt{\pi}\exp\left(-\frac{\sqrt{2\nu}z}{l}\right)\sum_{i=0}^p\frac{(p+i)!}{i!(p-i)!}\left(\frac{\sqrt{2\nu z}}{l}
\right)^{-\nu}2^{-\nu+p-i}$$ $$\frac{2^{1-\nu}}{\Gamma(\nu)}=\frac{1}{\sqrt{\pi}}\frac{\Gamma(p+1)}{\Gamma(2p+1)}2^\nu$$

まず、変形第2種Bessel関数は、一般に$$K_{p+1/2}(x)=\sqrt{\frac{\pi}{2x}}e^{-x}\sum_{i=0}^p\frac{(p+i)!}{i!(p-i)!}(\frac{1}{2x})^i$$とできます(Abramowitz and Stegun (1965). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. ISBN 0-486-61272-4.)。この公式に、$x=\sqrt{2\nu}z/l=\sqrt{2p+1}z/l$を代入すると、
\begin{eqnarray*}K_{\nu}(\frac{\sqrt{2\nu}}{l}z)&=&\sqrt{\frac{\pi}{2\sqrt{2\nu}z/l}}\exp\left(-\frac{\sqrt{2\nu}z}{l}\right)\sum_{i=0}^p\frac{(p+i)!}{i!(p-i)!}(\frac{1}{2\sqrt{2\nu}z/l})^i\\&=&\sqrt{\pi}\exp\left(-\frac{\sqrt{2\nu}z}{l}\right)\sum_{i=0}^p\frac{(p+i)!}{i!(p-i)!}\left(\frac{2\sqrt{2\nu z}}{l}
\right)^{-i-1/2}\end{eqnarray*}が成立します。

他方、Gamma関数の性質として、$x\Gamma(x)=\Gamma(x+1)$, $x>0 \hspace{3mm}$ や$\hspace{3mm} \Gamma(1/2)=\sqrt{\pi} \hspace{3mm}$などが成立しますが$$\Gamma(\frac{n}{2})\Gamma(\frac{n+1}{2})=\Gamma(n)2^{1-n}\sqrt{\pi},\hspace{3mm}n\geq 1$$なども成立します(一般の正の実数でも成立します)。$n=1$のとき両辺とも$\sqrt{\pi}$で一致し、$n=k$で等号が性質すれば、$n=k+1$で左辺は$$ \Gamma(\frac{k+1}{2})\Gamma(\frac{k+2}{2})=\Gamma(\frac{k+1}{2})\cdot \frac{k}{2}\Gamma(\frac{k}{2})=\frac{k}{2}\cdot \Gamma(k)2^{1-k}\sqrt{\pi}=\Gamma(k+1)2^{1-(k+1)}$$となり、$n=k+1$でも等号が成立することがわかります。これより、
$$\frac{2^{1-2p}}{\Gamma(p+1/2)}=\frac{1}{\sqrt{\pi}}\frac{\Gamma(p+1)}{\Gamma(2p+1)},\hspace{10mm} \frac{2^{1-\nu}}{\Gamma(\nu)}=\frac{1}{\sqrt{\pi}}\frac{\Gamma(p+1)}{\Gamma(2p+1)}2^\nu$$
が得られます。

確率空間を$(E,{\cal F},\mu)$とします。機械学習のためのカーネル第5章で、$k: E\times E\rightarrow {\mathbb R}$が可測であることを仮定しています。この意味について確認したいと思います。

任意の$\mathbb R$のBorel集合$B$について、$$\{\omega\in E\mid f(\omega)\in B\}\in {\cal F}$$であるとき、$f: E\rightarrow {\mathbb R}$は可測であるといいます。

$k: E\times E\rightarrow {\mathbb R}$が可測であるというのは、$\{(x,y)\in E\times E\mid k(x,y)\in B\}\in {\cal F}\times {\cal F}$を意味しています。ここで、${\cal F}\times {\cal F}$は1変数の可測集合の直積集合$C:=\{A\times B|A\in {\cal F},B\in {\cal F}\}$をすべて含む最小の$\sigma$集合体$\sigma(C)$になります。この仮定のもとで、以下のふたつが成立します。

• 各$x\in E$について、$E\ni y\mapsto k(x,y)\in {\mathbb R}$は可測
• $E\ni x\mapsto k(x,x)\in {\mathbb R}$は可測

いずれの証明でも、$k$の可測性から、$B$を任意の${\mathbb R}$のBorel集合としたときに、$A=k^{-1}(B) \in {\cal F}\times {\cal F}$であることを用います。

1つめは、$k_x(\cdot)=k(x,\cdot)$, $f_x: E\ni y\mapsto (x,y)\in E\times E$とおくと、$k_x=k\circ f_x$とできます。
このとき、$$k_x^{-1}(B)=f_x^{-1}\circ k^{-1}(B)=f_x^{-1}(A)$$となり、$A$の第2成分で$\cal F$の要素となります。したがって、$k_x$は可測になります。

２つめは、$g: E\ni x\rightarrow (x,x)$, $h: E\ni x\mapsto k(x,x)$として、$h=k\circ g$とできます。このとき、$$h^{-1}(B)=g^{-1}\circ k^{-1}(B)=g^{-1}(A)$$が得られます。このとき、$A$は同じ事象の対からなる事象となり、$h$は可測になります。

いろいろな教科書にあると思いますが、講義でよく用いるので、私の好きな書き方で証明してみました。「$H_0$を内積空間とする。Hilbert空間$H$があって、$H_0$は$H$の稠密な部分空間と等長的同型になる。このような$H$($H_0$の完備化)は同型を除いて一意に決まる。」。下記の証明では、実数全体$H={\mathbb R}$は有理数からなるCauchy列の集合の同値類(同じ値に収束するCauchy列どうしを同値とする)と読み替えることができます。

$H$とその内積を定義

体$K$上の内積空間$H_0$のCauchy列全体を$X$、$\{x_n\}_{n=1}^\infty,\{y_n\}_{n=1}^\infty\in X$の同値関係$\{x_n\}_{n=1}^\infty\sim\{y_n\}_{n=1}^\infty$を$\|x_n-y_n\|_{H_0}\rightarrow 0$ ($n\rightarrow \infty$)とし、その商を$H:=X/\sim$と書くものとします。そして、$\{x_n\}_{n=1}^\infty\in X$のクラスを$[\{x_n\}_{n=1}^\infty]\in H$と書くと、$\{x_n\}_{n=1}^\infty,\{y_n\}_{n=1}^\infty\in X$, $\alpha,\beta\in {K}$について、$[\{x_n\}_{n=1}^\infty],[\{y_n\}_{n=1}^\infty]\in H$, $\alpha x_n+\beta y_n\in H_0$, $$\alpha[\{x_n\}_{n=1}^\infty]+\beta[\{y_n\}_{n=1}^\infty]=[\{\alpha x_n+\beta y_n\}_{n=1}^\infty]\in H$$が成立し、$H$は線形空間となります(クラスの代表元によらないことはお確かめください)。また、$H$における内積を$$\langle [\{x_n\}_{n=1}^\infty], [\{y_n\}_{n=1}^\infty]\rangle_H:=\lim_{n\rightarrow\infty}\langle x_n, y_n\rangle_{H_0}$$で定義します。右辺の極限が存在し、その代表元によらないことは、以下のように示せます。$\{x_n\}_{n=1}^\infty\in X$に対して、$|\|x_n\|_{H_0}-\|x_m\|_{H_0}|\leq \|x_n-x_m\|_{H_0}$より$\{\|x_n\|_{H_0}\}$はCauchyで、したがって有界です。そして、Cauchy列$\{x_n\}_{n=1}^\infty,\{y_n\}_{n=1}^\infty \in X$に対して、\begin{eqnarray*}|\langle x_n,y_n\rangle_{H_0} – \langle x_m,y_m\rangle_{H_0}|&\leq& |\langle x_n-x_m,y_n\rangle_{H_0}| + |\langle x_m,y_n-y_m\rangle_{H_0}|\\&\leq& \|y_n\|\cdot \|x_n-x_m\|_{H_0} + \|x_m\|\cdot \|y_n-y_m\|_{H_0}\rightarrow 0\end{eqnarray*}が成立し、実数列$\langle x_n,y_n\rangle_{H_0}$は収束します。また、$\{x_n\}_{n=1}^\infty\sim\{x_n’\}_{n=1}^\infty$, $\{y_n\}_{n=1}^\infty\sim\{y_n’\}_{n=1}^\infty$のとき、
$$|\langle x_n,y_n\rangle_{H_0}-\langle x_n’,y_n’\rangle_{H_0}|\leq \|y_n’\|\cdot \|x_n’-x_n\|_{H_0} + \|x_n\|\cdot \|y_n-y_n’\|_{H_0}\rightarrow 0$$より、代表元のとりかたによらないことがわかります。

$H_0$は$H$で稠密

次に、$T: H_0\rightarrow H$を$x\mapsto [\{x,x,\ldots\}]$で定義すると、$\langle Tx,Tx\rangle_{H}=\langle x,x\rangle_{H_0}$を満たすので等長写像です。$T$の像は、$H$で稠密でもあります。実際、$\{x_n\}_{n=1}^\infty\in X$について、$Tx_l=[\{x_l,x_l,\ldots\}]$は、\begin{eqnarray*}\|Tx_l-[\{x_n\}_{n=1}^\infty]\|_H^2&=&
\langle Tx_l,Tx_l\rangle_{H}-2\langle Tx_l,[\{x_n\}_{n=1}^\infty]\rangle_{H}+\langle [\{x_n\}_{n=1}^\infty],[\{x_n\}_{n=1}^\infty]\rangle_{H}\\
&=&\langle x_l,x_l\rangle_{H_0}-2\lim_{n\rightarrow \infty}\langle x_l,x_n\rangle_{H_0}+\lim_{n\rightarrow \infty}\langle x_n,x_n\rangle_{H_0}=\lim_{n\rightarrow \infty}\|x_l-x_n\|^2_{H_0}
\end{eqnarray*}さらに、$\{x_n\}_{n=1}^\infty$はCauchyであるので、$l\rightarrow \infty$で右辺は0となります。すなわち、$x_1\leftrightarrow [\{x_1,\ldots\}]$, $x_2\leftrightarrow [\{x_2,\ldots\}]$, $\ldots$, が$[\{x_1,x_2,\ldots\}]$に収束します。$[\{x_n\}_{n=1}^\infty]$は$H$の任意の要素ですから、$H_0$は$H$の稠密な部分空間であることが示せました。

$H$は完備

最後に$H$の完備性を示します。$\{x_n^{(1)}\}_{n=1}^\infty, \{x_n^{(2)}\}_{n=1}^\infty,\ldots \in X$について、$[\{x_n^{(1)}\}_{n=1}^\infty], [\{x_n^{(2)}\}_{n=1}^\infty],\ldots \in H$がCauchyであると仮定します。内積の定義から、$$\|[\{x_n^{(l)}\}_{n=1}^\infty]-[\{x_n^{(m)}\}_{n=1}^\infty]\|_H=\lim_{n\rightarrow\infty}\|x_n^{(l)}-x_n^{(m)}\|_{H_0}$$であり、$[\{x_n^{(1)}\}_{n=1}^\infty], [\{x_n^{(2)}\}_{n=1}^\infty],\ldots$がCauchyであるので、任意の$\epsilon>0$について、ある正整数$N$があって、$$l,m,n\geq N \Longrightarrow \|x_n^{(l)}-x_n^{(m)}\|_{H_0}<\epsilon$$とできます。また、$$m,n\geq N \Longrightarrow \|x_n^{(n)}-x_m^{(m)}\|_{H_0}<\epsilon$$とできるので、$\{x_n^{(n)}\}_{n=1}^\infty$は$H_0$のCauchy列となります。特に、$\{x_n^{(n)}\}_{n=1}^\infty\in X$, $[\{x_n^{(n)}\}_{n=1}^\infty]\in H$が成立します。したがって、$$\|[\{x_n^{(n)}\}_{n=1}^\infty]-[\{x_n^{(l)}\}_{n=1}^\infty]\|_H^2=\lim_{n\rightarrow \infty}\|x_n^{(n)}-x_n^{(l)}\|^2_{H_0}$$において$l$を十分大きくとると、右辺を十分に小さくできます。したがって、$l\rightarrow \infty$で、$$H\ni [\{x_n^{(l)}\}_{n=1}^\infty]\rightarrow [\{x_n^{(n)}\}_{n=1}^\infty]\in H$$が示されました。

平滑化スプラインの問題は、
$$\sum_{i=1}^N\{y_i-f(x_i)\}^2+\lambda \int_0^1 \{f^{(q)}(x)\}^2dx \rightarrow {\rm min}$$を最小にする$f \in H:=W_q[0,1]$を求める問題として定式化できます。$q=2$の場合は、3次の自然なスプラインの範囲で最適解が存在することが知られています (「統計的機械学習の数理100問」の第6章)。また、Sobolev空間は$H=H_0+H_1$という直交するHilbert空間の直和で書けて、$P$を$H$から$H_1$への写像とすると、上記の問題は$$\sum_{i=1}^N\{y_i-f(x_i)\}^2+\lambda \|Pf\|^2dx \rightarrow {\rm min}$$とかけます。さらに、$H_0,H_1$もRKHSであって、その再生核を$k_0,k_1$と書くと、$H$の再生核は$k=k_0+k_1$となります。

まず、$M={\rm span}(k(x_1,\cdot),\ldots,k(x_N,\cdot))$、$M^\perp$をその直交補空間とし、$f=f_*+f_{\perp}$, $f_*\in M$, $f_{\perp}\in M^\perp$とかくと、$$\sum_{i=1}^N\{y_i-f_*(x_i)\}^2+\lambda \|Pf_*\|^2dx \rightarrow {\rm min}$$の最小化に帰着できます。というのも、$f(x_i)=\langle f,k(x_i,\cdot)\rangle_H=f_*(x_i)$とでき、
$$\|Pf\|^2= \|Pf_*+Pf_\perp\|^2=\|Pf_*|^2+\|Pf_\perp\|^2\geq \|Pf_*|^2$$ここで、$\langle Pf_*,Pf_\perp\rangle_H=0$を用いました。したがって、一般性を失うことなく、$f=\sum_{i=1}^N\beta_ik(x_i,\cdot)$とおいて、その最小化をはかればよいことになります。その場合、$$Pf=\sum_{i=1}^N\beta_iPk(x_i,\cdot)=\sum_{i=1}^N\beta_ik_1(x_i,\cdot)$$となるので、
$$\sum_{i=1}^N\{y_i-\sum_{j=1}^N\beta_j k(x_i,x_j)\}^2+\lambda \sum_{i=1}^N\sum_{j=1}^N\beta_i\beta_jk_1(x_i,x_j)$$
$K=(k(x_i,x_j))\in {\mathbb R}^{N\times N}$, $K_1=(k_1(x_i,x_j))\in {\mathbb R}^{N\times N}$, $y=[y_1,\ldots,y_N]^{\top}$とおけば、$\beta=[\beta_1,\ldots,\beta_N]^{\top}$は
$$\beta=(K^2+\lambda K_1)^{-1}Ky$$となります。

正定値対称行列$A\in {\mathbb R}^{N\times N}$を下三角行列$R\in {\mathbb R}^{N\times N}$を用いて$RR^\top$と書くことを、$A$をCholesky分解するといいます。以下の手順をふみます。
$$ A_{j,i}=\sum_{h=1}^NR_{j,h}R_{i,h}$$という関係式があるので、最初$R=O$(零行列)とし、第$i-1$列まで$R$の値が確定したとして、
1. $R_{i,i}=\sqrt{A_{i,i}-\sum_{h=1}^{i-1}R_{i,h}^2}$
2. $j=i+1,\ldots,N$に対して、$R_{j,i}=(A_{j,i}-\sum_{h=1}^{i-1}R_{j,h}R_{i,h})/R_{i,i}$
によって第$i$列の$i+1$行目以降を設定します。この操作を$i=1,\ldots,N$に対して行います。

そして、$R$の第$r+1$列以降を0とおいた台形の形をした$\tilde{R}$を用いて$A\approx \tilde{R}\tilde{R}^\top$というように(階数$r$に)近似することを$A$を不完全Cholesky分解するといいます。ただ、上記の手順を途中の$r$列目までで止めるだけでは芸がありません。近似の精度が良くなるように工夫します。

まず、最初に$B:=A$とし、上記の手順を以下のように修正します。$$B_{j,i}=\sum_{h=1}^NR_{j,h}R_{i,h}$$という関係式があるので、最初$R=O$とし、第$i-1$列まで$R$の値が確定したとして、$R_{k,k}=\sqrt{B_{k,k}-\sum_{h=1}^{i-1}R_{k,h}^2}$ ($i\leq k\leq N$)を最大にする$k$について、$B$の$i,k$行と$i,k$列、$R$の$i,k$行をいれかえます。その上で、$j=i+1,\ldots,N$に対して、$R_{j,i}=(B_{j,i}-\sum_{h=1}^{i-1}R_{j,h}R_{i,h})/R_{i,i}$によって第$i$列の$i+1$行目以降を設定します。また、大きさ$N$の単位行列で、$Q_i(i,k)=Q_{i}(k,i)=1$, $Q_i(i,i)=Q_{i}(k,k)=0$とした行列$Q_i$を設定します。そのようにして、$r$列目まですすめ、$P:=Q_{1}\cdots Q_r$を用いて以下のようにできます。$$A= PBP^\top\approx P\tilde{R}\tilde{R}^\top P^\top$$

このようにすると、誤差$B-\tilde{R} \tilde{R}^\top$をそのトレースで評価するとして、実行終了時の$\sum_{i=r+1}^NR_{i,i}^2$に等しくなります。実際、$r+1\leq i\leq N$について、$R^\top R$の$(i,i)$成分が$\sum_{j=1}^r R_{i,j}^2$となり、これと$B_{i,i}$との差が$R_{i,i}^2$となります。つまり、$R_{i,i}^2$の値の大きな$i$から順に選択していきます。事前に用意した$r$を用いて$r$列で止めてもよいし、$R_{i,i}^2$が事前に用意したある値にしてもよいと思います。また、上記の手順でいくと、$R^2_{i,i}$が単調減少になることが保証されます。実際、$R_{k,k}^2=B_{k,k}-\sum_{h=1}^{i-1}R_{k,h}^2$が第$i$列として選択されない($R^2_{i,i}より小さい)$と、$i+1$列目では、$R_{k,k}^2=B_{k,k}-\sum_{h=1}^{i}R_{k,h}^2$となって、さらに$R_{k,i}^2$だけ小さくなります。

行列$A\in {\mathbb R}^{m\times n}$を特異値分解して$A=U\Sigma V^\top$と書くものとします。ただし、 $U\in {\mathbb R}^{m\times n}$, $\Sigma \in {\mathbb R}^{n\times n}$, $V\in {\mathbb R}^{n\times n}$とし、$U^\top U=V^\top V=I$が成立し、$\Sigma$は対角行列でその各成分(特異値)は非負の値をとります。このとき、$$A^\top A= V\Sigma^2V^\top=(V \Sigma V^\top)^2$$とできます。また、正方行列$|A|:=V \Sigma V^\top$のトレースは、$\Sigma$の特異値$\lambda_1,\ldots,n$の和で常に非負になります。$|A|$の$(i,j)$成分は、$|A|_{i,j}=\sum_{k=1}^nv_{i,k}\lambda_{k}v_{j,k}$とかけるので、$|A|$のトレース(対角成分の和)は$$\sum_{i=1}^n |A|_{i,i}=\sum_{i=1}^n\sum_{k=1}^nv_{i,k}\lambda_{k}v_{j,i}=\sum_{k=1}^n \lambda_k \sum_{i=1}^n v_{i,k}^2=\sum_{i=1}^n \lambda_k$$となります。トレースというと$m=n$のときの$\sum_{i=1}^nA_{i,i}$をさすことが多いですが、関数解析では、$\sum_{i=1}^n |A|_{i,i}$のことをトレースノルムといいます。両者は非負定値対称のときに一致し、特異値$\lambda_1,\ldots,\lambda_n$は固有値になります。

同様の概念を一般の線型作用素にも適用できます。線型作用素の$T$について、$|T|:=\{T^*T\}^{1/2}$と書いて、$\sum_{i=1}^\infty\langle |T|e_i,e_i\rangle$と書きます。$\{\cdot\}^{1/2}$は作用素の平方根でと呼ばれるものです。トレースノルムがが有限のときその作用素はトレースクラスであるといいます。そして、自己共役のときに$\sum_{i=1}^\infty\langle Te_i,e_i\rangle$をトレースといい、さらに非負定値のときにトレース、トレースクラスは一致します。「機械学習のためのカーネル」の第2章の最後のトレース作用素の箇所では、自己共役かつ非負定値の線型作用素のみを扱っていて、両者は一致します。

Aronszajnというカーネルの数学者の結果です。「機械学習のためのカーネル 100問」の3.1節に掲載していますが、少しくだいてみました。テキストを最初から読んでいるか、関数解析を勉強したことのある人なら理解できると思います。

$H_1,H_2$をHilbert空間としたときに、その直積
$F:=H_1\times H_2$は、内積
$$
\langle (f_1,f_2),(g_1,g_2)\rangle_F := \langle f_1,g_1\rangle_{H_1}+\langle f_2,g_2\rangle_{H_2}, \hspace{5mm}
f_1,g_1\in H_1,\hspace{5mm} f_2,g_2\in H_2
$$のもとで、Hilbert空間になります。実際、$\|f_{1,n}-f_{1,m}\|_{H_1}$, $\| f_{2,n}- f_{2,m}\|_{H_2}$が
$$\hspace{3mm}\sqrt{\|f_{1,n}-f_{1,m}\|_{H_1}^2+\| f_{2,n}- f_{2,n}\|_{H_2}^2}=\|(f_{1,n},f_{2,n})-(f_{1,m},f_{2,m})\|_{F}
$$以下であることを用いると、以下が成立します。
$\{(f_{1,n},f_{2,n})\}$がCauchy $\Longrightarrow $ $\{f_{1,n}\}$, $\{f_{2,n}\}$がCauchy
$\Longrightarrow $ $\{f_{1,n}\}$, $\{f_{2,n}\}$がある$f_1\in H_1,f_2\in H_2$に収束
$\Longrightarrow $ $\|(f_{1,n},f_{2,n})-(f_{1},f_{2})\|_F= \sqrt{\|f_{1,n}-f_{1}\|^2+\|f_{2,n}-f_{2}\|^2}\rightarrow 0$
$\Longrightarrow $ $\{(f_{1,n},f_{2,n})\}$が$(f_1,f_2)\in F$に収束
すなわち、$H_1$,$H_2$が完備なら、$F$も完備です。

次に、$H_1,H_2$の直和
$H:=H_1 + H_2:=\{f_1+f_2|f_1\in H_1,f_2\in H_2\}$について考えます。$F$を写像$$u: F\ni (f_1,f_2)\mapsto f_1+f_2\in H$$の核$N:=\{(f_1,f_2)\in F|f_1+f_2=0\}$と、その直交補空間$N^\perp:=\{x\in F\mid \langle x,y\rangle=0, y\in N\}$に分解すると、$$N\cap N^\perp=\{(0,0)\}$$が成立します。ここで、$u$を$N^\perp$に制限した$v: N^\perp \rightarrow H$は単射$$v(f_1,f_2)=v(f_1′,f_2′)\Longrightarrow (f_1,f_2)=(f_1′,f_2′)$$になります。実際、$f_1+f_2=f_1’+f_2’$かつ$(f_1,f_2),(f_1′,f_2′)\in N^\perp$であれば、$$(f_1-f_1′,f_2-f_2′)\in N^\perp$$が成立します。他方、$f_1+f_2=v(f_1,f_2)=v(f_1′,f_2′)=f_1’+f_2’$は、$$(f_1-f_1′,f_2-f_2′)\in N$$を意味し、両者より、$(f_1-f_1′,f_2-f_2′)=(0,0)$が成立します。

$H=H_1+H_2$が以下の内積をもつとき、$H$は完備(Hilbert空間)となります。$$\langle f,g\rangle_H:=\langle v^{-1}(f),v^{-1}(g)\rangle_F\ ,\hspace{5mm}f,g\in H$$実際、$F$がHilbert空間で、$N^\perp$はその閉部分空間(テキスト命題20の1)ですから、$N^{\perp}$は完備となり、$\|f_n-f_m\|_H\rightarrow 0 \Longleftrightarrow \|v^{-1}(f_n-f_m)\|_F\rightarrow 0$
$\Longrightarrow$ $\|v^{-1}(f_n)-g\|_F\rightarrow 0$なる$g\in N^\perp$が存在$\Longrightarrow $ $\|f_n-v(g)\|_H\rightarrow 0$が成立します。

$H_1$, $H_2$が再生核$k_1,k_2$をもつとき、上記のように定義されたHilbert空間$H:=H_1 + H_2$は、$k_1+k_2$を核とするRKHSになります。この証明は(難しくありません)、テキストの付録を参照してください。

$E,E_1,\ldots,E_d$を集合、$R: E_1\times \cdots \times E_d\rightarrow E$とする。各$k_h: E_h\times E_h \rightarrow {\mathbb R}$, $h=1,\ldots,d$が正定値のとき、
$$k(x_i,x_j)=\sum_{R^{-1}(x_i)}\sum_{R^{-1}(x_j)}\prod_{h=1}^dk_h(x_{i,h},x_{j,h})$$
で定義される$k: E\times E\rightarrow {\mathbb R}$は正定値である。ただし、$R^{-1}(x_i)$は$R(x_{i,1},\ldots,x_{i,d})=x_i$なる$x_{i,1},\ldots,x_{i,d}\in E_1\times \cdots \times E_d$の集合とした。このステートメントの証明を、少し丁寧にやってみたい。

証明: \hspace{3mm}$x’=(x_1,\ldots,x_d)$, $y’=(y_1,\ldots,y_d)\in E_1\times \cdots\times E_d$

$k_h'(x’,y’):=k_h(x_h,y_h)$,\hspace{3mm}, $h=1,\ldots,d$\hspace{3mm} が正定値なので、
$$k'(x’,y’)=\prod_{h=1}^dk_h(x_h,y_h)$$
も正定値。したがって、正定値カーネル$k’$の特徴写像を$\varphi$として、
$$k(x,y)=\sum_{x’\in R^{-1}(x)}\sum_{y’\in R^{-1}(y)}k(x’,y’)=
\sum_{x’\in R^{-1}(x)}\sum_{y’\in R^{-1}(y)}
\langle \varphi(x’),\varphi(y’)\rangle_H
$$となり、$$\sum_{i=1}^n\sum_{j=1}^nz_iz_jk(x_i,x_j)=
\langle \sum_{i=1}^n
z_i\sum_{x_i’\in R^{-1}(x_i)}\varphi(x_i’),
\sum_{j=1}^n
z_j\sum_{x_j’\in R^{-1}(x_j)}\varphi(x_j’)\rangle_H
=
\|\sum_{i=1}^n
z_i\sum_{x_i’\in R^{-1}(x_i)}\varphi(x_i’)\|^2_H\geq 0
$$が任意の$n\geq 1$, $x_1,\ldots,x_n\in E$, $z_1,\ldots,z_n\in {\mathbb R}$について成立する。