Tree-Structured Parzen Estimatorの気になる式変形整理

　参考

　自分なりの理解として、重要そうだと感じたのは

TPEでのPIやEIで考える基準値 $y ^ *$ はそこまでの最良値ではなく分割基準の $y ^ \gamma$ の方
$y ^ \gamma$ で分割してモデル化するという性質からそこで積分を分けて式変形すると綺麗になる

前提

　Tree-Structured Parzen Estimator (TPE)はOptunaとかでも使われているブラックボックス最適化の一つ。

　関数 $f(\boldsymbol{x})$ の最小値を求めたい。ここまで $\mathcal{D} = \lbrace (\boldsymbol{x} _ n, y _ n) \rbrace _ {n = 1} ^ {N}$ のデータが得られているとする。

　最大化したい関数としてProbability of Improvement (PI)あるいはExpected Improvement (EI)が考えられる。 $y ^ *$ を基準値（TPE以外の場合だと、たとえば現在までの最良値）として、PIだと改善する確率を考える。

$\displaystyle \begin{align} \mathbb{P} (y \le y ^ * | \boldsymbol{x}, \mathcal{D}) = \int _ {-\infty} ^ {y ^ *} p(y|\boldsymbol{x}, \mathcal{D}) dy \end{align}$

　EIだと改善する量も考慮する。

$\displaystyle \begin{align} \mathrm{EI} _ {y ^ *} \lbrack \boldsymbol{x} | \mathcal{D} \rbrack = \int _ {-\infty} ^ {y ^ *} (y ^ * - y) p(y|\boldsymbol{x}, \mathcal{D}) dy \end{align}$

　PIは過去のデータでの有望なところを探す傾向にあり、EIはまだ調べていない領域を探索する傾向にあるらしい。TPEではPIと同等であるため、TPEはローカルに探索する傾向にある。

　TPEではある閾値 $\gamma \in (0,1)$ を考えて、値が小さい方（良い方）から割合 $\gamma$ 分のデータが良いものとなるような閾値 $y ^ \gamma$ を基準値とし、データを良いもの $(y \le y ^ \gamma)$ と悪いもの $(y \gt y ^ \gamma)$ に分割する。

$\displaystyle \begin{align} p(\boldsymbol{x}|y, \mathcal{D}) = \begin{cases} p(\boldsymbol{x}|\mathcal{D} ^ {(l)}) & (y \le y^\gamma) \\ p(\boldsymbol{x}|\mathcal{D} ^ {(g)}) & (y \gt y^\gamma) \end{cases} \end{align}$

　上位下位をそれぞれはKernel Density Estimators (KDE)でモデル化する。

　この $y$ の範囲で分割するという性質を式変形で活用していくことになる。

EIとPIの関係

TPEにおいてはEIとPIが比例関係になる。よって最大化の観点ではどちらを選んでも同じことになる。

比例になることの証明はc-TPE: Tree-structured Parzen Estimator with Inequality Constraints for Expensive Hyperparameter Optimizationの付録A.3に記載されている。

まず、ベイズの定理とTPEのモデル化から以下のような変形ができる。

$\displaystyle \begin{align} \mathbb{P} (y \le y ^ \gamma | \boldsymbol{x}, \mathcal{D}) &= \int _ {-\infty} ^ {y ^ \gamma} p(y|\boldsymbol{x}, \mathcal{D}) dy \\ &= \int _ {-\infty} ^ {y ^ \gamma} \frac{p(\boldsymbol{x}|y, \mathcal{D}) p(y | \mathcal{D})}{p(\boldsymbol{x}|\mathcal{D})} dy \\ &= \frac{p(\boldsymbol{x}|\mathcal{D} ^ {(l)})}{p(\boldsymbol{x}|\mathcal{D})} \int _ {-\infty} ^ {y ^ \gamma} p(y|\mathcal{D}) dy & (\because \mathrm{TPE}のモデル化) \end{align}$

同じことをEIにも適用して

$\displaystyle \begin{align} \mathrm{EI} _ {y ^ \gamma} \lbrack \boldsymbol{x} | \mathcal{D} \rbrack &= \int _ {-\infty} ^ {y ^ \gamma} (y ^ \gamma - y) p(y|\boldsymbol{x}, \mathcal{D}) dy \\ &= \frac{p(\boldsymbol{x}|\mathcal{D} ^ {(l)})}{p(\boldsymbol{x}|\mathcal{D})} \int _ {-\infty} ^ {y ^ \gamma} (y ^ \gamma - y) p(y|\mathcal{D}) dy \end{align}$

となり、これらの比は

$\displaystyle \begin{align} \frac{\int _ {-\infty} ^ {y ^ \gamma} (y ^ \gamma - y) p(y|\mathcal{D}) dy}{\int _ {-\infty} ^ {y ^ \gamma} p(y|\mathcal{D}) dy} \end{align}$

なので $\boldsymbol{x}$ については定数ということになる。正確にはこれが有限の正の定数値を取ることもちゃんと言わないといけないらしいが、そこは元論文参照。

PIの比への帰着

　PIを変形していき、比に帰着することを確認する。先程と同様の式変形を再度行って

となる。最後の行の変形は、そもそも $\gamma$ の定義からそのまま導かれる。ここで

$\displaystyle \begin{align} p(\boldsymbol{x}|\mathcal{D}) &= \int _ {-\infty} ^ {\infty} p(\boldsymbol{x}|y, \mathcal{D})p(y|\mathcal{D}) dy \\ &= p(\boldsymbol{x}|\mathcal{D} ^ {(l)}) \int _ {-\infty} ^ {y ^ \gamma}p(y|\mathcal{D}) dy + p(\boldsymbol{x}|\mathcal{D} ^ {(g)}) \int _ {y ^ \gamma} ^ {\infty}p(y|\mathcal{D}) dy \\ &= \gamma p(\boldsymbol{x}|\mathcal{D} ^ {(l)}) + (1 - \gamma) p(\boldsymbol{x}|\mathcal{D} ^ {(g)}) \end{align}$

であり、つまり

$\displaystyle \begin{align} \mathbb{P} (y \le y ^ \gamma | \boldsymbol{x}, \mathcal{D}) &= \frac{\gamma p(\boldsymbol{x}|\mathcal{D} ^ {(l)})}{\gamma p(\boldsymbol{x}|\mathcal{D} ^ {(l)}) + (1 - \gamma) p(\boldsymbol{x}|\mathcal{D} ^ {(g)})} \\ &= \left\lbrace \frac{\gamma p(\boldsymbol{x}|\mathcal{D} ^ {(l)}) + (1 - \gamma) p(\boldsymbol{x}|\mathcal{D} ^ {(g)})}{\gamma p(\boldsymbol{x}|\mathcal{D} ^ {(l)})} \right\rbrace ^ {-1} \\ &= \left\lbrace 1 + \frac{1-\gamma}{\gamma} \frac{p(\boldsymbol{x}|\mathcal{D} ^ {(g)})}{p(\boldsymbol{x}|\mathcal{D} ^ {(l)})} \right\rbrace ^ {-1} \\ \end{align}$

となるわけなので、逆数であることに注意して結局

$\displaystyle \begin{align} \frac{p(\boldsymbol{x}|\mathcal{D} ^ {(l)})}{p(\boldsymbol{x}|\mathcal{D} ^ {(g)})} \\ \end{align}$

を最大化すれば良いということになる。