読者です 読者をやめる 読者になる 読者になる

Obey Your MATHEMATICS.

機械学習関連の純粋数学や実験など

Reproducing Kernel Hilbert Spaceの数理とMercerの定理

こんにちは。


この記事は、皆さんサポートベクトルマシン(SVM)でお馴染みであろう

Reproducing Kernel Hilbert Space (再生核ヒルベルト空間) : (以下RKHS)

に関するただの個人的なメモです。


動機は、非常に重用なMercerの定理の証明がウェブ上で簡単に見つからなかったために色々調べてたものを整理する事です。

個人的に、RKHS周りの数理を整理しておきたかった、と言うのもあります。

※一応、ヒルベルト空間とその有界作用素の定義ぐらい知っていれば読めるようにリファレンスはなるべく付けてありますが、どう考えてもself-containedな記事ではありません。

§1. RHKSの定義とカーネルの関係

{ X }を任意の空でない集合とします。

定義(Reproducing Kernel Hilbert Space)
{ X } 上の関数から成るヒルベルト空間 {\mathcal{H}}{ X }上のReproducing Kernel Hilbert Spaceであるとは、各元{ x \in X }により定まる線形写像


{ L_x : \mathcal{H} \rightarrow \mathbb{R} \ , \ \ f \mapsto f(x) }.


有界作用素である時を言う。

リースの表現定理から、各{ y \in X } に対して関数{ K_y \in \mathcal{H} }が存在して

{  \left< \ f , \ K_y  \ \right>_\mathcal{H}= L_y (f) = f(y) \ , \ \  \forall f \in \mathcal{H} } .

を満たす。従って、{ f =  K_x \in \mathcal{H} }として上の式に代入すれば

{ K_x(y) = \left< \ K_x , \ K_y  \ \right>_\mathcal{H} } .

となる。関数 { K: X \times X \rightarrow \mathbb{R} }をこの右辺、即ち { K(x,y) := \left< \ K_y , \ K_x  \ \right>_\mathcal{H} } として定義すると、明らかにこの関数は対称な関数で、かつ、正定値である。

即ち

(1) { K(x,y) = K(y,x) } .
(2) { \sum_{i,j=1}^n c_i K(x_i,x_j) c_j \geq 0 , } { \forall n \in \mathbb{N} \ ,\ \ \forall x_i \in X,\ \ \forall c_i \in \mathbb{R} } .

を満たす。*1

定義(Reproducing Kernel)
上で定義された関数 { K: X \times X \rightarrow \mathbb{R} } をRKHS {\mathcal{H} }Reproducing Kernel(再生核)と呼ぶ。

これまでの議論から、RKHS {\mathcal{H} } に対して、(1),(2)を満たす再生核がに定まる事が分かったが、次のMoore-Aronszajnの定理から(1)(2)を満たす物として一意であることが分かる。また、逆も成立する:

Moore-Aronszajnの定理(Uniqueness of Reproducing Kernel)
{ X } を空でない集合とする。関数{ K: X \times X \rightarrow \mathbb{R} }が(1),(2)を満たす時、それを再生核として持つRKHS {\mathcal{H}}が一意的に存在する。

証明のスケッチ
証明はwikipediaにもあるのでスケッチ程度で。

{ X } 上の関数から成るベクトル空間{\mathcal{H}_0}{ \{ K_x:=K(x,-) : X \rightarrow \mathbb{R} \ \ | \ \ x \in X  \} } の線形結合で生成されるものとしそこに内積

{ < \ \sum_{i=1}^n a_i K_{x_i} \  , \ \sum_{j=1}^m b_j K_{y_j} \ > := \sum_i \sum_j a_i b_j K(x_i, y_j) } .

として定め、内積空間 { ( \ \mathcal{H}_0 \ , \ < \  , \ > \ )} を完備化したものが求める{\mathcal{H}}となる。□

§2. Moore-Aronszajnの定理の罠

サポートベクトルマシンに詳しい鋭い人はもう気付いているかと思いますが、

Moore-Aronszajnの定理は特徴写像については何の情報も与えてくれません。数学的にもなんのご利益がない(いや、あるんですが)、ただの普遍性を与えているだけです。

そこで重要になってくるのが、次の§で説明するMercer'sの定理で、特徴写像がReproducing Kernelを積分作用素の核として見た時の固有値展開をしてやることで具体的に書くことが出来る事を示しています。

§3. 積分作用素Mercer'sの定理

まずRKHSから一旦離れ、関数解析的な議論をします。

{ X \subset \mathbb{R}^d } をコンパクトな部分集合とし、ボレル測度を入れておき { L^2(X) }をL^2関数の空間とします。

定義(Mercer核)
関数 { K: X \times X \rightarrow \mathbb{R} }が 対称で連続かつ、positiveである、即ち、


{  \displaystyle \int \int f(x)K(x,y)f(y)dxdy   \geq 0 \ , \ \forall f \in L^2(X) }


この条件を満たす時、Mercer核と呼ぶ。

Mercer核 { K: X \times X \rightarrow \mathbb{R} }に対して、その連続性から次のような有界積分作用素

{ T_K : L^2(X) \rightarrow  L^2(X) \ , \ \ f \mapsto T_K(f)(x) : =\displaystyle \int f(y)K(x,y)dy }

が定まり、コンパクトな自己随伴作用素作用素(もっというとHilbert-Schmidt)となることが知られています。*2

Mercerの定理( Theorem 17 in [3] )
Mercer核 { K: X \times X \rightarrow \mathbb{R} }に対して、正の実数列{ \{ \mu_i  \}_{i=1}^\infty \subset \mathbb{R}_{>0} }と連続関数の列{ \{ \phi_i \}_{i=1}^\infty \subset C(X) }が存在して

{ K(x,y) = \displaystyle \sum_{i=1}^\infty \mu_i \phi_i(x)\phi_i(y) }

と言う級数展開が存在し、収束は一様絶対収束する。

証明のスケッチ
上述の通り、 { K } により定まる積分作用素{ T_K } は自己共役コンパクトであるから、自己共役コンパクト作用素のスペクトル定理*3により得られる固有値{ \{ \mu_i  \}_{i=1}^\infty }として、固有ベクトル{\{ \phi_i \}_{i=1}^\infty }として取る。
あとは

{ K^n(x,y) := K(x,y) - \sum_{i=1}^n \mu_i \phi_i(x)\phi_i(y)  }

と言う関数が定める積分作用素{T^n }Positiveである事を使って、{ K^n(x,x) \leq K(x,x)  }が分かり、不等式評価を頑張ると、定理の無限級数{ y  }を止めた時に一様絶対収束することが分かる。あとは気合。□


Mercer核が存在すると次のように、それを再生核とするRKHSが存在することが分かり、これによりMercer核は条件 (1) (2)を満たす事が分かる。つまり連続性を除いたらMercer核の条件は(1)(2)と同値。

更にその時に定まる特徴写像固有値固有ベクトルにより完全に決定される:

定義(Mercer核により定まるRKHS)
Mercer核 { K } に対応する固有値{ \{ \mu_i  \}_{i=1}^\infty }として、固有ベクトル{\{ \phi_i \}_{i=1}^\infty }として取る。この時、次の無限次元ベクトル空間に対して


{ \mathcal{H} := \left\{  \left. f \in L^2(X) \ \  \right| \ \  \displaystyle \sum_{i=1}^\infty \dfrac{\left< \ f \ , \ \phi_i \ \right>_{L^2}}{\mu_i} < \infty \right\}  }

内積

{  \left< \ f \ , \ g \ \right>_\mathcal{H} := \displaystyle \sum_{i=1}^\infty \dfrac{\left< \ f \ , \ \phi_i \ \right>_{L^2} \left< \ g\ , \ \phi_i \ \right>_{L^2}  }{\mu_i}  }


と定めると、{ (\mathcal{H}, \left<  -  ,  -  \right>_\mathcal{H} ) }再生核を{ K } とするRKHSとなる。

§4. Mercer'sの定理の拡張

{ X \subset \mathbb{R}^d } のコンパクト性を落としたらどうなるかみたいな試みがあるみたいです。

Mercer theorem for RKHS on noncompact sets

Mercer’s Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSs | SpringerLink


詳しくは知りません。気が向いたらいつか読みたい。

§ 参考文献

[1] http://www.mit.edu/~9.520/scribe-notes/class03_gdurett.pdf

[2]

Elliptic Operators, Topology, and Asymptotic Methods, Second Edition (Chapman & Hall/CRC Research Notes in Mathematics Series)

Elliptic Operators, Topology, and Asymptotic Methods, Second Edition (Chapman & Hall/CRC Research Notes in Mathematics Series)

[3]

Integral Equations (Wiley Classics Library)

Integral Equations (Wiley Classics Library)

[4]

関数解析 (数学シリーズ)

関数解析 (数学シリーズ)

[5] [チュートリアル講演] カーネルマシン

[6] ON THE MATHEMATICAL FOUNDATIONS OF LEARNING

*1: [1]Theorem 10

*2: [2] 参照

*3: [4]参照