学習理論の学習

統計的学習理論を学習してるときに思ったこととか

多項式カーネル

機械学習 統計的学習理論

証明を考えながら一気書きしたので文章が拙いのは見逃してください（そうでなくとも拙いですが）．

多項式カーネル

　正の実数 c > 0 に対して， d \in \mathbb N 次の多項式カーネル K : \mathbb R ^ N \times \mathbb R ^ N \to \mathbb R は 次式で定義されます．

\displaystyle{ \forall \boldsymbol x, \boldsymbol x' \in \mathbb R ^ N, \quad K(\boldsymbol x, \boldsymbol x') = (\boldsymbol x \cdot \boldsymbol x' + c)^d }

　多項式カーネルは \mathbb R ^ N から \mathbb R ^ H へと写していると考えられるそうです． ただし，ここで H は

\displaystyle{ H = \begin{pmatrix} N+d \\ d \end{pmatrix} }

のことです．

　本記事ではこの証明，つまり

\displaystyle{ K(\boldsymbol x, \boldsymbol x') = \phi (\boldsymbol x) \cdot \phi (\boldsymbol x') }

を満たす写像 \phi : \mathbb R ^ N \to \mathbb R ^ H が存在することを示します．

証明

　まず， z = \boldsymbol x \cdot \boldsymbol x' とおくと，二項定理より

\displaystyle{ K(\boldsymbol x, \boldsymbol x') = \sum _ {s = 0} ^ d \begin{pmatrix} d \\ s \end{pmatrix} z ^ s c ^ {d - s} }

と展開できます．

　さて，ベクトル \boldsymbol x, \boldsymbol x ' \in \mathbb R ^ N の各成分を

\displaystyle{ \boldsymbol x = \begin{pmatrix} x _ 1 & x _ 2 & \cdots & x _ N \end{pmatrix} ^ \top, \quad \boldsymbol x' = \begin{pmatrix} x' _ 1 & x' _ 2 & \cdots & x' _ N \end{pmatrix} ^ \top }

と書くことにします． こうすると， z ^ s は次のように展開できます．

\displaystyle{ \begin{align} z ^ s &= (\boldsymbol x \cdot \boldsymbol x') ^ s \\ &= ( x _ 1 x' _ 1 + x _ 2 x' _ 2 + \cdots + x _ N x' _ N) ^ s \end{align} }

ここで，多項定理の公式

\displaystyle{ ( z _ 1 + \cdots + z _ N) ^ d = \sum _ { r _ 1 , \ldots, r _ N : r _ 1 + r _ 2 + \cdots + r _ N = d } \begin{pmatrix} d \\ r _1 , \ldots , r _ N \end{pmatrix} z _ 1 ^ {r_1} z _ 2 ^ {r _ 2} \cdots z _ N ^ {r _ N} }

を使うと，

\displaystyle{ \begin{align} z ^ s &= ( x _ 1 x' _ 1 + x _ 2 x' _ 2 + \cdots + x _ N x' _ N + c) ^ s \\ &= \sum _ {\boldsymbol r : r _ 1 + r _ 2 + \cdots + r _ N + r _ N = s } \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} (x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \end{align} }

と書き直すことができます． ただし，表記を簡単にするために

\displaystyle{ \begin{align} \boldsymbol r &= \begin{pmatrix} r _ 1 & \ldots & r _ {N+1} \end{pmatrix}, \\ \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} &= \frac { s! } { r _ 1 ! \cdots r _ N ! } \end{align} }

としました． ある s に対して， \boldsymbol r を \sum _ {i=1} ^ N r _ i = s となるようにひとつ決めると， 和の中身はの積の部分（二項係数を除いた部分）は，

\displaystyle{ \begin{align} &(x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \\ =& \left( x ^ {r _ 1} _ 1 \cdots x ^ {r _ N} _ N \right) \left( x' ^ {r _ 1} _ 1 \cdots x' ^ {r _ N} _ N \right) &=: \phi _ { \boldsymbol r } (\boldsymbol x) \phi _ { \boldsymbol r } (\boldsymbol x') \end{align} }

と， \boldsymbol x に関する項と \boldsymbol x' に関する項の積の形に書き直せます． ただし，

\displaystyle{ \begin{align} \phi _ { \boldsymbol r } (\boldsymbol x) &= \left( x ^ {r _ 1} _ 1 \cdots x ^ {r _ N} _ N \right) \in \mathbb R, \\ \phi _ { \boldsymbol r } (\boldsymbol x') &= \left( x' ^ {r _ 1} _ 1 \cdots x' ^ {r _ N} _ N \right) \in \mathbb R \end{align} }

と定義しました．このように書くことで， \phi _ {\boldsymbol r} (\boldsymbol x) \phi _ {\boldsymbol r} (\boldsymbol x') は 内積 \phi (\boldsymbol x) \cdot \phi (\boldsymbol x') の第 \boldsymbol r 成分と考えることができます． z ^ s は \phi _ {\boldsymbol r} (\boldsymbol x) \phi _ {\boldsymbol r} (\boldsymbol x') を \sum _ {i=1} ^ N r _ i = s を満たすすべての \boldsymbol r について足し合わせているので

\displaystyle{ \begin{align} z ^ s &= \sum _ {\boldsymbol r : r _ 1 + r _ 2 + \cdots + r _ N + r _ N = s } \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} (x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \\ &= \phi _ { \boldsymbol r _ 1 } (\boldsymbol x) \phi _ { \boldsymbol r _ 1 } (\boldsymbol x') + \phi _ { \boldsymbol r _ 2 } (\boldsymbol x) \phi _ { \boldsymbol r _ 2 } (\boldsymbol x') + \cdots \\ &= \begin{pmatrix} \phi _ { \boldsymbol r _ 1 } (\boldsymbol x) \\ \phi _ { \boldsymbol r _ 2 } (\boldsymbol x) \\ \vdots \end{pmatrix} \cdot \begin{pmatrix} \phi _ { \boldsymbol r _ 1 } (\boldsymbol x') \\ \phi _ { \boldsymbol r _ 2 } (\boldsymbol x') \\ \vdots \end{pmatrix} &=: \phi _ s (\boldsymbol x) \cdot \phi _ s (\boldsymbol x') \end{align} }

と書くことができます．ただし， \sum _ {i=1} ^ N r _ i = s を満たす \boldsymbol r をそれぞれ \boldsymbol r _ 1, \boldsymbol r _ 2, \ldots のように書きました．

以上の議論から，各 s について z ^ s はベクトルの内積の形で書くことができるということがわかりました． 本記事の目的は K (\boldsymbol x, \boldsymbol x') が \mathbb R ^ H 上で内積を取った値を返す関数であることを示すことでしたので， これからすべきことは

  1. 各 s について \phi _ s (\boldsymbol x) が何次元ベクトルなのかを求める．
    1. で求めた次元数を s=0 から s=d まで足し合わせる．

の2つです．

1. 各 s について \phi _ s (\boldsymbol x) が何次元ベクトルなのかを求める．

　この問題は，今回の場合は次の問題と等価です．

\displaystyle{ (z _ 1 + z _ 2 + \cdots + z _ N) ^ s }

を展開したとき，項数はいくつか．

　この問題は，高校数学で習った組み合わせの問題ですね．要は， N 種類のものから重複を許して s 個選ぶ問題 です．従って，簡単な計算から各 s における (z _ 1 + z _ 2 + \cdots + z _ N) ^ s の項数は

\displaystyle{ \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \frac {(N+s-1)!} {s ! (N-1)!} }

となることがわかります．

2. 1. で求めた次元数を s=0 から s=d まで足し合わせる．

　次の量を求めたいです．

\displaystyle{ \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} }

次の補題から直ちに求まります．

補題

N \in \mathbb N とします．このとき，

\displaystyle{ \forall d \in \mathbb N, \quad \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

補題の証明

数学的帰納法で示します．

  • d = 1 のとき．
\displaystyle{ \begin{align} \sum _ {s=0} ^ 1 \begin{pmatrix} N \\ s \end{pmatrix} &= \begin{pmatrix} N \\ 0 \end{pmatrix} + \begin{pmatrix} N \\ 1 \end{pmatrix} \\ &= 1 + N \\ \begin{pmatrix} N + 1 \\ 1 \end{pmatrix} &= N+1 \end{align} }

よって， d=1 のときは成り立ちます．

  • d \geq 1 のときに成り立つと仮定します．
    このとき， d+1 のときにも成り立つことを示します．
\displaystyle{ \begin{align} \sum _ {s=0} ^ {d+1} \begin{pmatrix} N+s-1 \\ s \end{pmatrix} &= \sum _ {s=0} ^ {d} \begin{pmatrix} N+s-1 \\ s \end{pmatrix} + \begin{pmatrix} N+d \\ d+1 \end{pmatrix} \\ &= \begin{pmatrix} N+d \\ d \end{pmatrix} + \begin{pmatrix} N+d \\ d+1 \end{pmatrix} \\ &= \begin{pmatrix} N+d+1 \\ d+1 \end{pmatrix} \end{align} }

したがって， d+1 のときも成り立ちます．

以上より，任意の d \in \mathbb N に対して

\displaystyle{ \forall d \in \mathbb N, \quad \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

が成り立つことが示せました．

　上記の補題を使うことで，

\displaystyle{ \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

が成り立つことが直ちに言えるので， 多項式カーネルは \mathbb R ^ N から \mathbb R ^ H に写した後に内積を取ったものと考えられることが示せました．

余談

これは Foundation of Machine Learning の第 6 章の演習問題の一つ（しかもその半分）でした． 証明が間違っていないといいな，と願ってます．