# A Massively Parallel SMC Sampler for Decision Trees +
## 1 Introduction
### Related Work  
Bayesian DTs were first introduced to solve ML supervised learning problems in [11; 12] and improved in [13; 14]. The key idea is to generate \(N\) samples randomly (where each sample is a DT) in order to estimate the possible problem outcomes. This approach is widely used [15; 16] due to its good performance in terms of classification accuracy, but it is implemented sequentially, i.e., without any use of parallel computing.  
Each new sample in an MCMC chain is generated as a function of the previous one, which is why this approach is difficult to perform in parallel. There exist several attempts to parallelize a single MCMC chain. This approach was first discussed in [17], and more recent attempts can be found in [18; 19]. Examples can also be found in the context of DTs [18; 20; 21]. These studies have confirmed that, even on DTs, parallel approaches for a single MCMC chain are strongly problem-specific, which limits their applicability, and the results often show little to no speed-up improvements as the number of cores increases. Another widely used parallelization strategy is to run multiple chains in parallel. This approach was first discussed in [22], and more recent implementations can be found in [23; 24]. There are numerous examples of this method in the literature in the context of DTs [25; 26]. However, this parallelization strategy trades off the accuracy in order to achieve good scaling and runtime performance. This is particularly pertinent in the context of modern DM architectures, which often provide access to a larger number of computing resources than SM.  
Sequential Monte Carlo (SMC) samplers [27] represent an alternative class of Monte Carlo (MC) methods that can be applied in the same scenarios as MCMC. Their core idea involves combining importance sampling (IS) with resampling to create a population of \(N\) random samples. A key benefit of SMC is its ability to deliver competitive accuracy while being potentially parallelizable, as the samples are generated independently. However, effectively parallelizing SMC is challenging due to difficulties in parallelizing the runtime bottleneck, i.e., the redistribution step (a sub-task of resampling). While early attempts to parallelize redistribution did not show substantial speed-up [28; 29], more recent work on DM [30; 31] and on SM [32; 33; 34] has shown promising results. These parallelization methods are specifically designed for scenarios where all samples are of a fixed size. However, for DTs and other abstract data types (ADTs) like additive structures [35], samples can have variable sizes, making the techniques in [30; 31; 32; 33; 34] less directly applicable. In [36], a parallel SMC sampler for DTs on SM was introduced, but only the IS step was parallelized, leaving the resampling step sequential due to the complexities of redistributing variable-size samples in parallel. Consequently, this approach exhibited limited scalability. Another approach, found in [37], presents a sequential implementation of an SMC sampler for DTs. However, as shown in [38], this method achieves significantly lower accuracy compared to MCMC.