# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
We share our code via GitHub ([[https://github.com/DiscreteVariablesTaskForce/SMCDecisionTrees](https://github.com/DiscreteVariablesTaskForce/SMCDecisionTrees)]([https://github.com/DiscreteVariablesTaskForce/SMCDecisionTrees](https://github.com/DiscreteVariablesTaskForce/SMCDecisionTrees)), accessed on 21 November 2024). ### Experiment 1--Performance for Fixed Problem Size

This first experiment aims to compare the performance of SMC, single-chain MCMC, and multi-chain MCMC in terms of runtime and accuracy for a fixed problem size. The experimental setup is as follows. First, the number of samples in the SMC sampler, \(N\), must be an integer multiple of \(P\), for practical reasons. Since \(P\) is chosen as a power of two, it is also convenient to use power-of-two values for \(N\). Specifically, we use \(N=\{256,512,1024\}\) samples. The SMC sampler is run for \(K=10\) iterations across all datasets, a value determined empirically to achieve competitive classification accuracy. To ensure that all methods operate on the same problem size, we configure single-chain MCMC to draw \(N\times K=N_{T}\) samples in total and multi-chain MCMC to generate \(N\) chains, each with \(K\) samples. Consequently, all methods are evaluated using the same total problem size, \(N_{T}=N\times K\). #### 6.1.1 Results on Shared Memory

The findings for this experiment are presented in Table 1 and Figures 3(a), 4(a), 4(a) and 6(a). Table 1 shows the classification accuracy across all datasets for the largest problem size evaluated in this study, i.e., \(N_{T}=\) 10,240. As observed, the SMC sampler achieves classification accuracy comparable to that of single-chain MCMC, which generates an extended sequence of samples. However, while single-chain MCMC is well known for being an inherently sequential approach, the SMC sampler also demonstrates excellent scalability, measured by the runtime speed-up, i.e., the ratio between the runtime for \(P=1\) core and the runtime for \(P\) cores. Figure 4(a) shows that SMC on SM achieves up to a 16-fold speed-up (for Students), which improves when the problem size increases, as the computation becomes more intensive. This also happens when the size of the dataset is larger. We perceive this to happen because, when the size of the dataset increases, the DTs tend to grow (due to the increased number of possible features and/or thresholds), especially after initializing them by sampling from the prior (which may assign several nodes to each DT from the outset). This consequently increases the computation required for both IS and redistribution, while the data movement only increases in redistribution, since the IS step is embarrassingly parallel. We also point out that the achieved speed-up is not equal to \(P\) (i.e., the ideal speed-up), both because of the parallel overhead terms, \(O(\log_{2}P)\), and the cost of data movement. We also note that SMC for \(P=1\) is faster than single-chain MCMC. While this may seem counterintuitive, the reason is that SMC generates \(N\) samples in \(K\) iterations plus an initialization step. This means that each DT contains at most \(K\) extra nodes after the initialization step. On the other hand, single-chain MCMC produces a single, extended chain of \(N\times K\) DTs, potentially containing up to \(N\times K\) nodes. By leveraging up to \(P=32\) parallel threads, the SMC sampler achieves similar accuracy to single-chain MCMC but is significantly faster, up to eight times in Heart, up to 13 times in Diabetes, up to 42 times in Abalone, and up to 51 times in Students. These speed-up results are illustrated in Figure 6(a), which depicts the speed-up factor (relative to the number of SM threads, \(P\)) of SMC compared to single-chain MCMC for a problem size of \(N_{T}=\) 10,240. For this problem size, both methods achieve comparable classification accuracy. Although single-chain MCMC cannot be parallelized, multi-chain MCMC can run multiple chains in an embarrassingly parallel manner.