非線形SVM 〜 詳細説明 〜

戻る



問題が線形分離できないような場合,やっぱり非線形なモデルを考えたいわけで,常套手段はなんといっても,元の特徴空間を線形分離可能な別の特徴空間に変換してやってから線形分離してやる,っていう方法だよね.非線形SVMも例に漏れずこの方法を使う.

元の特徴空間におけるベクトルを,別の次元特徴空間に変換する関数を考える.は,スカラーを出力する任意の個の非線形関数を要素とするベクトルと定義する.

(2.1)






これを使って,非線形SVMの識別関数を次のように考える.

ただし (2.2)



学習データは個与えられているとし,と表す.これらのデータを2つのクラスおよびに分離することを考える.この学習データ集合に対して,が次の条件を満たすようにパラメータを調節することを考える.

(2.3)

ここで学習データに関する教師信号をとし,次のように定義する.

(2.4)

これを使うと,式(2.3)を次のように書きなおせる.

(2.5)

線形SVMのときと同じようにして,次の最小化問題を考える(マージン最大化).

(2.6)

ラグランジュの未定乗数法で問題を書き直して,

(2.7)

これをおよびで編微分して0とおくと,

(2.8)

(2.9)

式(2.8)より,

(2.10)



次にラグランジュ関数と書き換えて,式(2.9)および(2.10)を代入すると,

(2.11)

これをそれぞれについて分解すると次のようになる.

(2.12)

で,「関数(式(1.9))およびの条件下で最大化する問題」と置き換えてやれば,最適なを求めることができる.



と,ここまでは線形SVMのに置き換えて進めてきただけなのだけれど,ちょっと待ってもらいたい.式(2.12)の内積部分,まともに計算すると高次元なベクトル演算が入ってしまう.さらには式(2.2)のに関しても,内部で非常に高次元のベクトル演算が含まれてしまうため,実用上あまりよろしくないんではなかろうか.



ということで登場するのが,カーネルトリックだ.



カーネルトリックの種明かしは,なんのことはない,次のように内積をカーネル関数で置き換えてやるだけなんである.

(2.13)

しかし,これを使うことでの表記をすべて消すことができるため,めんどくさい高次元ベクトル演算が無くなって,計算が一気に簡単になってしまうのだ.すげー.



まずは式(2.12)に式(2.13)を代入すると,

(2.14)



次に式(2.10)を次のように意図的に変形してやる.

(2.15)

ここで,

(2.16)

というパラメータを定義してやると,式(2.15)より

(2.17)

のため,式(2.2)のを,パラメータの代わりにで表すことができる.

(2.18)

さてここで,SVMがSVMたる所以である部分だけれども,式(2.16)および式(2.18)から分かるように,ラグランジュ乗数がとなるベクトルデータ(つまり,SVではないデータ)に関するカーネルは識別関数に関与しないことを考えると,をSV,をSVの数とすれば,式(2.18)は次のようにしてよい.

(2.19)



式(2.19)に任意のサポートベクトルを代入することでパラメータが求まる.

(2.20)



最急降下法の最大化問題を解くには,

(2.21)

を逐次更新していけばよい.

式(2.14)をで編微分すると,

(2.22)

よって式(2.21)は次のようになる.

(2.23)

は学習係数で,小さな正の値とする.



カーネルトリックが有効であるようなカーネル関数は,の内積を定義し得るものである必要がある.正定値関数をカーネルとして考えるとそのようなが存在することが知られている.例としては,次のような「多項式型カーネル」または「ガウシアン型カーネル」がある.

多項式型カーネル関数:

ガウシアン型カーネル関数: