Parallel Approaches to Accelerate Bayesian Decision Trees

Markov Chain Monte Carlo(MCMC) can characterise a distribution without knowing the analytic form of that distribution. MCMC achieves this by using samples to characterise the distribution. The sampling operation is Markovian such that the new sample depends only on the previous one (and not any other samples before that previous one). MCMC is an extremely effective tool for Bayesian inference because it can handle a wide variety of posterior distributions and specifically those distributions which would be difficult or impossible to work with via analytic examination. MCMC has been used to solve Bayesian inference problems spanning biology [15], forensics [14], education [7], and chemistry [9], among other areas.

As will be explained in more detail in section 3.1, MCMC operates by proposing samples and then accepting these samples with a probability that is calculated such that the MCMC generates samples from the distribution of interest. Since the next step of the MCMC depends on the current sample, it is non-trivial for a single MCMC chain to be processed contemporaneously by several processing elements. Byrd [2] proposed a method to parallelise a single MCMC chain, where backup samples are calculated in separate threads of execution in anticipation of the possibility that the current move is not accepted. This is wasteful since it will often be the case that the current move is accepted (such that the backup samples are not needed). However, when the acceptance rate is relatively low, there will be increased utility from considering such backup samples. Of course, there will be a trade-off between having many concurrent threads generating such backup samples and them all being used. More generally, single-chain parallelisation can quickly become problematic as the efficiency of the parallelisation is not guaranteed.

Another way of improving the run-time of MCMC is to reduce the convergence rate by requiring fewer iterations. Metropolis-Coupled MCMC[1], $(MC)^{3}$, runs multiple MCMC chains at the same time. One chain is treated as “cold” and targets the posterior of interest, while the other chains are treated as “hot”, and attempt to sample from tempered versions of the posterior such that proposed samples are more likely to be accepted. The idea is that the space will be explored more quickly by the “hot” chains than by the “cold” chains: the “hot” chains find it easier to make what appear myopically to be disadvantageous moves across the parameter space. Results indicate improvements in run-time when more chains (and cores) were considered.

Several recent studies [5, 10, 12, 18] have considered MCMC in the context of Bayesian decision trees and as a replacement for traditional tree-based algorithms when tackling machine learning tasks. We are also aware that there are occassions (eg see [11]) when researchers are eager to use MCMC Decision Trees, but it is not feasible or efficient for their research, forcing them to use alternative methods: the prohibitively expensive likelihood evaluations are frequently sufficiently time-consuming that these algorithms cannot be practically applied to complex models with large-scale datasets. This paper aims to investigate alternative mechanisms for achieving improved run-time in the context of Bayesian decision trees, and to explore how we can best apply such algorithms to large datasets with either small or big feature spaces. Our focus is on applications where run-time is critical.

Existing papers consider a range of problem sizes. For example, [10] uses a dataset of 200 data, while [12] implemented some benchmarks results using a synthetic dataset of 300 data. There are also some comparison studies using Bayesian Trees; for example, [18] used 303 data points to train their algorithm, while [5, 6] compared different algorithms, including Bayesian Additive Regression Trees (BART), with a dataset of 2000 data points.

In this paper, we describe two methods with the aim of achieving a faster execution time for Bayesian decision trees. Our contributions are then:

• •

  We describe Sampling Using Multinomial Distribution (SUMD), a novel algorithm for performing inference in the context of Bayesian decision trees that uses a Sequential Monte Carlo (SMC) sampler to generate samples.

• •

  We describe Data Partitioning (DP), which, for transparency, we see as pragmatic and do not perceive to be novel and which spreads the data among the available cores, evaluating each tree faster than a conventional implementation of MCMC.

• •

  We consider a diverse range of datasets to assess which of these approaches is the most suitable way of parallelising Bayesian decision trees, and identify the effective number of cores that should be used, given the type and the length of the dataset being processed.

The remainder of this paper is organised as follows: Section 2 presents the statistical model used in Bayesian Decision trees; Section 3 then describes the methods we compare; Section 4 presents the experimental results, and Section 5 concludes the paper.

A decision tree operates by descending a tree. The process of outputting a classification probability for a given datum starts at a root node. At each non-leaf node, a decision as to which child node to progress to is made based on the datum and the parameters of the node. This process continues until a leaf node is reached. At the leaf node, a node-specific and datum-independent classification output is generated.

Our model describes the conditional distribution of a value for $Y$ given the corresponding values for $x$, where $x$ is a vector of predictors and $Y$ the corresponding values that we predict. We define the tree to be $T$ such that the function of the non-leaf nodes is to (implicitly) identify a region, $A$, of values for $x$ for which $p\left(Y|x\in A\right)$ can be approximated as independent of the specific value of $x\in A$, ie as $p(Y|x)\approx p(Y|\phi_{j},x\in A)$. This model is called a probabilistic classification tree, according to the quantitative response $Y$.

For a given tree, $T$, we define the depth of the tree to be $d(T)$, the set of leaf nodes to be $L(T)$ and the set of non-leaf nodes to be $\bar{L}(T)$. The tree, $T$, is then parameterised by: the set of features for all non-leaf nodes, $k_{\bar{L}(T)}$; the vector of corresponding thresholds, $c_{\bar{L}(T)}$; the parameters, $\phi_{L(T)}$, of the conditional probabilities associated with the leaf nodes. This is such that the parameters of the tree are $\theta(T)=[k_{\bar{L}(T)},c_{\bar{L}(T)},\phi_{L(T)}]$ and $\theta(T)_{j}$ are the parameters associated with the $j$th node of the tree, where:

Given a dataset comprising $N$ data, $Y_{1:N}$ and corresponding features, $x_{1:N}$, and since decision trees are specified by $T$ and $\theta(T)$, a Bayesian analysis of the problem proceeds by specifying a prior probability distribution, $p(\theta(T),T)$ and associated likelihood, $p(Y_{1:N}|T,\theta(T),x_{1:N})$. Because $\theta(T)$ defines the parametric model for $T$, it will usually be convenient to adopt the following structure for the joint probability distribution of $N$ data, $Y_{1:N}$, and the $N$ corresponding vectors of predictors, $x_{1:N}$:

which we note is proportional to the posterior, $p(T,\theta(T)|Y_{1:N},x_{1:N})$, and where we assume

Equation 6 describes the product of the probabilities of every data point, $Y_{i}$, being classified correctly given the datum’s features, $x_{i}$, the tree structure $T$, and the features/thresholds, $\theta(T)$, associated with each node of the tree. At the $j$th nod, equation 8 describes the product of possibilities of picking the $k_{j}$th feature and corresponding threshold, $c_{j}$, given the tree structure, $T$. Equation 9 is used as the prior for the tree $T$. This formula is recommended by [3] and three parameters specify this prior: the depth of the tree, $d(T)$; the parameter, $a$, which acts as a normalisation constant; the parameter, ${\beta>0}$, which specifies how many leaf nodes are probable, with larger values of $\beta$ reducing the expected number of leaf nodes. $\beta$ is crucial as this is the penalizing feature of our probabilistic tree which prevents an algorithm that uses this prior from over-fitting and allows convergence to occur[13]. Changing $\beta$ allows us to change the prior probability associated with “bushy” trees, those whose leaf nodes do not vary too much in depth.

An exhaustive evaluation of equation 4 over all trees, $T$, will not be feasible, except in trivially small problems, because of the sheer number of possible trees.

Despite this limitations, Bayesian algorithms can still be used to explore the posterior. Such algorithms simulate a chain sequence of trees, such as:

which converge in distribution to the posterior, which is itself proportional to the joint distribution, $p(Y_{1:N}|T,\theta(T),x_{1:N})p(\theta(T)|T)p(T)$, specified in equation 4. We choose to have a simulated sequence that gravitates toward regions of higher posterior probability. Such a simulation can be used to search for high-posterior probability trees stochastically. We now describe the details of algorithms that achieve this and how they are can be implemented.

Our comparison study has shown that by taking advantage of multi-core architectures, we can improve the run-time of Bayesian Decision Trees by up to $343$ times. According to our experimental results, our novel approach based on Sequential Monte Carlo samplers, SUMD, outperforms an approach that exploits data parallelism, with SUMD improving the run-time by an average of 88 times relative to a sequential Markov chain Monte Carlo implementation. Moreover, we have shown that the results obtained are very similar to the sequential implementation. We perceive that, by taking advantage of the improvements in modern processor designs, our methods help make Bayesian decision tree-based solutions more productive and increasingly applicable to a broader range of applications.

This study, though, has some limitations. First, to run in parallel and produce the speedups we described, the proposed methods require access to HPC nodes with substantial memory resources. Secondly, at present, the implementations we have are not yet as easy-to-use as existing (single-processor) libraries: we plan to address this in future work.