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

Die Auswertung der eigentlichen Funktion ${\displaystyle f}$ ist kostspielig (z. B. die passende Anzahl an Layers für ein Deep Neural Network zu finden), deshalb möcht man mit Hilfe der ${\displaystyle p(y|x)}$ die besten Hyperparameter ${\displaystyle x}$ finden, welche später dann in ${\displaystyle f}$ eingesetzt werden. Wir nehmen an, dass der Konfigurationsraum ${\displaystyle {\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 Wahrscheinlichkeitsdichte ${\displaystyle p(y|x)}$ wird auch Surrogatmodell (oder surrogat probability model) genannt und wird nicht direkt modelliert, stattdessen wendet man den Satz von Bayes an

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

und modelliert ${\displaystyle p(x|y)}$ und ${\displaystyle p(y)}$.

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

${\displaystyle p(x|y)={\begin{cases}l(x)&{\text{ falls }}y<y^{*}\\g(x)&{\text{ falls }}y\geq y^{*}.\end{cases}}}$

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

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

Einzelnachweise

1. ↑ J. S. Bergstra, R. Bardenet, Y. Bengio, B. Kégl: Algorithms for Hyper-Parameter Optimization. Advances in Neural Information Processing Systems: 2546–2554 (2011)