SVM)を実装してみます。SVMに関しては、有名なSVMのライブラリ(libsvm)を使ったことがあるだけで、アルゴリズム詳細はPRMLで初めて学習しました。変なことを書いていたらコメント欄で指摘してもらえると助かります。簡単な線形SVMを実装してみます。今までと同様に直線(超平面)でデータが完全に分離できる場合です。PRMLの7章には特に説明がありませんが、カーネル関数に下の線形カーネル(データのただの内積)を用いた場合に相当するようです。このカーネル関数を多項カーネルやガウシアンカーネルに変更すると線形分離不可能なデータも分類できるようになるとのこと。非線形SVMは次回ためしてみます。SVMの識別関数は、式(7.1)で表せます。今までと違ってバイアスパラメータをまとめないのが流儀なんでしょうか?今までと同様に訓練データと教師信号(クラス1のとき+1、クラス2のとき-1)の組からパラメータwとbを学習するのが目的です。SVMの特徴は、マージン(分類境界と訓練データ間の最短距離)を最大化するようなwとbを求めることです。このとき、wに式(7.5)のような制約を付けます。制約は訓練データの1つにつき1つなのでN個データがあったらN個制約の式があります。この制約は、すべてのデータがy>=1かy<=-1にあることを言っています。1の間にデータが存在しない空白地帯(マージン)ができます。この空白地帯が最大になるようにしたいってことですね。線形分離可能などんなデータでも式(7.5)の制約を満たすようにwを調節できます(PRMLの図7.1の右側がマージン最大化したイメージ図だと思いますが、左側とy=1、y=-1が入れ替わっているのはなぜなんでしょうね?誤植かな?)。マージン1/|w|を最大化するのですが、これは|w|^2を最小化する問題と等価になり、式(7.5)の制約のもとで式(7.6)を満たすwとbを求めればよいとのこと。制約付きの極値問題はラグランジュの未定乗数法で解くことができ、ラグランジュ乗数a_nを導入すると、ラグランジュ関数は式(7.7)になります。これを、wとbで偏微分して0とおく(極値条件)と式(7.8)と式(7.9)の2つの条件が出てきました。ここからが面白いところでこの条件を「元の」ラグランジュ関数に代入し、wとbを消去してaの関数にしてしまいます。ここで出てきた式(7.10)を双対表現と言うとのこと。双対表現にするとカーネル関数が出てきます。aが満たすべき制約は、式(7.9)と式(7.11)です。ここまでやると、wとbに関する最適化問題がaに関する最適化問題に置き換わってしまいます。programming)で解ける形式になっている!そして、aさえ求まればwも決まるので識別関数(7.1)はすぐに求められます。式(7.1)に式(7.8)を代入すると式(7.13)になり、wではなくaを使った識別関数の式に変換できます。bはサポートベクトルの条件から式(7.18)で求まります。Sはサポートベクトルの集合、N_Sはサポートベクトルの数です。何はともあれaが求まればwもbも求まって最終的に識別関数も求まるってことですね。次はラグランジュ乗数aを二次計画法で解こうって話になります。二次計画法は線形不等式のもとで二次関数を最小化する手法とのこと。(SMO)ってのがよくつかわれると紹介があります。説明がほとんどなくこれでは実装できないので、ずるをして(今回はSVMが目的なんで)cvxoptというPythonの最適化ライブラリを使ってみます。SMOかはわかりませんが、二次計画法も実装されています。b)とすればよいとあります(ドキュメントと例題はQとpの使い方が逆になっていますが、例題側にあわせています)。式(7.10)と全然形が違うと思ったのですが、実は下のように置くと同じ形になります。ラグランジュ乗数L(a)は最大化が目的ですが、下のようにおくと-L(a)とマイナスがつくので最小化を目指すことになります。Kはグラム行列ってやつですが、要素に教師信号をかけたt[i]*t[j]がつくので注意です。Nは訓練データ数です。実際にN=2くらいで行列を書き下してみると、下の設定による二次計画法がラグランジュ関数-L(a)と等しいことが確かめられます。anumpyのarrayではなく、cvxoptのmatrixではないと受け付けません。arrayとmatrixは相互変換できるように作られているようです。cvxoptを事前にインストールする必要があります。show()ラグランジュ乗数aの出力結果は、下のようになります。3.06443105e-09]ほとんどのデータに対応するラグランジュ乗数はa_n=0になっています(実際はすごく小さな数です)。a_n>0となるラグランジュ乗数に対応するデータx_nをサポートベクトルと呼びます。上の結果では、3つだけ0でないラグランジュ乗数があります。サポートベクトルは3つですね!分類境界は下のようになります。上の結果で水色の丸がa_n>0のサポートベクトルです。式(7.13)の識別関数からわかりますが、サポートベクトル以外のデータ(a_n=0)は識別関数にまったく影響しません。サポートベクトルのみで分類境界が決まります(これが疎な解の意味?)。疎な解だと何がうれしいのかPRMLには書かれてないようなんですが、ノイズに対して頑強で、サポートベクトルだけ予測できるので使用メモリも少なくてよいとかでしょうか?ためしに最小二乗法(2010/4/24)でうまくいかなかった例題を試してみます。ノイズデータがあってもサポートベクトルだけで分類境界が決まるのでまったく影響していません。次は、カーネル関数を変えて線形分離不可能なデータに対応できるようにしてみます。分類境界が非線形になると面白いよー。20:18線形SVMTweet広告を非表示にする関連記事2015-06-18Theanoによる多層パーセプトロンの実装Theanoによるロジスティック回帰の実装(2015/5/26)のつづき。...2014-04-02線形回帰による曲線フィッティング線形回帰による直線フィッティング(2014/4/1)のつづき。ついて調べたことを整理してお...2010-05-15K-meansクラスタリング9章のK-meansをPythonで実装してみます。»プロフィールid:aidiary人工知能とその関連分野に興味があります。)はてなブログをはじめよう!aidiaryさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。