「CMA-ES」の苦手をどう克服すればよいか　欠点を埋める派生アルゴリズム「Warm Starting CMA-ES」

「CMA-ES」の欠点を克服・緩和する方法

芝田将氏（以下、芝田）：先ほどいくつかCmaEsSamplerの欠点を挙げましたが、派生アルゴリズムというものをサポートしていて、それを使うことで先ほどの欠点を部分的に克服できたり、緩和できたりします。

例えば、先ほど「Separable CMA-ES」という派生アルゴリズムはハイパーパラメーター間の依存関係を無視することで、CMA-ESは高Budgetの時に有効になるという話をしましたが、Separable CMA-ESは、比較的低Budgetでも探索を進めることでよい解にたどり着くことができます。ただ、依存関係を無視してしまうので、依存関係が存在する問題ではいいパラメーターを見つけられなくなってしまうなどの問題があります。

もう1つの「IPOP-CMA-ES」はリスタート戦略です。CMA-ESが局所解に収束した時に自動でリスタートをする手法です。こちらは、restart_strategyオプションというものを指定することで有効化できます。

最後に紹介するのが「Warm Starting CMA-ES」という手法ですが、こちらは実際にサイバーエージェントの社内のプロダクトでも使われているので、のちほど詳しく、事例等を含めて紹介しようと思います。

Separable CMA-ESやIPOP-CMA-ESについては、Optunaの公式ブログに記事を寄稿したので、詳しく知りたいという方はぜひ読んでみてください。

派生アルゴリズム「Warm Starting CMA-ES」

次に、社内のプロダクトで導入していた「Warm Starting CMA-ES」という派生アルゴリズムの紹介を行います。Warm Starting CMA-ESは、似たようなハイパーパラメーター最適化のタスクの試行結果を事前情報として活用することで効率的に探索する手法です。

こちらは、先ほど紹介したチームメイトである野村将寛が中心となって提案し、「AAAI 2021」に採択された手法です。私がOptunaからも使えるようにしていて、source_trialsオプションというところで似たようなHPOタスクの試行結果のFrozenTrialのリストを渡すと、このWarm Starting CMA-ESを使うことができます。

Optunaのバージョンは、v2.6.0から利用可能です。（スライドを指して）使っている様子はこんな感じです。関連するタスクのFrozenTrialのリストを取り出して、source_trials引数に指定します。

これに似たHPOタスクは具体的にどういうものがあるかを、弊社の事例を含めてお話しします。弊社のとあるプロダクトでは、学習パイプラインを組んでいます。学習パイプラインは、定期的に新しいデータを取ってきて、モデルを再学習して、本番環境にデプロイするといった流れです。

その際に、学習するだけではなく多少データの分布が変わる可能性があり、適切なハイパーパラメーターも変わる可能性があるため、毎回その学習パイプライン上でハイパーパラメーター最適化を実行しています。

この学習パイプラインは、1週間に1回実行されますが、その際、毎回イチから愚直に探索を行うのではなく、先週ハイパーパラメーター最適化を行った時の試行結果をどこかに保存しておいて、それを次の週の最適化にうまく使いたいというのが今回のモチベーションです。

先週の試行結果と今週の最適化の試行結果は、探索している空間もモデルも同じです。単に最初のデータが少し変わっているだけなので、基本的には探索空間の景観は似たようなものになっている可能性がある、Warm Starting CMA-ESは有効に使えるだろうということで検証を行いました。まず、導入する前に実際にデータをもらってきてオフラインでの性能検証を行い、そこでOptunaのデフォルト最適化手法である単変量TPEと比べて約2倍の高速化を実現していることを確認しました。

学習のメトリクスの管理には「MLflow」を使用

このプロダクトでは、学習のメトリクスの管理などに「MLflow」というツールを使っています。MLflowには、メトリクスみたいなものを取るキーバリューのストアのほかに、生成したファイルをアップロードする、アーティファクトと言われるファイルストアみたいな仕組みがあります。

今回はOptunaの最適化を実行して、その最適化結果をSQLite3のファイルにRDBストレージで書き込み、そのSQLite3のファイルを丸ごとそのまま「MLflow Artifact」にアップロードします。次の週の実行時には、このMLflow Artifactから先週の試行結果のSQLite3のファイルをダウンロードして、Trialを引っ張ってきて使うという感じです。

（スライドを指して）連携するコードはこちらです。詳しくは紹介しませんが、もしMLflowを使う方がいれば、ぜひこちらを試してください。先週の試行結果を取ってくるのがMLflow上で少し複雑な処理になりますが、そちらはこのように書くことができます。こちらも詳しい解説はしませんが、もし同じようにMLflowを使っているという方がいれば、こちらのコードを参考にしてください。

開発効率を落とさずにデグレが出ないようにする工夫

最後に紹介するのは、利用者向けではなく、同じように最適化手法を実装している研究者の方やOptunaのコントリビューターの方向けの情報です。

（スライドを指して）このCMA-ESライブラリは私が作っていますが、それほど開発体制が整っているわけではありません。例えばOptunaであれば、コミッターは何人もいて、2 approve制でマージされるという状況です。CMA-ESライブラリは、私がほぼ1人で開発していて、レビュアーの確保も難しい状態です。

Optunaもそうですが、いろいろなところで使われているので、適当に開発してデグレを出すといろいろなところに迷惑をかけてしまいます。そのため、慎重に開発したいという思いはあります。ただ、開発効率は落としたくないので、開発効率をできるだけ落とさずにデグレが出ないような工夫をいくつか取り入れています。今日紹介するのは、「kurobako」と「GitHub Actions」を使った継続的ベンチマークと、「Coverage-guided Fuzzing」によるバグの検出です。

まずは継続的ベンチマークから話します。ベンチマークツールとして「kurobako」というものを使っています。これはOptunaの開発者の1人である太田健さんという方が作って、公開されているツールです。基本的には、コマンドラインツールのほかにインターフェイスを提供するPythonのライブラリがあるという感じです。

CMA-ESの開発もそうですが、最適化手法を実装していると確率的な振る舞いが多く、ユニットテストで保証できる振る舞いが極めて限定的なので、ユニットテストだけではかなり不十分です。こういうベンチマークツールを使って結果を確認することで、振る舞いに問題がないかも確認しています。

理想としてはコードを変更するたびにこちらを実行したいところですが、プルリク（プルリクエスト）を上げるたびにこれを引っ張ってきてkurobakoを実行して確認するのはすごく手間なので、どうにかして開発スピードを下げないように自動化していきたいと思っています。

そういうわけで、GitHub Actionsでプルリクを作成したタイミングで自動で実行するようにしました。kurobakoにはコマンドラインインターフェイスと専用のPythonライブラリがありますが、GitHub Actions上でうまく実行するために「github-actions-kurobako」というGitHub Actionsを自作しています。グラフの描画のほかに、（スライドを指して）右の写真のようにPRのコメントに結果を貼っています。

ただ貼るだけではありません。例えば新しいコミットを追加してプッシュすると、Actionが新しくトリガーされますが、その際にその結果をまた新しくコメントすると過去の結果などもいろいろと交じってしまって、すごくPRが見にくくなってしまいます。そのため、同じベンチマーク問題についてすでにコメントで結果が貼られている時は、過去のコメントを編集して更新しています。

実際にCMA-ESでは、これを使って3つのベンチマーク関数を実行しています。ただ少し難しい問題があり、先ほど紹介したWarm Starting CMA-ESは、素直にベンチマークを回すことができません。その理由は、実際ここで動かしているベンチマーク問題が、手元のMacBook Proでも5日から7日、1週間近くかかるようなすごく重たいベンチマークになっているからです。

私もWarm Starting CMA-ESを実装して再現実験した時は、GCPのAI Platformなどに分割して投げて実行しました。しかし、手元のMacBook Proでこれだけ時間がかかってしまうものをGitHub Actionsで実行するのは、計算リソース上不可能なので、近似的な評価値でもかまわないから似たような問題をうまく回したいと思ってやっています。

ここで、kurobakoの開発者である太田さんがやってくれました。私が以前AI Platformなどに投げて回していた時の実験結果をもとに、それと似たような評価値を推論するランダムフォレストのモデルを学習して作ってくれました。

そのサロゲートモデルを使うことで、実際にLightGBMのベンチマーク実験を回すのではなく、サロゲートモデルの評価推論値を代わりに使うことで、もともと5日から7日かかっていた実験が、GitHub Actions上で1分28秒という現実的な時間で動かせるようになりました。

「Fuzzing」によるバグの検出

最後に紹介するのが「Fuzzingによるバグの検出」です。CMA-ESライブラリを公開したのは、1年少し前になりますが、いろいろな方に使われている状態です。それ自体はうれしいですが、けっこうバグの報告を受け取ることがあります。

バグの報告を見ていると、そもそもCMA-ESが扱えない想定外の入力が渡されていて、それによってオーバーフローのエラーや例外が発生しています。1つ例を挙げると、どの点をサンプルしても同じような評価値になる場合、多変量正規分布の共分散行列はどんどん大きくなっていきますが、一定のタイミングでどこかsigma（表示変数）がオーバーフローエラーを起こしてしまって、Issue報告が来たりします。

こういう問題への対処はけっこう難しいと思っています。そもそも想定していない入力ですし、こういう探索空間、ベンチマーク問題をたくさん用意するのはなかなか難しい。

これをどうにか一斉に洗い出したい、なにか方法はないかと考えていた時、そういえばソフトウェアのテスト技法の中にはこういう問題に対処する方法があったと思いました。それがFuzzingです。

Fuzzingは、自動で大量に入力データを生成して、プログラムがクラッシュするような予測不可能な入力を発見するソフトウェアのテスト技法です。出てくるコンポーネントに「Fuzzer」というものがあり、Fuzzerが入力をひたすら生成します。今回、このFuzzingのテスト対象がCMA-ESライブラリです。

Fuzzerにはこの中身がわかりませんが、インターフェイスはわかっていて、ひたすら入力を送ることができるという構成で動かします。こちらも、ただやみくもに入力を生成していくのではなく、プログラムがクラッシュしそうなところを探します。どういう情報をもとに探すかというと、カバレッジの情報です。入力はたいていそれを動かして、その時のカバレッジの情報をもとに、まだ探索していない分岐などを自動的に探して、クラッシュしに行ってくれます。

もし、うまくクラッシュする入力データが見つかれば、それを「Crasher」といいますが、そのCrasherの情報をもとに「ああ、こういうケースでプログラムが壊れるんだな」となり、プログラムを修正できます。

テストには「Hypothesis」と「Atheris」を併用

Pythonには、FuzzingのほかにFuzzingに似たテスト技法「Property Based Testing」がありますが、そういうものを使えるフレームワークがあります。おそらく一番有名なのは「Hypothesis」です。

私は最初こちらを使っていましたが、無償で使えるOSS版だとかゆいところに手が届かなかったので、現在Googleの「Atheris」を使っています。Atherisは、「libFuzzer」という有名なCのFuzzingライブラリを使ったものです。

Macユーザーの場合はAppleのClangがlibFuzzerを同梱していなかったりするので、Atherisを使うためにはLLVMのコードを落としてきて自前でClangビルドするなど、少し使うのが面倒だったりします。しかし、すごくよくできていて、かゆいところにも手が届くライブラリです。

ただ、現状私はHypothesisとAtherisを併用しています。なぜなら、NumPy配列を入力として与えたいと思うことがよくあるからです。Atherisは、わりとプリミティブな変数や型しかサポートしていないので、インターフェイスの部分だけHypothesisを使って、実際のFuzzingエンジンの部分ではAtherisを使う。このHypothesisで書いたテスト対象のコードを動かしています。

実際にこちらを動かすことで、例外を発生する入力パターンを2件発見して修正しました。軽微な問題だったので残していてもさほど問題はなかったと思いますが、ひとまずなにかあればFuzzingで洗い出せる状況ができています。

ということで、CMA-ES Samplerについてお話ししました。CMA-ES Samplerの使い方はとても簡単で、samplerオプションから、特にオプションを指定せずにオブジェクトを作ってCMA-ES Samplerを指定するだけで使えます。けっこう性能が上がるケースもあるので、ぜひ使ってみてほしいです。

また、弊社の野村が考案した「Warm Starting CMA-ES」は、利用できる箇所がけっこう多いと思うので、ぜひそちらも使ってブログなどに書いてもらえるとうれしいです。

最後に、サイバーエージェントは開発者や研究者を募集しているので、もしご興味のある方がいれば、（スライドを指して）こちらからご連絡いただければうれしいです。発表は以上です。ありがとうございました。

質疑応答

司会者：芝田さん、ありがとうございました。チャットに質問が来ています。けっこう前のページになってしまいますが、「アニメーションを見る限り、CMA-ESだと評価関数に局所最適解がたくさん、しかも場所的に早いところにある場合、うまくいかなそうな感じがしましたが、そういった場合に対応策などはありますか？　単独のガウシアンの代わりにGMMを使うなど」。

芝田：ありがとうございます。おっしゃるとおりで、すごくいい質問だと思います。こちらの問題に対処する方法は大きく2つ知られています。

1つは、「population size」を大きくする方法。例えば、CMA-ESの分布を更新するにあたって、いくつか解を生成して、そちらの情報をもとに分布の更新を行っていきます。では、いくつ解を生成して評価をして、1回の分布の更新にいくつ解を使うのかというのが、population sizeという値です。こちらは大きければ大きいほど、そういう局所解にはまらずに、よりよい解に到達することが知られているので、こちらをすごく大きくするという方法が1つです。

もう1つは、IPOP-CMA-ESという、先ほど紹介したCMA-ESのリスタート戦略を使う方法です。「restart_strategy」というオプションを使うことで指定できますが、これは局所解にはまって、sigmaが十分に小さくなって収束したと判断されるタイミングでリスタートします。

リスタートする時は、平均ベクトルをもう一度ランダムで適当な場所に置きます。その時にpopulation sizeを、先ほどまでの2倍とか3倍とか、数倍に増やすことでより局所解にはまらずに探索を進める手法です。ですのでポイントは、分布が収束した時にリスタートすることと、population sizeを大きくすることが一般的な解決策です。

司会者：ありがとうございます。少し時間が押していますが、もう1つだけ回答をお願いします。「今回の事例では、Warm Starting CMA-ESは保存済みのモデルに追加のデータを食わせているだけに見えるのですが、ツールとしての利便性は別として、なにかそれ以上に特別なことはあるのでしょうか？」という質問をもらっています。

芝田：ありがとうございます。少し図が紛らわしかったのかもしれませんが、こちらで使っているのは前回の試行結果です。ですので、ここではモデルではなく、前回探索した時のハイパーパラメーターとその評価値のセットが使われています。

その値をそのまま使っているわけではなく、その評価値の情報をもとに有望な領域を推定して、そこに多変量正規分布の平均ベクトルや共分散行列を構築するといった手法です。

司会者：では、いったんここで質疑応答を終わりにして、芝田さんの発表は以上にしたいと思います。ありがとうございました。

芝田：ありがとうございました。