8.28 BART algorithm: iteration 2 and on

• In subsequent iterations, BART updates each of the $K$ trees one at a time

• In the $b$th iteration to update the $k$th tree, we subtract from each response value the predictions from all but the $k$th tree, to obtain a partial residual:

$r_i = y_i - \sum_{k'<k}\hat{f}^b_{k'}(x_i) - \sum_{k'>k}\hat{f}^{b-1}_{k'}(x_i)$

for the $i$th observation, $i = 1, …, n$

• Rather than fitting a new tree to this partial residual, BART chooses a perturbation to the tree from a previous iteration $\hat{f}^{b-1}_{k}$ favoring perturbations that improve the fit to the partial residual

• To perturb trees:

  • change the structure of the tree by adding/pruning branches

  • change the prediction in each terminal node of the tree

• The output of BART is a collection of prediction models:

$\hat{f}^b(x) = \sum_{k=1}^{K}\hat{f}^b_k(x)$

for $b = 1, 2,…, B$