# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Markov Chain Monte Carlo  
MCMC methods perform \(N_{T}\) iterations, for \(k=0,1,2,\ldots,N_{T}-1\), and each iteration produces a sample, \(\mathbf{t}_{k}\), from the posterior distribution, \(\pi(\mathbf{T},\theta|\mathbf{Y},\mathbf{x})\). Each sample includes a potential value for both \(\mathbf{T}\) and \(\theta\). The initial sample, \(\mathbf{t}_{0}\), is drawn from an arbitrary initial proposal distribution (also called an initial proposal here, for brevity), \(q_{0}(\cdot)\), which is chosen to be easy to sample from. After this, for every new iteration, a new sample is proposed by sampling from another proposal distribution (also called a proposal here, for brevity), \(q(\cdot|\mathbf{t}_{k-1})\), as follows:  
\[\mathbf{t}^{\prime}\sim q(\cdot|\mathbf{t}_{k-1}), \tag{1}\]  
where the proposal distribution is also arbitrary and is typically chosen to be convenient to sample from. The newly proposed sample \(\mathbf{t}^{\prime}\) is then either accepted or rejected based on the acceptance probability given by  
\[a(\mathbf{t}^{\prime},\mathbf{t}_{k-1})=\min\biggl{(}1,\frac{\pi(\mathbf{t}^ {\prime}|\mathbf{Y},\mathbf{x})}{\pi(\mathbf{t}_{k-1}|\mathbf{Y},\mathbf{x}) }\frac{q(\mathbf{t}_{k-1}|\mathbf{t}^{\prime})}{q(\mathbf{t}^{\prime}|\mathbf{ t}_{k-1})}\biggr{)}. \tag{2}\]  
In other words, the new sample, \(\mathbf{t}_{k}\), will be  
\[\mathbf{t}_{k}= \begin{cases}\mathbf{t}^{\prime}&\text{if }u\leq a(\mathbf{t}^{ \prime},\mathbf{t}_{k-1}),\\ \mathbf{t}_{k-1}&\text{if }u>a(\mathbf{t}^{\prime},\mathbf{t}_{k-1}),\end{cases}  \tag{3}\]  
Figure 2: An example of a DT with \(d(\mathbf{T})=3\), \(m=5\), and six leaf nodes with a quantitative response of two classes. where \(u\sim\texttt{Uniform}[0,1]\). After \(N_{T}-1\) iterations, we have a single chain of \(N_{T}\) samples from which we can estimate \(\mathbf{T}\) and \(\theta\). The performance in terms of classification accuracy is evaluated on a test set, and, for each tree, we compute a prediction; then, the overall accuracy is generated by either computing the mean of the predicted accuracy for each sample or by using majority voting. In this work, we use the mean. However, before doing so, an initial subset of the \(N_{T}\) samples, typically \(N_{b}=0.5N_{T}\), is discarded; this initial part of the process is called burn-in. This is performed to improve the quality of the estimation, since the first samples are likely to be generated before the algorithm has converged. Therefore, we expect this approach to provide competitive overall accuracy at the price of a potentially long runtime, as the samples are generated sequentially. In Section 6, we refer to this method (which is also illustrated in Algorithm 1) as single-chain MCMC. ```
0:\(N_{T},N_{b}\)
0:\(\mathbf{t}\)
1:\(\mathbf{t}_{0}\sim q_{0}(\cdot)\)
2:for\(k\gets 1\); \(k<N_{T}\); \(k\gets k+1\)do
3:\(\mathbf{t}^{\prime}\sim q(\cdot|\mathbf{t}_{k-1})\)
4:\(a(\mathbf{t}^{\prime},\mathbf{t}_{k-1})\leftarrow\min\Big{(}1,\frac{\pi( \mathbf{t}^{\prime}|\mathbf{Y},\mathbf{x})}{\pi(\mathbf{t}_{k-1}|\mathbf{Y},\mathbf{x})}\frac{q(\mathbf{t}_{k-1}|\mathbf{t}^{\prime})}{q(\mathbf{t}^{ \prime}|\mathbf{t}_{k-1})}\Big{)}\)
5:\(u\sim\texttt{Uniform}[0,1]\)
6:if\(u\leq a(\mathbf{t}^{\prime},\mathbf{t}_{k-1})\)then
7:\(\mathbf{t}_{k}\leftarrow\mathbf{t}^{\prime}\)
8:else
9:\(\mathbf{t}_{k}\leftarrow\mathbf{t}_{k-1}\)
10:endif
11:endfor
12: Burn-in the first \(N_{b}\) samples in \(\mathbf{t}\)
```  
**Algorithm 1** Single-Chain MCMC  
This approach is inherently sequential, as each sample is generated as a function of the previous one. One could try to parallelize either (1) or (2), as performed in [20], for example. However, this approach is strongly problem-dependent and often results in poor scalability. Another alternative is to run \(N\) chains in parallel, each with \(K\) samples [21; 26], such that the total number of samples is \(N_{T}=N\times K\). In Section 6, we refer to this method (which is briefly summarized in Algorithm 2) as multi-chain MCMC.