# What is the "tree" structure in Tree Parzen Estimators?

Context

In Algorithms for Hyper-Parameter Optimization, the authors propose a "tree-structured" configuration space. Here, a configuration space is a space of hyperparameters.

Questions

1. What precisely is the tree in the tree Parzen estimator (TPE)? E.g. what precisely are the nodes and edges in the graph for the configuration space of the TPE?

2. Are the nodes pairs (hyperparameter, value) and child nodes pairs (hyperparamter, quantile_val) where the quantile_val $$\gamma$$ is defined so that $$p(y < y^*) = \gamma$$? [paragraph before start of section 4.1]

3. In section 4.1 they further state that the densities $$\ell$$ and $$g$$ are "tree-structured" -- how so?

Outlook

If there is a general (but precise) notion of using "trees" in sequential model-based global optimization (SMBO), I'd appreciate any references.

(This was asked earlier [independently] at https://datascience.stackexchange.com/q/42133/55122. My answer here is an extension of my answer there.)

I think the authors make it clearest in the introduction:

In this work we restrict ourselves to tree-structured configuration spaces. Configuration spaces are tree-structured in the sense that some leaf variables (e.g. the number of hidden units in the 2nd layer of a DBN) are only well-defined when node variables (e.g. a discrete choice of how many layers to use) take particular values.

See for instance this example in HyperOpt:

from hyperopt import hp
space = hp.choice('classifier_type', [
{
'type': 'naive_bayes',
},
{
'type': 'svm',
'C': hp.lognormal('svm_C', 0, 1),
'kernel': hp.choice('svm_kernel', [
{'ktype': 'linear'},
{'ktype': 'RBF', 'width': hp.lognormal('svm_rbf_width', 0, 1)},
]),
},
{
'type': 'dtree',
'criterion': hp.choice('dtree_criterion', ['gini', 'entropy']),
'max_depth': hp.choice('dtree_max_depth',
[None, hp.qlognormal('dtree_max_depth_int', 3, 1, 1)]),
'min_samples_split': hp.qlognormal('dtree_min_samples_split', 2, 1, 1),
},
])


1. Nodes are (potentially collections of) hyperparameters, and (at least) when a discrete list of values is provided, child nodes can be created for values from that list. (Above, the choice of C only needs to be made when the classifier type is svm.)

2. No, the quantile values are just used to separate "good" from "poor" values of the hyperparameter. (I found this blog post very helpful, although it doesn't really discuss the tree structure.)

3. The densities are approximations of (subsets of) the configuration space. So sampling points according to those densities amounts to tracing the tree structure, with probabilities of each path being determined by the approximation functions $$\ell, g$$.

• i'm trying to correlate the above answer with an implementation of hyperopt (see my temp answer below). i don't see the connection atm but hopefully others can help Apr 29 '20 at 20:30
• I'm not sure why the downvotes; please comment if anything is incorrect. As to the tpe.py link, that doesn't contradict anything I've written; the densities, initially uniform on the tree, get updated (as Parzen estimators, using the already-tested points). This is explained pretty well in the paper, but with nice graphics in the blog post. The code's docstring's "posterior inference graph" is the tree I've described, imbued with a distribution a la the second paragraph of section 4 in the paper. Apr 30 '20 at 18:16

An implementation should help shed light. After asking on github, it looks like the "tree-structure" vaguely mentioned in the original article may be implemented through a posterior inference graph that has nodes consisting of priors and their values. Exactly how these nodes are collected to form a tree and updated may be found in this implementation's "build_posterior" method.

If anyone can shed more light on the precise details, I'd be happy to accept that as an answer.

• Thanks for the github issue, and the source file link. But I think the tree structure in that code is the same as I've described, just imbued with a prior. See my comment on my answer. I would like to better understand the pyll code, to know more clearly how the parzen estimators get updated, and to understand how the initial uniform distribution (inside rand.suggest?) gets initialized. Apr 30 '20 at 18:25

I think @Ben Reiniger said is correct, the paper is well-defined what is tree-structured. However, I am curious that what's the situation of multiple hyperparameters. Is there two Parzen estimator p(x|y)=l(x) and g(x) in each leaf? So, it supposes each hyperparameter is independent, rather than l(x1,x2,x3...xn).