Bias of nearest neighbor error estimates

Area of Science:

• Machine Learning
• Statistical Learning Theory
• Pattern Recognition

Background:

• Nearest Neighbor (NN) methods are widely used for classification and regression.
• Estimating the asymptotic error of NN classifiers is crucial for performance evaluation.
• Finite sample sizes introduce bias in NN error estimates, deviating from asymptotic values.

Purpose of the Study:

• To examine the bias of finite-sample nearest neighbor (NN) and 2-NN errors.
• To derive explicit relationships between bias, sample size, dimensionality, metric, and data distributions.
• To propose a novel procedure for estimating asymptotic NN error in high-dimensional settings.

Main Methods:

• Derivation of analytical expressions for NN and 2-NN error bias.
• Experimental validation of derived expressions.
• Development of an extrapolation procedure using mean NN errors across multiple sample sizes.

Main Results:

• Expressions accurately relate NN error bias to key factors including sample size and dimensionality.
• The derived relationships effectively predict bias.
• A new procedure demonstrates efficacy in estimating asymptotic NN error, particularly for high-dimensional data.

Conclusions:

• Finite sample size significantly impacts NN error estimation bias.
• Increasing sample size alone may not suffice for accurate asymptotic error estimation in high dimensions.
• The proposed extrapolation method offers a robust solution for bias reduction and accurate asymptotic error estimation.