今回は、SVMに関する他のサイトの情報を元にSageでSVMを試してみます。 参考(ほとんどコピー)にしたのは以下のサイトです。
上記で説明されたSVMを計算する2通りの方法が7章を理解する上で助けになりました。
SVMのテストには、PRMLの図7.4、
で使用された(赤と青の点が入り混ざっている)人工データを使います。
カーネルには、$exp(-\gamma||x - x'||^2)$のガウスカーネルを使い、$\gamma=0.45$とします。
|
|
「きちめも」で実装されている、「サポートベクターマシン入門」の付録に掲載されているSMO(Sequenctial Minimal Optimization) は、J. Platt(1988)で発表されたもので、2つのデータ点に対する最適化問題を解析的に求め、ヒューリスティクスな選択で反復的な処理を 高速に収束させる手法です。
以下では、「きちめも」の実装に若干の修正を加えています。
|
|
SMOの計算結果は、図7.4と同様のパターンを得ました。
|
|
「人工知能に関する断想録」では、適化ライブラリCVXOPTを使ってSVMを計算しています。
「人工知能に関する断想録」のポイントは、CVXOPTの入力形式に $$ \begin{array}{ll} \mbox{minimize} & (1/2)x^TPx + q^Tx \\ \mbox{subject to} & G x \leq h \\ & A x = b \end{array} $$ 制約条件$0 \le a_n \le C$をどうやって組み入れるかですが、 $$ G x \leq h $$ を $$ \begin{pmatrix} -1 & 0 \\ 0 & -1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a_1\\ a_2 \end{pmatrix} \le \begin{pmatrix} 0 \\ 0 \\ C \\ C \end{pmatrix} $$ とすることで解決されたそうです。
「人工知能に関する断想録」からの変更点は
|
|
|
pcost dcost gap pres dres 0: 5.5960e+01 -7.6903e+04 9e+04 1e-01 4e-14 1: -1.2616e+03 -1.1595e+04 1e+04 1e-02 3e-14 2: -2.0141e+03 -4.1694e+03 2e+03 2e-03 3e-14 3: -2.3490e+03 -3.5920e+03 1e+03 8e-04 3e-14 4: -2.5794e+03 -3.0567e+03 5e+02 3e-04 3e-14 5: -2.6539e+03 -2.9363e+03 3e+02 1e-04 3e-14 6: -2.7063e+03 -2.8304e+03 1e+02 5e-05 3e-14 7: -2.7337e+03 -2.7873e+03 5e+01 1e-05 4e-14 8: -2.7496e+03 -2.7604e+03 1e+01 2e-06 4e-14 9: -2.7532e+03 -2.7548e+03 2e+00 2e-07 4e-14 10: -2.7538e+03 -2.7538e+03 8e-02 8e-09 4e-14 11: -2.7538e+03 -2.7538e+03 1e-03 9e-11 4e-14 Optimal solution found. pcost dcost gap pres dres 0: 5.5960e+01 -7.6903e+04 9e+04 1e-01 4e-14 1: -1.2616e+03 -1.1595e+04 1e+04 1e-02 3e-14 2: -2.0141e+03 -4.1694e+03 2e+03 2e-03 3e-14 3: -2.3490e+03 -3.5920e+03 1e+03 8e-04 3e-14 4: -2.5794e+03 -3.0567e+03 5e+02 3e-04 3e-14 5: -2.6539e+03 -2.9363e+03 3e+02 1e-04 3e-14 6: -2.7063e+03 -2.8304e+03 1e+02 5e-05 3e-14 7: -2.7337e+03 -2.7873e+03 5e+01 1e-05 4e-14 8: -2.7496e+03 -2.7604e+03 1e+01 2e-06 4e-14 9: -2.7532e+03 -2.7548e+03 2e+00 2e-07 4e-14 10: -2.7538e+03 -2.7538e+03 8e-02 8e-09 4e-14 11: -2.7538e+03 -2.7538e+03 1e-03 9e-11 4e-14 Optimal solution found. |
CVXOPTの計算は、SMOよりも高速で解も安定しています。
CVXOPTの計算結果も、図7.4と同様のパターンを得ました。
|
|
|
|