サポートベクターマシンとは［カーネル法による非線形サポートベクターマシン］
ここからはこれまで述べてきたサポートベクターマシンにカーネル法を適用することにより非線形サポートベクターマシンへ拡張することを考えます。
カーネル法の導入
これまで述べてきたサポートベクターマシーン分離面が超平面であることを前提としていました。しかし、実際の問題では正例データと負例データの境界が超平面であるよりは、複雑に入り組んだ超曲面である可能性が高いことが想定されます。
このようなデータに、これまで述べてきたようなクラス境界を超平面とするサポートベクターマシーンを適用しても、高い分類性能を期待することは難しそうです。
たとえば下図のような単純なケースでさえ正例データ（○）と負例データ（×）を分ける直線は存在しないため、１００％の分類性能は達成できません。
しかし、このようなデータでも線形分離が可能になるような別の空間へ変換できれば、変換先の空間ではクラス境界が超平面になるのでサポートベクターマシーンを用いることが可能になります（下図参照）。元のデータが存在する空間のことを入力空間、変換先の空間のことを特徴空間といいます。一般的に入力空間の次元$n$より特徴空間の次元$M$の方が大きくなります（同じ場合もあります）。実際にこのような写像の例をあとで示します。
入力空間のデータ$x$から特徴空間のデータ$z$へ写像する関数$\phi(x)$とすると$z$は
$$
\begin{align}
z&=(z_1,\ldots,z_M)^T\\
&=(\phi_1(x),\ldots,\phi_M(x))^T
\end{align}
$$
と表現できますので、変換後のデータ$z$に対してソフトマージンサポートベクターマシンを適用します。
特徴空間の例
ここで一旦話を中断し、入力空間では線形分離できないデータでも高次元の特徴空間に写像すると線形分離可能になる例を示しておきます。
下図のような２次元訓練データがあるとします。赤データを正例、緑データは負例としておきます。このデータを正例と負例に分割する直線が存在しないことは明らかです。しかし曲線であれば両クラスを分離する事ができます。図の黒い円（$x_1^2+x_2^2=1$）がその一例です。
ここで、２次元入力空間の各点$x=(x_1, x_2)$を３次元特徴空間の点$z=(z_1, z_2, z_3)$に写像する変換
$$
z=\phi(x_1, x_2)=(x_1^2, x_2^2, \sqrt{2}x_1x_2)
$$
を考えます。この写像$\phi$で図の黒い円上のデータを変換すると、３次元特徴空間の平面$w^Tz+b=0$の上に乗ることがわかります。実際$w=(1, 1, 0)^T, b=-1$とおいた場合の平面の式は$z_1+z_2+0z_3-1=x_1^2+x_2^2-1=0$となるからです。
実際にこの図のデータを関数$\phi$で３次元特徴空間に写像すると、下図のように赤データと緑データを平面で分離できるようになりました。この特徴空間でサポートベクターマシンを適用すれば１００％の分類精度が得られます。
YouTubeに入力空間から特徴空間への写像を説明した動画がありましたので紹介します。$\phi(x)$の関数形は上の例と異なるようですが、イメージ的には同じです。
特徴空間での定式化
話を戻して特徴空間でのソフトマージンサポートベクターマシンを構成しましょう（$x$を$z$に置き換えるだけです）。
特徴空間でのソフトマージンサポートベクターマシン
訓練データ
$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}$
と、特徴空間への写像$z=\phi(x)=(\phi_1(x),\ldots,\phi_M(x))$が与えられたとき、
$$
\begin{align}
\mathcal{F}&= \{(z_1, y_1), \ldots, (z_l, y_l)\}, (z_i, y_i) \in R^M \times \{-1, 1\},\\
z_i&=(\phi_1(x_i),\ldots,\phi_M(x_i))^T, i=1,\ldots,l
\end{align}
$$
は線形分離可能とします。次の最適化問題を解き、$\alpha$を求めす。
- 目的関数
$$
\sum_{i=1}^{k}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jz_i^Tz_j
$$
を制約条件のもとで$\alpha$に関して最小化制約条件：
$$
C \geqq \alpha_i\geqq 0, i=1,\ldots,k\\
\sum_{i=1}^{l}\alpha_iy_i=0
$$決定関数は
$$
\hat{f}(z) = \text{sgn}(\sum_{\mathcal{V}}\alpha_iy_iz_i^Tz + b)
$$
となります。ここで$b$は
$$
\begin{align}
b&=-\frac{1}{2}\sum_{\mathcal{V}}(\alpha_iy_iz_i^Tz_{+}+\alpha_iy_iz_i^Tz_{-})
\end{align}
$$
$\mathcal{V}$はサポートベクターの集合です。
さて、一般に特徴空間の次元$M$は入力空間の次元より高くなります。場合によっては$M=\infty$になることもあります。高次元になるほど内積$z^T_iz_j$の計算量は増加し、関連データを保持するためのメモリも増加していきます。
ためしに多項式写像によって特徴空間に変換されたデータを保持するために必要とされるメモリ量を帰納的に見積もってみます。
$$
\begin{align}
M&={}_dC_2\\
&=\frac{d!}{(d-2)!2!}\\
&=\frac{d(d-1)}{2}
\end{align}
$$
となります。
たとえば入力空間が１００次元（$d=100$）であれば、特徴空間の次元は約５０００次元($100\times(100-1)/2$)になります。入力データがテキストデータのときには入力空間の次元が数千～数万になることもあります。もし１万次元のデータを写像すると特徴空間の次元は５千万次元となります。
サポートベクターマシンを適用するまえに入力空間のデータを特徴空間に変換しておくと、訓練データ１件を保持するのに必要なメモリ量は約４００MB(50,000,000*8=400,000,000)になります。訓練データが１件ということはないので、あっという間にメモリが不足してしまいます。
このように特徴空間に明にデータを写像するような状況を回避するのがこれから述べるカーネル法です。
前述したサポートベクターマシンのアルゴリズムをよく見ると特徴空間でのデータ$z$はすべて内積として、すなわち$z_i^Tz_j=\phi^T(x_i)\phi(x_j)$として現れています。
実はカーネルと呼ばれる関数$K$を使えば、特徴空間での内積計算$\phi(x)^T\phi(y)$を回避できます。すなわち
$$
K(x,y)=\phi(x)^T\phi(y)
$$
とできます。ただ無条件にこのようなカーネルを構成できるのではなく、マーサー(Mercer)の条件を満たす必要があります（詳細は参考文献参照）。
また、カーネルを用いるメリットは特徴空間への写像$\phi(x)$の具体的な形がわからなくても内積が計算できます。さらに、高次元の特徴空間で内積を計算するのではなく、入力空間でカーネルを計算すればよいので計算量とメモリを大幅に削減できます。
特徴空間におけるサポートベクターマシンのアルゴリズムにあらわれる内積をすべてカーネルで置き換えてしまえば内積計算を回避できます。これをカーネルトリックと呼びます。カーネルトリックにより特徴空間での変数を陽に扱わない手法のことをカーネル法と呼びます。
訓練データ
$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}$
が与えられたとき、次の最適化問題を解き$\alpha$を求めます。
- 目的関数
$$
\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jK(x_i,x_j)
$$
を制約条件のもとで$\alpha$に関して最小化
- 制約条件
$$
C \geqq \alpha_i\geqq 0, i=1,\ldots,l\\
\sum_{i=1}^{l}\alpha_iy_i=0
$$決定関数は
$$
\hat{f}(x) = \text{sgn}(\sum_{\mathcal{V}}\alpha_iy_iK(x_i,x) + b)
$$
となります。ここで$b$は
$$
\begin{align}
b&=-\frac{1}{2}\sum_{\mathcal{V}}(\alpha_iy_iK(x_i, x_{+})+\alpha_iy_iK(x_i,x_{-}))
\end{align}
$$
$\mathcal{V}$はサポートベクターの集合です。
これで分類問題に対するサポートベクターマシンの最終形が完成しましました。
カーネルの例
サポートベクターマシンの特徴の一つは、解きたい問題に応じてカーネルを適切に選び汎化能力を向上できることです。実際、問題の種類に応じて様々なカーネルが開発されています。
ここでよく用いられるカーネル$K(x,x')$をいくつか紹介します。
- 線形カーネル
もとの訓練データが線形分離可能であればわざわざ特徴空間に写像する必要はないので、このような場合には次の線形カーネルを用いることにより実質的にはカーネル法を用いない線形のサポートベクターマシンになります。
$$
K(x,x')=x^Tx'
$$
テキストデータのように大規模で疎なデータ（ほとんどの列が０であるようなデータ）でよく用いられます。
- 多項式カーネル
次数を$d$とする多項式カーネルは次式で与えられます。パラメータ$d, scale, offset$はユーザーが指定する必要があります。
$$
K(x,x')=(scale \times x^Tx'+offset)^d
$$
画像を分類するときによく用いられます。なお$offset$は通常１とします。$d=1, scale=1, offset=0$とすれば線形カーネルとなります。
- ラジアル基底関数カーネル（RBFカーネル、ガウシアンカーネル）
ラジアル基底関数(RBF, radial basis function)カーネル（ガウシアンカーネルとも呼ばれます）は次式で与えられます。パラメータ$\sigma(>0)$はユーザーが指定します。
$$
K(x,x')=\exp(-\sigma||x-x'||^2)
$$
データに関する事前知識がない場合に用いられる汎用的なカーネルです。最もよく用いられるカーネルの一つです。
- 双曲線正接カーネル
双曲線正接カーネル(hyperbolic tangent kernel)は次式で与えられます。パラメータ$scale, offset$はユーザーが指定します。
$$
K(x,x')=\tanh(scale \times x^Tx'+offset)
$$
おもにニューラルネットワークの代わりとして用いられます。
この他にも文字列カーネルなど色々ありますが省略します。
最後に$K(x,y)=\phi(x)^T\phi(y)$となるカーネル$K$を実際に構成できることを示す例を挙げておきます。
つぎの写像を考えます。
$$
z=\phi(x_1, x_2)=(x_1^2, x_2^2, \sqrt{2}x_1x_2)
$$
特徴空間での内積$\phi(x)^T\phi(y)$を計算してみると
$$
\begin{align}
\phi(x)^T\phi(y)&=(x_1^2, x_2^2, \sqrt{2}x_1x_2)^T(y_1^2, y_2^2, \sqrt{2}y_1y_2)\\
&=x_1^2y_1^2+x_2^2y_2^2+2x_1x_2y_1y_2\\
&=(x_1y_1+x_2y_2)\times(x_1y_1+x_2y_2)\\
&=(x_1y_1+x_2y_2)^2\\
&=(x^Ty)^2\\
&=(1 \times x^Ty+0)^2
\end{align}
$$
となり、これは多項式カーネルで次数$d=2$、$scale=1$、$offset=0$とおいた式と等しいことがわかります。
この例のように特徴空間で内積$\phi(x)^T\phi(y)$をそのまま計算する代わりに、入力空間で$(x_1y_1+x_2y_2)^2$を計算すれば良いことがわかります。
ほかにも色々と書きたいと思っていたのですが、案外時間がかかりそうなので、このへんで終わります。
参考文献
- Nello Cristianini、John Shawe‐Taylor、大北 剛 (翻訳) 、サポートベクターマシン入門、 共立出版
- 小野田 崇、サポートベクターマシン (知の科学) 、オーム社
