TPE(tree-structured parzen estimator)について
Published: 2018-12-18

最近DNNのパラメータチューニングをすることになり,その過程でTPEというアルゴリズムについて勉強したのでまとめる.

はじめに

DNNではハイパーパラメータをチューニングする必要があります.

簡単な方法として,グリッドサーチやランダムサーチがありますが,グリッドサーチではパラメータが増えると計算量が多くなり,ランダムサーチでは計算量は抑えられますが,最適なパラメータを得る確率は低いです.そこで,確率的なモデルを導入して効率よくパラメータを探索する方法が色々と研究されました.TPE(tree-structured parzen estimator)はその中の1つです.以下では,TPEを含む最適化アルゴリズムのフレームワークであるSMBOについて触れた後,TPEについて説明します.

SMBO(Sequential Model-Based Optimization)

SMBOはハイパーパラメータ最適化アルゴリズムのためのフレームワークです. 4つのコンポーネントから構成されています.

  • $f$: 目的関数($x$における損失)
  • $M$: $f$を近似する確率モデル
  • $S$: 獲得関数(パラメータを評価して次の探索値を決める)
  • $H$: 探索の履歴

イメージとしては,$f$を最小化するようなハイパーパラメータ$x$を見つけたい場合に,$f$よりも計算量的に評価しやすい$M$によって予測分布を構築して,$M$上で一番良さそうな候補を$S$によって決めているような感じです.SMBOのフレームワーク上において$M$や$S$に様々なモデルを用いることが可能であり,TPEは$M$の実装の一つです.

また,TPEでは$S$として,expected Improvement(EI)を使用しています.($EI$は$TPE$以外でも使用されます) $$ EI(x) = \int_{-\infty}^\infty max(y^* - y,0)p(y|x)dy $$ この式では,既存の値$y^*$に対する値の改善の期待値を表しています.$EI$ が最も高いハイパーパラメータ$x^*$が次の候補として選択されることになります.

TPE(tree-structured parzen estimator)

TPEでは,$M$をモデリングする時,$p(y|x)$ではなく,代わりに$p(x|y)$をモデリングします.

$p(x|y)$は閾値$y*$によって分けられた2つの分布によって構成されます. $$ p(x|y) = \begin{cases} l(x) & (y < y^*) \newline g(x) & (y \geqq y^*) \newline \end{cases} $$

$y*$は,分位数$\gamma$で事前に与える必要があります.($p(y<y^*) = \gamma$)

$l(x)$と$g(x)$は,$y$が大小により分割された$x$の分布であり,これらの確率密度関数はサンプル済みの点からカーネル密度推定により推定されます.

ここで,今構築したモデルに対する$EI$を計算すると,

$$ EI(x) = \int_{-\infty}^\infty max(y^* - y,0)p(y|x)dy \\
$$

$$ = \int_{-\infty}^{y^\ast} (y^\ast - y)p(y|x)dy $$

$$ =\int_{-\infty}^{y^\ast} (y^\ast - y)\frac {p(x|y)p(y)} {p(x)}dy $$

$$ \vdots (略) $$

$$ = \frac {\gamma y^*l(x) - l(x) \int_{-\infty}^{y^*}p(y)dy} {\gamma l(x) + (1 - \gamma)g(x)} \propto \bigl(\gamma + \frac {g(x)} {l(x)}(1- \gamma)\bigl)^{-1} $$

つまり,$\frac {l(x)}{ g(x)}$を最も大きくするように$x^*$を選ぶと,$EI$を最大化することができるということです.TPEのアルゴリズムでは,1回のイテレーションで$\frac {l(x)}{ g(x)}$が最大化されるような$x^*$を返します.

tpe-sampled-candidates

この図では,赤が$l(x)$, 青が$g(x)$の分布を表しています.$l(x)$上からサンプリングした候補点に対して,$\frac {l(x)}{ g(x)}$を計算して,一番良かったものをそのイテレーションでの最適解$x^*$として返却します.

おわりに

今回は,TPEについて簡単にまとめました.雰囲気を掴んでもらえたら幸いです.正確なことは参考にある論文を読んでもらえたらと思います.また,Optuna のコードが非常に分かりやすいので,読めば細かい挙動が分かると思います.

なんか間違いがあれば教えてくれると嬉しいです.

参考