Kernel Methods

Definition 6.1 (Kernels)

関数 \(K\) は \(\mathcal X\) 上のカーネルと呼ばれる

\[K \colon \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\]

• アイデアは、任意の2点 \(\forall x, x' \in \mathcal{X}\) に対して、
  \(K(x, x′)\) が特徴量空間と呼ばれるヒルベルト空間 \(\mathbb{H}\) への いくつかの写像 \(\Phi \colon \mathcal{X} \rightarrow \mathbb{H}\)について、ベクトル \(\Phi(x)\) と \(\Phi(x')\) の内積に等しくなるようなカーネル \(K\) を定義すること
  (内積を入力空間のものと区別するために，一般的に内積を \(\langle\cdot,\cdot\rangle\) と表記する)

\[ \forall x, x' \in \mathcal{X}, \;K(x,x') = \left\langle \Phi(x),\Phi(x')\right\rangle \tag{6.1} \]

(内積から定義されるノルムに関して完備性を満たす内積空間をヒルベルト空間という。(青本p172) 完備性とは、任意のコーシー列が極限を持つ性質のことをいう (青本p170))

• カーネル \(K\) の重要な利点① : efficiency
  • 多くの場合、\(\Phi\) と \(\mathbb{H}\) の内積を計算することよりも有意に効率的であり、
    いくつかのケースでは、\(\mathbb{H}\)の次元は無限大であるため内積の計算ができないこともある
• カーネル \(K\) の重要な利点② : flexibility
  • 明示的に写像 \(\Phi\) を定義したり、計算する必要はない
  • カーネル \(K\) は，\(\Phi\) の存在が保証されている限り任意に選ぶことができる
    　➡ カーネル \(K\) が Mercer’s condition (PDS condiion) を満たす

Theorem 6.2 (Mercer’s condition)

\(\mathcal{X} \subset \mathbb{R}^N\) をコンパクト集合とし
\(K \colon \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\) を連続で対称な関数とする
すると、 \(K\) は任意の自乗可積分関数 \(c \:(c \subset L_2(\mathcal{X}))\) に対して、 \[ \int_{\mathcal{X} \times \mathcal{X}}c(x)c(x')K(x,x')dxdx'\geq0 \]

が成り立つ場合には、\(a_n > 0\)について以下のように一様に収束した形の展開を認める

\[ K(x,x') = \sum^{\infty}_{n = 0}a_n \phi_n(x)\phi_n(x') \]

• この条件は、SVMのようなアルゴリズムの最適化問題の凸性を保証し、それによって大域最小値への収束を保証するために重要である

• 定理の仮定の下でマーサーの条件と同等の条件は、カーネル \(K\) が正定値対称 (positive definite symmetric : PDS) であること

• この性質は、特に \(\mathcal{X}\) についての仮定を必要としないので、実際にはより一般的なものである

Definition 6.3 (Positive definite symmetric kernels : 正定値対称カーネル)

任意の \(\{x_1,...,x_m\} ⊆\mathcal{X}\) に対して、行列 \(\bf{K} \mathrm{= [K(x_i,x_j)]_{ij} \in \mathbb{R}^{m \times m}}\) が対称半正定値 (Symmetric Positive Semidefinite : SPSD) である場合
カーネル \(K \colon \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\) は、正定値対称 (PDS) であると言われる

\(K\) が対称であり、以下の2つの等価な条件のいずれかが満たされていれば、\(K\)はSPSDである

• \(K\) の固有値が非負である

• 任意の列ベクトル \(c = (c_1, . . . ,c_m)^\top \in \mathbb{R}^{m \times 1}\)において以下を満たす

\[ \bf{c^\top Kc} \:\mathrm{=\sum^{n}_{i,j=1} c_ic_jK(x_i,x_j) \geq 0 \tag{6.2}} \]

• 標本 \(S = (x1,....,xm)\) に対して、\(\bf{K} \mathrm{= [K(x_i,x_j)]_{ij} \in \mathbb{R}^{m \times m}}\) は、カーネル行列またはKと標本Sとの関係を表すグラム行列と呼ばれている

Example 6.4 (Polynomial kernels : 多項式カーネル)

定数 \(\forall c > 0\) について、次数 \(d \in \mathbb{N}\)の多項式カーネルは、以下の (6.3)式 によって \(\mathbb{R}^N\) 上に定義されたカーネル \(K\) である

\[ \forall \bf{x,x'} \mathrm{\in \mathbb{R}^N , K(\bf{x,x'}) \;\mathrm{=(\bf{x,x'} \mathrm{\;+ \;c})^d}} \tag{6.3} \]

• 多項式カーネルは入力空間を次元 \({N+d \choose d}\) の高次元空間に写像する（演習6.12参照）

  • (例) 次元 \(N = 2\) の入力空間に対して、2 次の多項式 (d = 2) は，次元 6 の次の内積に対応する

\[ \forall \bf{x,x'} \mathrm{\in \mathbb{R}^2 , K(\bf{x,x'}) \mathrm{\;=\;(x_1x_1' + x_2x_2'+\;c})^2 =\left[\begin{array}{ccc} x_1^2 \\ x_2^2 \\ \sqrt{2}\:x_1x_2 \\ \sqrt{2c}\:x_1 \\ \sqrt{2c}\:x_2 \\ c \end{array} \right] \cdot \left[\begin{array}{ccc} x_1'^2 \\ x_2'^2 \\ \sqrt{2}\:x_1'x_2' \\ \sqrt{2c}\:x_1' \\ \sqrt{2c}\:x_2' \\ c \end{array} \right] } \tag{6.4} \]

• このように、2次多項式に対応する特徴量は
  元の特徴量（\(x_1\) と \(x_2\)）、これらの特徴量の積、および定数特徴量である

• より一般的には、次数 \(d\) の多項式カーネルに対応する特徴は、元の特徴に基づいたせいぜい次数 \(d\) のすべての単項式である

• (6.4)のように多項式カーネルを内積として明示的に表現することで、それらがPDSカーネルであることが直接証明される

Example (Figure 6.3)

多項式カーネルの応用を説明するために、図6.3aの例を考えてみる
これは2次元の単純なデータ集合で、線形に分離できないものを示している
排他的論理和（XOR）関数の観点から解釈すると、XOR問題として知られている：点のラベルは、その座標のうちの1つが正確に1であれば青色である しかし、これらの点を(6.4)で述べたように2次多項式で定義された6次元空間に写すと、問題は式 \(x_1x_2 = 0\) の超平面で分離可能になる
図6.3bは、これらの点を3番目と4番目の座標で定義された2次元空間に投影したもの

図6.3 : XOR分類問題と多項式カーネルの使用の説明
(a) 入力空間で線形的に分離不可能なXOR問題 (b) 2次多項式カーネルを用いて線形に分離可能

Example 6.5 (Gaussian kernels)

任意の定数 \(\sigma >0\) について、ガウシアンカーネルまたは動径基底関数 (RBF) は、\(\mathbb{R}^N\) 上で以下の(6.5)式のように定義されたカーネル \(K\) である

\[ \forall \bf{x,x'} \mathrm{\in \mathbb{R}^N , K(\bf{x,x'}) \;\mathrm{=exp\left(- \frac{||\bf{x'-x}||\mathrm{^2}}{2\sigma^2} \right) }} \tag{6.5} \]

ガウシアンカーネルは、応用で最も頻繁に使用されるカーネルの一つ

6.2.3節で、カーネル \(K′：(\bf{x,x′}\)\()\rightarrow exp\left( \frac{\bf{x'\cdot x}}{\sigma^2} \right)\) で正規化することにより、ガウシアンカーネルがPDSカーネルであると導出できることを証明する

Example 6.6 (Sigmoid kernels)

任意の実数 \(a, b ≥ 0\) について、シグモイドカーネルは、\(\mathbb{R}^N\) 上で以下の(6.6)式のように定義されたカーネル \(K\) である

\[ \forall \bf{x,x'} \mathrm{\in \mathbb{R}^N , K(\bf{x,x'}) \;\mathrm{=tanh\left(a(\bf{x'-x}\mathrm)+b \right) }} \tag{6.6} \]

SVMでシグモイドカーネルを使用することは、シグモイド関数を介して定義されることが多い単純なニューラルネットワークに基づく学習アルゴリズムと密接に関連したアルゴリズムを導く

\(a < 0\) または \(b < 0\) の場合、カーネルはPDSではなく、対応するニューラルネットワークは凸最適化の収束保証の恩恵を受けない(演習6.18参照)

6.2.2 Reproducing kernel Hilbert space

ここではPDSカーネルの重要な性質である、ヒルベルト空間の内積を誘導することを証明する この証明には以下の補題を利用する

Lemma 6.7 (Cauchy-Schwarz inequality for PDS kernels)

\(K\) をPDSカーネルとする。すると，任意の \(x,x′\in \mathcal{X}\) において以下の(6.7)式が成り立つ

\[ K(x,x')^2 \leq K(x,x)K(x',x') \tag{6.7} \]

Proof
行列 \(\bf{K} = \left( \begin{array}{ccc} K(x,x) & K(x,x') \\ K(x',x) & K(x',x') \\ \end{array} \right)\) を考えてみる

定義により、\(K\) がPDSであれば、\(\bf K\) はすべての \(x, x'∈\mathcal X\) に対してSPSDである

特に\(\bf K\) の固有値の積 \(det(\bf K\mathrm)\) は非負でなければならない
したがって、\(K(x', x) = K(x, x')\) を用いて証明を締めくくる以下の等式が得られる

\[ det(\bf K\mathrm) = K(x,x)K(x',x')\ - K(x,x')^2 \geq 0 \]

Theorem 6.8 (Reproducing kernel Hilbert space (RKHS) )

\(K : \mathcal{X} × \mathcal{X} → \mathbb{R}\) を PDS カーネルとすると、ヒルベルト空間 \(\mathbb{H}\) (定義A.2参照) と\(\mathcal{X}\) から \(\mathbb{H}\) への写像 \(Φ\) が存在し、そのような写像 \(Φ\) は以下の(6.8)式を満たす

\[ \forall x,x' \in \mathcal{X},\: K(x,x') = \langle \Phi \mathrm(\mathit x),\Phi \mathrm(\mathit x') \rangle \tag{6.8} \]

さらに、\(\mathbb{H}\) はreproducing property (再生性) と呼ばれる以下の性質を持つ

\[ \forall h\in\mathbb{H},\;\forall x \in \mathcal{X},\:h(x) = \langle h,K(x,\cdot)\rangle \tag{6.9} \]

\(\mathbb{H}\) は \(K\) に関連付けられた再生核カーネルヒルベルト空間(Reproducing Kernel Hilbert Space : RKHS)と呼ばれる

Proof

任意の \(x ∈\mathcal X\) について、以下を満たすような \(Φ(x) : \mathcal X \rightarrow \mathbb{R}^\mathcal{X}\) を定義する

\[ \forall x,x' \in \mathcal{X},\: \Phi \mathrm(\mathit x)\Phi \mathrm(\mathit x') = \mathit{K \mathrm(\mathit{x,x'})} \]

このような関数 \(Φ(x)\) の有限線形結合の集合として \(\mathbb H_0\)を定義する

\[ \mathbb H_0 = \left\{\sum_{i \in I}a_i\Phi(x_i): a_i \in \mathbb{R},x_i \in \mathcal{X},|I|<\infty \right\} \]

ここで \(f = \sum_{i \in I}a_i\Phi(x_i),g = \sum_{j \in J}b_j\Phi(x'_j)\) とする全ての \(\forall f,g \in \mathbb H_0\) において、以下のように定義される \(\mathbb H_0 \times \mathbb H_0\) 上の 演算 \(\langle -,-\rangle\) を導入する

\[ \langle f,g \rangle = \sum_{i \in I,j \in J}a_ib_jK(x_i,x'_j) = \sum_{j \in J}b_jf(x'_i) = \sum_{i \in I}a_ig(x_i) \]

定義により、\(\langle -,-\rangle\)は対称である。最後の2つの式 \(\left(\sum_{j \in J}b_jf(x'_i) = \sum_{i \in I}a_ig(x_i)\right)\) は、\(\langle f,g \rangle\) が \(f\) と \(g\) の特定の表現に依存しないことを示し、\(\langle -,-\rangle\) が双線形 (bilinear) であることも示している

さらに、\(K\) はPDSなので、\(\forall f = \sum_{i \in I}a_ig(x_i)∈\mathbb H_0\) において、

\[ \langle f,f \rangle = \sum_{i,j \in I}a_ia_jK(x_i,x_j) \geq 0 \]

したがって、\(\langle -,-\rangle\) は正の半正定値双線形である。この不等式は、\(\langle -,-\rangle\) の双線形性を用いて、\(f_1,...,f_m\) と \(c_1,...,c_m∈\mathbb R\)において、以下の不等式が成り立つことをより一般的に暗示している

\[ \sum^{m}_{i,j = 1}c_i,c_j\langle f_i,f_j\rangle = \left\langle \sum^{m}_{i = 1}c_if_i,\sum^{m}_{j = 1}c_jf_j \right\rangle \geq 0 \]

したがって、\(\langle -,-\rangle\) は \(\mathbb H_0\) 上のPDSカーネルである
よって、任意の \(f∈\mathbb H_0\) と任意の \(x∈\mathcal X\) について、補題6.7により以下のように書くことができる

\[ \left\langle f,\Phi(x) \right\rangle \leq \left\langle f,f \right\rangle \left\langle \Phi(x),\Phi(x) \right\rangle \]

さらに、\(\langle -,-\rangle\) の再生性を観察する
\(\forall f = \sum_{i \in I}a_ig(x_i)∈\mathbb H_0\) において、\(\langle -,-\rangle\) の定義より、

\[ \forall x \in \mathcal X, \; f(x) = \sum_{i \in I}a_iK(x_i,x) = \left\langle f,\Phi(x) \right\rangle \tag{6.10} \]

したがって、\(\forall x ∈ \mathcal X,\:\left[f(x)\right]^2 ≤ \langle f,f\rangle K(x,x)\) は、\(\langle -,-\rangle\) の定値性を示す

このことは、\(\langle -,-\rangle\) が \(\mathbb H_0\) 上に内積を定義していることを意味し、それによって \(\mathbb H_0\) は前ヒルベルト空間となる

\(\mathbb H_0\) は標準的な構成に従って、稠密 (ちゅうみつ) なヒルベルト空間 \(\mathbb H\) を形成するために完備化されうる

また、Cauchy-Schwarzの不等式により、任意の \(x ∈\mathcal X\) に対して、\(f \mapsto \langle f,Φ(x)\rangle\)はリプシッツであり、したがって連続である

よって、\(\mathbb H_0\) が\(\mathbb H\) の中で稠密なので、再生性 (6.10) も\(\mathbb H\) 上で保持される (Q.E.D)

Note

• PDSカーネル \(K\) に対して定理の証明で定義されたヒルベルト空間 \(\mathbb H\)は、\(K\) に関連付けられた再生核カーネルヒルベルト空間 (Reproducing Kernel Hilbert Space : RKHS) と呼ばれる

• \(\forall x,x'∈\mathcal X\) に対して \(K(x,x')\) を持つ \(Φ:\mathcal X \rightarrow \mathbb H\) が存在するような任意のヒルベルト空間 \(\mathbb H\)は、\(K\) に関連付けられた特徴空間 (feature space)と呼ばれ、\(Φ\) は特徴写像 (feature mapping) と呼ばれる

• \(K\) に関連付けられた特徴空間は一般的に一意ではなく、異なる次元を持つことがあることに注意

  • 実際には、\(K\) に関連付けられた特徴空間の次元を参照するとき、明示的に記述された特徴写像に基づく特徴空間の次元を参照するか、K に関連付けられた RKHS の次元を参照する

• 定理6.8はPDS カーネルを用いて特徴空間または特徴ベクトルを暗黙的に定義することができることを示唆している

• 前章で述べたように、学習の成功において特徴量が果たす役割は非常に重要である

• 乏しい特徴量では、目標ラベルとの関連性がなく、学習は非常に困難になるか不可能になる可能性がある

• 対照的に、優れた特徴はアルゴリズムに非常に貴重な手がかりを与える可能性がある

• したがって、PDSカーネルを用いた学習と固定入力空間の場合、有用な特徴を求めるという問題は、有用なPDSカーネルを見つけるという問題に置き換わる

  • 標準的な学習問題では特徴がタスクに関するユーザの事前知識を表すのに対し、ここではPDSカーネルがこの役割を果たす
    →タスクに対する適切なPDSカーネルの選択が非常に重要になる

6.2.3 Properties

• PDS カーネルのいくつかの重要な特性を紹介

  • まず、PDS カーネルが正規化できること、そして、正規化されたカーネルも PDS であることを示す

  • そして、PDS カーネルのいくつかの重要な閉性 (closure properties) を証明する
    これは、より単純なカーネルから複雑な PDS カーネルを構築するために用いることができる
    (与えられた集合の演算がその集合上で閉性（へいせい、英: closure property; 包性）を持つとは、その集合の元に対して演算を施した結果がふたたびもとの集合に属することを言う。複数の演算からなる集まりが与えられた場合も、それら演算の族に関して閉じているとは、それが個々の演算すべてに関して閉じていることを言う
    例)自然数全体の成す集合は、加法について閉じているが減法について閉じていない。整数全体の成す集合は、乗法について閉じているが除法について閉じていない)

任意のカーネル \(K\) に対して、以下の(6.11)式で定義された正規化カーネル (normalized kernel) \(K'\)を関連付けることができる

\[ \forall x,x' \in \mathcal X, \; K'(x,x') = \begin{cases} 0 & \left( K(x,x) = 0 \right) \cup \left( K(x',x') = 0 \right)\\ \frac{K(x,x')}{\sqrt{K(x,x)K(x',x')}} & (otherwise) \end{cases} \tag{6.11} \]

正規化カーネル \(K′\) の定義より、\(K(x, x) ≠ 0\) となるような\(\forall x ∈\mathcal X\) について、\(K'(x, x) = 1\) となる

正規化カーネルの例は、パラメータ \(σ > 0\) のガウシアンカーネルであり、これは、\(K'：(\bf{x,x'}\mathrm) \mapsto\mathit {exp\left(\frac{\bf x \cdot x'}{\sigma^2}\right)}\) に関連付けられた正規化カーネルである

Lemma 6.9 (Normalized PDS kernels)

KをPDSカーネルとすると、\(K\) に関連付けられた正規化カーネル \(K'\) はPDSである

Proof
\({x_1,\ldots,x_m} ⊆ \mathcal X\) とし、\(c\) を \(\mathbb R^m\) の任意のベクトルとする

和 \(\sum^{m}_{i,j = 1}c_ic_jK'(x_i,x_j)\) が非負であることを示す

補題6.7より、\(K(x_i, x_i) = 0\) であれば \(K(x_i,x_j) = 0\) であるので、したがって、\(\forall j ∈[1,m]\) について \(K'(x_i,x_j) = 0\) である

したがって、\(i∈[1,m]\) に対して \(K(x_i,x_i)>0\) と考えることができる

すると、和は次のように書きかえることができる
ここで \(Φ\) は定理6.8によって \(K\) に関連付けられた特徴写像であり、\(\|\cdot\|_{\mathbb H}\) を特徴空間 \(\mathbb H\) の内積によって誘導されるノルムである (例：\(\forall w \in \mathbb H,\;\|\bf w\|_{\mathbb H} = \sqrt{\langle \bf w,w \rangle}\))

\[ \sum^{m}_{i,j = 1}\frac{c_ic_jK(x_i,x_j)}{\sqrt{K(x_i,x_i)K(x_j,x_j)}} =\sum^{m}_{i,j = 1}\frac{c_ic_j \left\langle\Phi(x_i),\Phi(x_j)\right\rangle}{||\Phi(x_i)||_{\mathbb H}||\Phi(x_j)||_{\mathbb H}} = \left\|\sum^{m}_{i}\frac{c_i\Phi(x_i)}{\|\Phi(x_i)\|_{\mathbb H}}\right\|^2_{\mathbb H} \geq 0 \]

したがって正規化カーネル \(K'\) はPDSであることが示された (Q.E.D)

Theorem 6.10 (PDS kernels — closure properties)

PDS カーネルは、和、積、テンソル積、点極限(?)、およびすべての \(n∈\mathbb N\) に対して \(a_n≧0\) のべき級数 \(\sum^{\infty}_{n = 0}a_nx^n\) との合成の下で閉じている

Proof

任意の \(m\) 点の集合に対するPDSカーネル \(K\) と \(K'\) から生成された2つのカーネル行列 \(\bf K\) と\(\bf K'\)から始める

前提として、これらのカーネル行列はSPSDである

任意の \(\bf{c} \mathit{∈\mathbb R^{m×1}}\) に対して、以下のようになることを観察する

\[ (\bf{c^\top Kc}\ge \mathrm{0}) \cap (\bf{c^\top K'c}\ge \mathrm{0})\Rightarrow \bf{c^\top (K+K')c}\ge \mathrm{0} \]

(6.2)式より、これは \(K + K'\) が SPSD であり、したがって \(K + K'\) が PDS であることを示す

積の下での閉性を示すために、任意のSPSD行列 \(\bf K\) に対して、\(\bf K = MM^\top\)となるような \(\bf M\) が存在するという事実を用いる

\(\bf M\) の存在は例えば、\(K\) の特異値分解やコレスキー分解によって生成できるため、保証されている

\(KK'\) に関連するカーネル行列は \((\bf K_{\mathit {ij}}K'_{\mathit {ij}})_{\mathit {ij}}\) である

任意の \(\bf{c}∈\mathbb R^{\mathit m×\mathrm 1}\) に対して、\(\bf K_{\mathit {ij}}\)を\(\bf M\)の要素で表現すると、\(\bf z_\mathit k = \left[\begin{matrix} c_1 \bf M_{\mathrm{1k}} \\ \vdots \\ c_m \bf M_{\mathrm{mk}} \end{matrix}\right]\) を用いて次のように書くことができる

\[ \begin{aligned} \sum^{m}_{i,j = i}c_ic_j(\bf K_{\mathit {ij}}K'_{\mathit {ij}}) &= \sum^{m}_{i,j = i}c_ic_j\left( \left[\sum^m_{k = 1}\bf M_{\mathit {ik}}M_{\mathit {jk}}\right]\bf K'_{\mathit {ij}}\right)\\ &= \sum^m_{k = 1}\left[\sum^{m}_{i,j = i}c_ic_j\bf M_{\mathit {ik}}M_{\mathit {jk}}\bf K'_{\mathit {ij}}\right]\\ &= \sum^m_{k = 1}\bf z_k^\top K'z_k \ge \mathrm0 \end{aligned} \]

これはPDSカーネルが積の下で閉じていることを示している

\(K\) と \(K'\) のテンソル積は、2つのPDSカーネル \((x_1,x'_1,x_2.x'_2) \mapsto K(x_1,x_2)\) と、\((x_1,x'_1,x_2.x'_2) \mapsto K'(x'_1,x'_2)\) の積としてPDSとなる

次に、\((K_n)_{n∈\mathbb N}\) を、点極限 \(K\) を持つPDSカーネルの列とする

\(\bf K\) を \(K\) に関連付けられたカーネル行列とし、\(\bf K_n\) を\(\forall n∈\mathbb N\) について \(K_n\)に関連付けられたものの1つとすると、

\[ (\forall n,\bf c^\top K_nc \ge \mathrm 0) \Rightarrow \lim_{n \rightarrow \infty}\bf c^\top K_nc \mathrm= \bf c^\top K_nc \ge \mathrm 0 \]

これは、点極限の下での閉性を示している

最後に、\(\forall x,x'∈\mathcal X\) に対して、\(K\) が \(|K(x,x')|<\rho\) であるPDSカーネルであると仮定し、\(f : x \mapsto \sum^{\infty}_{n = 0}a_nx^n, a_n ≥0\) を収束半径 (radius of convergence) \(\rho\) を持つべき級数とすると、\(n∈\mathbb N\)について、\(K^n\) と \(a_nK^n\) は積の下の閉包によるPDSである

\(\forall N∈\mathbb N\) について、\(\sum^{N}_{n =0}a_nK^n\) は \(a_nK^n\) らの和の下の閉性によるPDSであり、\(f ◦K\)はNが無限に傾くにつれて、\(\sum^{N}_{n =0}a_nK^n\) の極限の下の閉性によるPDSである (Q.E.D)

例：expの収束半径が無限大であるため、任意のPDSカーネル \(K\) に対して \(exp(K)\) はPDSであることをこの定理は暗示している

SVMs with PDS kernels

• 第5章では、SVMの双対最適化問題や解の形式が入力ベクトルに直接依存せず、内積のみに依存することを議論した

• PDS カーネルは暗黙的に内積を定義する（定理 6.8）ので、SVM を拡張し、内積 \(x \cdot x'\) の各インスタンスを \(K(x,x')\) に置き換えることで、任意の PDS カーネル \(K\) とSVMを組み合わせることができる

• これは、PDSカーネルを用いて(5.33)式を拡張したSVM最適化問題と解の以下の一般的形 (general form) につながる

\[ \max_{\bf \alpha}\sum^{m}_{i = 1}\alpha_i-\frac{1}{2}\sum^{m}_{i,j = 1}\alpha_i\alpha_jy_iy_jK(x_i,x_j)\\ \mathrm{subject \;to \;}0\mathit{\le\alpha_i\le C \cap \sum^{m}_{i = 1}\alpha_iy_i }= 0,\mathit{i} \in [1,m] \tag{6.13} \]

• (5.34)式を考慮すると、仮説hの解は \(0 < α_i < C\) の \(\forall x_i\)について、\(b = y_i - \sum^{m}_{j = 1}α_jy_jK(x_j,x_i)\)とおくと、以下の(6.14)式のように書くことができる

\[ h(x) = sgn\left(\sum^m_{i = 1}\alpha_iy_iK(x_i,x)+b\right)\tag{6.14} \]

6.3.2 Representer theorem

オフセット \(b\) のモジュロ (剰余演算, mod) では、SVMの仮説解は、関数 \(K(x_i,\cdot)\) の線形結合として書けることに注目する
ここで \(x_i\) はサンプル点である

Representer定理として知られる次の定理は、これが実際にはオフセットのないSVMを含む幅広いクラスの最適化問題に適用される一般的な性質であることを示している

Theorem 6.11 (Representer theorem)

\(K : \mathcal X × \mathcal X → \mathbb R\) を PDS カーネル、\(\mathbb H\) を対応する RKHS とすると、非減少関数 \(G：\mathbb R → \mathbb R\) と損失関数 \(L：\mathbb R^m → \mathbb R ∪{+∞}\) の場合、以下の最適化問題の解は \(h^∗ = \sum^m_{i = 1}α_iK(x_i,\cdot)\) としかならない

\[ \newcommand{\argmin}{\mathop{\mathrm arg~min}\limits} \argmin_{h \in \mathbb H} F(h) = \argmin_{h \in \mathbb H} G(\|h\|_{\mathbb H}) + L\left(h(x_1),\dots,h(x_m)\right) \]

\(G\) がさらに増加すると仮定すると、任意の解はこの形式を持つ

Proof
\(\mathbb H_1 = span({K(x_i,\cdot): i ∈[1,m]})\) とする (\(\mathbb H_1\) は \(K(x_i,\cdot)\) が張る空間を指す)

任意の \(h ∈ \mathbb H\) は、\(\mathbb H=\mathbb H_1⊕\mathbb H_1^\bot\) に従って、\(h=h_1+h^\bot\) の分解を認める。ここで、\(⊕\) は直和 (direct sum)である

\(G\) は非減少 (non-decreasing)なので、\(G\left(\|h_1\|_{\mathbb H}\right) \le G\left(\sqrt{\|h_1\|_{\mathbb H}^2+\|h^\bot\|_{\mathbb H}^2}\right) = G(\|h\|_{\mathbb H})\) となる

再生性により、\(\forall i ∈ [1,m]\) に対して、\(h(x_i) = \langle h, K(x_i, \cdot)\rangle = \langle h_1, K(x_i, \cdot)\rangle = h_1(x_i)\) となる

したがって、\(L\left(h(x_1), ... , h(x_m)\right) = L\left(h_1(x_1), . , h_1(x_m)\right)\) となり、\(F(h_1) ≤ F(h)\) となる

これにより、定理の最初の部分が証明される

Gがさらに増加する場合、\(\|h^\bot \|_{\mathbb H} >0\) のとき、\(F (h_1 ) < F (h)\) となり、最適化問題の解はすべて \(\mathbb H_1\) にしかならない (Q.E.D)

6.3.3 Learning guarantees

ここでは、PDS カーネルに基づいた仮説集合に対する汎化学習保証を提示する

次の定理6.12は、ノルムが制限されたカーネルベースの仮説の経験ラデマッハ複雑度に一般的な境界を与える
これはある \(Λ≧0\) において、\(\mathcal H = \left\{h \in \mathbb H:\|h\|_{\mathbb H}\le\Lambda\right\}\) の形式の仮説集合である ここで、\(\mathbb H\) はカーネル \(K\) に関連付けられた RKHS である

再生性により、任意の \(h∈\mathcal H\) は、\(x \mapsto \langle h, K(x, \cdot)\rangle = \langle h, Φ(x)\rangle\) の形式で、\(\|h\|_{\mathbb H} ≤ Λ\) をもつ ここで、\(Φ\)は、\(K\) に関連付けられた特徴写像であり、それは、\(x\mapsto \langle \bf{w},\mathrm Φ(\mathit x)\rangle\) の形式で、\(\|\bf w\|_{\mathbb H} ≤ Λ\) をもつ

Theorem 6.12 (Rademacher complexity of kernel-based hypotheses)

\(K : \mathcal X × \mathcal X → \mathbb R\) を PDS カーネルとし、\(Φ:\mathcal X → \mathbb H\) を \(K\) に関連付けられた特徴写像とする

\(S ⊆ \left\{x:K(x,x)≤r^2\right\}\) を大きさ \(m\) の標本とし、ある \(Λ≧0\) において \(\mathcal H = \left\{x \mapsto \langle \bf{w},\mathrm Φ(\mathit x)\rangle:\;\|\bf w\|_{\mathbb H} ≤Λ\right\}\) とすると、

\[ \hat{\mathfrak R}_S(\mathcal H) \le\frac{\Lambda\sqrt{\mathrm{Tr}[\bf K]}}{m}\le\sqrt{\frac{r^2\Lambda^2}{m}}\tag{6.16} \]

Proof

この定理は、カーネル行列のトレースがカーネルに基づく仮説集合の複雑さを制御するための重要な量であることを示している

Definition 6.14 (Negative definite symmetric (NDS) kernels )

カーネル \(K : \mathcal X × \mathcal X → \mathbb R\) が対称であり、\(\{x_1,...,x_m\} \subseteq \mathcal X\) と \(1^\top \bf c \mathrm = 0\) となる \(\bf{c} ∈\mathbb R^{\mathrm m×1}\) において以下のような場合、そのカーネルは負定値対称 (NDS) であると言われる

\[ \bf c^\top Kc \mathrm \le 0 \]

明らかに、\(K\) がPDSならば\(-K\)はNDSであるが、一般的には逆は成り立たない

以下にNDSカーネルの標準的な例を示す

Example 6.15 (Squared distance — NDS kernel)

\(\mathbb R^N\) における二乗距離 \((x, x') \mapsto \|x'-x\|^2\) はNDSカーネルを定義する

\(\bf c ∈ \mathbb R^{\mathrm m×1}\) で \(\sum^m_{i = 1}c_i = 0\) とする

すると、任意の \(\{x_1,...,x_m\} ⊆\mathcal X\) について、以下のように書くことができる

\[ \begin{aligned} \sum^m_{i,j = 1} c_ic_j\|\bf x_{\mathit i} -x_{\mathit j}\|^\mathrm 2 &= \sum^{\mathit m}_\mathit{i,j \mathrm = 1}c_ic_j\left(\bf x_{\mathit i} - x_{\mathit j}\right)\cdot\left(\bf x_{\mathit i} - x_{\mathit j}\right)\\ &= \sum^{\mathit m}_\mathit{i,j \mathrm = 1}\mathit c_ic_j\left(\|\bf x_{\mathit i}\|^{\mathrm 2} + \|\bf x_{\mathit j}\|^{\mathrm 2} -\mathrm 2\bf x_{\mathit i} \cdot x_{\mathit j}\right)\\ &= \sum^{\mathit m}_\mathit{i,j \mathrm = 1}\mathit c_ic_j \left(\|\bf x_{\mathit i}\|^{\mathrm 2} + \|\bf x_{\mathit j}\|^{\mathrm 2}\right) - 2\sum^m_{i = 1}c_i\bf x_{\mathit i}\cdot\sum^{\mathit m}_{\mathit j \mathrm = 1}c_\mathit j\bf x_{\mathit j}\\ &= \sum^{\mathit m}_\mathit{i,j \mathrm = 1}\mathit c_ic_j \left(\|\bf x_{\mathit i}\|^{\mathrm 2} + \|\bf x_{\mathit j}\|^{\mathrm 2}\right) - 2\left\|\sum^m_{i=1}c_i\bf x_{\mathit i}\right\|^2 \\ &\le \sum^m_{i,j = 1}c_ic_j \left(\|\bf x_{\mathit i}\|^{\mathrm 2} + \|\bf x_{\mathit j}\|^{\mathrm 2}\right)\\ &= \left(\sum^m_{j = 1}c_j\right)\left(\sum^m_{i = 1}c_i\|\bf x_{\mathit i}\|^2\right) + \left(\sum^m_{i = 1}c_i\right)\left(\sum^m_{j = 1}c_j\|\bf x_{\mathit j}\|^2\right)\\ &= 0 \end{aligned} \]

次の定理はNDS カーネルと PDS カーネルの関係を示す

これらの結果はPDSカーネルを設計するための別の一連のツールを提供する

Theorem 6.16

\(K'\) を \(\forall x_0\) について \(\forall x,x' \in \mathcal X,\;K'(x, x') = K(x, x_0) + K(x', x_0) - K(x, x') - K(x_0, x_0)\) によって定義されるとすると、\(K\) はNDSであることと、\(K'\) がPDSであるは同値 (iff) である

Proof

\(K'\) がPDSであるとし、\(\forall x_0\) について、\(K(x, x') = K(x, x_0)+K(x_0, x')-K(x_0, x_0)-K'(x, x')\) を持つような \(K\) を定義する

そして、\(\bf c^\top1 \mathrm= 0\) となるような \(\forall \bf c\in\mathbb R^{\mathit m}\) と、任意の点の集合 \((x_1,...,x_m)∈\mathcal X^m\) において、以下のように \(K\) がNDSであることを証明する

\[ \begin{aligned} \sum^m_{i,j = 1}c_ic_jK(x_i,x_j) &= \left(\sum^m_{i = 1}c_iK(x_i,x_0)\right)\left(\sum^m_{j = 1}c_j\right) + \left(\sum^m_{i = 1}c_i\right)\left(\sum^m_{j = 1}c_jK(x_0,x_j)\right) - \left(\sum^m_{i = 1}c_i\right)^2K(x_0,x_0) - \sum^m_{i,j = 1}c_ic_jK'(x_i,x_i)\\ &= -\sum^m_{i,j = 1}c_ic_jK'(x_i,x_j)\\ &\le 0 \end{aligned} \]

ここで\(K\) がNDSであると仮定し、\(\forall x_0\) について \(K′\) を定義する

そして、\(c_0 = -\bf c^\top1\) となるような \(\forall \bf c\in\mathbb R^{\mathit m}\) と、先に定義した \(x_0\) と同様に任意の点 \((x_1,...,x_m)∈\mathcal X^m\) において次のようにNDSの性質を保持する： \(\sum^m_{i,j=0} c_ic_j K(x_i,x_j) ≤ 0\)

これは、以下を意味する

\[ \begin{aligned} \sum^m_{i,j = 0}c_ic_jK(x_i,x_j) &= \left(\sum^m_{i = 0}c_iK(x_i,x_0)\right)\left(\sum^m_{j = 0}c_j\right) + \left(\sum^m_{i = 0}c_i\right)\left(\sum^m_{j = 0}c_jK(x_0,x_j)\right) - \left(\sum^m_{i = 0}c_i\right)^2 K(x_0,x_0) - \sum^m_{i,j = 0}c_ic_jK'(x_i,x_i)\\ &= -\sum^m_{i,j = 0}c_ic_jK'(x_i,x_j)\\ &= -\sum^m_{i,j = 1}c_ic_jK'(x_i,x_j) - c_0\sum^m_{i= 0}c_iK'(x_i,x_0) - c_0\sum^m_{j= 0}c_jK'(x_j,x_0) - c_0^2K'(x_0,x_0)\\ &\le 0 \end{aligned} \]

この式は、\(2 \sum^m_{i,j = 1}c_ic_j K'(x_i, x_j) ≥ -2c_0 \sum^m_{i = 0}c_iK'(x_i, x_0) + c^2_0K'(x_0, x_0) = 0\) を意味する

\(∀x∈\mathcal X, K'(x, x_0) = 0\)なので、この等式は成立する (証明終了)

6.5.1 Weighted transducers

シーケンスカーネルはWeighted transducers を用いて効果的に表現し、計算することができる

以下の定義において、\(Σ\) は有限の入力アルファベット、\(∆\) は有限の出力アルファベット、\(\epsilon\) は空の文字列または null label を表し、それらは任意の文字列と連結しても変更されない

Definition 6.19

Weighted transducer \(T\) は、\(\mathit 7\) -タプル (組) \(T = (Σ, ∆, Q, I, F, E, \rho)\) である

• \(Σ\) は有限の入力アルファベット
• \(∆\) は有限の出力アルファベット
• \(Q\) は状態の有限集合
• \(I⊆Q\) は初期状態の集合
• \(F⊆Q\) は最終状態の集合
• \(E\) は \(Q×\left(Σ∪\{\epsilon\}\right)×\left(Σ∪\{\epsilon\}\right) ×\mathbb R×Q\) の遷移要素の有限多集合
• \(\rho : F \rightarrow \mathbb R\) は\(F\) を \(\mathbb R\) に写像する最終重み関数

transducer \(T\) の大きさは、その状態数と遷移数の合計であり、\(|T|\) で示される

つまり、Weighted transducers とは、各遷移に入力と出力の両方のラベルを付け、実数値の重みを持たせた有限オートマトンのことである

下図にweighted finite-state transducer (重み付き有限状態 transducer) の例を示す

• この図では、遷移の入力ラベルと出力ラベルをコロンで区切り、重みをスラッシュで区切って示している

• 初期状態は太い円で、最終状態は二重の円で表されている

• 最終状態 \(q\) での最終重み \(ρ[q]\) はスラッシュの後に表示される

• パス \(π\) の入力ラベルは、\(π\) に沿って入力ラベルを連結して得られる文字列要素 \(Σ^∗\) である

• 同様に、パス \(π\) の出力ラベルは、出力ラベルを \(π\) に沿って連結して得られる

• 初期状態から最終状態へのパスを accepting path という

• accepting path の重みは、そのパスを構成する遷移の重みと、パスの最終状態の重みを掛け合わせて得られる

• weighted transducer は、\(Σ^∗ × ∆^∗\) から \(\mathbb R\) への写像を定義する

• weighted transducer \(T\) が文字列のペア \((x, y) ∈Σ^∗ × ∆^∗\) に関連付ける重みを \(T(x,y)\) と表し、入力ラベル \(x\) と出力ラベル \(y\) を持つすべての accepting path の重みを合計して得られる

  • 例えば、図6.4の transducer では、入力ラベル \(aab\) と出力ラベル \(baa\) を持ち、重みが \(3×1×4×2\) のパスと、重みが \(3×2×3×2\) のパスをもつので、\((aab,baa)\) のペアに3×1×4×2+3×2×3×2の重みを与えている

6.5.2 Rational kernels

以下では、シーケンスカーネルの定義に関する一般的な枠組みを確立する

Definition 6.20 (Rational kernels)

1. カーネル \(K : Σ^∗ × Σ^∗ → \mathbb R\) は、ある weighted transducer \(U: \forall x,y ∈ Σ^∗,K(x,y) = U(x,y)\) によって定義される写像と一致する場合、rational (有理である) という

2. \(T_1:\Sigma^* \times \Delta^* \rightarrow \mathbb R\) と \(T_2:\Delta^* \times \Omega^* \rightarrow \mathbb R\) の2つをweighted transducers とすると、\(T_1\) と \(T_2\) の composition (合成) は以下のように定義される

\[ \forall x\in \Sigma^*,\forall y \in \Omega^*,\:(T_1 \circ T_2)(x,y) = \sum_{z \in \Delta^*} T_1(x,z)T_2(z,y) \]

3. transducer \(\forall T:\Sigma^* \times \Delta^* \rightarrow \mathbb R\) について，\(T\) の逆写像を \(T^{-1} : \Delta^* \times \Sigma^* \rightarrow \mathbb R\) とすると，これは \(T\) から各遷移の入力ラベルと出力ラベルを入れ替えて得られる transducer である

\[ \forall x, y,\; T^{-1}(x, y) = T (y, x) \]

次の定理は、任意の weighted transducer からPDS rational kernel を構築する一般的な方法を与える

Theorem 6.21

任意の weighted transducer \(T = \left(Σ,∆,Q,I,F,E,ρ\right)\) において、関数 \(K = T ◦ T^{-1}\) は PDS rational kernel である

Proof
合成と逆写像の定義により、 \[ \forall x, y∈Σ^∗,\;K(x,y) = \sum_{z \in\Delta^*} T(x,z)T(y,z) \]

Kは次のように定義されるカーネル列 \((K_n)_{n \ge 0}\)の pointwise limit (点極限) である

\[ \forall n \in \mathbb N,\; \forall x,y \in \Sigma^*,\;\; K_n(x,y) = \sum_{|z|\le n}T(x,z)T(y,z) \]

ここで、和は長さが最大で \(n\) の \(∆^∗\) 内のすべての列に対して足し合わせられる

任意のサンプル \((x_1, ... , x_m)\) に対応するカーネル行列 \(\bf K_n\) はSPSDなので、\(K_n\) はPDSである

このように、\(K\) はPDSカーネル \(\left(K_n\right)_{n∈\mathbb N}\) の列の pointwise limit (点極限) としてPDSである (証明終了)

参考 (MLP サポートベクターマシン p79~)

• 教科書だけではなんとなくイメージしにくい (というかよくわからなかった) ので、MLP 『サポートベクターマシン』 (p79~) を参考にする

• ここでは、全部分列カーネル (all-subsequence kernel) を紹介

example all-subsequence kernel

• 文字列中のすべての部分列の出現回数に注目

  • ここで部分列 (subsequence) とは文字列の中で連続していないてもよい \(p\) 個の文字
  • 部分文字列 (substring) は、文字列の中で連続する \(p\) 個の文字

• 昇順に並んだ \(p\) 個の添字を \(\bf i \mathrm= \left(\mathit{i_\mathrm 1,\dots,\mathit i_\mathrm p}\right)\) \(\left(i_1<i_2<\dots<i_p\right)\) とし、その添字に対応する文字による文字列を \(\bf s_i\) とする

• ここで、特徴写像の要素を文字列 \(u\) を部分列としていくつ含んでいるかで定義する

\[ \phi_u(s) = \left|\left\{\bf i\;\mathrm|\mathit{u \mathrm= \bf s_i}\right\}\right| \]

任意の長さの文字列の集合を \(\mathcal A^* = \bigcup_{p＝0}^{\infty}\mathcal A^p\) と表記すると、全部分列カーネルの特徴写像は以下の式で表される

\[ \bf \phi\mathrm(s) = (\phi_u(\bf s\mathrm))_{u \in \mathcal A^*} \]

• 以下の表にこの特徴写像の例を示す