Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 30J (Mathematics of Machine Learning)

A regression tree chooses a threshold $s$ and constant predictions $c_L,c_R$ to minimize the squared-error criterionwhere $s$ ranges over thresholds producing two nonempty groups. For a fixed split, the least-squares minimizers are the two sample means,Thus the first split is the candidate threshold with the smallest sum of the two within-node residual sums of squares.

With $X_1<\cdots <X_n$, it suffices to put the threshold between $X_m$ and $X_{m+1}$ for $m=1,\dots ,n-1$. Form the prefix sumsThey take $O(n)$ operations to compute. The minimized squared errors for the two children areandEach candidate value $L_m+R_m$ therefore takes constant time once the prefix sums are available. Scanning all $n-1$ candidates takes $O(n)$ operations in the sense of Big O notation, and retaining the minimizing $m$ gives the optimal split.

WriteThe ordinary least squares estimators givewhereThe denominator is positive because the sorted inputs are distinct and $m\ge 2$.

For each $m$, the displayed objective is the sum of the minimized linear-regression residual sums of squares on the prefix $1:m$ and suffix $(m+1):n$. Precompute prefix sums ofThis requires $O(n)$ operations. The corresponding five sums over a suffix are obtained by subtracting a prefix sum from the total.

For any block of $k$ observations, these raw sums give in constant timeBy the formula for the residual sum of squares in simple linear regression, its minimized loss isHence both losses for a proposed $m$ take constant time. Evaluating their sum for $m=2,\dots ,n-2$ and keeping the minimum is another $O(n)$ scan, so the complete minimization uses $O(n)$ computations.