Parzen-Tree Estimator

Tree-structured Parzen Estimator (kurz Parzen-Tree Estimator oder TPE) sind Schätzfunktionen, die unter anderem in der bayesschen Hyperparameteroptimierung verwendet werden, um eine Approximation $p(y|x)$ einer eigentlichen gesuchten Zielfunktion $f:𝒳\to ℝ$ zu konstruieren ($𝒳$ ist der Konfigurationsraum, $x$ eine Menge von Hyperparameter und $y=f(x)$ ein Score der Zielfunktion).

Die Auswertung der eigentlichen Funktion $f$ ist „kostspielig“ (z. B. die passende Anzahl an Layers für ein Deep Neural Network zu finden), deshalb möchte man mit Hilfe der $p(y|x)$ die besten Hyperparameter $x$ finden, welche später dann in $f$ eingesetzt werden. Es wird angenommen, dass der Konfigurationsraum $𝒳$ eine Baumstruktur besitzt (z. B. die Anzahl Neuronen auf Layer 4 wird erst bestimmt, wenn es überhaupt mindestens 4 Layers gibt). TPE konstruiert dann einen Baum von Kerndichteschätzern.

Die Wahrscheinlichkeitsdichte $p(y|x)$ wird auch Surrogatmodell (oder surrogat probability model) genannt und wird nicht direkt modelliert, stattdessen wendet man den Satz von Bayes an

$p(y|x)=\frac{p(x|y)p(y)}{p(x)}$

und modelliert $p(x|y)$ und $p(y)$.

Die Funktion $p(x|y)$ wird durch Einführung eines Schwellenwertes $y^{*}$ in zwei Dichten aufgeteilt, so dass diese nicht mehr von $y$ abhängen

$p(x|y)=\{\begin{array}{cc}l(x)& \text{ falls }y<y^{*}\\ g(x)& \text{ falls }y\ge y^{*}.\end{array}$

Der Schwellenwert $y^{*}$ ist dabei ein $\alpha$-Quantil, das heißt $p(y\le y^{*})=\alpha$.

Die Dichten $l(x)$ und $g(x)$ werden dann mit Hilfe von Kerndichteschätzern konstruiert. Für $l(x)$ werden die Observationen $\{x_i\}$ mit $f(x_i)<y^{*}$ verwendet. Die restlichen Observationen, für die $f(x_k)>y^{*}$ gelten, werden zur Konstruktion von $g(x)$ benötigt.