I am trying to understand the details of BART (Bayesian Additive Regression Trees). In particular, I would like to know how the Metropolis Hastings acceptance probability is calculated for BART. My references for BART are (Chipman 1998), (Chipman 2010) and (Hill 2020). In order to focus on how Metropolis Hastings works for BART, I will focus on Bayesian CART (Chipman 1998), which is a Bayesian approach to estimate a regression tree model. As described in (Chipman 2010), BART builds on Bayesian CART, but expands the model to a sum-of-trees model instead of relying on a single regression tree.
Metropolis Hastings is used in Bayesian CART (and in BART) to generate a Markov chain of regression trees, which converges to the posterior distribution (see the references for details). More concretely, let $T_i$ denote the $i^{th}$ tree in the chain. A candidate $T^*$ for $T_{i+1}$ is generated by stochastically modifying $T_i$ with one of four modifications: growing a terminal node (chosen with probability 0.25), pruning a pair of terminal nodes (0.25), changing a nonterminal rule (0.40), and swapping a decision rule between parent and child (0.10) (see the references for details). The acceptance probability $\alpha$ of the candidate is calculated in the standard Metropolis Hastings way (the following formula is copied from (Chipman 1998)):
$\alpha(T_i,T^*)=\min \left( \frac{q(T_i|T^*)p(y|x,T^*)p(T^*)}{q(T^*|T_i)p(y|x,T_i)p(T_i)}, 1 \right)$
where
- $q(K | T)$ is the transition kernel (the probability that $T$ is proposed as a candidate given that the current tree is $T$)
- $p(y|x,T)$ is the probability of observing the outcome $y\in \mathbb{R}^n$ ($n$ is the sample size) given the predictors $x\in \mathbb{R}^{n\times p}$ ($p$ is the number of predictors)
- $p(T)$ is our prior probability on tree structure $T$
(Chipman 1998) provides a closed-form expression of $p(y|x,T)$, so I know how this quantity is calculated. However, I am more in doubt about how to calculate $q(K | T)$ and $p(T)$. My current idea is to use the four modification rules (described above) to derive a simple program that can calculate $q(K | T)$. Likewise, I want to use the stochastic tree-generating process, which is used to define $p(T)$ to derive a simple program that can calculate $p(T)$. This process is defined by to probabilities. The first is $p_{split}(d)=\alpha(1+d)^{-\beta}$, which specifies the prior probability that a node with depth $d$ is not a leaf node. The second is $p_{rule}(r | \eta , T)$, which - given that the node $\eta$ in the tree $T$ is not a leaf node - specifies the probability that the node splits the observations with decision rule $r$. A decision rule $r$ in a regression tree is defined by the predictor and threshold that the observations are split according. (Chipman 1998) simply uses a uniform distribution on available predictors and thresholds for the node $\eta$ as the prior rule probability $p_{rule}$ (available means that if the predictor and threshold are chosen, then the node's children will be non-empty). See (Chipman 1998) for more details on how the tree prior $p(T)$ is defined.
I have two questions:
- Do you know of any references, where I can read how the calculations of $q(K|T)$ and $p(T)$ are implemented?
- Do you think that it is the right approach to use the generative processes, which defines $q(K|T)$ and $p(T)$, to derive and implement some simple programs that can calculate these quantities? If yes, how would you approach these derivations?
Thank you very much for your help.
References:
- Chipman, H., George, E., & McCulloch, R. (1998). Bayesian CART Model Search. Journal of the American Statistical Association, 93(443), 935-948.
- Chipman, Hugh A.; George, Edward I.; McCulloch, Robert E. BART: Bayesian additive regression trees. Ann. Appl. Stat. 4 (2010), no. 1, 266--298.
- Hill, Jennifer and Linero, Antonio and Murray, Jared, Bayesian Additive Regression Trees: A Review and Look Forward (March 2020). Annual Review of Statistics and Its Application, Vol. 7, Issue 1, pp. 251-278, 2020
