Optunaから簡単に利用できる「CMA-ES」　進化計算で最も有力な連続最適化問題のアルゴリズム

ハイパーパラメーター最適化に関連するライブラリを作成

芝田将氏（以下、芝田）：それでは発表を始めます。最初に、簡単に自己紹介をします。サイバーエージェントという会社の「AI Lab」という研究組織に所属しています。OSSの開発では「Optuna」のコミッターで、ほかにはKubernetes上でマシンラーニングのシステムを運用するプラットフォーム「Kubeflow」の中の「Katib」というコンポーネントのレビュー権限なども持っています。

そのほかにもいろいろ、ハイパーパラメーター最適化に関連するライブラリを作って公開していて、その1つが今日紹介する「CMA-ES」のライブラリです。こちらはOptunaでも使われています。

ほかにも、OptunaをGo言語に移植して公開したり、「optuna-dashboard」というライブラリを作ったりしています。optuna-dashboardは、現在開発を進めているところですが、基本的な機能はけっこうそろってきたかなと思うので、みなさんもよければ、ぜひ使ってみてください。使い方はとても簡単で、pipからoptuna-dashboardをインストールして、ストレージURLを指定するだけです。

では本題の、今回のテーマにあるCMA-ES、「CMA Evolution Strategy」というアルゴリズムについてお話しします。今日の内容はざっくり3つに分かれています。前半の2つが利用者向けの話。最後の3つ目は、ふだん私がCMA-ESという最適化手法を実装する中で、バグを減らすためにこのように取り組んでいるという話です。同じような数値計算のプログラムを書いている人には、けっこう有用な話もあるかもしれないので紹介します。

ブラックボックス最適化の最も有力な手法「CMA Evolution Strategy」

それでは、CMA-ESというアルゴリズムの概要と使いどころ、Optunaから利用する際のTipsをお話しします。CMA-ESは、進化計算における最も有力なブラックボックス最適化の手法の1つとして知られています。このアルゴリズムは、多変量正規分布を探索空間上に初期化してそこから解をサンプルし、その解の評価値を利用して、よりよい解を生成するような分布へと更新していく手法です。

（スライドを指して）言葉では少しわかりづらいので、アニメーションを用意しました。右の図が二次元の探索空間を示しています。星の位置が最適解で、丸が多変量正規分布を表しています。

最初に、この多変量正規分布からいくつか解をサンプルして、それをハイパーパラメーターとして評価します。評価すると当然評価値が得られるので、それをもとにどの評価値がよかったかがわかるのですが、評価値のよいものから重み付けしていって、その情報をもとに多変量正規分布のパラメーターを更新します。

この図の場合、多変量正規分布からサンプルした解の中で、よい解が左下のほうに集まっているので、多変量正規分布の平均ベクトルは左下のほうに移動して、共分散行列は若干左下に伸びるような、このようなかたちのパラメーターに更新されます。

この操作を繰り返していくことで、だんだん最適解のポイントに近づいていき、最終的にはその最適解、つまり最適なパラメーターに近いものをただひたすらサンプルする分布へと収束していきます。

（スライドを指して）実際に、私が作ったツールの中に可視化ツールを用意したので、その動きを見ていきます。最初に、ど真ん中に多変量正規分布がサンプル生成されて、実際にサンプルされたハイパーパラメーターはこの赤い点で示されています。星の位置が最適解ですが、パラメーターをサンプルしながらだんだん多変量正規分布が最適解のほうに寄りつつ、小さく収束していく様子が確認できます。

OptunaのCMA-ES実装CmaEsSampler

では、CMA-ESの概要はここまでにして、Optunaから利用する際について話していきます。まず、CMA-ESのPythonライブラリにはどういうものがあるかを紹介します。一番有名なのは、「pycma」というライブラリです。これはCMA-ESのオーサーであるNikolaus Hansenさんという方が実装して公開したものです。

Optunaでも、初期のCMA-ESのサポートにおいてはこのpycmaが使われていました。ただそちらのバージョンは2.0.0でDeprecatedとなっています。なぜそうなったかというと、私がCMA-ESライブラリを作ったからです。こちらはpycmaに比べると、かなり実装も簡潔で読みやすく、拡張も容易なライブラリです。こちらの公開後、正式にOptunaのCMA-ES Samplerとして使うようになり、今いろいろな開発を続けている状態です。

Optunaからの利用法はとても簡単で、「sampler」を指定するだけです。（スライドを指して）この部分です。「optuna.samplers.CmaEsSampler」のオブジェクトを作って、sampler引数で指定します。こんな感じで、多くのケースでは、基本的にオプションはなにも指定せずデフォルトのままで問題ないかと思います。

実際これを公開した頃に、産総研（産業技術総合研究所）の知り合いがCMA-ESを使ってくれました。21次元というけっこう大きな探索空間でAUCの最大化をしていて、デフォルトの最適化手法である単変量TPE（TPESampler）では、AUCは3日間で0.89くらいまでしか到達できませんでしたが、CMA-ESでAUCが0.96まで上がりました。これも利用方法はすごく簡単で、変更1行でパフォーマンスが上がります。ここでの成果が国際会議への採択にもつながっていて、私の名前も謝辞に書いてくれたので、作ってよかったなと思った事例です。

このように、CMA-ESは簡単に使えて、デフォルトの最適化手法から切り替えることで大幅に性能が上がるケースもあります。もちろん、すべての問題がよくなるわけではなく、得意な問題、不得意な問題はあります。

よく使うオプションをいくつか紹介

今、オプションに関してはデフォルトでOKという話をしましたが、よく使う可能性があるものをいくつか紹介します。実際にはもっとたくさんありますが、ここで紹介するのは「x0」と「sigma0」です。

最初に多変量正規分布を初期化する時に、CmaEsSamplerはデフォルトでは探索空間のど真ん中に平均ベクトルを置いて、標準偏差はサーチスペースの幅÷6などといった感じで、ヒューリスティックに決めています。ただ、もし事前に有望な領域がわかっていれば、このx0というオプションから平均ベクトル、sigma0というオプションから標準偏差を指定することも可能です。

一方sigma0は、Optunaの内部実装を理解していないと適切な値の設定が難しいので、わかっている方のみが使えるオプションになるかと思います。こちらをもう少しわかりやすくできればいいなとは思っているのですが、現状は少し使うのが難しいオプションです。ただ、もし有望な領域がわかっていれば、ぜひ使ってみてください。

次のオプションは「independent_sampler」です。CmaEsSamplerは、質的変数、suggest_categoricalなどで提案するパラメーターを、CMA-ESでは扱うことができません。強引に扱う方法もありますが、あえて扱わずに、このindependent_samplerという違うサンプラーにサジェストしてもらうようにしています。特に、探索空間の中にCMA-ESでは扱えない質的変数が含まれている時、こちらのデフォルトはRandomSamplerが指定されていますが、TPESamplerに指定を切り替えることで性能が上がるケースもあるかと思います。

最後は「consider_pruned_trials」というオプションです。これは私が入れたものではなく、今村秀明さんというコミッターの方が追加してくれました。枝刈りを使った時に、CmaEsSamplerがデフォルトの場合は、枝刈りされたTrialを使わないようにしています。それを使う方法で改善するかは、あまり自明ではないのですが、導入時に今村さんにベンチマークを取ってもらって改善を確認しました。枝刈り手法と同時に使うという方は、検証してみるといいと思います。

ほかにもいろいろオプションがありますが、それ以外のオプションは公式ドキュメントを見てください。

「CMA-ES」の使いどころ

そして、一番重要なCMA-ESの使いどころです。私のAI Labのチームメイトである野村将寛さんが、2019年の「PyCon JP 2019」で『ハイパーパラメーター最適化の理論と実践』という発表を行いました。（スライドを指して）その発表で、彼の主観込みになりますが、こういう時にはこういう手法を使うといいだろうということを表で示してくれています。比較しているのは、ガウス過程ベースのベイズ最適化とTPE、さらにCMA-ESです。

ご覧のように、TPEはどんな空間でもけっこうよく動きますが、CMA-ESは質的変数を扱えません。また、低Budgetである「n_trials」の回数がすごく少ないと、ほかの手法に比べてあまりいいパラメーターを見つけられません。ただ、Budgetが十分に確保できる場合には、CMA-ESを使うことでいいパラメーターが見つかることもあります。

目安としては、ハイパーパラメーターの数掛ける100以上だと、ほぼCMA-ESがよいというのが私の感覚としてはあります。また、わりと論文でもそのように言われています。なので、少し多いですが、5次元の空間であれば500回くらい必要という感じです。

今の話は手法の観点からこう使い分けるといいという話ですが、Optunaの実装上、苦手な問題もあります。その1つが「分散最適化」です。CMA-ESは一般的に分散最適化を得意とする手法ですが、Optunaの分散最適化のモデル、並行処理のモデルとは少し相性が悪くて、一部の評価値が無駄になってしまいます。

Ask-and-Tellインターフェイスを使って、バッチ最適化をすることで効率的に回すこともできますが、CmaEsSamplerの内部実装を理解していないと適切にバッチ最適化を回すことが難しいので、基本的には少し効率が悪くなってしまう気がします。

また、Optunaの特徴としてDefine-by-Runインターフェイスを採用しているので、探索空間が動的に変化することがよくありますが、動的変化した場合、現状だとすべてindependent_samplerで指定しているRandomSamplerやTPESamplerにfallbackします。

Optuna v2.8に「Group Decomposed Search Space」という新しい探索空間の仕組みが入ったので、こちらに対応すれば今後この問題は緩和されていくと思いますが、現状は動的に変化する場合にはCmaEsSamplerが使えません。

（次回へつづく）