Add nelder-mead sampler

[KanaiYuma-aist]

Nelder-Mead Sampler と、対応したテストを追加しました。

Nelder-Mead Sampler の仕様

• 基本的には現行aiaccelの _nelder_mead.py をベースとしています。
  • Vertex クラス、Store クラスは削除しました。
• Sampler の引数は、パラメータの範囲設定の dict と初期点のランダムサーチに使う seed 値の int 、NelderMeadの頂点移動に用いるパラメータ coef の各パラメータ(r, e, ic, oc, s) のfloatとしています。
• 探索パラメータを計算した際に、範囲外のパラメータが出力された時は、その座標の計算を行わずに(内部的にはinfとして扱い)次の探索パラメータの計算を行います。
• 現状、並列化には対応していません。

テストについて

• ユニットテストを tests/unit_tests 直下に、アルゴリズムテストを tests/sampler/nelder_mead 直下にそれぞれ追加しました。
  • ユニットテストのカバレッジは 96% となっています。

    
    $ coverage report
    Name                                           Stmts   Miss  Cover
    ------------------------------------------------------------------
    aiaccel/__init__.py                                0      0   100%
    aiaccel/hpo/__init__.py                            0      0   100%
    aiaccel/hpo/samplers/__init__.py                   0      0   100%
    aiaccel/hpo/samplers/nelder_mead_sampler.py      200      3    98%
    tests/unit_tests/test_nelder_mead_sampler.py     394      0   100%
    ------------------------------------------------------------------
    TOTAL                                            594      3    99%

  - アルゴリズムテストは results.csv から想定している計算結果を読み取り、 `optuna.study()` で探索を実行して、パラメータと計算結果を小数点以下第7位(assertAlmostEqual のデフォルト設定)まで一致しているかどうかを判定しています。

[KanaiYuma-aist]

NelderMeadAlgorismの実装を yield を用いて、極力オリジナルの NelderMead に近い形で改修しました。 UnitTest は並列化実装の調査・改修後に修正予定です。

[KanaiYuma-aist]

@yoshipon pushありがとうございます。

Validate code formats や Optimizer Algorithm Test がエラーになる軽微な typo を修正しました。 また、 generate_initial_vertices は __iter__ 内部に移しても問題無かったので、削除しました。

98a15178437cc560ff60f9548773b21aeb71c866

[yoshipon]

修正ありがとうございました．細かい部分何か所か修正させて頂きました． ruff format が抜けていたので，mypy / ruff等はpre-commitで確認頂くと良い気がします．

やっと理解できたのですが，確かにnum_iterationsって反復回数ではないから意味がないんですね．削除しました． あと，verticesとvaluesについて，可視化しようと思うとメンバで持ってないと困りますね… ごめんなさい，これも戻しました．

seedですが，np.random.seedを指定するのでなく，rngのインスタンスを保持しておいて，そのseedを設定するように修正頂いて良いでしょうか．

[KanaiYuma-aist]

np.random.RandomState に seed を設定し、それを用いて乱数生成するように変更しました。

9a2f5daf9435f3e7c083cf5c65a824b79f48980f

[yoshipon]

修正ありがとうございます．では一旦，Optunaでの並列サンプリングについて調査頂き，Slack等でご報告頂いて議論できればと思います．

[KanaiYuma-aist]

調査中に発見した懸念点について、共有します。

optunaの機能に study.enqueue_trial があります。 https://optuna.readthedocs.io/en/stable/reference/generated/optuna.study.Study.html#optuna.study.Study.enqueue_trial

これは初期パラメータを固定したりするのに使われる機能ですが、現状のNelderMeadSamplerでこの機能を用いようとすると想定していない挙動を取ります。

study.enqueue_trial で指定されたパラメータを NelderMeadAlgorism に反映する機能が無いため、 パラメータを study.enqueue_trial で固定しようとすると、 NelderMeadAlgorism 内ではパラメータはランダムで選ばれたパラメータが利用され、 計算結果のみ study.enqueue_trial で指定されたパラメータの結果が利用されます。

例 ユーザプログラムを f(x, y) とした時、 study.enqueue_trial({"x": 5, "y": 5}) が実行されると、 パラメータ {"x": 5, "y": 5} の計算結果 f(5, 5) となるべきところが、 パラメータ {'x': 3.745401188473625, 'y': 9.50714306409916}(ランダムに選ばれたパラメータ) の計算結果 f(5, 5) となる。

[KanaiYuma-aist]

並列化処理を一部残して削除し、並列実行時（パラメータ出力不可のタイミングで before_trial が呼ばれた時）と enqueue_trial 実行後に ask が実行された時（trial.system_attrs["fixed_params"] が存在する時）に RuntimeError を発生させるように改修しました。

1e7e6e3b308a684830e92d186b4f10e724875808

[KanaiYuma-aist]

不適切なタイミングで ask を実行した際

というのは具体的にはどういう状況でしょうか？

ask-tell で reflect 後等のパラメータが出力できないタイミングで ask し、tell を未実行の状態で ask をもう一度呼び出すような状況を想定しています。

エラーメッセージを読んで「なぜoutputできないのか」が類推できる方がユーザによって親切と思います． 「パラレルで実行したり，XXX (↑の状況) で実行したりしていませんか？」などをメッセージに付け加えた方が良い気がしています．

承知しました。そのように付け加えます。

[yoshipon]

ご説明ありがとうございます．

tell を未実行の状態で ask をもう一度呼び出すような状況を想定しています。

これは状況的には「askのparallel callはできない」と等価だと思うのですがいかがでしょうか．実際複数のtrialが並列して存在しているので．

[KanaiYuma-aist]

そうですね。「askの並列呼び出し(parallel call)はできない」のメッセージを表示するほうが具体的で良さそうです。 そちらに変更しておきます。

[KanaiYuma-aist]

vertex_queue を追加し、パラメータの受け渡しを queue で行うように改修しました。 その都合で非同期処理(threading)を追加しました。

is_ready の制御は NelderMeadAlgorism が行うのが適切だと思い、get_vertex, put_vertices メソッドを追加して、それらで is_ready を制御するようにしました。

924cdd7bb3d2e2efe34aa3b857c43b88d7e18706

[KanaiYuma-aist]

is_ready を NelderMeadAlgorism 内に保持させると、非同期処理の都合で記述が複雑になるので、NelderMeadSampler 内に移動させました。 （vertex_queue が空かどうかで is_ready を制御しようとすると、 reflect の計算処理中に ask が実行されると、本来 reflect のパラメータを返せるタイミングにも関わらず、vertex_queue にパラメータが put される前故に False 扱いになってしまう等）

71e80820f9aa71b85fc3ba7432e6aa5841ea88cd

[KanaiYuma-aist]

(開発者会議メモ) ・ミューテックス(threading.lock？)を利用して、 is_ready を削除する（vertex_queue が空の時に ask が実行されたらエラーを raise するようにする） ・threading を立ち上げるのは NelderMeadAlgorism 内にする ・NelderMeadAlgorism 内にqueue 用の setter getter を作成する

[KanaiYuma-aist]

NelderMeadAlgorism を yield を用いる形に改修しました。

なお、_waiting_for に関しては、yield と return を両立する形だと mypy でエラーが出たので、 返り値の result をメンバにして yield のみを用いる形に変更しました。

https://github.com/aistairc/aiaccel/blob/7d3f9a971803a365b4766afdc41a5ffb853e8e2a/aiaccel/hpo/samplers/nelder_mead_sampler.py#L59-L65

[yoshipon]

ありがとうございます。 Generatorの型をNone, None, Noneでなく、正しく指定すればmypy通りませんでしょうか？

[KanaiYuma-aist]

型の書き方を勘違いしていただけでした。（引数の3つ目に return value の型を書くんですね・・・）

修正してメンバの results は削除しました。

[KanaiYuma-aist]

開発者会議メモ ・ユニットテストの expand 等のテスト内部を一般化する ・Sampler内部の Coordinate の名称が optuna 的に適切かどうかを調査する ・user_attrs の中身の先頭文字は小文字か大文字化 optuna 的にどちらが正しいのかを調査する

[KanaiYuma-aist]

・Sampler内部の Coordinate の名称が optuna 的に適切かどうかを調査する

TPESampler を参考にすると、適切なのは param sample 辺り？ https://github.com/optuna/optuna/blob/master/optuna/samplers/_tpe/sampler.py

・user_attrs の中身の先頭文字は小文字か大文字化 optuna 的にどちらが正しいのかを調査する

GridSampler を参考にすると、小文字が正しい。 https://github.com/optuna/optuna/blob/master/optuna/samplers/_grid.py

[KanaiYuma-aist]

少し手が空いたので、下記のペンディングになっている項目について調査・ローカルにて仮実装し、要相談項目をまとめました。

• study.enqueue_trial について

現状のコードに対して、ローカルにて initial 時限定で enqueue_trial が反映できるように仮実装しました。 （まだpushはしていません。） 問題なければこのまま実装してしまいたいのですが、 nelder_mead のメインループ中に enqueue_trial が発生した時の挙動はどのようにするのが適切でしょうか？ （以前 enqueue_trial についてお話した際は、ループの最初の reflect に戻る？ような処理を行うと聞いた覚えがあります。その場合、shrink中に enqueue_trial が発生した場合の処理を考える必要がありそうです。）

• 並列化について

現状のコードであれば、 NelderMeadAlgorism の引数 block （queue.get 時にブロックするかどうか）を True にし、 get_vertex の前後に threading.lockによるロックを入れれば、 optunaの機能(study.optimize(njobs=3))で並列化できることを確認しました。

ただし、block = True の状態だと、ユーザが ask-tell で sampler を用いると、実装によっては queue.get 時にデッドロックする可能性が有ります。 上記を踏まえて、並列実行の ON / OFF ができるような引数（ON の時に block = True にする）を追加するのが適切かと思うのですが、いかがでしょうか？

[KanaiYuma-aist]

開発者会議メモ

• enqueue_trial について
  • 通常の NelderMead で決定されるパラメータの他に、enqueue されたパラメータも並列で計算できるようにする。
  • NelderMead で決定されたパラメータと、enqueue されたパラメータとで比較して、enqueueされたパラメータの方が良ければ、reflectに戻ってenqueue されたパラメータを単体に取り込む。
  • enqueue されたパラメータの方が悪ければ、NelderMead で決定されたパラメータを取り込んで、通常通り NelderMeadの処理を続行する。
  • shrink 中は shrink 中に決定された複数のパラメータと、enqueue されたパラメータとで比較して、より良い点を単体に取り込む。（？）
  • (initial 中は enqueue された分だけランダムで打つパラメータを減らす？ それとも shrinkと同様にランダムで打ったパラメータと、enqueue されたパラメータとで比較する？ 前者の方が自然だと思われるので、ひとまずは前者で進める)
• 並列化について
  • 上記の enqueue_trial の並列化をできるようにする。
  • threading.lock の処理は NelderMeadAlgorism 内に記述して、 NelderMeadAlgorism をスレッドセーフとする。
  • 他は基本的には上記のコメントの「並列化について」の通りにする。

[KanaiYuma-aist]

NelderMead で決定されたパラメータと、enqueue されたパラメータとで比較して、enqueueされたパラメータの方が良ければ、reflectに戻ってenqueue されたパラメータを単体に取り込む。

enqueue されたパラメータの方が良かった場合、 そのパラメータを単体の一番valueが低い vertexと置き換えて reflect を行う （単体の value(s) > enqueue されたパラメータのvalue(s) > NelderMead で決定されたパラメータのvalue の場合は、そのまま NelderMeadの処理を続行する？） or そのパラメータを reflect で計算されたパラメータとして扱い、その後の処理(expand or inside_contract or outside_contract)を行う のどちらの方が良いでしょうか？

（後者は NelderMead の計算が崩れそうなので、一旦前者で進めます。）

[KanaiYuma-aist]

懸念点メモ

• enqueue されたパラメータを反映した結果、アフィン独立ではない単体が生成された時にどうするか（今までもランダムで決定された初期点で生成される確率は一応存在しましたが）
• 初期 simplex の計算段階で dimension + 1 以上のパラメータが enqueue された時にどうするか
  • それらのパラメータの中からより良い dimension + 1 個のパラメータを選び、初期点とするのが適切？

[KanaiYuma-aist]

3/18の開発者会議内で協議した内容に従って、 enqueue_trial と並列化に対応しました。

以下、差分について補足します。

• NelderMeadAlgorism
  • enqueue_trial にて追加されたパラメータと計算結果を受け取る queue を追加しました。(enqueue_vertex_queue, enqueue_value_queue)
  • put_enqueue_vertex メソッドでは、enqueue_trial で指定が無かったパラメータについては、ランダムでパラメータを決定してから enqueue_vertex_queue に put します。
  • _waiting_for_list メソッドで、 enqueue_value_queue から計算結果を取り出す処理を追加しています。
  • _initialization メソッドでは、engueue_trial で追加されたパラメータ数が dimension + 1 以下の場合に、ランダムでパラメータを生成して、yield で返します。
  • パラメータ数が dimension + 1 よりも多い場合は、より良い dimension + 1 個のパラメータを選択して、初期 Simplex とします。
  • _recontract_simplex メソッドでは、engueue_trial で追加されたパラメータに、Simplex の一番評価の悪い value 及び reflect 等で計算した value よりも良い value が存在した時に、既存の Simplex のパラメータ、reflect 等で計算したパラメータ、engueue_trial で追加されたパラメータの中からより良い dimension + 1 個のパラメータを選択して、Simplex を更新します。
  • _expand, _outside_contract, _inside_contract メソッドは、ruff のエラーの都合で _generator メソッドを短くするために分離したものです。
  • _generator メソッドでは、メインループ中に計算したパラメータと結果を past_vertices, past_values で記憶して、 _recontract_simplex メソッドで利用しています。
  • 各計算後に _recontract_simplex メソッドを追加しています。
• NelderMeadSampler
  • parallel_enabled 引数を追加しています。True の時に optuna.study.optimize による並列化が可能になります。
  • （手動で ask-tell を用いて並列化する際には False にしないとデッドロックが起きる可能性があるのが、少し複雑かもしれません）
  • before_trial メソッドでは、trial.system_attrs["fixed_params"] が存在する (enqueue_trial が発生している)場合には、NelderMeadAlgorism.get_vertex() は実行せずに、put_enqueue_vertex メソッドから帰ってきた param を計算に用います。
  • after_trial メソッドでは、通常の NelderMead から出力されたパラメータと、enqueue_trial で追加されたパラメータをそれぞれ個別に NelderMeadAlgorism の queue に put します。

[yoshipon]

修正ありがとうございます． あーcomplexityのエラー出ちゃうんですね．ここは分けると逆に可読性が下がると個人的には感じます． noqaで無視しても良い気がするので，今日の打ち合わせで議論させて下さい．

enqueue_valueの扱いですが，例外で対応するのはどうでしょうか？

while True:
    try:
        ...
        self.values[1:] = yield from self._waiting_for_list(len(self.vertices[1:]), self.values)
        ...
    except Enqueued as e:
        self.vertices, self.values = self.reconstract_simplex(
            self.vertices,
            self.values,
            e.enqued_vertices,
            e.enqued_values
        )

のようなものをイメージしています． waiting_for_XXX メソッドの中で，単体の点より良い点が見つかったら例外を吐く実装です． try-exceptの濫用でしょうか…？

[KanaiYuma-aist]

開発者会議メモ

• ruff のエラー ( _generator is too complex )について
  • _generator に限り（計算のアルゴリズムを記述する箇所に限り）、ruff の （できれば complex のルールのみ？）適用しないようにする。
  • 上記の方法を調べる必要あり？
  • 適用しない場合のルール作りも必要？（際限なく複雑化させていいわけでも無いため）
  • （適用しない　ではなく　制限を緩める（ある程度の複雑化を許容する）　でも可？）
• enqueue_valueの扱い
  • simplex の最悪パラメータ、及び reflect 等で計算済みかつ simplex に未反映のパラメータよりも良いパラメータが enqueue で入力された場合に、例外を投げる
  • 例外を投げる箇所はどこが適切？（nelder_mead のメインループ内で raise するのは、アルゴリズムが見辛くなって好ましくないので、_waiting_for_float 内部で raise する？）
  • try - except で例外をキャッチして、そこで recontract_simplex を呼び出す。

[KanaiYuma-aist]

try - except で例外をキャッチして、そこで recontract_simplex を呼び出すように改修しました。 recontract_simplex を呼び出す箇所が1箇所のみになったので、recontract_simplex 関数は削除して _generator 内に統合しました。

d9c0b6be36301dd16e0138e169aabebe9af42e00

また、この改修で ruff のエラー ( _generator is too complex )は解消されました。 try - except を導入した分で if 文が減ったのが解消された理由のようです。 （これ以上なにか _generator に追加することがあれば、また発生しそうですが・・・）

[KanaiYuma-aist]

開発者会議メモ

• ruff のエラーは try - except の実装でギリギリ回避可能な状態になったので、一旦保留とする。
  • 発生自体は _generator の行の末尾に # noqa: C901 を追加することで、 _generator 内部でのみ ruff の too complex エラーを無視できる。 https://docs.astral.sh/ruff/linter/#error-suppression
• 並列処理・enqueue_trial 関連のテストコードを書く。

[KanaiYuma-aist]

並列処理・enqueue_trial 関連のアルゴリズムテストを追加しました。

dc7c71c5e475cdcafb7e10ee9e389d1c8123197a 7760fe239dd7529ec97d576ff6c59de02fef4a08 5e28324294536e4666e3927504ea3e2b5b4d5bab

[KanaiYuma-aist]

開発者会議メモ

• テストコードの pytest への移行を行う
  • mock は pytest には無い（正確には pytest-mock というモジュールはあるが、unittest.mock のラッパーなので実質的にはpytestには無い？）ので、暫定で mock は unittest のままにする
• value_queue, enqueue_vertex_queue, enqueue_value_queue の統合を行う（コードの確認？）
• enqueue_trial の処理を行う際は、すべてのパラメータが指定されている時のみ処理を行う
  • すべてのパラメータが指定されていない時は例外を出す
• nelder_mead でパラメータを出力できない時に、指定された他sampler？(randomやtpe)からパラメータを出力するオプションを追加する
  • そのパラメータは enqueue と同様に扱う（simplex のよりも良い結果が出たら、simplex を再構成する）

[KanaiYuma-aist]

push 頂いたコードを元に並列処理・enqueue処理を正常に行えるように改修しました。

主な差分は下記コミットにまとまっています。 896d72ca73fbf52a0361c717f711d57ffad9d651

以下差分の補足です。

• NelderMeadAlgorism
  • 並列処理の initialize 時に results.get() を実行する回数が分からないと、デッドロックすることがあったので、self.num_enqueued を追加して results.get() の実行回数を明確にしました。
  • それに伴い、_waiting_for_results, _initialization の結果受け取りのループ回数に self.num_enqueued を追加しています。
  • raise UnexpectedVerticesUpdate を実行する条件を max(単体の values) > min(enqueue values) に変更しました。（暫定）
  • _initialization 内の処理を random vertices 生成 -> 計算結果の受け取り の処理順に変更しました。
  • 計算結果の受け取り -> 不足分の random vertices 生成 だと、ランダム値生成後に enqueue が発生した際に results に enqueue されたパラメータが残ってしまい、_initialization中に enqueue されたパラメータを処理できなくなります。
• その他軽微なtypoの修正(不等号の向きや引数の順番等)

[yoshipon]

pushありがとうございます．確認しました．めっちゃバグ埋め込んでましたね… すみません．

[KanaiYuma-aist]

after_trial での整列を削除して、 _waiting_for_results で vertex , valueを両方ともパラメータが帰ってきた順番で返すことで、vertex -value 間の整合性を取るように改修しました。

c17169f11bb0d76e2b437f9b00845efc2d8fe9fe

また、initialize 中に enqueue_trial が発生せず、ランダムなパラメータのみ生成された場合にも、UnexpectedVerticesUpdate が発生していたので、 （結果的にはそのままでも正常に動作はしていたが、想定外の挙動ではあるので、）UnexpectedVerticesUpdate が発生する条件も修正しました。

d7fbbff77583c6b72894e0d345558c80a7b2e128

[KanaiYuma-aist]

nelder_mead でパラメータを出力できない時に、指定された他sampler(randomやtpe)からパラメータを出力するオプションを追加しました。(sub_sampler) （sub_sampler 機能の sampler test は作成中です。）

c08a2ac6418e6d7d259d23cea001518be1a62c75

アルゴリスムテストコードを pytest に移行しました。

e6a262d62f134a5ccc0cc2b85a01f7104e2931c8

[KanaiYuma-aist]

sampler test をpytest に移行しました。 また、sub_sampler 機能の sampler test を追加しました。

bb24195e78f79e1107dcef2d73eb6f47c8470b0b

[KanaiYuma-aist]

開発者会議メモ

• sub_sampler
  • sampler 内部で sub_sampler 用の study を呼んでいるが、これを sub_sampler の before_trial, sample_independent, after_trial を呼び出す形に改修する
• テスト関連
  • クラスにする必要が無い箇所を修正する
  • fixture 関連は共通している部分のみとして、部分的に利用している箇所は関数化もしくはクラス化する

[KanaiYuma-aist]

@yoshipon 次回の開発者会議が3週間後（恐らく5/13）とかなので、上記が終わった後にやることがあればコメントください。 （sampler のドキュメント作成とか？）

[KanaiYuma-aist]

sub_sampler 用の study を sub_sampler の before_trial, sample_independent, after_trial に置き換える場合の懸念点

• before_trial, sample_independent, after_trial の引数に study が含まれているが、sub_sampler の before_trial 等を実行する際の引数 study は（study(sampler=sub_sampler) ではなく） nelder_mead_sampler で用いている study(sampler=nelder_mead_sampler) で問題無いか？
  • sampler の実装次第？
  • TPESampler の場合は、過去に計算したパラメータと結果を参照しているのみだったので、特に問題無さそうだった。（むしろ nelder mead 側で計算した結果もTPEで参照出来てる？のでこちらの方が良いのかもしれない）

[KanaiYuma-aist]

sub_study を削除して、sub_sampler の before_trial, sample_independent, after_trial を呼び出す形に改修しました。 懸念->https://github.com/aistairc/aiaccel/pull/346#issuecomment-2068558990

781c7a13581646a7da2babef2b1d4a4981179564

テストコード中のクラスにする必要のない箇所のクラス削除、部分的にしか利用していない fixture の削除を行いました。

f56f429b0b1e986dc39d2a8f3d61626666fa3d61