はじめに
今回はサポートベクトルのカーネル法についてまとめていきたいと思います。
よろしければ前回の記事もご覧ください。
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく①～理論と数式編～
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく②～ラグランジュの未定乗数法～
カーネル法について
それではカーネル法について解説していきます。
ここで、Wikipediaからの引用を見ていきましょう。
カーネル法（カーネルほう、英: kernel method）はパターン認識において使われる手法の一つで、 判別などのアルゴリズムに組み合わせて利用するものである。よく知られているのは、サポートベクターマシンと組み合わせて利用する方法である。
パターン認識の目的は、一般に、 データの構造(例えばクラスタ、ランキング、主成分、相関、分類)を見つけだし、研究することにある。この目的を達成するために、 カーネル法ではデータを高次元の特徴空間上へ写像する。特徴空間の各座標はデータ要素の一つの特徴に対応し、特徴空間への写像（特徴写像）によりデータの集合はユークリッド空間中の点の集合に変換される。特徴空間におけるデータの構造の分析に際しては、様々な方法がカーネル法と組み合わせて用いられる。特徴写像としては多様な写像を使うことができ（一般に非線形写像が使われる）、それに対応してデータの多様な構造を見いだすことができる。
カーネル法とは、低次元のデータを高次元に写像して分離する方法だと考えてよいと思います。
厳密には違うのですが、まあここはざっくりとした理解で良いでしょう。
それでは、なぜサポートベクトルマシンでカーネル法が用いられるのかを解説します。
以下の二種類のデータを分類する場合を考えてください。
このような二次元のデータの場合、一次元の直線で二つの種類のデータを分離することができませんね。
このように線形分離不可能な問題に対応するために、このデータを多次元のデータに拡張しましょう。
具体的には、二次元のデータ$X = (x_1, x_2)$を五次元に拡張する場合には以下のような関数を通して写像します。
$$ψ(X) = (x^2_1, x^2_2, x_1x_2, x_1, x_2)$$
このように、データの次元をより高次元に拡張したものを高次元特徴空間と呼び、それに対して最初の入力データの空間を入力空間と呼びます。
上の式をより一般化しましょう。n次元の入力空間のデータを、より高次元のr次元特徴空間に写像する関数を以下のように定義します。
ψ(X) = (φ_1(X), φ_2(X), φ_3(X), ...φ_r(X))
$φ_1(X)$などの関数は、元の関数のデータを組み合わせて変化を加えるという関数です。
このような関数を用いて高次元特徴空間にデータを拡張していくと、ある段階で分離超平面により分離可能なデータになります。というか、究極的には一つ一つのデータを全て別の次元、データがn個あればn次元まで拡張すれば、必ずn-1次元の分離超平面で分離することができます。
つまり、線形分離可能なデータに変化するのです。
後はこの分離超平面を逆写像して元のデータの分離超平面に変換することで、入力空間においてデータを分離する曲線(厳密には入力空間よりも一つ次元が小さな次元に曲線を拡張したもの)を得ることができます。
それでは、高次元特徴空間における最適化問題の式を考えていきましょう。
高次元特徴空間の最適化問題の式を考える前に、入力空間の最適化問題の復習です。
max\Bigl\{{\tilde{L}(α) = \sum_{i=1}^{N}α_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{i=j}^{N}α_iα_jt_it_j{X_i}^TX_j\Bigr\}}\\
\sum_{i=1}^{N}α_it_i = 0, \quad 0 \leqq α_i \leqq C, i = 1,2,...N
高次元特徴空間のデータは入力空間のデータ$X_i^T$,$X_j$1を関数$ψ(X)$を用いて写像したものであるので、高次元特徴空間の最適化問題は以下のようになります。
max\Bigl\{{\tilde{L}(α) = \sum_{i=1}^{N}α_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{i=j}^{N}α_iα_jt_it_j{ψ(X)_i}^Tψ(X)_j\Bigr\}}\\
\sum_{i=1}^{N}α_it_i = 0, \quad 0 \leqq α_i \leqq C, i = 1,2,...N
高次元特徴空間において、この最適化問題をといていけばよいことが分かりますね。
ここで問題になるのは以下の項です。
{ψ(X)_i}^Tψ(X)_j
特徴空間が高次元になればなるほど、この項の計算量がとんでもないことになりますよね。
この部分の計算を簡単にする方法がカーネルトリックと呼ばれる方法です。
以下のようにカーネル関数を定義します。
K(X_i, X_j) = {ψ(X)_i}^Tψ(X)_j
少しごまかしますが、このカーネル関数を用いると$ψ(X)$を直接計算せずに内積を計算することができます。
このように、$ψ(X)$を直接計算せずに内積を計算するためにはある条件を満たす必要があるのですが、なんだかよく分からない 説明するのが大変なので参考となるサイトだけ貼っておきます。
双対問題において$ψ(X)$は内積の形でしか出てこないため、この方法は非常に有用です。
以下のような三つのカーネル関数が用いられます。
ガウスカーネル
K(X_i, X_j) = exp\bigl\{-\frac{||X_i -X_j||^2}{2σ^2}\bigl\}
多項式カーネル
K(X_i, X_j) = (X_i^TX_j + c)^d
シグモイドカーネル
K(X_i, X_j) = tanh(bX_i^TX_j + c)
それでは、実際に多項式カーネルにより内積が簡単に計算できる具体例をみていきましょう。
以下のような二次元入力空間を三次元特徴空間に写像する関数を考えます。
ψ(X) = ψ(x_1, x_2) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)
この関数を用いると、二つの二次元ベクトルX, Yは以下のようになります。
ψ(X) = ψ(x_1, x_2) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\\
ψ(Y) = ψ(y_1, y_2) = (y_1^2, \sqrt{2}y_1y_2, y_2^2)
それではこれらの内積を考えていきましょう。
\begin{align}
ψ(X)^Tψ(Y) & = (x_1^2, \sqrt{2}x_1x_2, x_2^2)^T(y_1^2, \sqrt{2}y_1y_2, y_2^2)\\
&=x_1^2y_1^2 + 2x_1y_1x_2y_2 + x_2^2y_2^2\\
&= (x_1y_1 + x_2y_2)^2\\
&=((x_1,x_2)^T(y_1,y_2))^2\\
&=(X^TY)^2
\end{align}
このように、$ψ(X)^Tψ(Y)$を直接計算せずに、元のベクトルの内積を二乗することで、$ψ(X)^Tψ(Y)$を計算することができます。
カーネル法についてもう少し詳しく知りたい方はこちらの記事を参考にしてください。
終わりに
ここまでで今回の記事は終了です。
ここまで読んで頂きありがとうございました。
よろしければ次回の記事もご覧ください
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく④～ソフトマージンとハードマージンの実装～
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく⑤～カーネル法を用いた分類の実装～