1
$\begingroup$

I'm working on implementing a Bayesian optimization class in Python. As a surrogate model, I used a Gaussian process until now. From what I read it's quite standard as it is efficient and intuitive. However, as mentioned in the paper Decision Forests for Classification,Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning, Random forests might be more efficient for ambiguous training data and for multi-modal distribution of data (I am careful with those affirmations as the authors make those points on a few toy cases only).

I then would like to use random forests as a surrogate model as well as Gaussian processes. For Gaussian processes in Bayesian optimization, a few acquisition functions are available in the literature, some of them have a known analytic form (GP-UCB for example), are well studied and easy to implement.

I am looking for an acquisition function similar to GP-UCB, for random forests surrogate model. Do you know any acquisition function adapted to random forests (if possible with an analytic form) ?

Improve this question
$\endgroup$
1
2
$\begingroup$

Acquisition functions are not about a specific surrogate model. They can be calculated for many of them given that the output of a surrogate model is not a single prediction $\hat{y}(x)$, but a probability distribution $\hat{p}(x)$.

In case, of the Gaussian process regression, we assume that the output is Gaussian distribution. So it is sufficient to specify mean $\mu(x) = \hat{y}(x)$ and variance $\sigma^2(x)$ at a specific $x$ to specify this distribution. Moreover, many acquisition functions have an analytical form. For example, UCB has the form $\mu(x) + \beta \sigma(x)$. As you note this probability distribution is a natural extension.

The problem of random forest is that there is no good extension of this model that allows obtaining a probability distribution instead of a single prediction value or even obtain reliable uncertainty estimate for prediction.

Moreover, the random forest model predicts only values that are inside the range of values presented in the training sample, while during Bayesian optimization we want to find points with output values that are outside this range.

Finally, if you propose an acquisition function, then you should find an optimum of it. For Random Forest both uncertainty estimates and mean values are piecewise constant. Thus, to find an optimum of an acquisition function like UCB, you should be able to adopt a global optimization algorithm with zero gradients almost everywhere. Seem like a computationally expensive problem.

These three issues lead to the complexity of a Random forest application in Bayesian optimization. You should start this project at your own risk with questionable benefits in the end.

There should be some options for Bayesian optimization using random forests as surrogate models, but it seems that they are outside of the scope of the main research and industrial practices

Improve this answer
$\endgroup$
10
  • $\begingroup$ Quantile regression forests gives a conditional distribution for unobserved data points jmlr.org/papers/volume7/meinshausen06a/meinshausen06a.pdf, and I believe that the proof of consistency qualify it as a good extension to get a probability distribution. $\endgroup$ – nathan raynal Mar 26 '20 at 8:33
  • $\begingroup$ Also, about the fact that random forests only predicts output inside the range of the training sample is an issue. While this is true, I don't see how it's an issue. we do not observe output from the surrogate model but from the original model or from experimental data, the surrogate model only guides the next choice of predictor variable, so the new observation can be outside the range of the actual observations, especially if exploration is preferred during the Bayesian optimization. $\endgroup$ – nathan raynal Mar 26 '20 at 8:40
  • $\begingroup$ For quantile regression forests (QRF) you see that the prediction and quantile are still in the range of that given in the training sample, so yes, using QRF we have some exploration properties. But we predict that the value at a new point exceeds the current best value with probability zero or probability 0.5 in a close neighborhood near the current best point, so no reasonable exploitation is possible with the best model. $\endgroup$ – Alexey Zaytsev Mar 26 '20 at 15:02
  • $\begingroup$ @nathanraynal for GP we can predict values that are outside of the current range of outputs or at least provide reasonable quantities at each point. Some models have similar behavior e.g. linear regression, but they are linear, so no interesting results for global optimization are possible with linear regression models. $\endgroup$ – Alexey Zaytsev Mar 26 '20 at 15:04
  • 1
    $\begingroup$ @nathanraynal From formula (6) in meinshausen06a the quantile value for output $y$ is a weighted sum of indicators $1_{Y_i < y}$, the sum of all weights is 1 and each weight is $\geq 0$. So, if $y$ exceeds all $Y_i$ in the sample, then $\hat{F}(y| X = x) = 1$, so probability of this particular value is zero. So, for any $x$ the QRF predicts $0$ probability for all values that exceed the current maximum. $\endgroup$ – Alexey Zaytsev Mar 26 '20 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.