Page 325 - Introduction to Statistical Pattern Recognition

7 Nonparametric Classification and Error Estimation 307

(7.15)

(7.16)

On the other hand, the conditional Buyes risk given X is

(7.17)

where the 2nd line is the MacLaurin series expansion of the first line. Using
(7.15)-(7.17), it is not difficult to prove that these conditional risks satisfy the
following inequalities, regardless of 6 [ 11.
l* * * * *
.
--Y <r2 <r4 I.. <I-* I.. 5r3 srl 12r*. (7.18)
,
2
r;
The proof for r* I was given in (3.157). Figure 7-2 shows these risks as
functions of 5. The inequalities of (7.18) can also be seen in Fig. 7-2. In
addition, is plotted in Fig. 7-2, because E{m) is the Bhattacharyya
bound of the Bayes error. Figure 7-2 shows that the kNN risks are better
bounds than the Bhattacharyya bound. Taking the expectation of these risks
with respect to X, the corresponding errors can be obtained. Therefore, these
errors also satisfy the inequalities of (7.18). Thus,
1, *
-E 5 &2NN < &:&IN < . . . 5 E* 5 . . . 5 EjNN 5 5 2E* , (7.19)
2
where
E* =E(r*(X)} and E;NN =E(r;(X)}. (7.20)

Equation (7.19) indicates that the error of the voting NN procedure is
less than twice the Bayes error. This is remarkable, considering that the pro-
cedure does not use any information about the underlying distributions and
only the class of the single nearest neighbor determines the outcome of the
decision.