カーネル」カテゴリーアーカイブ

機械学習のためのカーネルの講義がYoutubeに

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

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

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

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

ランダム要素であることと同値な条件(「機械学習のためのカーネル」命題70(1))

(Ω,F,P)を確率空間とします。Rに値をとるいわゆる確率変数は、ΩωX(ω)Rが可測であることが定義になります。同様に、Hilbert空間Hについて、ΩωF(ω)Hが可測であるとき、Fをランダム要素とよびます。ランダムな関数という言い方をしてもよいでしょう。ランダム要素は、gHr>0について、{ωΩF(ω)gH<r}Fの要素ということができます。ここでは、「Fがランダム要素であることと、任意のfHについてF,fHが確率変数であることが同値」であることを示します。

以下では、hHa>0を用いて{gHghH<a}とかける集合によって生成されるσ集合体をσhHaRを用いて{gHg,hH<a}とかける集合によって生成されるσ集合体をσと書くものとします。このとき、σ=σが成立します(T. Hsing and R. Eubank, 2015)。その証明は最後に行うとして、認めて議論をすすめます。

まず、各fHについて、φ:Hgg,fHRは連続(|gg|<ϵ|g,fg,f||gg||f|<|f|ϵ)なので、F,fは可測になります。逆に各fHについてF,fが可測であれば、各aRについて
F1{gHg,f<a}={ωΩF(ω),f<a}Fとなり、σ=σからFは可測、すなわちHのランダム要素になります。

このことからf:Ω×ERが可測であって各ωΩf(ω,)Hであれば、Ωωf(ω,)Hのランダム要素になります。実際、各hHf(ω,),hが可測になるので、f(ω,)H, ωΩであれば、ランダム要素になります。

σ=σの証明:
fHについて、φ:Hgg,fHRは連続なので、Rの任意の開集合Bの逆像φ1(B)Hも開集合となります。したがって、σσが成立します。次に、逆方向の包含関係を示します。{ei}Hの正規直交基底として、
{gHg,e12+g,e22<ϵ}=qQ({gHg,e12<q}{gHg,e22<ϵ2q})σ{gHj=1i1g,ej2+g,ei2<ϵ}=qQ({gHg,j=1i1ej2<q}{gHg,ei2<ϵ2q})σより、帰納法から以下が得られます。
{gHg|<ϵ}=j=1{gHk=1jg,ek2<ϵ2}σ したがって、任意の{gHgh<ϵ}σが以下のようにかけます。
qQ({gHg2<q}{gH2g,h>qϵ2+h2})ここで、{gHg2<q}はこれまでの議論からσの要素、第2項はもともとσですから、全体としてσの要素です。したがって、σσが成立します。

Matern カーネルについて(機械学習のためのカーネル6.4節)

Eを距離空間として、k:E×E×ERとして、x,yEの距離をzとしたときに、φν(z):=21νΓ(ν)(2νzl)νKν(2νzl)によって定義される正定値カーネルk(x,y)=φν(z)をMaternカーネルといいます。ただし、ν,l>0はカーネルのパラメータ、Kνは第2種変形Bessel関数です。Kν(x):=π2Iν(x)Iν(x)sin(νx),Iν(x):=m=01m!Γ(m+ν+1)(x2)2m+ν

Maternカーネルはνを切り上げした整数の回数だけ微分でき、νでGaussカーネルφ(z)=exp(z22l2)に収束します。

以下では、pを非負整数としてν=p+1/2とかけるとき、
φν(z)=exp(2νzl)Γ(p+1)Γ(2p+1)i=0p(p+i)!i!(pi)!(8νzl)piとなることを示します。この公式はよく使われていますが、証明を載せている文献やネットの記事などが少ないので、メモのために書いておきました。

具体的には、以下の2式を示します。Kν(2νzl)=πexp(2νzl)i=0p(p+i)!i!(pi)!(2νzl)ν2ν+pi 21νΓ(ν)=1πΓ(p+1)Γ(2p+1)2ν

まず、変形第2種Bessel関数は、一般にKp+1/2(x)=π2xexi=0p(p+i)!i!(pi)!(12x)iとできます(Abramowitz and Stegun (1965). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical TablesISBN 0-486-61272-4.)。この公式に、x=2νz/l=2p+1z/lを代入すると、
Kν(2νlz)=π22νz/lexp(2νzl)i=0p(p+i)!i!(pi)!(122νz/l)i=πexp(2νzl)i=0p(p+i)!i!(pi)!(22νzl)i1/2が成立します。

他方、Gamma関数の性質として、xΓ(x)=Γ(x+1), x>0Γ(1/2)=πなどが成立しますがΓ(n2)Γ(n+12)=Γ(n)21nπ,n1なども成立します(一般の正の実数でも成立します)。n=1のとき両辺ともπで一致し、n=kで等号が性質すれば、n=k+1で左辺はΓ(k+12)Γ(k+22)=Γ(k+12)k2Γ(k2)=k2Γ(k)21kπ=Γ(k+1)21(k+1)となり、n=k+1でも等号が成立することがわかります。これより、
212pΓ(p+1/2)=1πΓ(p+1)Γ(2p+1),21νΓ(ν)=1πΓ(p+1)Γ(2p+1)2ν
が得られます。

カーネルが可測であること(機械学習のためのカーネル5.1節)

確率空間を(E,F,μ)とします。機械学習のためのカーネル第5章で、k:E×ERが可測であることを仮定しています。この意味について確認したいと思います。

任意のRのBorel集合Bについて、{ωEf(ω)B}Fであるとき、f:ERは可測であるといいます。

k:E×ERが可測であるというのは、{(x,y)E×Ek(x,y)B}F×Fを意味しています。ここで、F×Fは1変数の可測集合の直積集合C:={A×B|AF,BF}をすべて含む最小のσ集合体σ(C)になります。この仮定のもとで、以下のふたつが成立します。

  • xEについて、Eyk(x,y)Rは可測
  • Exk(x,x)Rは可測

いずれの証明でも、kの可測性から、Bを任意のRのBorel集合としたときに、A=k1(B)F×Fであることを用います。

1つめは、kx()=k(x,), fx:Ey(x,y)E×Eとおくと、kx=kfxとできます。
このとき、kx1(B)=fx1k1(B)=fx1(A)となり、Aの第2成分でFの要素となります。したがって、kxは可測になります。

2つめは、g:Ex(x,x), h:Exk(x,x)として、h=kgとできます。このとき、h1(B)=g1k1(B)=g1(A)が得られます。このとき、Aは同じ事象の対からなる事象となり、hは可測になります。

内積空間の完備化

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

Hとその内積を定義

K上の内積空間H0のCauchy列全体をX{xn}n=1,{yn}n=1Xの同値関係{xn}n=1{yn}n=1xnynH00 (n)とし、その商をH:=X/と書くものとします。そして、{xn}n=1Xのクラスを[{xn}n=1]Hと書くと、{xn}n=1,{yn}n=1X, α,βKについて、[{xn}n=1],[{yn}n=1]H, αxn+βynH0, α[{xn}n=1]+β[{yn}n=1]=[{αxn+βyn}n=1]Hが成立し、Hは線形空間となります(クラスの代表元によらないことはお確かめください)。また、Hにおける内積を[{xn}n=1],[{yn}n=1]H:=limnxn,ynH0で定義します。右辺の極限が存在し、その代表元によらないことは、以下のように示せます。{xn}n=1Xに対して、|xnH0xmH0|xnxmH0より{xnH0}はCauchyで、したがって有界です。そして、Cauchy列{xn}n=1,{yn}n=1Xに対して、|xn,ynH0xm,ymH0||xnxm,ynH0|+|xm,ynymH0|ynxnxmH0+xmynymH00が成立し、実数列xn,ynH0は収束します。また、{xn}n=1{xn}n=1, {yn}n=1{yn}n=1のとき、
|xn,ynH0xn,ynH0|ynxnxnH0+xnynynH00より、代表元のとりかたによらないことがわかります。

H0Hで稠密

次に、T:H0Hx[{x,x,}]で定義すると、Tx,TxH=x,xH0を満たすので等長写像です。Tの像は、Hで稠密でもあります。実際、{xn}n=1Xについて、Txl=[{xl,xl,}]は、Txl[{xn}n=1]H2=Txl,TxlH2Txl,[{xn}n=1]H+[{xn}n=1],[{xn}n=1]H=xl,xlH02limnxl,xnH0+limnxn,xnH0=limnxlxnH02さらに、{xn}n=1はCauchyであるので、lで右辺は0となります。すなわち、x1[{x1,}], x2[{x2,}], , が[{x1,x2,}]に収束します。[{xn}n=1]Hの任意の要素ですから、H0Hの稠密な部分空間であることが示せました。

Hは完備

最後にHの完備性を示します。{xn(1)}n=1,{xn(2)}n=1,Xについて、[{xn(1)}n=1],[{xn(2)}n=1],HがCauchyであると仮定します。内積の定義から、[{xn(l)}n=1][{xn(m)}n=1]H=limnxn(l)xn(m)H0であり、[{xn(1)}n=1],[{xn(2)}n=1],がCauchyであるので、任意のϵ>0について、ある正整数Nがあって、l,m,nNxn(l)xn(m)H0<ϵとできます。また、m,nNxn(n)xm(m)H0<ϵとできるので、{xn(n)}n=1H0のCauchy列となります。特に、{xn(n)}n=1X, [{xn(n)}n=1]Hが成立します。したがって、[{xn(n)}n=1][{xn(l)}n=1]H2=limnxn(n)xn(l)H02においてlを十分大きくとると、右辺を十分に小さくできます。したがって、lで、H[{xn(l)}n=1][{xn(n)}n=1]Hが示されました。

Sobolev空間での平滑化スプラインの一般化(機械学習のためのカーネル4.4節)

平滑化スプラインの問題は、
i=1N{yif(xi)}2+λ01{f(q)(x)}2dxminを最小にするfH:=Wq[0,1]を求める問題として定式化できます。q=2の場合は、3次の自然なスプラインの範囲で最適解が存在することが知られています (「統計的機械学習の数理100問」の第6章)。また、Sobolev空間はH=H0+H1という直交するHilbert空間の直和で書けて、PHからH1への写像とすると、上記の問題はi=1N{yif(xi)}2+λPf2dxminとかけます。さらに、H0,H1もRKHSであって、その再生核をk0,k1と書くと、Hの再生核はk=k0+k1となります。

まず、M=span(k(x1,),,k(xN,))Mをその直交補空間とし、f=f+f, fM, fMとかくと、i=1N{yif(xi)}2+λPf2dxminの最小化に帰着できます。というのも、f(xi)=f,k(xi,)H=f(xi)とでき、
Pf2=Pf+Pf2=Pf|2+Pf2Pf|2ここで、Pf,PfH=0を用いました。したがって、一般性を失うことなく、f=i=1Nβik(xi,)とおいて、その最小化をはかればよいことになります。その場合、Pf=i=1NβiPk(xi,)=i=1Nβik1(xi,)となるので、
i=1N{yij=1Nβjk(xi,xj)}2+λi=1Nj=1Nβiβjk1(xi,xj)
K=(k(xi,xj))RN×N, K1=(k1(xi,xj))RN×N, y=[y1,,yN]とおけば、β=[β1,,βN]
β=(K2+λK1)1Kyとなります。

不完全Cholesky分解 (機械学習のためのカーネル 4.7節)

正定値対称行列ARN×Nを下三角行列RRN×Nを用いてRRと書くことを、AをCholesky分解するといいます。以下の手順をふみます。
Aj,i=h=1NRj,hRi,hという関係式があるので、最初R=O(零行列)とし、第i1列までRの値が確定したとして、
1. Ri,i=Ai,ih=1i1Ri,h2
2. j=i+1,,Nに対して、Rj,i=(Aj,ih=1i1Rj,hRi,h)/Ri,i
によって第i列のi+1行目以降を設定します。この操作をi=1,,Nに対して行います。

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

まず、最初にB:=Aとし、上記の手順を以下のように修正します。Bj,i=h=1NRj,hRi,hという関係式があるので、最初R=Oとし、第i1列までRの値が確定したとして、Rk,k=Bk,kh=1i1Rk,h2 (ikN)を最大にするkについて、Bi,k行とi,k列、Ri,k行をいれかえます。その上で、j=i+1,,Nに対して、Rj,i=(Bj,ih=1i1Rj,hRi,h)/Ri,iによって第i列のi+1行目以降を設定します。また、大きさNの単位行列で、Qi(i,k)=Qi(k,i)=1, Qi(i,i)=Qi(k,k)=0とした行列Qiを設定します。そのようにして、r列目まですすめ、P:=Q1Qrを用いて以下のようにできます。A=PBPPR~R~P

このようにすると、誤差BR~R~をそのトレースで評価するとして、実行終了時のi=r+1NRi,i2に等しくなります。実際、r+1iNについて、RR(i,i)成分がj=1rRi,j2となり、これとBi,iとの差がRi,i2となります。つまり、Ri,i2の値の大きなiから順に選択していきます。事前に用意したrを用いてr列で止めてもよいし、Ri,i2が事前に用意したある値にしてもよいと思います。また、上記の手順でいくと、Ri,i2が単調減少になることが保証されます。実際、Rk,k2=Bk,kh=1i1Rk,h2が第i列として選択されない(Ri,i2)と、i+1列目では、Rk,k2=Bk,kh=1iRk,h2となって、さらにRk,i2だけ小さくなります。

トレースクラスの作用素

行列ARm×nを特異値分解してA=UΣVと書くものとします。ただし、 URm×n, ΣRn×n, VRn×nとし、UU=VV=Iが成立し、Σは対角行列でその各成分(特異値)は非負の値をとります。このとき、AA=VΣ2V=(VΣV)2とできます。また、正方行列|A|:=VΣVのトレースは、Σの特異値λ1,,nの和で常に非負になります。|A|(i,j)成分は、|A|i,j=k=1nvi,kλkvj,kとかけるので、|A|のトレース(対角成分の和)はi=1n|A|i,i=i=1nk=1nvi,kλkvj,i=k=1nλki=1nvi,k2=i=1nλkとなります。トレースというとm=nのときのi=1nAi,iをさすことが多いですが、関数解析では、i=1n|A|i,iのことをトレースノルムといいます。両者は非負定値対称のときに一致し、特異値λ1,,λnは固有値になります。

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

正定値カーネルk1,k2のRKHSがH1,H2のときのk1+k2のRKHS

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

H1,H2をHilbert空間としたときに、その直積
F:=H1×H2は、内積
(f1,f2),(g1,g2)F:=f1,g1H1+f2,g2H2,f1,g1H1,f2,g2H2のもとで、Hilbert空間になります。実際、f1,nf1,mH1, f2,nf2,mH2
f1,nf1,mH12+f2,nf2,nH22=(f1,n,f2,n)(f1,m,f2,m)F以下であることを用いると、以下が成立します。
{(f1,n,f2,n)}がCauchy {f1,n}, {f2,n}がCauchy
{f1,n}, {f2,n}があるf1H1,f2H2に収束
(f1,n,f2,n)(f1,f2)F=f1,nf12+f2,nf220
{(f1,n,f2,n)}(f1,f2)Fに収束
すなわち、H1,H2が完備なら、Fも完備です。

次に、H1,H2の直和
H:=H1+H2:={f1+f2|f1H1,f2H2}について考えます。Fを写像u:F(f1,f2)f1+f2Hの核N:={(f1,f2)F|f1+f2=0}と、その直交補空間N:={xFx,y=0,yN}に分解すると、NN={(0,0)}が成立します。ここで、uNに制限したv:NHは単射v(f1,f2)=v(f1,f2)(f1,f2)=(f1,f2)になります。実際、f1+f2=f1+f2かつ(f1,f2),(f1,f2)Nであれば、(f1f1,f2f2)Nが成立します。他方、f1+f2=v(f1,f2)=v(f1,f2)=f1+f2は、(f1f1,f2f2)Nを意味し、両者より、(f1f1,f2f2)=(0,0)が成立します。

H=H1+H2が以下の内積をもつとき、Hは完備(Hilbert空間)となります。f,gH:=v1(f),v1(g)F ,f,gH実際、FがHilbert空間で、Nはその閉部分空間(テキスト命題20の1)ですから、Nは完備となり、fnfmH0v1(fnfm)F0
v1(fn)gF0なるgNが存在 fnv(g)H0が成立します。

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

たたみ込みカーネルは正定値(カーネル1.6節)

E,E1,,Edを集合、R:E1××EdEとする。各kh:Eh×EhR, h=1,,dが正定値のとき、
k(xi,xj)=R1(xi)R1(xj)h=1dkh(xi,h,xj,h)
で定義されるk:E×ERは正定値である。ただし、R1(xi)R(xi,1,,xi,d)=xiなるxi,1,,xi,dE1××Edの集合とした。このステートメントの証明を、少し丁寧にやってみたい。

証明: \hspace{3mm}x=(x1,,xd), y=(y1,,yd)E1××Ed

kh(x,y):=kh(xh,yh),\hspace{3mm}, h=1,,d\hspace{3mm} が正定値なので、
k(x,y)=h=1dkh(xh,yh)
も正定値。したがって、正定値カーネルkの特徴写像をφとして、
k(x,y)=xR1(x)yR1(y)k(x,y)=xR1(x)yR1(y)φ(x),φ(y)Hとなり、i=1nj=1nzizjk(xi,xj)=i=1nzixiR1(xi)φ(xi),j=1nzjxjR1(xj)φ(xj)H=i=1nzixiR1(xi)φ(xi)H20が任意のn1, x1,,xnE, z1,,znRについて成立する。