Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 218 / 5

For $\eta (x)=\mathbb{P}(Y=1\mid X=x)$, the risk isThe Bayes classifier is ${\psi }^{\mathrm{Bayes}}(x)=1_{\{\eta (x)\ge 1/2\}}$, with risk $\mathbb{E}\min \{\eta (X),1-\eta (X)\}$.

The K-nearest neighbors algorithm takes the majority label among the $k$ training features closest to the query, with a stated tie rule. Its data-dependent risk is the conditional test error given the training sample, and $R_n$ denotes its expectation over that sample.

For one nearest neighbour, condition on a feature value $X=x$ and couple the coincident nearest feature as $X_1=x$. The two labels are conditionally independent Bernoulli$(\eta (x))$, so their mismatch probability isIntegration over $X$ gives

For each $k=1,\dots ,100$, the call to knn.cv performs leave-one-out nearest-neighbour classification and the third line stores the fraction of omitted observations misclassified. Choose a minimizer of ls, then fit the nearest-neighbour classifier with that $k$ to the full data.

A weighted nearest-neighbours classifier predicts one whenwhere neighbours are distance ordered. Under the usual smooth-density and smooth-regression assumptions, asymptotically optimal weights downweight distant neighbours, for example normalized positive parts of $1-(i/k{)}^{2/p}$. The optimal weighted-nearest-neighbour theorem gives smaller leading asymptotic regret than equal weights.