In the $$1$$-nearest neighbor algorithm, the required distance function $$d$$, or equivalently the vector-valued basis function $$\phi(\mathbf{x})$$ used to featurize the data, encodes the model's inductive bias. While any distance metric allows the model to achieve zero training error and eventually converge to an optimal predictor, different choices of $$d$$ represent different underlying assumptions about the data patterns. Consequently, with a finite amount of available data, these different inductive biases will yield different predictors, and their performance will depend on how compatible their assumptions are with the observed data.

Claude

The $$1$$-nearest neighbor algorithm is the simplest case of the $$k$$-nearest neighbor approach, where $$k=1$$. At training time, the learner memorizes the dataset, and at prediction time, it assigns a new data point the label of its single closest neighbor based on a chosen distance function $$d$$. Because it memorizes the data, the algorithm always achieves a training error of zero by perfectly interpolating the training data. Despite this, it can still generalize; under mild conditions, the $$1$$-nearest neighbor algorithm is a consistent estimator, meaning it eventually converges to the optimal predictor.

Learn Before

Related