# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
As shown in Figure 6, multi-chain MCMC scales effectively with \(P\) and outperforms SMC in terms of runtime, by up to a factor of two (in Abalone and Students), up to a factor of four (in Diabetes), and up to a factor of six (in Heart), as indicated in \[\mathbf{t}_{k}^{i} \sim q(\cdot|\mathbf{t}_{k-1}^{i}), \tag{5a}\]6 This behavior is expected for two reasons. First, Algorithm 2 is embarrassingly parallel, while the SMC sampler has computational complexity of \(O(\log_{2}N)\). Second, the constant per-sample time in multi-chain MCMC is determined solely by Equations (1)-(3). By contrast, updating each sample in the SMC sampler involves additionalcalculations, including proposing and weighting the new sample, as well as operations from Equations (6), (8), and (9) and Algorithm 5, with a constant time of \(O(\overline{M})\) (see Lemma 1). Despite its scalability and faster runtime, multi-chain MCMC yields lower accuracy compared to SMC and single-chain MCMC for the same fixed problem size (see Table 1). SMC achieves superior accuracy because its \(N\) samples are not only weighted but are also iteratively updated and corrected \(K\) times through sampling and resampling. In contrast, single-chain MCMC generates a single, extended chain of unweighted samples that are likely to have converged. On the other hand, multi-chain MCMC produces \(N\) independent short chains, each with \(K\ll N\) unweighted samples, which are less likely to have converged. \[\mathbf{t}_{k}^{i} \sim q(\cdot|\mathbf{t}_{k-1}^{i}), \tag{5a}\]7 _Cont._

\[\mathbf{t}_{k}^{i} \sim q(\cdot|\mathbf{t}_{k-1}^{i}), \tag{5a}\]8 Runtimes for MCMC and SMC vs. total sample size \(N_{T}\). \[\mathbf{t}_{k}^{i} \sim q(\cdot|\mathbf{t}_{k-1}^{i}), \tag{5a}\]9 _Cont._

\[\mathbf{w}_{k}^{i} =\mathbf{w}_{k-1}^{i}\frac{\pi(\mathbf{t}_{k}^{i}|\mathbf{Y}, \mathbf{x})}{\pi(\mathbf{t}_{k-1}^{i}|\mathbf{Y},\mathbf{x})}\frac{q\Big{(} \mathbf{t}_{k-1}^{i}|\mathbf{t}_{k}^{i}\Big{)}}{q\Big{(}\mathbf{t}_{k}^{i}| \mathbf{t}_{k-1}^{i}\Big{)}}. \tag{5b}\]0 Speed-ups for SMC for \(K=10\) iterations and increasing number of samples \(N\). \[\mathbf{w}_{k}^{i} =\mathbf{w}_{k-1}^{i}\frac{\pi(\mathbf{t}_{k}^{i}|\mathbf{Y}, \mathbf{x})}{\pi(\mathbf{t}_{k-1}^{i}|\mathbf{Y},\mathbf{x})}\frac{q\Big{(} \mathbf{t}_{k-1}^{i}|\mathbf{t}_{k}^{i}\Big{)}}{q\Big{(}\mathbf{t}_{k}^{i}| \mathbf{t}_{k-1}^{i}\Big{)}}. \tag{5b}\]1 _Cont._

#### 6.1.2. Results on Distributed Memory

Regarding this experiment, the reader is referred to Figures 3(b), 4(b), 4(b) and 4(b) for the runtimes and speed-ups. For the accuracy, the reader is again referred to Table 1, as the accuracy performance for SMC, single-chain MCMC, and multi-chain MCMC only depends on the selected values for \(N\), \(K\), and \(N_{T}\) and not on the type of architecture. On a qualitative level, the results on DM resemble the ones presented in Section 6.1.1. Indeed, the differences are seen in terms of quantitative results. Details follow. SMC scales well with respect to itself for \(P=1\) core; more precisely, for \(P=256\), SMC achieves up to a 200-fold speed-up for the largest considered dataset (Students), as Figure 4(b) illustrates. This means that SMC is once again able to provide roughly the same classification accuracy as single-chain MCMC (for the same problem size) but is significantly faster, as shown in Figure 4(b). More precisely, the SMC sampler is able to provide the same accuracy as single-chain MCMC but is faster by up to a factor of 197 in Heart, by up to a factor of 292 in Diabetes, by up to a factor of 588 in Abalone, and by up to a factor of 640 in Students. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Method** & \(\mathbf{P}\) & **Heart** & **Diabetes** & **Abalone** & **Students** \\ \hline SMC & Any & 77.44\% & 73.27\% & 22.48\% & 71.48\% \\ Single-Chain & 1 & 77.01\% & 73.78\% & 22.53\% & 71.64\% \\ Multi-Chain & Any & 67.42\% & 66.76\% & 20.27\% & 55.53\% \\ \hline \hline \end{tabular}
\end{table}