Dynamic Trees for Learning and Design

By Matthew A. Taddy, Robert B. Gramacy, Nicholas G. Polson. 2009

134 citations recorded by the source corpus.

Dynamic regression trees are an attractive option for automatic regression and classification with complicated response surfaces in online application settings. We create a sequential tree model whose state changes in time with the accumulation of new data, and provide particle learning algorithms that allow for the efficient online posterior filtering of tree states. A major advantage of tree regression is that it allows for the use of very simple models within each partition. The model also facilitates a natural division of labor in our sequential particle-based inference: tree dynamics are defined through a few potential changes that are local to each newly arrived observation, while global uncertainty is captured by the ensemble of particles. We consider both constant and linear mean functions at the tree leaves, along with multinomial leaves for classification problems, and propose default prior specifications that allow for prediction to be integrated over all model parameters conditional on a given tree. Inference is illustrated in some standard nonparametric regression examples, as well as in the setting of sequential experiment design, including both active learning and optimization applications, and in online classification. We detail implementation guidelines and problem specific methodology for each of these motivating applications. Throughout, it is demonstrated that our practical approach is able to provide better results compared to commonly used methods at a fraction of the cost.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Raiders of the Lost Architecture: Kernels for Bayesian Optimization in Conditional Parameter Spaces (2014, background): “In part icular, tree-based models, such as random forests, can be a better choice if there are many data points ( a dGPs thus become computationally inefficient), if the input dimensionality is high, if the noise is not normall y distributed, or if there are non-stationarities [3, 4, 5].”
BART: Bayesian Additive Regression Trees (2008, neutral): “q[,3],col=4,lwd=2,lty=2) legend("topleft",legend=c("OLS polymonial-12 fit","Smooth-spline fit","BART fit"), col=c(3,2,4),lwd=2,lty=1) 41/45”
Mondrian Forests: Efficient Online Random Forests (2014, background): “incremental CART [5], ITI [23], VFDT [11] and dynamic trees [21], but to the best of our knowledge, these are focused on learning decision trees and have not been generalized to online random forests.”
Optimization Under Unknown Constraints (2010, background): “Finally, it may be worthwhile to consider surrogate models beyond GPs. Dynamic trees for regression and classification show considerable promise (Taddy et al., 2010).”
Variable selection and sensitivity analysis using dynamic trees, with an application to computer code performance tuning (2011, methodology): “For those interested in using these techniques, software is available in the dynaTree [Gramacy and Taddy (2011)] package for R , which also includes all the methods of this paper.”
bartMachine: Machine Learning with Bayesian Additive Regression Trees (2013, unknown): “Recent advances in ensemble methods include dynamic trees (Taddy, Gramacy, and Polson 2011) and Bayesian additive regression trees (BART; Chipman, George, and McCulloch 2010), which depart from predecessors in that they rely on an underlying Bayesian probability model rather than a pure algorithm.”
Bayesian and Empirical Bayesian Forests (2015, methodology): “We hypothesis that this is due to the notoriously poor mixing of the BCART MCMC, such that this ﬁt is neither ﬁnding a posterior mean (as it is intended to) or optimizing to a local posterior mode (as DT does).”