ベイズ最適化のアルゴリズム

アルゴリズムの概要

ベイズ最適化のアルゴリズムでは、有界領域でスカラー目的関数 f(x) を x について最小化しようとします。関数は確定的でも確率的 (同じ点 x で評価したときに異なる結果を返す可能性がある) でもかまいません。x の成分は、連続的な実数、整数、カテゴリカル (離散的な名前の集合) のいずれにすることもできます。

メモ

この説明全体で、D は x の成分の個数を表します。

最小化の主な要素は以下になります。

• f(x) のガウス過程モデル。

• f(x) の新しい評価位置のそれぞれでガウス過程モデルを変更するためのベイズ更新法。

• 次の評価点 x を決定するために最大化する (f のガウス過程モデルに基づく) "獲得関数" a(x)。詳細は、獲得関数のタイプ と 獲得関数の最大化 を参照してください。

アルゴリズムの概要:

• 変数の範囲内で無作為に選択した NumSeedPoints 個の点 x_i について y_i = f(x_i) を評価します。NumSeedPoints は bayesopt の設定です。評価の失敗がある場合は、評価が NumSeedPoints 回成功するまで無作為な点を選択します。各成分の確率分布は、optimizableVariable の Transform の値に応じて均等スケールまたは対数スケールのいずれかになります。

次に、以下の手順を繰り返します。

1. f(x) のガウス過程モデルを更新して、Q(f|x_i, y_i for i = 1,...,t) の各関数に対する事後分布を取得します (内部的に、bayesopt は fitrgp を使用してガウス過程モデルをデータにあてはめます)。

2. 獲得関数 a(x) を最大化する新しい点 x を求めます。

このアルゴリズムは次のいずれかに達すると停止します。

• 一定の反復回数 (既定は 30)

• 一定の時間 (既定は無制限)

• ベイズ最適化の出力関数またはベイズ最適化のプロット関数で指定した停止基準

並列におけるアルゴリズムの違いについては、並列ベイズ アルゴリズムを参照してください。

モデルをあてはめるためのガウス過程回帰

目的関数 f の基となる確率モデルは、観測値にガウス ノイズが追加されたガウス過程の事前分布です。つまり、f(x) の事前分布は、平均が μ(x;θ)、共分散カーネル関数が k(x,x′;θ) のガウス過程です。ここで、θ はカーネル パラメーターのベクトルです。bayesopt が使用する特定のカーネル関数については、カーネル関数を参照してください。

少し詳しく説明すると、一連の点 X = x_i は関連する目的関数の値 F = f_i で表されます。関数値 F の事前分布の同時分布は、平均が μ(X)、共分散行列が K(X,X) の多変量正規分布になります。ここで、K_ij = k(x_i,x_j) です。

一般性を失うことなく、事前平均は 0 になります。

さらに、分散が σ² のガウス ノイズが観測値に追加されていると考えられます。したがって、事前分布の共分散は K(X,X;θ) + σ²I になります。

ガウス過程回帰モデルを観測値にあてはめるには、ノイズ分散 σ² とカーネル パラメーター θ を求めることになります。このあてはめは、fitrgp によって実行される計算負荷の高いプロセスです。

観測値へのガウス過程のあてはめの詳細については、ガウス過程回帰を参照してください。

カーネル関数

カーネル関数 k(x,x′;θ) はガウス過程回帰の品質に大きく影響を与える可能性があります。bayesopt は、カーネル (共分散) 関数のオプションで定義されている ARD Matérn 5/2 カーネルを使用します。

Snoek、Larochelle および Adams[3]を参照してください。

獲得関数のタイプ

bayesopt では、6 種類の獲得関数を使用できます。3 つの基本タイプがありますが、expected-improvement には per-second または plus による修正もあります。

• 'expected-improvement-per-second-plus' (既定の設定)

• 'expected-improvement'

• 'expected-improvement-plus'

• 'expected-improvement-per-second'

• 'lower-confidence-bound'

• 'probability-of-improvement'

獲得関数は、事後分布関数 Q に基づいて点 x の適合度を評価します。エラー制約 (目的関数のエラーを参照) など連結制約がある場合、すべての獲得関数は Gelbart、Snoek および Adams[2]の提案に従って "適合度" の推定を変更します。制約が満たされる確率の推定値を適合度に乗算することにより獲得関数が得られます。

• 期待改善量

• 改善の確率

• 信頼限界の下限

• 秒単位

• プラス

期待改善量

'expected-improvement' 群の獲得関数は、目的関数の増大要因となる値を無視して、目的関数の期待改善量を評価します。つまり、以下を定義します。

• 最小の事後平均の位置として x_best

• 事後平均の最小値として μ_Q(x_best)

その場合、期待改善量は

$$EI\left(x,Q\right)=E_Q\left[\max \left(0,{\mu }_Q\left(x_{\text{best}}\right)-f\left(x\right)\right)\right].$$

改善の確率

'probability-of-improvement' の獲得関数は、'expected-improvement' と同様の計算をよりシンプルな方法で行います。どちらの場合も、bayesopt はじめに x_best と μ_Q(x_best) を計算します。そして、'probability-of-improvement' の場合、bayesopt はマージン パラメーター m で修正することにより新しい点 x で目的関数の値が向上する確率 PI を計算します。

$$PI\left(x,Q\right)=P_Q\left(f\left(x\right)<{\mu }_Q\left(x_{\text{best}}\right)-m\right).$$

bayesopt は推定ノイズ標準偏差として m を使用します。bayesopt はこの確率を次のように計算します。

$$PI=\Phi \left({\nu }_Q\left(x\right)\right),$$

ここで

$${\nu }_Q\left(x\right)=\frac{{\mu }_Q\left(x_{\text{best}}\right)-m-{\mu }_Q\left(x\right)}{{\sigma }_Q\left(x\right)}.$$

ここで、Φ(·) は単位正規 CDF、σ_Q は x におけるガウス過程の事後標準偏差です。

信頼限界の下限

'lower-confidence-bound' の獲得関数は、各点で事後平均から標準偏差の 2 倍を減算した曲線 G を調べます。

$$G\left(x\right)={\mu }_Q\left(x\right)-2{\sigma }_Q\left(x\right).$$

G(x) は目的関数モデルの信頼包絡線より 2σ_Q 小さくなります。そして、bayesopt は G の負数を最大化します。

$$LCB=2{\sigma }_Q\left(x\right)-{\mu }_Q\left(x\right).$$

秒単位

目的関数を評価する時間は、領域によって異なる場合があります。たとえば、多くのサポート ベクター マシンは特定の点の範囲で大幅に計算時間が変化します。このような場合、bayesopt は獲得関数で時間の重みを使用することにより、秒単位で向上させることができます。コストに重みを付けた獲得関数には、名前に per-second という語句が含まれています。

これらの獲得関数は以下のように機能します。目的関数の評価時に、bayesopt は目的関数の評価時間を点 x の関数として別のベイズ モデルに保持します。獲得関数が使用する毎秒の期待改善量は次のようになります。

$$EIpS\left(x\right)=\frac{E{I}_Q\left(x\right)}{{\mu }_S\left(x\right)},$$

ここで、μ_S(x) は時間のガウス過程モデルの事後平均です。

プラス

目的関数の局所的な最小値を回避するため、名前に plus がある獲得関数は、領域を "過剰利用" していると推定した場合に動作を変更します。過剰利用について理解するため、σ_F(x) が x における事後目的関数の標準偏差であるとします。σ を加法性ノイズの事後標準偏差であるとします。したがって

σ_Q²(x) = σ_F²(x) + σ².

正の数値である ExplorationRatio オプションの値になるように t_σ を定義します。bayesopt の plus の獲得関数は、各反復後に次の点 x が以下を満たすかどうかを評価します。

σ_F(x) < t_σσ.

条件が満たされる場合、x は過剰利用であると判断されます。そして、Bull[1]が提案しているように、θ に反復回数を乗算することにより獲得関数のカーネル関数が修正されます。この変更により、観測値の間にある点の分散 σ_Q が大きくなります。次に、新しくあてはめたカーネル関数に基づいて新しい点が生成されます。新しい点 x が再び過剰利用になる場合、θ に 10 という追加係数を乗算して再度試します。これを最大 5 回繰り返して、過剰利用にならない点 x を生成しようとします。このアルゴリズムでは、次の点として新しい x が受け入れられます。

したがって、ExplorationRatio は大域解を向上させる新しい点を探索するか、あるいは既に調べた点の近傍に集中するかのトレードオフを制御します。

獲得関数の最大化

内部的に、bayesopt は以下の一般的な手順を使用して獲得関数を最大化します。

1. 'expected-improvement' で始まるアルゴリズムの場合と 'probability-of-improvement' の場合、bayesopt は変数の範囲内で数千個の点を抽出し、最良 (平均値が小さい) 実行可能点をいくつか選択し、局所探索を使用して改善を行い、表面上の最良実行可能点を見つけることにより、事後分布について最小実行可能平均 μ_Q(x_best) を推定します。実行可能とは、点が制約 (ベイズ最適化の制約を参照) を満たすことを意味します。

2. すべてのアルゴリズムの場合、bayesopt は変数の範囲内で数千個の点を抽出し、最良 (獲得関数の値が大きい) 実行可能点を選択し、局所探索を使用して改善を行い、表面上の最良実行可能点を見つけます。獲得関数の値は目的関数のサンプルではなくモデル化された事後分布に基づくので、高速に計算することができます。

参照

[1] Bull, A. D. Convergence rates of efficient global optimization algorithms. https://arxiv.org/abs/1101.3501v3, 2011.

[2] Gelbart, M., J. Snoek, R. P. Adams. Bayesian Optimization with Unknown Constraints. https://arxiv.org/abs/1403.5607, 2014.

[3] Snoek, J., H. Larochelle, R. P. Adams. Practical Bayesian Optimization of Machine Learning Algorithms. https://arxiv.org/abs/1206.2944, 2012.

参考

bayesopt | BayesianOptimization

関連するトピック

• ベイズ最適化のワークフロー
• bayesopt を使用した交差検証分類器の最適化
• ベイズ最適化の使用による分類器の当てはめの最適化
• ブースティング回帰アンサンブル回帰の最適化
• ベイズ最適化の出力関数
• 連結制約があるベイズ最適化
• tall 配列を使用したベイズ最適化