Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 218 / 3

The classification form of CART starts with the root rectangle $R=[0,1{]}^2$. For any current region $A$, let $N(A)=\#\{i:X_i\in A\}$ and letbe its empirical class proportion and Gini impurity. A candidate axis-aligned split $X_j\le s$ partitions $R$ into $U$ and $V$. Its impurity change isAmong all coordinates and thresholds between consecutive observed coordinates, CART chooses a split minimizing $Q$, then applies the same recursive partitioning independently to the children until a stopping rule is met. Each terminal region predicts its majority class. Pruning may then select a smaller subtree by penalizing the number of leaves.

For the resulting classifier $\hat{C}$, the training error iswhile its prediction error is $R(\hat{C})=\mathbb{P}\{\hat{C}(X_{new})\ne Y_{new}\}$ for an independent observation drawn from the target population.

Let $w=N(U)/N(R)$, so $1-w=N(V)/N(R)$. Since class counts add,The function $g(p)=p(1-p)$ is concave function on $[0,1]$. Jensen inequality therefore giveswhich is precisely $Q\le 0$. Thus an axis-aligned split cannot increase the weighted empirical Gini impurity.

A random forest fits each of its $500$ classification trees to an independent bootstrap sample of the nine observations. At each node it draws mtry=2 candidate coordinates; because the data have exactly two coordinates, both are available, and a CART impurity calculation chooses the split. The trees are grown deeply without ordinary cost-complexity pruning, and their majority vote is the forest prediction.

R reports an out-of-bag error estimate: an observation is predicted only by trees whose bootstrap samples omitted it. The confusion matrix says that class 1 has three correct and three incorrect out-of-bag predictions, while class 2 has one correct and two incorrect predictions. Hence the total out-of-bag error is $5/9$.

The loop performs Leave-one-out cross-validation: for each $i$ it fits a forest to the other eight observations, tests it on observation $i$, and averages the nine zero-one losses. A random forest's out-of-bag error estimate approximates the same held-out prediction error from one fit, because each tree automatically omits roughly a proportion $e^{-1}$ of the observations in its bootstrap sample.

The one-nearest-neighbour classification boundary consists of the portions of the Voronoi diagram separating cells whose observed labels differ. For these nine grid points it forms diagonal and vertical or horizontal perpendicular-bisector segments around the three triangular observations. Every training point is its own nearest neighbour, so, absent a distance tie convention that excludes the query itself, its training error is zero.

An unpruned maximal CART classifier repeatedly cuts with vertical or horizontal lines until every terminal rectangle is pure or contains observations that cannot be separated by an axis-aligned split. Here the distinct grid points can be isolated into pure rectangles, producing a step-shaped, axis-aligned decision boundary and zero training error.

The random forest boundary is the majority vote of many bootstrap-grown axis-aligned trees. It remains piecewise axis-aligned but averages away many unstable individual cuts, so one should sketch a less extreme boundary enclosing regions supported repeatedly by the triangular points. Its resubstitution training error is typically small and can be zero, but bootstrap omission and voting mean that zero is not guaranteed. The relevant built-in estimate is instead the out-of-bag error, which the output gives as $5/9$; this large value reflects the tiny sample and unstable labels near the class boundary.