サイトアイコン マサムネの部屋

カーネルの正体

カーネル法

カーネル法入門の記事では、なんだか良く分からないけどカーネルという行列があって、それを使うとモデルの表現力が劇的に向上する、何故か知らないけど、カーネルには色々な種類があって、どうやらどんな行列でもカーネルと呼ぶわけでは無いらしい、 という雰囲気を感じてくれたと思います。 この記事では、そもそもカーネルとは何ぞや、という数学的なお話を書きたいと思います。
カーネル法入門や、既存手法のカーネル化の記事はこちら。

以下の本を参考にしています。エンジニア系の人はカーネル法の本を、数学系の人は両方読むと良いです。

スポンサーリンク

カーネルと再生核ヒルベルト空間

まずは何者をカーネルと呼んでいたのかはっきりさせましょう。優しめの解説は別の記事で書きます (多分) 。基本的にヒルベルト空間が何か分かっていればふんわり分かりますが、知らない人はまずはこちらの記事を読んでください。

カーネル法の為の線形代数
カーネル法でキーとなる概念は内積です。内積について解説しています。

\(\mathcal{H} \)を実ヒルベルト空間とします。また、 写像\( \phi :X \rightarrow \mathcal{H} \)を一つ固定します。Xは説明変数からなるデータだと思ってください。そして、\( \mathcal{H} \)の内積\( <\cdot ,\cdot > _{\mathcal{H}} \)を使って、以下の空間を定義します。
$$\begin{eqnarray}
\mathcal{K} =\left \{ f_{w} : X \rightarrow \mathbb{R} ; f_w (x) = <w, \phi (x)> | w \in \mathcal{H} \right \}
\end{eqnarray}$$
パット見は良く分からないですね。\(w \in \mathcal{H} \)を固定して、\( \phi \)で持ってきたx と内積を取る、という関数全体の集合が\( \mathcal{K}\)です。基本的には、内積を取る関数全体の集合ですが、\( \phi \)を通してXの内積みたいな雰囲気にしてます。
\( \mathcal{K} \)は線形空間になります。和と\( \mathbb{R} \)の作用は以下のように定まります。

\( w,v\in \mathcal{H} , a\in \mathbb{R} \) とします。
$$\begin{eqnarray}
f_v +f_w &=&f_{v+w}\\
a f_w &=&f_{aw}
\end{eqnarray}$$
Xには線形性を仮定していませんが、線形性を持つべきはwの側だけというのがポイントです。w側に線形性があれば、内積の線形性で上手く線形空間になるわけです。

次は、\( \mathcal{K} \)に内積をいれましょう。今の定義には少し弱い所があって、\( f_w (x) = f_v (x) \)が成り立ったからと言って、\( w=v \)とはならないのです。それを解消するために、良くある手法ですが、最小値を取ります。

\( w \in \mathcal{H} \) とします。wに対して、\( w^{\ast} \)を次のように定義します。
$$\begin{eqnarray}
\mathcal{W} = \{ v | v\in \mathcal{H} , f_w =f_v \} \\
w^{\ast} = \inf_{w \in \mathcal{W} } \| w \|
\end{eqnarray}$$
\(\mathcal{K}\) の内積を以下で定義します。
$$\begin{eqnarray}
<f_w , f_v >_{\mathcal{K}} = <w^{\ast} , v^{\ast} >_{\mathcal{H}}
\end{eqnarray}$$

\( k: X\times X \rightarrow \mathbb{R} ; k(x,x’)= <\phi(x) , \phi(x’) >_{\mathcal{H}} \)と置きます。\(k_x = k(\cdot , x ) \)とすると、これはXから\( \mathbb{R} \)への写像になっています。なんとなく予想できるかもしれませんが、 \(k_x \in \mathcal{K} \)となります。 この写像が大事になります。次の定理の実用上大事な部分だけを証明しましょう。

  1. \( \mathcal{K}\)はヒルベルト空間になる。
  2. \( k(\cdot , x)\in \mathcal{K} \)
  3. (再生性 )任意の\( f\in \mathcal{K} \)と任意の\( x \in X\) に対して \( f(x) = <f, k(\cdot , x)>_{\mathcal{K} } \)

逆に、2と3を満たすような2変数関数kは\( \mathcal{k} \)に対して一意に定まる。

上の定理で 大事な所は、\( \mathcal{K} \)というヒルベルト空間は, 1個の写像\(k \)から全ての元を説明できるという事です。 \( \mathcal{K} \)は元々 \( \phi \) でXを\( \mathcal{H} \)に持って来て内積を取るという関数全体なので、それ以上の情報もそれ以下の情報も持っていないので当たり前と言えば当たり前ですが。

2.については、\( k(\cdot , x) = f_{\phi (x)}\)である事から分かります。
3.を示しましょう。
\(w \in \mathcal{H} \)として、 \( w= w^{\ast} + w’ \) と直交分解 します。つまり、 \( w^{\ast} \)と \(w’ \)の内積が0という事です。 また、\( \phi (x) = \phi (x) ^{\ast} +\phi (x)’ \)と同じように分解します。\( \mathcal{W} \) の定義から次の事が分かります。
$$\begin{eqnarray}
<w^{\ast} , \phi (x) >_{\mathcal{H}}& =& <w, \phi (x) >_{\mathcal{H}} \\
&=& <w^{\ast}, \phi (x) >_{\mathcal{H}} + <w’ , \phi (x) >_{\mathcal{H}}
\end{eqnarray}$$
この事から、\( <w’ ,\phi (x) >_{\mathcal{H}} =0 \)です。今、\( w \)は任意に取っていたので、任意の\( w’ \in \mathcal{H} \)に対して \( <w’, \phi (x) >_{\mathcal{H}} =0 \)が言えました。こうなると最早\( \phi (x) \)を分解することは出来ないので、\( \phi (x) =\phi (x) ^{\ast} \) です。\( \mathcal{K} \)での内積の定義から、以下が成り立ちます。
$$\begin{eqnarray}
<f_w, k(\cdot , x) >_{\mathcal{K} } & =& <w^{\ast}, \phi (x)^{\ast} >_{\mathcal{H}} \\
&=& <w, \phi (x) >_{\mathcal{H}} =f_w (x)
\end{eqnarray}$$
これで3.が示せました。次に、2.3.を満たす 関数が\( k , l \)とあったとしましょう。
2と3の性質から、任意の\(x ,x’ \in X \)に対して、
$$\begin{eqnarray}
k(x,x’ ) =<k(\cdot , x) , l(\cdot , x’ )>_{\mathcal{K} } =l(x,x’)
\end{eqnarray}$$
で、\( k = l \)が分かります。

定理の中の再生性が面白い事を言っています。つまり、\( \mathcal{K} \)の元の関数としての値が、\( k(\cdot ,x) \in \mathcal{K} \)だけから計算出来てしまうという事です。\( k\)だけで、ヒルベルト空間\(\mathcal{K} \)が作り直せてしまうという意味で、\( k \)を \(\mathcal{K} \)の再生核と呼びます。また、\( \mathcal{K} \)のように、再生核を持つヒルベルト空間を再生核ヒルベルト空間と呼びます。この再生核の事を、カーネルと呼びます。
これでカーネルが何者なのかなんとなく分かりました。再生核ヒルベルト空間の再生核がカーネルです。次の疑問は、どんな関数が再生核足りえるか、ということですね。調べていきましょう。

カーネルと正定値性

再生核は、内積で定義されているので、少なくとも対称である必要があります。では、\( X \times X \rightarrow \mathcal{H} \)という写像で、対称な写像なら再生核になるのでしょうか?内積で定義されているという事に注目すると、再生核は正定値性も持っています。きっとこれも無いと駄目でしょう。どちらが本当に大事な性質なのでしょうか。

実は正定値性です。
\( k: X\times X \rightarrow \mathbb{R} \)が正定値とは、次のことを指します。
kから任意のn次元正方行列\( K= \{ k(x_i , x_j \} \)を定義した時、任意の\( \vec{\alpha} \in \mathbb{R}^n \)に対して、 \(\vec{\alpha}^{T} K \vec{\alpha} \geq 0 \)

再生核は正定値である。逆に、kが正定値ならば、kを再生核に持つヒルベルト空間がただ一つ存在する。
[証明]
\( k \) を再生核とします。再生性から、
$$\begin{eqnarray}
\vec{\alpha}^{T} K \vec{\alpha} &=& \sum \sum \alpha _i K_{ij} \alpha _j \\
&=& \left< \sum \alpha _i k(\cdot , x_i) , \sum \alpha _j k(\cdot , x_j )\right>_{\mathcal{K} }\\
&=& \| \sum \alpha _i k(\cdot , x_i ) \| _{\mathcal{K} } ^2 \geq 0
\end{eqnarray}$$
この計算から、kは正定値です。
逆に、kが正定値だとします。この時、\( \sum \alpha_i k(\cdot , x_i ) \) 全体が張る線形空間\( \mathcal{K} \)を考えます。内積は以下の式で入れます。
$$\begin{eqnarray}
\left < \sum \alpha _i k( \cdot , x_i ) , \sum \beta _j k( \cdot , x_j ) \right > _{\mathcal{K} }
= \sum \alpha _i \beta _j k(x_i , x_j)
\end{eqnarray}$$
kが正定値なので、\( \mathcal{K}\)は内積空間になります。また、内積の定義から\( k \)は再生核です。これをヒルベルト空間にすることで、再生核ヒルベルト空間になります。作り方から、このヒルベルト空間は一意です。

この定理から、カーネルとは、正定値関数という事が出来ます。1実際に使うカーネルは、正定値で対称な事が多い気がしませんか?それは何故か解説します。

データとカーネルの関係

カーネルが何者かは分かりましたが、これが機械学習やデータ分析とどうやって繋がってくるのか、もう少し説明したいと思います。一般に再生核ヒルベルト空間は無限次元の空間ですが、得られるデータは有限個です。しかし、データの数と同じ次元の正定値行列があれば、それをカーネルとみなすことが出来ます。

Kをn次正定値対称行列とする。このとき、任意の\( x=( x_1, \cdots , x_n ) \in X \)に対して、 \(\phi : X^{n} \rightarrow \mathbb{R} \)が存在して、以下が成り立つ。
$$\begin{eqnarray}
K_{ij} &=& \left< \phi (x_i) , \phi (x_j) \right> _{\mathbb{R} ^n } \\
&=& \sum _{l} \phi _{l} (x_i ) \phi _{l} ( x_j )
\end{eqnarray}$$
つまり、データと同じ大きさの正定値対称行列があれば、それをカーネルとして使えるという事です。
[証明]
Kが 正定値対称行列 なので、固有値は全て0より大きい実数値になります。固有値を\( \lambda _1 , \cdots ,\lambda _n \) それに対応する固有ベクトルを\( u _1 , \cdots , u_n \)とおくと、Kは以下の形に書けます。
$$\begin{eqnarray}
K =\sum \lambda _i u_i u_i ^{T}
\end{eqnarray}$$
\( \phi _l (x_j ) =\sqrt{ \lambda _l } {u_{l} }_{j} \)と置けば、
$$\begin{eqnarray}
K_{ij} = \sum _{l} \phi _{l} (x_i ) \phi _{l} ( x_j )
\end{eqnarray}$$
が成り立ちます。

この定理によって、元々知られているカーネル関数を計算しないで、適当な正定値対称行列を作ってもそれがカーネルになっている事が保証されます。もちろん、それが役に立つかまでは保証していません。
大事なことは、カーネル関数を組み合わせる時に、行列が正定値対称性を保てば何をしてもよいという事です。例えば、カーネル同士を足したりかけたりしても良いわけです。

まとめ

・カーネルとは再生核のこと。
・カーネルとは正定値関数のこと。
・どちらも同じこと。
・カーネルは自由に作れるし、既存の物を加工できる。

  1. 定義から、\( \mathcal{K} \) の基底は\( k( \cdot , x_i) \) で張られます。ヒルベルト空間に良い基底があれば、基底たちと内積を取ることで、どんな元でも基底の線形和にできます。つまり、基底で表現出来てしまいます。\( \mathcal{K} \)の中にデータに正しい予測値を返す関数があると仮定すれば、その関数はカーネルで表現できます。これが、カーネル法の表現力の高さの所以です。