tune の設計

設計目標

自動チューニングは、候補を計測することで構成（ブロックサイズ、カーネルの変種、レイアウト）を選びます。素朴に行うと過剰適合します。「勝者」は、たまたま計測された形状で、たまたまノイズが有利に働いた候補であることが多いのです。tune はこれを防ぐポリシーの部品、すなわち頑健なスコア、実用的な同率判定、確認、ホールドアウトを提供し、候補のビルドと実行はアプリケーションに任せます。そこでは候補を他のベンチマークと同じように検証・計測できます。

数学的背景

スコア

$n$ 回計測された候補 $c$ はサンプル $t_1, \dots, t_n$ を持ちます。そのスコアは、stats の設計で導いた頑健性の理由から、使用可能な（有限かつ非負の）サンプルの中央値です。副次的な指標 $s_c$ （ワークスペースのバイト数、コードサイズ）が同率の決着をつけます。

勝者の呪い

$\hat p_c = p_c + \varepsilon_c$ を、真のコスト $p_c$ と平均ゼロのノイズを持つ候補 $c$ の計測スコアとします。計測値の最小値を選ぶと、下方に偏ります:

\mathbb E\bigl[\min_c \hat p_c\bigr] \le \min_c \mathbb E[\hat p_c] = \min_c p_c ,

真に最良の $c^*$ について $\min_c \hat p_c \le \hat p_{c^*}$ であり、期待値を取ると $\mathbb E[\min_c \hat p_c] \le p_{c^*}$ となるからです。コストの似た候補が多数あると、選ばれた候補は良いというより運が良かった可能性が高くなります。ここから 2 つの対策が導かれ、TuningBudget はその両方に名前を付けています。finalists を新しい confirmation_samples で再計測すること（新しいノイズは選択とは独立なので、確認されたスコアは不偏です）、そして勝者を、選択に使われなかった holdout で評価することです。

実用的な同率

閾値 $t$ を指定した select_best は、同率の集合を作ります

F = \Bigl\{\, c : \frac{p_c - p_{\min}}{p_{\min}} \cdot 100 \le t \,\Bigr\},

そして $F$ のうち副次的な値が最良の要素、次に ID が最小の要素を返します。この規則は順序に依存しません。 $F$ は値だけで定義され、第 2 段階は $F$ 上の全順序（副次的な値、次に ID）の最小値であり、ID が一意なら一意に定まります。したがって入力を並べ替えても結果は変わりません。

パレート支配

両方の指標を最小化するとき、 $p_o \le p_c$ 、 $s_o \le s_c$ かつ $(p_o, s_o) \ne (p_c, s_c)$ であれば、 $o$ は $c$ を支配します（ $o \prec c$ ）。フロントは $\{c : \nexists\, o \prec c\}$ です。主コストでソートすると、フロントの副次的コストは厳密に減少します。 $p_a < p_b$ かつ $s_a \le s_b$ なら $a \prec b$ となり矛盾するので、 $s_a > s_b$ です。フロント上で主コストが等しい点は、副次的コストも等しくなければなりません。フロント外のすべての点は、フロント上の点に支配されます（支配は有限集合上の狭義半順序なので、すべての鎖は極小元で終わります）。

大きな空間のランダムな部分集合

seeded_order は、ID のシード付き 64 ビット FNV-1a ハッシュで候補をソートします。これは擬似ランダムな置換として働きます。その最初の $B$ 個の候補を取ります。ID が品質と無関係なら、どの候補も同じ確率で先頭部分に入り、空間の上位割合 $q$ に属する候補を先頭部分が少なくとも 1 つ含む確率は次のとおりです

1 - (1 - q)^{B} .

$B = 60$ で、上位 5 % についてすでに $1 - 0.95^{60} \approx 0.954$ になります。これはグリッドに対するランダム探索を支持する古典的な議論です。¹1 J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization”, JMLR 13, 2012.

設計上の決定

ポリシーはここに、副作用はアプリケーションに

問題。 候補のビルドはカーネルのコンパイルを意味することがあり、その実行はプロトコルの下で検証・計時されなければなりません。選択。 tune はスコアを入力として受け取り、何も実行しません。BuiltCandidate は runner.Implementation を持ちます。理由。 そうすることでチューニングの計測は、他のすべてのベンチマークと同じ検証、キャリブレーション、イベントストリームを通り、チューニングのポリシーは作り物の数値でテストできます。

中央値によるスコア

score_samples は使用可能なサンプルの中央値を取り、使用可能なサンプルのない候補を無効とします。そのため、壊れた計測が 0 や NaN を返したことで候補が勝つことはありません。

有界な先頭部分に対する全探索

exhaustive_scores は列挙の最初の budget 個の候補をスコア付けし、却下されたものも含めてそれぞれに BuildEvent を記録します。seeded_order と組み合わせると、先頭部分は再現可能なランダム部分集合になります。自然な順序と大きな予算では、完全なグリッド探索になります。ポリシー文字列 global:<id> は単一のグローバルな勝者を示します。より細かいポリシー（形状ごと、パレート）は select_best、pareto_frontier、@model.DeploymentPolicy で構築します。

適応的な確認

confirmation_count は、相対的な不確かさが 5 % と 20 % を超えるのに応じて基本の確認回数を 1 倍、2 倍、3 倍にし、予算に制限します。ノイズの多い最終候補はより多くのサンプルを得て、静かなものは時間を無駄にしません。

正しさと不変条件

select_best は使用可能なスコアがないときにちょうど None を返します。それ以外の場合、その結果は使用可能で、最速のものから閾値以内にあり、入力の順序に依存しません（上で導いたとおり）。
pareto_frontier は使用可能で支配されないスコアだけを、主指標、副次的指標、ID の順にソートして返します。
exhaustive_scores は高々 budget 個の候補を調べ、有効な候補に対してのみスコアのコールバックを呼び出します。
seeded_order は入力の置換であり、ID とシードだけに依存します。
confirmation_count は $[0, \text{budget}]$ に収まります。

採用しなかった代替案

ベイズ最適化や進化的探索。 効果的ですが、空間のモデルが必要で、結果の再現が難しくなります。フック（neighbors、seeded_order）によりユーザーが探索を書くことはできます。
平均によるスコア。 1 回のプリエンプトされた実行が結果を決めてしまいます。
生の最小値を選ぶ。 勝者の呪いを受けます。

境界

ここでは候補のビルド、実行、検証は行いません。
TuningBudget、TuningObjective、HoldoutPlan はデータであり、それらを強制する関数はありません。
CandidateSpace.neighbors はパッケージ内のどの関数でも使われません。
exhaustive_scores 自体は seeded_order を使いません。ランダムな部分集合が欲しい場合は、先に空間を並べ替えてください。

J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization”, JMLR 13, 2012. ↩