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

Question

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.

Answer 1

(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),
    },
    ])

So, the answers to your questions:

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$.

Answer 2

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.

Answer 3

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).