Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 218 / 3 / d / Solution

The limiting conditional error of one-nearest-neighbour classification is

1 - \sum_{k} p_{k} (x)^{2}

. Put

M = max_{k} p_{k} (x)

and

r = 1 - M

. By the Cauchy-Schwarz inequality, the other

K - 1

probabilities satisfy

\sum_{k : p_{k} \neq = M} p_{k}^{2} \geq \frac{r ^{2}}{K - 1} .

Consequently

1 - \sum_{k} p_{k}^{2} \leq 1 - (1 - r)^{2} - \frac{r ^{2}}{K - 1} = 2 r - \frac{K}{K - 1} r^{2} .

Now

E r = R_{Bayes}

, and Jensen inequality gives

E r^{2} \geq (E r)^{2}

. Taking expectations proves

lim_{n \to \infty} R (h_{n}^{1NN}) \leq 2 R_{Bayes} - \frac{K}{K - 1} R_{Bayes}^{2} .

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version