We consider the 1-Nearest-Neighbor classifier for multi-class classification with C classes. Assume we have n number of labeled samples Dn={(xi,yi)}i=1n where xiRd and yi[C]:={1,,C} for all i[n]. The samples are drawn independently from an unknown distribution p(x,y). As in the lectures, for a data point x having label y, we consider the 01 loss function for a classifier f:Rd[C] given by: L(f(x),y)={01y=f(x)otherwise For a given classifier f, the expected classification error for a single point x and the average error rate are given by (1) and (2), respectively. R(f,x)=Eyp(yx)L(f(x),y)R(f)=Exp(x)R(f,x)=Ex,yp(x,y)L(f(x),y) We denote the optimal Bayes classifier for the problem as f. Thus, for a given sample x, the classifier f returns the value: f(x)=y[C]argmaxp(yx) The corresponding average error rate for the Bayes classifier f is denoted by R(f). Let (x,y) be a test sample drawn from the distribution p(x,y). The goal of this problem is to prove that in the limit n (i.e. for asymptotically large number of training samples), the following holds: R(fNNC)=Exp(x)R(fNNC,x)R(f)(2C1CR(f)) Here fNNC denotes the 1-Nearest-Neighbor classifier, R(fNNC) is the average error rate given access to asymptotically large number of training samples, and R(fNNC,x) denotes the classification error of the 1-Nearest-Neighbor algorithm for a given point x. Note that incorrect classification occurs for the sample x (with a label y ) precisely when its nearest neighbor (denoted by (x) ) in the training set has a different label (y(x)=y). We will now prove (3) by working through the following sub-problems. (a) For a sample point x with true label y, denote the nearest neighbor by (x) having label y(x). Show that the equality (*) holds in the following equation R(fNNC,x):=p(y=y(x)x)=()1c=1Cp2(cx) The L.H.S. in the above denotes the probability of x and its nearest neighbor (x) having different labels. Note: You may assume that as n,p(cx)=p(c(x)) for all c[C]. (b) Consider the expected classification error of f for the point x R(f,x):=1p(yx) where y=y[C]argmaxp(yx). Prove the following R(f,x)=c=gp(cx) (c) Using the expression (4) derived in part (b), prove the following R2(f,x)(C1)c=yp2(cx) Hint: Using (4), show that R(f,x) can be expressed as R(f,x)=u1 for some uRC1, where 1 represents the all ones vector in RC1 and use the Cauchy-Schwarz inequality- (d) Using the results from part (b) and (c), show that the following holds for the point x 1c=1Cp2(cx)R(f,x)(2C1CR(f,x)) (e) Taking the expectation of (5) from part (d), finally prove that we have R(fNNC)R(f)(2C1CR(f)) where R(fNNC) is the average error rate of the 1-Nearest-Neighbor algorithm given access to asymptotically large number of training samples as defined in (3). Hint: You may use the fact that the variance Var(R(f,x))0, where Var() is the variance of a random variable
