Local Nearest Neighbour Classification with Applications to Semi-Supervised Learning

• Activity Number: 80 - Inference Methods for High-Dimensional and Complex Data
• Type: Contributed
• Date/Time: Sunday, July 30, 2017 : 4:00 PM to 5:50 PM
• Sponsor: Section on Statistics in Imaging
• Author(s): Timothy I. Cannings* and Thomas Berrett and Richard J. Samworth
• Companies: Universtiy of Southern California and University of Cambridge and Statistical Laboratory, University of Cambridge
• Keywords: Classification ; nearest neighbours ; semi-supervised ; asymptotic analysis

Abstract

We present a new asymptotic expansion for the global excess risk of a local k-nearest neighbour classifier, where the choice of k may depend upon the test point. This expansion elucidates conditions under which the dominant contribution to the excess risk comes from the locus of points at which each class label is equally likely to occur, as well as situations where the dominant contribution arises from the tails of the marginal distribution of the features. Our results motivate a new k-nearest neighbour classifier for semi-supervised learning problems, where the unlabelled data are used to obtain an estimate of the marginal feature density, and then fewer neighbours are used for classification when this density estimate is small. The potential improvements over the standard k-nearest neighbour classifier are illustrated both through our theory and via a simulation study.