Zenn
🕘

SVM の最適化は本当に遅いのか

2024/12/22に公開
機械学習
数理最適化
tech

はじめに

この記事は数理最適化アドベントカレンダー 2024 の 12/22 の記事です。

皆さん、最近 SVM (Support Vector Machine) 使っていますか？
使っていないですよね？
私もです。

SVM が現状使われていないのは「精度が出にくい」「速度が遅い」の 2 点だと思います。ただ、速度については裏の最適化手法の事情に言及せずに、なんとなく scikit-learn の SVM を使ってみたら遅かったという理由で雑に dis られているのがちょっとかわいそうだと思ったので、遅いとされる要因をちゃんと書いておくことにしました。

SVM の最適化手法

scikit-learn などの SVM の実装では SMO (Sequential Minimal Optimization) を使っているのに対して、ニューラルネットでは確率的勾配降下法が使われています。

「SMO と確率的勾配法はどちらが速い最適化手法ですか？」と聞かれたら、ぶっちぎりで SMO の方が速いです。というか、そもそも勾配法が最適化としては速い手法ではありません。

最適化手法の速さはどう評価されるのか

SMO が「速い最適化手法」なのに SVM が実用上遅いとされるのは、一言で言うと SMO の最適化精度が今の機械学習においては過剰で時代に合っていないからでしょう。

数理最適化の文脈で「最適化問題を解く」は十分に最適解に近い解を得ることを指します。ここで言う十分は、たとえば最適解との距離が 1e-5 以下であるとか、それくらいの精度を当たり前に要求します。scikit-learn の SMO では torelance のデフォルト値が 1e-3 に設定されていますが[1]、これでも当時の機械学習の感覚に合わせて結構ガバガバな設定です。

最適解のそこそこ近くまでは軽量な確率的勾配法の方が速いですが、近傍での最適解への収束は SMO の方が圧倒的に速いです。SVM を確率的勾配降下法で解くことも可能ですが、SMO と同じくらいの精度で解こうとすると、小さい問題でも死ぬほど時間がかかります。

ですが、最近の機械学習はデータ量でゴリ押す方向へシフトしていることもあり、実用上はちゃんと収束させなくても機械学習的には十分な精度が得られます。一方で、最適化の人間からすると、解の周辺まで行くのと近傍での収束は後者のが圧倒的に時間がかかるため、最適化手法の速度は近傍での収束の速さで評価するのが常識です。ここに機械学習と数理最適化の感覚の違いがあり、単純に SVM と SMO が遅いと言われると違和感を覚えるわけです。

SVM と確率的勾配降下法

じゃあ SVM も SMO じゃなくて確率的勾配降下法で雑に解けば良いんじゃない？という話になります。
実際、SVM を確率的勾配降下法で解くのが結構流行った時期がありました。

ただ、それが可能なのは線形カーネルの SVM に限られてしまいます。SVM で非線形な識別を実現するにはカーネル法を使うことになるのですが、このカーネル法と確率的勾配降下法の相性が悪いことが問題になります。詳細は省きますが、カーネル法を使うと変数である重みを表現するのに全てのサンプルが必要になってしまうので、サンプルごとに分割して勾配を計算することができなくなってしまいます。

そうなると、結局ニューラルネットなどと同様に非線形な識別を行おうとすると SVM は SMO を使うことになってしまうので、これが前述の通り今の機械学習と噛み合わないわけです。

何とかならんのか？

  • カーネル法に対して上手く確率的勾配降下法を適用できるようになる
  • 確率的勾配降下法以外で SVM を雑に解く手法が開発される

のどちらかができれば状況は変わると思っていて、個人的には前者の方が希望がありそうな気がしています。

実際、RBF カーネルを上手く近似する研究なんかもあったりして、こういうのが発展すればいつか速度の問題は解決するんじゃないかなとは思います。まあ、そうは言ってもしばらくはかつてのニューラルネットのように冬の時代を過ごすことにはなりそうですが。

それでも、凸性を保ちつつ非線形な識別を可能にするという方向は研究としては大きな価値があると思います。

おわりに

Q. そもそも SVM が機械学習的に精度が出ないのは何で？

知りません。理論上は任意の関数を近似できるはずなので、GBDT みたいな決定木ベースの手法と比べるとデータに寄り添った処理が入っていなくて実用上は精度が出にくいとかじゃないですかね。

Q. 結局お前は SVM 使うんか？

使いません。カーネル法で大規模なデータを扱いやすい最適化手法とその良い実装が出てきたらワンチャンあるかもしれないので呼んでください。

脚注

  1. SMO の場合は KKT 条件の違反度合いです ↩︎

Discussion