# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo

Table 1: Classification accuracy for the same problem size, \(N_{T}=10,240\) samples, generated by each method as follows: \(N=1024\) samples updated \(K=10\) times for SMC; one chain of \(N_{T}=10,240\) samples for single-chain MCMC; \(N=1024\) chains of \(K=10\) samples each for multi-chain MCMC. Figure 6: Speed-ups for multi-chain MCMC for \(K=10\) samples per chain and increasing number of chains \(N\). Figure 7: Speed-up gain of SMC vs. single-chain MCMC for (approximately) the same accuracy. As we also observe on SM, multi-chain MCMC scales well and is faster than SMC on DM as well, as shown in Figures 4b and 6b. The reason is once again that multi-chain MCMC is an embarrassingly parallel algorithm with a faster computation time per sample than SMC, and it is bound to an optimal \(O(\log_{2}N)\) time complexity on DM as well, as proven in Lemma 2 and Theorem 1. Considering the trade-off between the runtime and accuracy inherent to multi-chain MCMC on both SM and DM computer architectures, one might question whether increasing \(K\) to match the elapsed time of SMC would allow multi-chain MCMC to achieve superior accuracy. This question is addressed in the following section. ### Experiment 2--Accuracy for Fixed Elapsed Time

Building on the previous section, this experiment aims to compare the classification accuracy of SMC and multi-chain MCMC when both methods are run for the same elapsed time. To achieve this, we first identify the best runtimes for SMC and multi-chain MCMC at \(N=1024\) and then incrementally increase \(K\) in multi-chain MCMC until the runtimes of the two methods are approximately equivalent. #### 6.2.1 Results on Shared Memory

Table 2 presents the results of this experiment conducted on SM across all datasets. As observed, we had to increase \(K\) in multi-chain MCMC by a factor of 4.2 for Heart, 3.3 for Diabetes, 1.8 for Abalone, and 1.5 for Students compared to the previous experiment (where \(K=10\)). This adjustment led to improved accuracy across all datasets relative to the results in Table 1. Specifically, the accuracy increased from 67.42% to 71.89% for Heart, from 66.76% to 69.49% for Diabetes, from 20.27% to 20.62% for Abalone, and from 55.53% to 60.32% for Students. Nonetheless, despite these improvements, the accuracy achieved by multi-chain MCMC remains substantially lower than the accuracy achieved by SMC. #### 6.2.2 Results on Distributed Memory

The results for this experiment on DM are provided in Table 3 for all datasets. At both the qualitative and quantitative levels, the results in Table 3 for DM are similar to the ones presented in Table 2 for SM. Indeed, in order to run for (roughly) the same elapsed time as SMC, multi-chain MCMC requires \(K=30\) samples per chain on Heart, \(K=20\) samples per chain on Diabetes, \(K=12\) samples per chain on Abalone, and \(K=14\) samples per chain on Students. This has again translated into improved classification accuracy with respect to the values reported in Table 1. More precisely, multi-chain MCMC achieves, once again, significantly lower classification accuracy than SMC. We note that the classification accuracies for SMC are identical to the ones in Table 2, as the values of \(N\) and \(K\) for SMC are unchanged. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Dataset** & **Method** & \(\mathbf{P}\) & \(\mathbf{N}\) & \(\mathbf{K}\) & **Time** & **Accuracy** \\ \hline Heart & SMC & 32 & \(2^{10}\) & 10 & 7.6 [s] * & 77.44\% \\  & Multi-Chain MCMC & 32 & \(2^{10}\) & 42 & 7.6 [s] * & 71.89\% \\ \hline Diabetes & SMC & 32 & \(2^{10}\) & 10 & 13 [s] * & 73.27\% \\  & Multi-Chain MCMC & 32 & \(2^{10}\) & 33 & 13 [s] * & 69.49\% \\ \hline Abalone & SMC & 32 & \(2^{10}\) & 10 & 47 [s] * & 22.48\% \\  & Multi-Chain MCMC & 32 & \(2^{10}\) & 18 & 47 [s] * & 20.62\% \\ \hline Students & SMC & 32 & \(2^{10}\) & 10 & 77 [s] * & 71.48\% \\  & Multi-Chain MCMC & 32 & \(2^{10}\) & 15 & 77 [s] * & 60.32\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Accuracy per time unit on SM.