# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
In other words,

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]0

where \(p(\mathbf{Y}|\mathbf{T},\theta,\mathbf{x})\) is the likelihood and \(p(\theta,\mathbf{T})\) is the prior. More precisely, for each individual term in (11), we use the following expressions:

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]1

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]2

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]3

Using the Poisson distribution for the \(p(\mathbf{T})\) term is common practice in the literature [12; 15; 16]. As we can see, (14) only requires the tuning of the \(\lambda\) hyperparameter. Another valid expression can be found in [42; 43]. This alternative, however, requires the tuning of two hyperparameters. Therefore, we employ (14) for simplicity. #### 4.3.2 Proposal Distribution

The proposal distribution, \(q(\cdot|\cdot)\), defines a set of four possible operations that either modify the structure of the DT and/or update its parameters. These operations are as follows. * _Grow_. This operation increases the dimensionality of the DT by randomly selecting a leaf node and attaching two child nodes to it. * _Prune_. This operation reduces the dimensionality of the DT by selecting a non-leaf node at random and removing its child nodes. * _Change_. This operation randomly selects a non-leaf node, \(j\), and updates its feature, \(\mathbf{k}^{\prime}\), and threshold, \(\mathbf{c}^{\prime}\), without altering the tree's dimensionality. * _Swap_. This operation randomly selects two non-leaf nodes, \(i\) and \(j\), and exchanges their features, \(\mathbf{k}^{i}\) and \(\mathbf{k}^{\prime}\), as well as their thresholds, \(\mathbf{c}^{i}\) and \(\mathbf{c}^{\prime}\), keeping the tree's dimensionality unchanged. The probabilities of applying these operations, \(p(Grow)\), \(p(Prune)\), \(p(Change)\), and \(p(Swap)\), are user-specified and must sum to 1. A common choice is to assign equal probabilities of 25% to each operation. Details on the computation of \(q(\cdot|\cdot)\), used in (2) and (5b), can be found in [20] and are omitted here for brevity. #### 4.3.3 Initial Proposal

The initial proposal distribution, \(q_{0}(\cdot)\), is defined by sampling from the prior distribution of the DT, \(p(\mathbf{T})\). ## 5 Theoretical Results

### Algorithmic Details

In this section, we describe the parallelization on both SM and DM of all tasks in the SMC sampler, including our approach to parallelizing the redistribution step. It is relatively straightforward to infer that both steps to initialize and update the samples and the weights, i.e., Equations (4) and (5), are embarrassingly parallel. On SM, as well as on DM, these steps can be parallelized by equally dividing the iteration space of the related for loops, for \(i=0,1,\ldots,N-1\), across the \(P\) cores, such that each core, \(id=0,1,\ldots,P-1\), works on a chunk of \(n=\frac{N}{P}\) samples and weights with index \(i=id\cdot n,id\cdot n+1,id\cdot n+2,\ldots,(id+1)\cdot n-1\). Therefore, these steps achieve \(O(\frac{N}{P})\) time complexity. The same can be said about (9). Equation (6) requires the computation of a vector sum. On both SM and DM, this operation is parallelizable by using reduction, which notoriously achieves \(O(\frac{N}{P}+\log_{2}P)\) time complexity. The prefix sum in Equation (8) can also be performed in \(O(\frac{N}{P}+\log_{2}P)\) by using prefix reduction [44; 45]. Once again, this is true for both SM and DM. Thus far, it is clear that all steps in Algorithm 4, except Algorithm 3, achieve, at most, \(O(\log_{2}N)\) time complexity for \(P\to N\). We note that the parallel overhead term, \(\log_{2}P\), will, in practice, limit the speed-up to less than \(P\), but it becomes less important compared with \(\frac{N}{P}\) in increasing \(N\).