Tree-structured Parzen Estimator

GP と TPE はどちらもベイズ最適化に分類される最適化手法であり、これらを紹介します。両者の違いは以下の通りです。

GP は p(y|x) を使って EI（Expected Improvement, 期待改善量）を計算します。
- 観測点から事後分布を仮定し、それを使って次の探索点を決定します。
- GP の処理過程には逆行列の計算が含まれるため、時間計算量は O(n^3) です。
TPE は p(x|y) と p(y) を使って EI を計算します。
- y の事後分布 p(y|x) は必要ありません。
- TPE の時間計算量は O(nlogn) です。これは、y* の値によって y を 2 つに分割する際に値をソートする必要があるためです。
- 各変数は（多変量ではなく）独立していると仮定されるため、上記で入力された変数の数 d を用いた全体の時間計算量は O(dnlog(n)) となります。

TPE アルゴリズムについて

上記の説明だけでは分かりにくいかもしれないため、このセクションでは実際の TPE の動作について説明します。
TPE による最適化は、STEP2 から STEP3 を繰り返し実行することで行われます。

まず、ランダムサンプリングが行われます。ここでは、以下の関数の最小化問題を解くものとしてサンプリングします。

y = exp(x)*sin(3πx)
-1 < x < 1

星印がサンプリング点です。

得られたサンプリング点は、l(x) と g(x) の 2 つに分割されます。
Tunny では、デフォルトで上位 10% の個体数または 25 個体のうち小さい方の値である y* によって、これらを 2 つに分割します。

以下の例では y*=-0.83 であり、この値によって l(x) と g(x) に分割されています。

次に、l(x) と g(x) それぞれについてカーネル密度推定（KDE）が行われます。
KDE は、値のヒストグラムを滑らかな曲線で表現したものと考えることができます。以下の図の棒グラフは l(x) と g(x) のヒストグラムを示し、曲線は KDE の結果です。

KDE によって推定された l(x) は、上位の個体（すなわち値が小さい個体）によって得られる x の確率と考えることができ、g(x) は下位の個体（すなわち値が大きい個体）によって得られる x の確率と考えることができます。

TPE では、l(x) と g(x) の比、すなわち l(x)/g(x) が最大となる x を求めることで、次の探索点が決定されます。この例では x=0.455 の点です。

これは、上記の説明から、TPE が小さい値を持つ個体を獲得する確率が高く、大きい値を持つ個体を獲得する確率が低い点を計算していることを意味します。

KDE は Parzen Estimator としても知られており、これが TPE の「PE」の部分の由来です。

STEP 1 ではランダムサンプリングが行われますが、このステップは非常に重要です。Tunny はデフォルトで 10 点をサンプリングしますが、この数が自分の最適化問題に対して適切かどうかは常に検討してください。また、TPE の論文では以下の数を推奨しています。

"number of variables" *11 - 1

十分なサンプリングが行われないと、KDE が適切に実行されず、次の探索点をうまく見つけることができません。例として、上記で行ったサンプリング数の半分のみでサンプリングした場合の結果を以下に示します。

十分にサンプリングされていないため、次の探索点は x=-0.434 と計算されており、これは大域最小値が存在する x=0.5 付近の値とは完全に異なっています。