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