# Chapter 7 Algorithm

Algorithm type: Metropolis within GIBBS for a hierachical Bayesian tree

Reason: We have closed posteriors for most parameters, but not for the tree structure

Data: Target variable $$y$$, groups $$j = 1,\dots,m$$, set of features X

Result: Posterior distributions for all parameters

Initialisation;

Hyper-parameters values for $$\alpha, \beta, k_1, k_2$$;

Number of groups $$m$$;

Number of observations $$N =\sum_{j = 1}^{m} n_j$$;

Number of iterations I;

• define $$\mu_{\mu} = 0$$, $$\mu^{0}$$, $$\tau^{0}$$, and $$\mu_j^{0}, j = 1,\dots, m$$ as the initial parameter values

• for i from 1 to I do:

• grow a new $$T^{\text{new}}$$ tree by either growing, pruning, changing or swapping a root node

• set $$l_{\text{new}}$$ = log full conditional for the new (candidate) tree

$$l_{\text{new}} = \sum_{l = 1}^{b_{\text{new}}} -\frac{1}{2} \log(|\boldsymbol{W}_{1,l}|) + \log(\Gamma(N_l/2 + \alpha))$$ $$-(N_l/2 + \alpha)\left[ \log \beta + \log\Big(\frac{(\mathbf{y}_l - \mathbf{W}_{0,l})^T \mathbf{W}_{1,l}^{-1} (\mathbf{y}_l - \mathbf{W}_{0,l})}{2} \Big) \right]$$
• set $$l_{\text{old}}$$ = log full conditional for the previous tree
$$l_{\text{old}} = \sum_{l = 1}^{b_{\text{old}}} -\frac{1}{2} \log(|\boldsymbol{W}_{1,l}|) + \log(\Gamma(N_l/2 + \alpha))$$ $$-(N_l/2 + \alpha)\left[ \log \beta + \log\Big(\frac{(\mathbf{y}_l - \mathbf{W}_{0,l})^T \mathbf{W}_{1,l}^{-1} (\mathbf{y}_l - \mathbf{W}_{0,l})}{2} \Big) \right]$$
• set $$a = \exp(l_{\text{new}} - l_{\text{old}})$$

• generate $$u \sim U[0, 1]$$
• if $$u < a$$ then:
• set $$T = T^{\text{new}}$$
• end
• sample $$\mu$$ from the posterior $$N(\frac{(\tau/k_1) \bar \mu m}{\tau(\frac{1}{k_2} + \frac{m}{k_1})}, (\tau(\frac{1}{k_2} + \frac{m}{k_1}) )^{-1})$$ (because of $$\bar \mu$$)

• for j in 1:m do:

• sample $$\mu_j$$ from the posterior $$N(\frac{\mu/k_1 + \bar y_j n_j}{n_j + 1/k_1}, ((n_j + \frac{1}{k_1})\tau)^{-1})$$
• end

• sample $$\tau$$ from the posterior $$\text{Gamma}\Big(n/2 + \alpha, \beta + \frac{(\mathbf{y} - \mathbf{W}_0)^T \mathbf{W}_1^{-1} (\mathbf{y} - \mathbf{W}_0)}{2}\Big)$$

• end