劣勾配法(ヒンジ損失）書いたよ

ソースコード

ソースコード

内容

• 劣勾配法の解説は，以下のブログ記事が詳しいです．
  • 劣微分を用いた最適化手法について(3) | Preferred Research

• こちらでも劣勾配法について簡単に説明したいと思います．
• 多クラス分類問題を解く場合，ヒンジ損失関数は以下の式で定義することが出来ます．
  • 
  • ここで，が現在の重みベクトル，が入力ベクトル，が正解ラベルです．
  • ヒンジ損失関数では，正解ラベルのスコアと不正解ラベルのうち一番高いスコアとの差が重要な役割を果たします．

• このように定義したヒンジ損失関数を用いて，劣勾配法はデータが1つ与えられるたびに以下の更新式に従い重みベクトルを更新します．
  • 
• ここで，は，毎回の更新時にどの程度重みベクトルを動かすかを調節するステップ幅です．
  • 多くの場合，ステップ幅はとなる値を用います．[Zinkevich, 2003]
• 以上が劣勾配法（ヒンジ損失関数）のアルゴリズムです．

• 今回はヒンジ損失関数を用いていますが，凸な関数であれば任意の関数を用いることが出来ます．
  • さらに，Regretという概念を用いることで，最適解への収束性を示すことが可能です．[Zinkevich, 2003]

実験結果

既存手法との比較は以下になります．

NaiveBayes
accuracy : 9800 / 10000
Perceptron(1 iteration)
accuracy : 9725 / 10000
PA-II(1 iteration, C=0.001)
accuracy : 9789 / 10000
Subgradient Method(1 iteration, eta=1.0)
accuracy : 9802 / 10000

劣勾配法の精度が一番高いですね．
データセットによって，どの手法が一番精度が高いか，というのは変わってくると思います．
速度は，PerceptronやPA-IIと遜色ありません．