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