Exercise 6.9

$e(f(x))={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{c=1}^{C}P[y=c,f(x)\ne c]={\sum }_{c\ne m}P[y=c]={\sum }_{c\ne m}{\pi }_c(x)=1-{\pi }_m(x)=\eta (x)$

Observe that

When $N\to \infty$, we expect ${𝜖}_N(x)\to 0$ because when the data set gets very large, every point $x$ has a nearest neighbor that is close by. That is, we have $x_{[1]}(x)\to x$ for all $x$. This is the case if $P(x)$ has bounded support.

By the continuity of $\pi (x)$, This indicates that ${\pi }_c(x_{[1]})\to {\pi }_c(x)$ and since $|{𝜖}_N(x)|\le \left|\underset{c}{\max <!--\; FUNCTION\; APPLICATION\; -->}\right|({\pi }_c(x)-{\pi }_c(x_{[1]}))\left|\right|$, it follows that ${𝜖}_N(x)\to 0$.

So we conclude that $e(g_N(x))\to {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{c=1}^C{\pi }_c(x)(1-{\pi }_c(x))$ when $N\to \infty$ with high probability according to the law of large number.

Since we also have $\sum <!--\; FUNCTION\; APPLICATION\; -->a_i=1$, apply above inequality to $a_2,a_3,\dots ,a_C$, we have

$(C-1){\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i\ne 1}{a}_i^2\ge {({\sum }_{i\ne 1}{a}_i)}^2$, add $(C-1)a_1^2$ to both sides we have

$(C-1)\sum <!--\; FUNCTION\; APPLICATION\; -->a_i^2\ge (C-1)a_1^2+{({\sum }_{i\ne 1}{a}_i)}^2=(C-1)a_1^2+{(1-a_1)}^2$. Divide both sides by $C-1$, we have

$\sum <!--\; FUNCTION\; APPLICATION\; -->a_i^2\ge a_1^2+\frac{{(1-a_1)}^2}{C-1}$.

Now take expectation w.r.t. $x$ on $g_N(x)$, we have

Apply the above inequality, we have

From problem (a), we have $\eta (x)=1-{\pi }_1(x)$, take this into above inequality, we have

Where $E_{\mathit{out}}^{\text{∗}}=E_{\mathit{out}}[\eta (x)]$ and we have used $E_{\mathit{out}}[{\eta }^2(x)]\ge {(E_{\mathit{out}}[\eta (x)])}^2={(E_{\mathit{out}}^{\text{∗}})}^2$

As $N\to \infty$, we have $E_{\mathit{out}}[{𝜖}_N(x)]\to 0$, so

$E_{\mathit{out}}(g_N(x))\le 2E_{\mathit{out}}^{\text{∗}}-\frac{C}{C-1}{(E_{\mathit{out}}^{\text{∗}})}^2$

This demonstrates that for multiclass problem, the simple nearest neighbor is at most a factor of 2 from optimal.