# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
We note that, in the theoretical analysis of this section, we omit the overhead due to the data movement for simplicity reasons. The cost of data movement on SM could be roughly represented as \(O(t_{\text{SM}}\frac{N}{P})\), where \(t_{\text{SM}}\) is the average cost of copying a sample from memory address \(i\) to memory address \(j\), while, on DM, it could be roughly represented as \(O(t_{\text{DM}}\frac{N}{P}\log_{2}P)\), where \(t_{\text{DM}}\) is the average cost of messaging a sample from core \(i\) to core \(j\). The accurate quantification of \(t_{\text{SM}}\) and \(t_{\text{DM}}\) is difficult because it is strongly dependent on the hardware (e.g., using NUMA or UMA architectures) and is beyond the scope of this manuscript, but it is a very interesting point of study for future work. ## 6 Numerical Results

This section presents two experiments that compare SMC with single-chain MCMC and multi-chain MCMC using four publicly available datasets of increasing size, commonly utilized in ML classification studies ([[https://archive.ics.uci.edu/dataset/45/heart+disease](https://archive.ics.uci.edu/dataset/45/heart+disease)]([https://archive.ics.uci.edu/dataset/45/heart+disease](https://archive.ics.uci.edu/dataset/45/heart+disease)), [[https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database](https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database)]([https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database](https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database)), [[https://www.kaggle.com/datasets/hurshd0/abalone-uci](https://www.kaggle.com/datasets/hurshd0/abalone-uci)]([https://www.kaggle.com/datasets/hurshd0/abalone-uci](https://www.kaggle.com/datasets/hurshd0/abalone-uci)), [[https://archive.ics.uci.edu/dataset/697/predict+students+dropout+and+academic+success](https://archive.ics.uci.edu/dataset/697/predict+students+dropout+and+academic+success)]([https://archive.ics.uci.edu/dataset/697/predict+students+dropout+and+academic+success](https://archive.ics.uci.edu/dataset/697/predict+students+dropout+and+academic+success)), accessed on 21 November 2024). The first dataset, Heart Disease (Heart), includes 303 records and 75 features. The second dataset, Pima Indians Diabetes (Diabetes), consists of 768 records and 9 features, designed to predict whether a patient has diabetes, with two possible outcome classes. The third dataset, Abalone, contains 4177 records and 9 features, aimed at classifying the ages of abalones into 29 possible outcome classes. The fourth dataset, Predict Students' Dropout and Academic Success (Students), comprises 4424 records and 37 features and focuses on classifying students' enrollment status into three possible outcomes: enroll, drop out, or graduate. In both experiments, 70% of the data were used for training, while the remaining 30% were reserved for testing. For each experiment, we include results for both SM and DM architectures, but we purposely avoid direct comparisons of the same methods (e.g., SMC) across different memory architectures, given the substantial differences between SM and DM. The results on DM are obtained on a cluster of 320 cores, equally distributed across 8 machines, each mounting 384 GB memory and a '2 Xeon Gold 6138' CPU, which indeed provides 40 cores. For obvious reasons, the results on SM are obtained using only one of these 8 machines. We note that, independently of the system architecture, we always employ power-of-2 numbers of cores, as all algorithms described in Section 5 use the divide-and-conquer paradigm. Therefore, we are bound to use up to \(P=256\) cores for the results on DM and up to \(P=32\) cores for the results on SM. As stated in Section 2, the SM code is parallelized using OpenMP and interfaces with Python through Cython, and the DM code is also developed in Python and is parallelized by using MPI through the mpi4 py library.