I read this a while back – not sure if it was ever published.
Parameter space exploration with Gaussian process trees, Gramacy, Lee, Macready (ICML 2004):
- Use binary trees to partition space and learn separate GPs for each partition. This allows for a type of nonstationarity in the covariance function (which is important to the authors in this case because they are modelling dynamics of an obect in both sub and super sonic settings; covariance between both cases are very dissimilar).
- Aside from nonstationarity, the partitioning also helps with another problem faced by GPs, which is the n^3 costs. By partitioning the space, a smaller number of samples are used since they are spread out over a number of GPs instead of just in 1.
- Mention that the general concept is similar to one proposed in a paper by Kim et al, Analyzing nonstationary spatial data using piecewise Gaussian processes, which uses a Vornoi diagram to partition the state space. They point out that the Vornoi diagram creates a large number of partitions, they would prefer just to have a few.
- Actual method of building the tree (when to make partitions, and where) seems to be pretty simplistic, but I could be misunderstanding things here. Nothing as complicated as, say, minimizing entropy which is done in the standard decision tree method. Could this be improved upon by more sophisticated branching techniques?
- Adaptive sampling is also used, specifically sampling is done where the greatest standard deviation in the output is expected. Ok, but I could see how this is problematic in some cases. For example, in some regions there may naturally be a large variance in the results, this approach would focus on that region even if no further improvement could be made. Assuming that noise has a uniform variance everywhere means this isn’t a problem though, I suppose.
- Compared with more simple sampling mechanisms (Latin hypercube, LH), the results in their experiments are pretty good; they generally get better accuracy than LH even with half the number of samples.