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:{\mathcal {X}}\to \mathbb {R}$ zu konstruieren (${\mathcal {X}}$ ist der Konfigurationsraum, $x$ eine Menge von Hyperparameter und $y=f(x)$ ein Score der Zielfunktion).

Die Idee dahinter ist, dass das Auswerten der eigentlichen Funktion $f$ kostspielig ist (z. B. die passende Anzahl an Layers für ein Deep Neural Network zu finden), deshalb möcht man mit Hilfe der $p(y|x)$ die besten Hyperparameter $x$ finden, welche später dann in $f$ eingesetzt werden. Wir nehmen an, dass der Konfigurationsraum ${\mathcal {X}}$ 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 Funktion $p(y|x)$ wird auch Surrogatsfunktion (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)$. Für $p(y)$ gibt es keine spezifische Anforderungen.

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{cases}l(x)&{\text{ falls }}y<y^{*}\\g(x)&{\text{ falls }}y\geq y^{*}.\end{cases}}$

Der Schwellenwert $y^{*}$ ist dabei ein $\alpha$-Quantil, das heißt $p(y\leq 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.