テンソル列最適化 ttopt#

ttopt は、Tensor Train Optimization (TTOpt) によるパラメータ探索を行う Algorithm です。 目的関数をパラメータの組で添字付けられた高次元テンソルとみなし、そのごく一部だけを選択的に評価する交差近似によって、勾配を使わずに最適値とその位置を探索します。 手法の概要は後述の「アルゴリズムの説明」を参照してください。

前準備#

TTOpt の実行には scipy が必要です。また、MPI 並列化を用いる場合は mpi4py をインストールしてください。

$ python3 -m pip install scipy
$ python3 -m pip install mpi4py

入力パラメータ#

[algorithm.param] セクション#

  • min_list

    形式: 実数のリスト。長さは dimension の値と一致させます。

    説明: 各パラメータが取りうる最小値。

  • max_list

    形式: 実数のリスト。長さは dimension の値と一致させます。

    説明: 各パラメータが取りうる最大値。

[algorithm.ttopt] セクション#

次のハイパーパラメータを指定できます。

  • p_points

    形式: 整数または整数のリスト。長さは dimension の値と一致させます。

    説明: パラメータ \(x_i\) を離散化する際の基数 \(P_i\) （分解した各インデックスがとる値の数。2進数表現なら 2）。 パラメータは \(N_i = P_i^{q_i}\) 個の等間隔点に離散化されます。 整数の場合はすべての次元で同じ値になります。 デフォルトは 2 です。

  • q_points

    形式: 整数または整数のリスト。長さは dimension の値と一致させます。

    説明: パラメータ \(x_i\) を離散化する際のインデックスの分解数 \(q_i\) （分割数 \(N_i = P_i^{q_i}\) を決める指数。2進数表現ならビット数に相当）。 整数の場合はすべての次元で同じ値になります。 デフォルトは 1 です。

注釈

デフォルト設定（p_points = 2, q_points = 1）では、各パラメータは \(2^1 = 2\) 点にしか離散化されません。 連続パラメータを最適化する場合は、十分な分解能が得られるよう q_points を 10〜20 程度 （\(2^{10} \approx 10^3\) 〜 \(2^{20} \approx 10^6\) 分割）に設定してください。

  • r_max

    形式: 整数 (default: 4)

    説明: テンソル近似のランクの上限（小テンソル同士をつなぐボンド次元の最大値）。大きいほど複雑な関数形を捉えやすくなりますが、最適化の各ステップでの目的関数の評価回数が増えます。

  • max_f_eval

    形式: 整数 (default: 10000)

    説明: 目的関数の評価回数の上限。最適化の計算予算に相当します。カウンタは候補点の束を評価するたびに更新され、束の評価後に上限判定を行うため、実際の評価回数は max_f_eval をいくらか超えることがあります。カウンタには評価をリクエストした候補点数（キャッシュ済みの点を含む）が計上されます。

  • maxvol_tol

    形式: 実数 (default: 1.001)

    説明: 最大体積部分行列を求める反復（後述の maxvol 法）の停止閾値。1 に近づけるほど厳密な最大体積条件まで反復を続け、ちょうど 1 に設定すると厳密な最大体積条件を要求します。1 未満の値は意味を持ちません（停止条件が満たされないため、反復は常に maxvol_max_it 回まで実行されます）。通常はデフォルト値のままで問題ありません。

  • maxvol_max_it

    形式: 整数 (default: 1000)

    説明: 最大体積部分行列を求める反復の最大回数。

  • init_points

    形式: 実数のリストのリスト (default: [])

    説明: 最適化の冒頭で評価する初期候補。内側の各リストの長さは dimension と一致させます。任意のパラメータで、既知の候補領域を最適化器に伝えるために用います。

  • save_eval_history

    形式: 真偽値 (default: true)

    説明: true のとき、評価した各候補点を ttopt_eval_history.txt に追記します（MPI ランク 0 のみ）。

  • eval_history_buffer_rows

    形式: 整数 (default: 256)

    説明: ttopt_eval_history.txt への書き出し閾値 \(N_{\mathrm{flush}}\) 。バッファ内の行数が \(N_{\mathrm{flush}}\) 以上になった時点で、バッファ全体をまとめて書き出します。

出力ファイル#

[base] の output_dir を OUTPUT と書くことにします（root_dir からの相対パスで指定した場合は root_dir/output_dir の絶対パスが使われます）。 各 MPI ランクは、作業ディレクトリとして OUTPUT 直下のランク番号付きサブディレクトリ（例 OUTPUT/0/）を用います。TTOpt が書き出す主なファイルは OUTPUT 直下に置かれます（下記、特に記載がなければ MPI ランク 0 のみが作成）。

ttopt_hyperparameters.txt#

準備フェーズ（prepare）の終了時に、入力で与えた主なハイパーパラメータを 1 行 1 項目で保存します。

nprocs = 1
bounds = [[-6.0, 6.0], [-6.0, 6.0]]
p_points = [2 2]
q_points = [20 20]
r_max = 4
max_f_eval = 10000
maxvol_tol = 1.001
maxvol_max_it = 1000
save_eval_history = True
eval_history_buffer_rows = 256

ttopt_history.txt#

最適化ループの各ステップ（候補点の束を評価し、これまでの最良点を更新した直後）ごとに、累積の関数評価回数と、その時点での最良点 x_opt および最良値 fx_opt が追記されます。先頭の # 行は列の意味です。

# $1: count
# $2: x_opt[0]
# $3: x_opt[1]
# $4: fx_opt
8 3.420030040769616e+00 -9.735097632501253e-01 7.005409201321578e+00
24 3.420030040769616e+00 -2.098510836134754e+00 2.643948442798083e+00
...

次元が \(D\) のとき、データ列は 1 列目が評価回数、2 列目から \(D+1\) 列目が x_opt[0], ..., x_opt[D-1]、最後の列が fx_opt です。

res.txt#

終了後の全体最良解（MPI 使用時は全ランクの結果のうち最良）を、目的関数値 fx と各パラメータ（既定のラベルは x1, x2, …）でテキスト保存します。

fx = 3.188892404355571e-08
x1 = 3.584424576210571
x2 = -1.8480795365138398

ttopt_eval_history.txt#

save_eval_history が true のときのみ OUTPUT/ttopt_eval_history.txt に作成されます。評価をリクエストした各候補点（キャッシュ済みでソルバーが呼ばれなかった点も含む）の座標と f(x) が行単位で並びます（先頭の # 行は列ラベル。パラメータ名は label_list が設定されていればそれが使われます）。1列目は行の通し番号です。

# $1: row index
# $2: x1
# $3: x2
# $4: f(x)
1 3.420030040769616e+00 -5.098513697160432e+00 5.218032809779967e+02
2 3.420030040769616e+00 -9.735097632501253e-01 7.005409201321578e+00
...

time.log#

アルゴリズム全体の計測時間は、アルゴリズム側のランク 0 のプロセスのみが OUTPUT/0/time.log に書き出します。

アルゴリズムの説明#

Tensor Train Optimization (TTOpt) [1] は、高次元の離散最適化問題に対する勾配不要のブラックボックス最適化手法です。 連続変数についても、各変数を離散化することで適用でき、離散変数と連続変数が混在する問題にも対応できます。

TTOpt では、目的関数 \(f(x_1, \dots, x_n)\) を、各パラメータの組を添字とする高次元テンソルの要素とみなします。 ただし、この巨大なテンソル全体を明示的に計算することはしません。 Tensor Train（TT。行列積状態 MPS と同等）形式による低ランク表現を利用し、TT-cross と呼ばれる交差近似法によって、必要なテンソル要素だけを選択的に評価します。

TT-cross では、maxvol（maximum-volume）法を用いて、テンソルの構造を効率よく捉えられる行・列に対応するサンプル点を選択します。 この操作を Tensor Train の各次元に沿って繰り返すことで、目的関数の評価回数を抑えながら最適値とその位置を探索します。

また、各パラメータ \(x_i\) に \(N_i = P_i^{q_i}\) 個の離散点がある場合、そのインデックスを \(P_i\) 状態を持つ \(q_i\) 個の小さなインデックスへ分解する「量子化」を行うことができます。 これにより、非常に細かく離散化されたパラメータ空間も、小さな局所次元を持つ高階テンソルとして扱えます。 入力パラメータの p_points, q_points はそれぞれ \(P_i\), \(q_i\) に対応します。

この方法では、探索空間全体を格納したり評価したりする必要がないため、パラメータ空間が巨大な場合や、1回の目的関数評価に大きな計算コストを要する場合に有効です。 また、目的関数の各サンプル点での評価は独立に実行できるため、MPI を用いて複数プロセスに分散することも可能です。

リスタート#

algorithm.checkpoint を true にすると、実行中の状態が status.pickle に保存されます。保存されるのは次のタイミングです。

  1. ダブルスイープ(右→左と左→右の一巡)が完了し、checkpoint_steps または checkpoint_interval の条件を満たしたとき

  2. max_f_eval に到達して実行を終了するとき(最終状態)

run_mode は odatse コマンドの --init, --resume, --cont に対応します。

  • "initial"

    最初から実行します。

  • "resume"

    中断した計算をチェックポイントから再開します。

  • "continue"

    終了した計算を延長します。TTOpt では "resume" と同じ動作になります。 評価回数の上限 max_f_eval はチェックポイントに保存されず、 毎回入力ファイルから読み直されるため、max_f_eval を増やして再実行すると、 保存された状態から続きの評価が行われます。

注釈

延長した計算の結果は、最初から大きな max_f_eval で一括実行した場合と一致します。 再実行時に一部の評価が再計算されますが、評価値のキャッシュもチェックポイントに 含まれるため、ソルバーが再度呼ばれることはありません。

参考文献#

[1] K. Sozykin et al., arXiv:2205.00293 (2022).