# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
After resampling, a new iteration starts from (5), and, after \(K-1\) iterations, the final samples are used to obtain estimates on a test set. More precisely, for each DT, we compute the classification accuracy, and then one could either use the mean or majority voting to calculate the overall accuracy. As described in Section 4.1, for MCMC, in this work, we compute the mean. Algorithm 4 summarizes the steps above. In line with the notation used for single-chain MCMC and multi-chain MCMC, we say that SMC has a total problem size equal to \(N_{T}=N\times K\), since each of the \(N\) samples is updated \(K\) times. For the same problem size, we expect our experimental results to show that SMC achieves comparable accuracy to single-chain MCMC with a faster runtime due to its parallel nature. In the same settings, we expect our experimental results to show that SMC achieves significantly higher accuracy than multi-chain MCMC at the price of a longer runtime. ```
1:\(K,N\)
2:t_k
3:\(\mathbf{t}_{0}^{i}\sim q_{0}(),\forall i=0,1,\ldots,N-1\)
4:\(\mathbf{w}_{i}^{i}\leftarrow\frac{1}{N},\forall i=0,1,\ldots,N-1\)
5:for\(k\gets 0\); \(k<K\); \(k\gets k+1\)do
6:\(\mathbf{t}_{k}^{i}\sim q(\cdot|\mathbf{t}_{k-1}^{i}),\ \forall i=0,1,2,\ldots,N-1\)
7:\(\mathbf{w}_{i}^{i}\leftarrow\mathbf{w}_{i-1}^{i}\frac{\pi(\mathbf{t}_{i-1}^{ i}|\mathbf{t}_{k}^{i})}{\pi(\mathbf{t}_{i}^{i}|\mathbf{t}_{k-1}^{i})},\ \forall i=0,1,2,\ldots,N-1\)
8:\(\mathbf{w}_{k}^{i}\leftarrow\frac{\mathbf{w}_{i}^{i}}{\sum_{i=0}^{N-1}\mathbf{ w}_{i}^{i}},\ \forall i=0,1,2,\ldots,N-1\)
9:\(N_{eff}\leftarrow\frac{1}{\sum_{i=1}^{N}(\mathbf{w}_{i}^{i})^{2}}\)
10:if\(N_{eff}<\frac{N}{2}\)then
11:\(\mathbf{cdf}^{i}\gets N\sum_{j=0}^{i-1}\mathbf{w}_{k}^{i},\ \forall i=0,1,\ldots,N-1\)
12:\(u\sim\)Uniform\([0,1]\)
13:\(\mathbf{ncopies}^{i}\leftarrow\)\(\mathbf{cdf}^{i+1}-u\)\(\lceil\mathbf{cdf}^{i}-u\rceil,\ \forall i=0,1,\ldots,N-1\)
14:\(\mathbf{t}_{k}\leftarrow\)Redistribution\((\mathbf{t}_{k},\mathbf{ncopies},N)\)
15:\(\mathbf{w}_{k}^{i}\leftarrow\frac{1}{N},\ \forall i=0,1,\ldots,N-1\)
16:endif
17:endfor
```  
**Algorithm 4** Sequential Monte Carlo Sampler  
In the third and final step of resampling, each weight, \(\mathbf{w}^{i}\), is reset to \(1/N\). After resampling, a new iteration starts from (5), and, after \(K-1\) iterations, the final samples are used to obtain estimates on a test set. More precisely, for each DT, we compute the classification accuracy, and then one could either use the mean or majority voting to calculate the overall accuracy. As described in Section 4.1, for MCMC, in this work, we compute the mean. Algorithm 4 summarizes the steps above. In line with the notation used for single-chain MCMC and multi-chain MCMC, we say that SMC has a total problem size equal to \(N_{T}=N\times K\), since each of the \(N\) samples is updated \(K\) times. For the same problem size, we expect our experimental results to show that SMC achieves comparable accuracy to single-chain MCMC with a faster runtime due to its parallel nature. In the same settings, we expect our experimental results to show that SMC achieves significantly higher accuracy than multi-chain MCMC at the price of a longer runtime. ```
1:\(K,N\)
2:t_k
4:\(\mathbf{w}_{k}^{i}\leftarrow\frac{1}{N},\forall i=0,1,\ldots,N-1\)
5:for\(k\gets 0\); \(k<K\); \(k\gets k+1\)do
6:\(\mathbf{w}_{k}^{i}\leftarrow\mathbf{w}_{k-1}^{i}\frac{\pi(\mathbf{t}_{k-1}^{i}| \mathbf{t}_{k}^{i})}{\pi(\mathbf{t}_{k-1}^{i}|\mathbf{t}_{k}^{i})}\)
7:\(\mathbf{w}_{k}^{i}\leftarrow\

### Posterior and Proposals for Bayesian Decision Trees

In this section, we briefly describe how to compute the posterior, the proposal, and the initial proposal in the specific case of DTs. #### 4.3.1 Posterior Distribution

The posterior is proportional (up to a normalization constant) to the product of the likelihood and the prior.