SVMの最適化にL-BFGSを使っていいのか? → たぶん大丈夫

機械学習 最適化

適切なタイトルは「SVMの主形式を制約なし非線形最適化で解く」だと思う．

きっかけはSEXI2013/WSDM2013読み会で @harapon さんが担当された論文 Identifying Users' Topical Tasks in Web Search (WSDM2013) ．ここにLinear SVM (SMO) とLinear SVM (L-BFGS) という手法が出てくる．

いかにゆとりといえど，さすがにPRMLを三周回っているとSVMが主形式，双対形式ともに二次計画 (QP) であるということくらいは覚えている．はてL-BFGSは準ニュートン法，制約なし非線形最適化に用いる最適化手法という認識である．これって使ってよいのだろうか?

最初は下記のつぶやきのとおり思っていたのだけれどこれは間違い．KKT相補性条件のことを忘れている．


というわけでしばらく調べていたら下記の論文を見つける．

どうやらこの論文は下記の本に掲載されたもののupdate版らしい．

Large-Scale Kernel Machines (Neural Information Processing)

Large-Scale Kernel Machines (Neural Information Processing)

  • 作者: Léon Bottou,Olivier Chapelle,Dennis DeCoste,Jason Weston
  • 出版社/メーカー: The MIT Press
  • 発売日: 2007/09/30
  • メディア: ハードカバー
  • クリック: 1回
  • この商品を含むブログを見る

一言でいうとSVMを制約なし非線形最適化問題として定式化する，という話．ただしHinge lossでは微分不可能な点があって困るので二乗誤差関数やHuber loss (二乗誤差関数とHinge lossを合わせたようなもの) を使いますよ，とも言っている．本論文ではNewton法を使っているが，勾配情報がわかれば準ニュートン法は使えるのでもちろんL-BFGS法も利用可能．

なおここで言う念のため，ここでいう二乗誤差は
\sum_{i=1}^N (\max(0, 1 - y_i \mathbf{w}^T \mathbf{x}_i))^2
という感じでhinge lossの線形損失部分を自乗したもの．

説明書きによると線形カーネルの場合にはStandard SVM solver (SMOだろうか?) よりも速いらしい．非線形カーネルの場合はcompetitiveだとか．


実装については論文を眺めてみるとヘシアンの計算まで丁寧に書いてあるので論文通りに実装すれば動きそうだけれど，現在のサポートベクタに応じて対応する単位行列を用意する必要があり，そこがちょっと面倒くさそうなので，今度時間があるときに実装してみよう．(コードに直すとシンプルかもしれないけれど棚上げ)

以下のような実装があるらしい (他にもあるかもしれない)

なお @niam さんに教えてもらったonline L-BFGS法を使う方法もあるらしい．

というわけでSVMをL-BFGSで最適化するのはよさそう．ただし，二乗誤差やHuber-lossを使った際に通常のSVMと等価になるのかというところに疑問が残る．Huber lossでhを限りなく小さくすれば等価だろうけれど，そうでない場合にはたとえCパラメータを同じにしても異なるサポートベクタとそれらに対応するパラメータが得られそう．

なお，Chapelle論文の二乗誤差をどーこーかで見たことあるなと思ったら，昨年のWSDM2012読み会で紹介した "Learning to Rank with Multi-Aspect Relevance for Vertical Search" に出てきた損失関数だった．奇しくも同じWSDMというところに不思議な縁を感じる．