Statistics and Data Science Seminar
Guan Yu
University of Buffalo
Locally Weighted Nearest Neighbor Classifier and Its Theoretical Properties
Abstract: Weighted nearest neighbor (WNN) classifiers are fundamental non-parametric classifiers for
classification. They have become the methods of choice in many applications where limited
knowledge of the data generation process is available a priori. There exists a vast room of
flexibility in the choice of weights for the neighbors in a WNN classifier. In this talk, I will introduce
a new locally weighted nearest neighbor (LWNN) classifier, which adaptively assigns weights for
different test data points. Given a training data set and a test data point x0, the weights for
classifying x0 in LWNN is obtained by minimizing an upper bound of the conditional expected
estimation error of the regression function at x0. The resultant weights have a neat closed-form
expression, and therefore the computation of LWNN is more efficient than some existing
adaptive WNN classifiers that require estimating the marginal feature density. Like most other
WNN classifiers, LWNN assigns larger weights for closer neighbors. However, in addition to the
ranks of neighbors' distances, the weights in LWNN also depend on the raw values of the
distances. Our theoretical study shows that LWNN achieves the minimax rate of convergence of
the excess risk, when the marginal feature density is bounded away from zero. In the general
case with an additional tail assumption on the marginal feature density, the upper bound of the
excess risk of LWNN matches the minimax lower bound up to a logarithmic term.
Wednesday April 14, 2021 at 4:00 PM in Zoom