What makes a Tree-Structured Parzen Estimator "tree-structured?"

Question

From what I understand the Tree-Structured Parzen Estimator (TPE) creates two probability models based on hyperparameters that exceed the performance of some threshold and hyperparameters that don't.

What I don't fully understand is why TPE is "tree-structured." Is the simple clustering of y > thresh and y < thresh sufficient to call it a "tree?" When I envision a "tree structure" I usually think of many different "forks," perhaps some that are not binary and some that are forks of forks. Although a tree with just one fork is still technically a tree, the name "Tree-Structured Parzen Estimator" seems like it would describe something much more complex.

My question is whether or not I am missing some other deeper conceptual "forks" inherent in TPE that would turn it into a "tree" when you look at the bigger picture.

Answer 1

It means that your hyperparameter space is tree-like: the value chosen for one hyperparameter determines what hyperparameter will be chosen next and what values are available for it.

From a HyperOpt example, in which the model type is chosen first, and depending on that different hyperparameters are available:

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

From the original paper:

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.

Answer 2

Well, I can't give you the perfect answer since I am still working on the details about the algorithm myself. But some parameter space descriptions imply that there is no connection between different values, like randint or choice. If you choose one of the options, it does not impy that for the other option the loss function should somehow be similar.