Adaptive Parzen Estimator

Question

I am trying to implement the Tree Parzen Estimator for hyperparameter optimization. I follow this paper https://papers.nips.cc/paper/4443-algorithms-for-hyper-parameter-optimization.pdf, in which section 4 is the relevant one.

I am confused about Section 4.2: "The Adaptive Parzen Estimator yields a model over X by placing density in the vicinity of K observations B = {x(1), ..., x(K)} ⊂ H".

• What is "Adaptive Parzen Estimator"? Is it similar to multivariate kernel density estimators?
• What is K? What K observations to pick?
• Given the way they deal with discrete variables (bottom of the page), this seems to not model dependencies between discrete variables and all other variables. Is that correct? When you have a multivariate KDE, obviously it models dependencies between variables. But not when you just increase probability of some discrete value according to how many times it has been seen. Or am I mistaken?

If this technique is first defined in this paper, it seems underspecified to me. Maybe someone with some knowledge about this technique can fill the holes?

Answer 1

I was also having some trouble understanding everything when reading the paper. To the specific questions you listed here, I might provide my understanding:

1. Parzen estimators (or Parzen windows) are indeed kernel density estimators. In the linked wiki page, it is also stated that if the bandwidth is not fixed, the estimator is referred to as being adaptive, which gives rise to adaptive Parzen estimators (a.k.a. variable kernel density estimation).
2. Since $\mathcal{B} \subset \mathcal{H}$, it seems that they only use a subset of the history to do the kernel density estimation. In this case, $K$ would be the number of observations that are used for the kernel density estimation.
3. That seems to be correct. If we take a look at the implementation, it seems to me as if every variable is treated independently of all other values (i.e. no multivariate distributions for continuous variables either). Although it might be that I misinterpreted the code.

I might have answered your questions at this point, but this does not necessarily make things much clearer. E.g. it is still unclear whether balloon or pointwise estimators were used or how to sample $\mathcal{B}$ from $\mathcal{H}$. Of course, if we take a look at the reference implementation of TPE, these details can be found (spoiler: the bandwidth is the bounded maximum difference to the nearest neighbours). However, even Yoshua Bengio (last author) acknowledges that this should have been cited properly in the paper.