Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 31K (Mathematics of Machine Learning)

Start with the root region ${\mathbb{R}}^p$. For any current terminal region $R$, coordinate $k$, and threshold $s$, formdiscarding splits that leave an empty child. For each child use its training-response meanCompare candidate splits by the resulting residual sum of squarestogether with the unchanged residual sums in the other leaves. Choose the leaf, coordinate, and threshold minimizing the total. Replace that leaf by its two children and repeat until the stopping rule or the prescribed $J$ leaves is reached. The resulting terminal regions are ${\hat{R}}_1,\dots ,{\hat{R}}_J$, andThis is the standard regression tree construction.

Let $m_i=\mathbb{E}(Y_i\mid X_i)$. Conditional on $X_{1:n}$,The responses are conditionally independent, so cross-covariances vanish and

Because the regions partition predictor space,Only one summand is nonzero. Put
$q_j=\mathbb{P}(X\in {\hat{R}}_j)$; the partition is deterministic because $D^{\prime }$ is fixed, and $N_j\sim \mathrm{Bin}(n,q_j)$. The variance bound and
$N_j/(N_j+1{)}^2\le 1/(N_j+1)$ giveThis is the conditional variance of a fixed regression-tree partition bound.