カーネル法の為の線形代数

カーネル法を学ぶ上で絶対に理解するべき概念があります。それは、内積です。内積は、線形空間上に長さの概念を導入する上で必要になります。カーネル法では、データを内積がカーネルで定まる無限次元の空間に飛ばし、その空間独自の内積で距離を測ることで、データの複雑な構造を解きほぐします。2次元上に書かれた立体的な図形を1次元に射影してしまうと全体が見えませんが、3次元で俯瞰すれば全体が一目瞭然、という雰囲気です。
この記事では、内積について解説します。
詳しい話や、解説していない箇所は、以下の本2冊を読んでください。どちらも読めば、線形代数で困ることは殆ど無いと思います。

東京大学出版会の線形代数入門は、行列について詳しく具体的に書いています。初学者で根気のある人にはお勧めです。

線形代数の世界は、管理人を数学の道へ誘ってしまった本です。抽象的に書かれている本です。自分で章末問題などで具体例を計算する必要があります。

線形空間の定義と例
内積とその例
線形空間からヒルベルト空間へ
まとめ

線形空間の定義と例

内積を定義するには、線形空間が必要です。一応 ¹ 定義と例を書いておきます。簡単には、足し算とスカラー倍が出来る集合です。スカラー全体の事を体と呼びます。体というのは、簡単に言うと足し算と掛け算が出来る集合です。線形空間についての詳しい解説は別の記事があるのでどうぞ。

線形空間(ベクトル空間)の解説

線形空間(ベクトル空間)についての解説記事です。線形代数が出来るうれしさを紹介した後、線形空間の定義、線形空間の例を紹介します。機械学習への応用についても少し触れています。

線形空間の定義を正確に定義を書くと以下のようになります。

集合$ V $が体$ K $上の線形空間(ベクトル空間)であるとは、和とスカラー倍$ + : V \times V \rightarrow V , * :K \times V \rightarrow V $があって、以下の条件を満たすことです。ただし、$+ (v, w) =v+w , *(a,v ) =a*v $とします。また、断らなければ、$a,b,$は任意の(\K\)の元を表し、 $v,w,z $は任意の(\V\)の元を表します。さらに、$K $の中での積と、スカラー倍$ * :K \times V \rightarrow V $ は区別せずに書きます。

$ (v+w)+z=v+(w+z) $が成り立つ。
$ 0 \in V $ で、$ v+0 = 0+v = v$を満たすものがただ一つ存在する。
任意の $ v \in K $ に対して、$ v+w=w+v =0 $となる $ w \in V $がただ一つ存在する。
$v+w = w+v $ が成り立つ。
$a*(v+w) = (a*v + a*w $が成り立つ。
$ a*(b*v)) = (a*b)*v , (a+b)*v = a*v + b*v $
$1*v=v $が成り立つ。
$a*b =b*a $が成り立つ。
$ a* (b+c ) =a*b + a*c $と$ (a+b) *c = a*c +b*c $が成り立つ。

2.を線形空間の零元と呼びます。 (3) の元をvの逆元と呼び、$-v $で表します。 ²
$ -v = (-1)* v$となります。数学に慣れていない人は、右辺と左辺は意味が違う事を理解したうえで、証明してみてください。

実数全体の集合$ \mathbb{R} $ とか複素数全体$ \mathbb{C} $、整数を素数pで割った時の余りの集合$ \mathbb{Z}_p $ が体としてよく使われます。

体Kは、自分自身に備わっている積を自分自身への作用とみて線型空間になります。つまり、体KはK上の線形空間です。
$ \mathbb{Z} _{p} $が体になることを確かめましょう。数を整数全体$\mathbb{Z} $ の元としてみる時は$n , m $と書き、[mathjax]$\mathbb{Z} _{p} $の元としてみる時は[mathjax]$ \bar{n}, \bar{m} $と書きます。整数の世界では$ \mathbb{Z_{p} } $の元は集合で表すことが出来ます。
$$\begin{eqnarray}
\bar{n} = \left\{ n+kp| k\in \mathbb{Z} \right\}
\end{eqnarray}$$
のようになります。
$\mathbb{Z_{p}} $ に以下で足し算と掛け算を定義します。
$$\begin{eqnarray}
\bar{n} +\bar{m} &=& \overline{n+m} \\
\bar{n} \cdot \bar{m} &=& \overline{nm}
\end{eqnarray} $$
右辺の足し算や掛け算は整数の足し算と掛け算です。$ \bar{n} = \bar{m} $だからといって、$n =m $ではないので、この定義でおかしなことが起きないか確かめる必要があります。
例えば、$ p=3 $とすると、$ \bar{3} =\bar{6} =\bar{9} $ですが、$ 3 \neq 6 \neq 9 $です。
この時に、上の足し算の定義で$ \bar{3} + \bar{5} $を計算しようと思うと以下のような計算をしてもよい事になります。
$$\begin{eqnarray}
\bar{3} +\bar{5} &=& \overline{3+5} \\
\ &=& \overline{6+5} \\
\ &=& \overline{9+5}
\end{eqnarray} $$
このような計算をしても、全ての答えが等しくならなければなりません。一般に、足し算が上手く定義されているか確かめてみましょう。
[mathjax]$ n\neq m , \bar{n} =\bar{m} $としましょう。この時、整数kを用いて、[mathjax]$m= n+ kp $と書けます。任意の[mathjax]$ l \in \mathbb{Z} $について、
$$\begin{eqnarray}
\bar{n}+ \bar{l}&=& \overline{n+l} \\
\bar{m}+ \bar{l} &=& \overline{m+l}=\overline{n+l+kp} =\overline{n+l} \\
&=&\bar{n} + \bar{l}
\end{eqnarray}$$
となります。
[mathjax]$ \bar{n} =\bar{m} $ となる [mathjax]$ n\neq m ,$で足し算の結果が違わないので、[mathjax]$ \mathbb{Z}_p $での和がうまく定義出来ていることが分かりました。³
積も同じようにwell-defined であることが示せます。積についての逆元が必要ですが、集合論の知識を用いて、存在することが分かります。

$ a , b,c \in \mathbb{Z} _{p} , a \neq 0 $に対して、$ a*b =a*c $ ならば、$b=c $⁴である。$ \mathbb{Z} _{p} $は有限個しか元が無いので、$a $倍する写像は、全射でもあり、逆写像があります。a倍写像の1の逆像がaの逆元です。

線形空間の他の例としては、例えば関数からなる空間があります。
f,gを $ \mathbb{R} $上で定義された関数とします。関数の足し算を [mathjax]$ (f+g) (x)= f(x) +g(x) $と置く事で、関数からなる空間は[mathjax]$ \mathbb{R} $上の線形空間となります。 ⁵

内積とその例

内積について解説します。内積を導入することで、線形空間の中で距離を測ったり、ベクトルの大きさを認識できるようになります。

Vを線形空間とします。 [mathjax]$ \cdot : V\times V \rightarrow \mathbb{R} $ が内積 ⁶ であるとは、任意の [mathjax]$ v, w \in V,a \in \mathbb{R} $ に対して以下を満たすことです。

$ (v+w) \cdot z = v\cdot z + w\cdot z $
$ v\cdot (w+z) = v \cdot w + v \cdot z $
$ a(v \cdot w) = (av)\cdot w =v \cdot (aw) $
$ v \cdot w = w \cdot v $
$ v \cdot v \geq 0 $

$ (V,\cdot ) $の組を内積線形空間と呼びます。

内積があると何が嬉しいのでしょうか？
内積によって、線形空間の中で幾何学的な情報を考える事が出来るようになります。例えば、距離とノルム(大きさ)を考える事が出来ます。

[mathjax]$ (V,\cdot ) $を内積線形空間とします。[mathjax]$ v,w \in V $に対して、vのノルム[mathjax]$ \| v\| $、vとwの距離 $ d(v,w) $ を以下で定義します。
$$ \begin{eqnarray}
\| v \|&=&\sqrt{ v \cdot v }\\
d(v,w) &=& \| v-w \|
\end{eqnarray} $$

ノルムには、以下の大事な性質があります。

コーシー・シュワルツの不等式
$$ \begin{eqnarray}
\| v \cdot w\|& \leq & \| v \| \| w \|
\end{eqnarray} $$
等号が成立するのは、一方が一方の実数倍のときのみで、その時に限る。

それぞれのベクトルの大きさを掛けたものと内積が一致するのは、ベクトルが平行な時だけ、というわけです。

内積線形空間の例を見ましょう。内積は、行列を使って表すことが出来る場合があります。カーネル法ではそれを上手く使っています。

[行列から定まる内積]
$ \mathbb{R} ^n $ で実数n個の組からなる線形空間とします。標準的な内積を以下で定義できます。
$$ \begin{eqnarray}
v \cdot w =\sum v_i w_i
\end{eqnarray} $$
これは高校でも習う内積ですが、 [mathjax]$ \mathbb{R} ^n $ には、他にも内積があります。
[mathjax]$ A =\{ a_{ij} \} $を [mathjax] $A =A^T $を満たし ⁷ 、固有値がすべて0以上の行列とします。以下のように定義しても内積となります。
$$ \begin{eqnarray}
v \cdot w = v^{T} A w =\sum_{i,j} v_i a_{ij} w_j
\end{eqnarray} $$
このとき、Aを計量行列と呼びます。計量行列として、単位行列を取ると初めの内積の例が再現されます。
カーネル$k : X\times X \rightarrow \mathbb{R} $を考えましょう。
カーネルのグラム行列
$$ \begin{eqnarray}
K=\{ K_{ij} \} =k(x_i , x_j )
\end{eqnarray} $$
は、上記の性質を満たすような行列です。よって、カーネルを計量行列として使用でき、カーネルを使って内積を作る事が出来ます。
$$ \begin{eqnarray}
v\cdot _{K} w =\sum v_i k(x_i , x_j) v_j
\end{eqnarray} $$
カーネル自体は、2変数関数$k $によって定義されているので、無限の自由度を持っています。この無限の自由度をデータの数という有限次元で使えるのがカーネルトリックと呼ばれる手法です。

カーネルについて詳しく説明した記事があるので、興味のある方はどうぞ。

カーネルの正体

カーネル法では、カーネルという魔法の道具と、カーネルトリックという技でモデルの表現力を劇的に上げる事が出来ます。しかし、カーネルとは一体何なのでしょうか。その疑問を正定値性、再生核ヒルベルト空間という概念で解決します

[関数空間の内積]
無限次元の線形空間で最も身近なものは、実数値関数です。(多分)
$ \ L^2 $ で [mathjax]$ \mathbb{R} ^n $ 上の2乗可積分関数全体とします。 [mathjax]$ f,g \in L^2 $ に対して、内積を以下で定義出来ます。
$$ \begin{eqnarray}
f \cdot g = \int f(x) g(x) dx
\end{eqnarray} $$
この内積で関数同士の距離や、関数の大きさを考える事が出来るようになります。

線形空間からヒルベルト空間へ

カーネル法を使うだけならヒルベルト空間は必要ないんですが、真面目に理論を理解するには必要です。ちょっとだけヒルベルト空間について書いておきます。
内積付き線形空間がヒルベルト空間であるとは、内積が誘導するノルムによって定まる位相について完備であることです。位相というのは、近さの概念の一般化です。ノルムの大きさ一定の部分空間を球と呼んだりしますが、球の半径を変えていって、球の内部に入れば近いみたいなそんな感じです。
詳細が知りたい人は以下の本で関数解析を勉強すると良いです。
共立出版の本は、当時は鉄板の本でした。解析学を勉強したらその流れで関数解析という感じの本です。量子力学の数学的構造という本は、固有値問題がらみの話を沢山書いています。結構具体的です。

数学を学んだ人が一番最初にヒルベルト空間だと習うのが、 [mathjax]$ L^2 $ だと思います。もちろん、[mathjax]$ \mathbb{R} ^n $もヒルベルト空間です。内積付きの線形空間があると、それをヒルベルト空間にする方法があります。
[mathjax]$ \mathbb{R} ^n $ はn個の組のベクトルで、どんなベクトルも表示できるという意味で有限次元ですが、 [mathjax]$ L^2 $ は無限次元です。線形代数だけの枠組みでは無限次元の話はあまり扱えないのですが、位相という概念を導入することによって詳しい性質を見ることが出来ます。
位相の概念は、カーネル法を使う上では殆ど必要でないので、内積線形空間+良い位相でヒルベルト空間と覚えておけば良いと思います。