Skip to content

第4回 非線形写像とカーネル関数

Jump to bottom
levelfour edited this page Dec 5, 2014 · 12 revisions

非線形写像の導入

「非線形変換で高次元空間に写像することで線形分離可能になる可能性がある」という期待の下、まずはd次元学習データx∈R^dに対して

\{\phi_j(\mathbf{x})\}_{j=1}^M

というM次元の非線形写像の集合を導入し、

\mathbf{\phi(x)}=\left(\phi_0(\mathbf{x}),\phi_1(\mathbf{x}),...\phi_M(\mathbf{x})\right)^T

というように学習データを非線形変換したものを入力データとして考える。線形識別関数

f(\mathbf{x_i})=\mathbf{w^T\phi(x_i)}+b

を用いてこの入力データ群が線形分離可能であれば、第4回 - 線形SVMのKKT条件1より、最適な識別超平面の法線ベクトルwは

\mathbf{w_0}=\sum_{i=1}^N\alpha_it_i\mathbf{\phi(x_i)}

と書ける。このとき識別関数fは

f(\mathbf{x})=\mathbf{{w_0}^T\phi(x)}+b=\sum_{i=1}^N\alpha_it_i\mathbf{\phi^T(x_i)\phi(x)}

となる。fに含まれる非線形項を次のように取り出す。

K(\mathbf{x_i},\mathbf{x})=\mathbf{\phi^T(x_i)\phi(x)}

この関数を核関数/カーネル関数と呼ぶ。

双対問題は以下の関数の最大化になる。

L_d(\mathbf{\alpha})=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jt_it_jK(\mathbf{x_i,x_j})\;\;\mathrm{subj.\;to}\;\;0\le\alpha_i\le C,\mathbf{\alpha^Tt}=0

線形の場合とくらべて(x^T)x→Kとなっているだけだが、逆に線形SVMはK(u,v)=(u^T)vというカーネル関数を用いていると考えることもできる（線形カーネルと呼んだりする）。

非線形写像の次元が大きいとき、すなわちM>>dのとき、たとえ非線形空間内で線形分離可能になっていたとしても M次元ベクトルφの内積（カーネル関数）を計算するのは時間がかかってしまい、認識効率が悪い可能性がある。 カーネル関数の引数x∈(R^d)の内積計算で済めば、計算が高速になる。 このようなカーネル関数を内積カーネルという（名前が紛らわしい）。

scikit-learnでのSVMの使い方

勉強のためには実際にSVMを実装するのは重要だが、実用上はライブラリを使うのが望ましいので、scikit-learnでのSVMの利用の仕方を説明する。 scikit-learnでは以下のモジュールにSVMが含まれている。

from sklearn import svm

次のようにすればSVMの識別器が作れる。

clf = svm.SVC()

このとき、SVCに引数を与えることでSVMのパラメータを変更することができる。カーネル関数によらない引数はCとkernelである。 Cはソフトマージンのコストパラメータである。 kernelは利用するカーネル関数であり、文字列で指定する。

  • 'linear': 線形カーネル
  • 'poly': 多項式カーネル
  • 'rbf': RBFカーネル
  • 'sigmoid': シグモイドカーネル

例えば以下のように使う。

clf = svm.SVC(C=1e-2, gamma=1e-4, kernel='rbf')

また、自分で定義したカーネル関数を使うこともできる。通常の関数通り定義して、kernelに指定すればよい。 gammaはRBFカーネルのパラメータである。後述する。 学習、推定は他の識別関数と統一的に行える。

clf.fit(data, target)
predicted_label = clf.predict(unknown_data)

これからよく利用されるカーネル関数を紹介する。

多項式カーネル

多項式カーネルは内積カーネルの一つである。多項式カーネルは以下のような関数である。（α≥0）

K_p(\mathbf{u,v})=(\alpha+\mathbf{u^Tv})^p

例えば

\mathbf{u}=\begin{pmatrix}u_1\\u_2\end{pmatrix},\;\;\mathbf{v}=\begin{pmatrix}v_1\\v_2\end{pmatrix},\;\;\alpha=1

とする。このとき2次の多項式カーネルは

K_2(\mathbf{u,v})=(1+\mathbf{u^Tv})^2=(1+u_1v_2+u_2v_2)^2=1+{u_1}^2{v_1}^2+2u_1u_2v_1v_2+{u_2}^2{v_2}^2+2u_1v_2+2v_1v_2

と表される。ここでφを

  • \phi(\mathbf{u})=(1,{u_1}^2,\sqrt{2}u_1u_2,{u_2}^2,\sqrt{2}u_1,\sqrt{2}u_2)^T
  • \phi(\mathbf{v})=(1,{v_1}^2,\sqrt{2}v_1v_2,{v_2}^2,\sqrt{2}v_1,\sqrt{2}v_2)^T

とおけば、K_2(\mathbf{u,v})=\phi(\mathbf{u})^T\phi({\mathbf{v})と分解することができる。 カーネル関数K_2は6次元の非線形写像であり、その値は2次元ベクトルの内積で計算することができる。

scikit-learnで指定できるパラメータはgamma,degree,coef0である。 それぞれ以下のような意味を持つ。

  • gamma: (u^T)vの係数
  • coef0: α
  • degree: p

つまり

K_p(\mathbf{u,v})=(\mathrm{coef0}+\gamma\mathbf{u^Tv})^{\mathrm{degree}}

である。

動径基底関数カーネル(RBFカーネル)

RBFカーネル(radial bases function kernel)は、おそらく最も広く利用されているカーネル関数である。 ガウス分布関数の関数系をしているため、**ガウシアンカーネル(Gaussian kernel)**と呼ばれることもある。 scikit-learnのsvm.SVCも、デフォルトではRBFカーネルを採用している。

K_\sigma(\mathbf{u,v})=\exp\left(-\frac{1}{2\sigma^2}{||\mathbf{u}-\mathbf{v}||}^2\right)

scikit-learnで指定できるパラメータはgammaであり、gamma=1/(2(σ^2))≥0である。

K_\sigma(\mathbf{u,v})=\exp(-\gamma{||\mathbf{u}-\mathbf{v}||}^2)

シグモイドカーネル

K(\mathbf{u,v})=\tanh(c\mathbf{u^Tv}+\theta)

ニューラルネットワークとの関連で用いられることがあるようだ。ここでは触れるにとどまっておく。

scikit-learnで指定できるパラメータは以下のとおりである。

  • gamma: c
  • coef0: θ

K(\mathbf{u.v})=\tanh(\gamma\mathbf{u^Tv}+\mathrm{coef0})

ライブラリについての補足

このwikiでは一貫してscikit-learnを用いた解説を行っているが、ことSVMに限っていえば一般的によく用いられているのはlibsvmというライブラリである。 libsvmは数多くのメジャーな言語をサポートしたSVM専用ライブラリであり、学術論文でも頻繁に使用されている。 scikit-learnのsvm.SVCは内部的にはlibsvmのCythonラッパーになっている。

Clone this wiki locally