Bayesian and Empirical Bayesian Forests

1 Bayesian and Empirical Bayesian Forests Matt Taddy TADDY @ CHICAGOBOOTH . EDU. University of Chicago Booth School of Business Chun-Sheng Chen CHUNSCHEN @ EBAY. COM. eBay Jun Yu JUNYU @ EBAY. COM. eBay Mitch Wyle MWYLE @ EBAY. COM. eBay Abstract is an archetype for the successful strategy of tree ensemble learning. For prediction problems with training sets that are We derive ensembles of decision trees through large relative to the number of inputs, properly trained en- a nonparametric Bayesian model, allowing us to sembles of trees can predict out-of-the-box as well as any view random Forests as samples from a posterior carefully tuned, application-specific alternative. distribution. This insight provides large gains in interpretability, and motivates a class of Bayesian This article makes three contributions to understanding and forest (BF) algorithms that yield small but reli- application of decision tree ensembles (or, Forests ).

2 Able performance gains. Based on the BF frame- Bayesian forest : A nonparametric Bayesian (npB) point- work, we are able to show that high-level tree hi- of-view allows interpretation of Forests as a sample from a erarchy is stable in large samples. This leads to posterior over trees. Imagine CART applied to a data gen- an Empirical Bayesian forest (EBF) algorithm for erating process (DGP) with finite support: the tree greed- building approximate BFs on massive distributed ily splits support to minimize impurity of the partitioned datasets and we show that EBFs outperform sub- response distributions (terminating at some minimum- sampling based alternatives by a large margin. leaf-probability threshold). We present a nonparametric Bayesian model for DGPs based on multinomial draws from (large) finite support, and derive the Bayesian forest 1.

3 Introduction (BF) algorithm for sampling from the distribution of CART. trees implied by the posterior over DGPs. Random Forests Decision trees are a fundamental machine learning tool. are an approximation to this BF exact posterior sampler, They partition the feature (input) space into regions of re- and we show in examples that BFs provide a small but re- sponse homogeneity, such that the response (output) value liable gain in predictive performance over RFs. associated with any point in a given partition can be pre- dicted from the average for that of its neighbors. The classi- Posterior tree variability: Based upon this npB framework, fication and regression tree (CART) algorithm of (Breiman we derive results on the stability of CART over different et al., 1984) is a common recipe for building trees; it grows DGP realizations.

4 We find that, conditional on the data al- greedily through a series of partitions on features, each of located to a given node on the sample CART tree, the prob- which maximizes reduction in some measure of impurity at ability that the next split for a posterior DGP realization the current tree leaves (terminal nodes; , the implied in- matches the observed full-sample CART split is put space partitioning). The development of random Forests p (RF) by (Breiman, 2001), which predict through the aver- p (split matches sample CART) & 1 p e n , (1). n age of many CART trees fit to bootstrap data resamples, where p is the number of possible split locations and n the Proceedings of the 32 nd International Conference on Machine number of observations on the node. Even if p grows with Learning, Lille, France, 2015.

5 JMLR: W&CP volume 37. Copy- n, the result indicates that partitioning can be stable con- right 2015 by the author(s). ditional on the data being split. This conditioning is key: Bayesian and Empirical Bayesian Forests CART's well known instability is due to its recursive na- predictors regardless of the underlying data distribution . ture, such that a single split different from sample CART they do not rely upon distributional assumptions to share at some node removes any expectation of similarity below information across training observations. Our DGP model, that node. However, for large samples, (1) implies that we detailed below, leads to a posterior for dgp that is repre- will see little variation at the top hierarchy of trees in a for- sented through random weighting of observed support. A. est. We illustrate such stability in our examples.

6 Bayesian forest contains CART fits corresponding to each draw of support weights, and the BF ensemble prediction Empirical Bayesian Forests : the npB forest interpreta- is an approximate posterior mean. tion and tree-stability results lead us to propose Empirical Bayesian Forests (EBF) as an algorithm for building ap- proximate BFs on massive distributed Nonparametric model for the DGP. Empirical Bayesian analysis fixes parameters in high levels We employ a Dirichlet-multinomial sampling model in of a hierarchical model at their marginal posterior mode, nonparametric Bayesian analysis. The approach dates back and quantifies uncertainty for the rest of the model con- to Ferguson (1973). Chamberlain & Imbens (2003) provide ditional upon these fixed estimates. EBFs work the same an overview in the context of econometric problems.

7 Rubin way: we fit a single shallow CART trunk to the sam- (1981) proposed the Bayesian bootstrap as an algorithm for ple data, and then sample a BF ensemble of branches at sampling from versions of the implied posterior, and it has each terminal node of this trunk. The initial CART trunk since become closely associated with this model. thus maps observations to their branch, and each branch BF is fit in parallel without any communication with the Use zi = {xi , yi } to denote the features and response for other branches. With little posterior variability about the observation i. We suppose that data are drawn indepen- trunk structure, an EBF sample should look similar to the dently from a finite L possible values, (much more costly, or even infeasible) full BF sample. In a L. X. number of experiments, we compare EBFs to the common dgp = p(z) = !

8 L 1[z= l ] (2). distributed-computing strategy of fitting Forests to data sub- l=1. samples and find that the EBFs lead to a large improvement P. where !l 08l and l !l = 1. Thus the generat- in predictive performance. This type of strategy is key to ing process for observation i draws li from a multinomial efficient machine learning with Big Data: focus the Big' with probability !li , and this indexes one of the L support on the pieces of models that are most difficult to learn . points. Since L can be arbitrarily large, this so-far implies Bayesian Forests are introduced in Section 2 along with a no restrictive assumptions beyond that of independence. survey of Bayesian tree models, Section 3 investigates tree The conjugate Q prior for ! is a Dirichlet distribution, written stability in theory and practice, and Section 4 presents the L.

9 Dir(!; ) / l=1 !j l 1 . We will parametrize the prior Empirical Bayesian forest framework. Throughout, we use with a single concentration parameter = a > 0, such that publicly available data on home prices in California to il- E[!l ] = a/La = 1/L and var(!l ) = (L 1)/[L2 (La+1)]. lustrate our ideas. We also provide a variety of other data Suppose you have the observed sample Z = [z1 zn ]0 . analyses to benchmark performance, and close with de- For convenience, we allow l = k for l 6= k in the case scription of how EBF algorithms are being built and per- of repeated values. Write l1 .. ln = 1 .. n so that zi = i form in large-scale machine learning at and Z = [ 1 n ]0 . Then the posterior distribution for ! has !i = a + 1 for i n and !l = a for l > n, so that 2. Bayesian Forests n Y L. Y. p(!) / !ia !la 1.

10 (3). Informally, write dgp to represent the stochastic process de- i=1 l=n+1. fined over a set of possible DGPs. A Bayesian analogue to classical distribution-free' nonparametric statistical analy- This, in turn, defines our posterior for the data generating sis ( , Hollander & Wolfe, 1999) has two components: process through our sampling model in (2). There are many possible strategies for specification of a 1. set a nonparametric statistic T (dgp) that is of interest and l for l > The non-informative prior that arises in your application regardless of the true DGP, as a ! 0 is a convenient default: in this limit, !l = 0. 2. and build a flexible model for the DGP, so that the with probability one for l > We apply this limiting posterior distribution on T (dgp) can be derived from 1. The unobserved l act as data we imagine we might have posterior distribution on possible DGPs.