SVM_カーネルトリック

非線形 SVM 関連

分類時、直線で分類できない場合は非線形 SVM で分類する。
カーネルトリックという方法を用いて非線形の識別を実現している。

 

カーネルに辿り着くまでの流れ
線形 SVM → 主問題 → ラグランジュの未定乗数法により双対問題を導出 →カーネル

カーネルトリックとは

元々のデータ空間から高次元空間にデータを写像し、
その高次元空間上で線形データ解析を行うことを指す。https://qiita.com/pesuchin/items/c55f40b69aa1aec2bd19   より拝借。

f:id:koshinRan:20180601225309p:plain

 

別の言葉で説明  ↓

実空間のデータを超平面で分離できる空間に写像してから、
線形 SVM と同じ仕組みでデータを分離する。https://qiita.com/rennnosuke/items/fab837825b64bf50be56  より拝借。

f:id:koshinRan:20180601225514p:plain

 

超平面でデータ集合が分離できることを線形分離可能という。

非線形 SVM は、
線形分離可能ならば、その空間内で線形 SVM の考え方を
適用すればよいという考え方。

 

 

写像の方法  メモ程度

主問題、双対問題という言葉が出てきたがよく分からない。

双対問題の中で、別空間への写像が行われる。

 

双対問題:
最適化問題における主問題の補問題を指す。
どちらか一方の解法が両方の問題の解法となる。

 

最適化問題
与えられた制約条件の下で、
ある目的関数を最大または最小にする解を求めること。
数理計画問題ともいわれている。

 

最適化問題は、制約条件や目的関数などを数式 ( 数理モデル ) にしないと解けない。

 

ソフトマージンを適用した線形SVMにおける主問題は、以下の様なもの。https://qiita.com/rennnosuke/items/fab837825b64bf50be56 より拝借。

f:id:koshinRan:20180601230029p:plain

「境界に最も近いデータ点と境界の距離が、なるべく離れるようにしたい」
という意図が、この主問題に落とし込まれている。

 

この主問題ラグランジュの未定乗数法を使って解いていく

ラグランジュの未定乗数法とは、
制約条件の与えられた目的関数を最適化したい時、
新しい目的関数を作り最適化する手法。

 

ラグランジュの未定乗数法により双対問題を導出する。
導出した双対問題から、SVM非線形に拡張する。

 

双対問題 では、内積が出現している。( よく分からん )
SVM は、目的関数や識別関数が入力パターンの内積のみに依存した形に
なっており、
内積が計算できれば最適な識別関数を構成することが可能。

 

非線形写像した空間での 2 つの要素 ( Φ(x1)  Φ(x2) )内積
入力特徴 x1 、x2 のみから計算できるなら、非線形写像によって変換された
特徴空間での特徴を計算する代わりに、K (x1, x2) から
最適な非線形写像を構成できる。
http://home.hiroshima-u.ac.jp/tkurita/lecture/svm.pdf  より拝借。

f:id:koshinRan:20180601230520p:plain

このような K のことをカーネルという。

カーネル計算のみで最適な識別関数を構成するテクニックのことを
カーネルトリックと呼んでいる。
代表的なカーネルとして RBF カーネル多項式カーネルなどがある。

 

 

こちらから。
https://qiita.com/rennnosuke/items/fab837825b64bf50be56
http://home.hiroshima-u.ac.jp/tkurita/lecture/svm.pdf
最適化問題とは | データ分析基礎知識

 

以上。