K Nearest Neighbor as a Neural Network

A Neural network is a universal function approximator, so in theory it is possible to learn any function using a neural network. As K-nearest neighbor is a method of predicting the label of a new datapoint from the test set, it is possible to express its prediction function as a neural network, although less intuitive. This article will show how to express a 1-Nearest Neighbor as a 3 layer neural network, using the given datapoints. If you would like to jump directly into the accompanying code, just follow this link to the notebook.

Here’s what we will cover:

1. Introduction
2. K Nearest Neighbor
3. Expressing KNN as a Neural Network
   1. Layer 1: Computing the distance function
   2. Layer 2: Softmax Layer
   3. Layer 3: Prediction Layer
4. Implementation
5. Future Work
6. Conclusion

Introduction

k-Nearest Neighbor is a non-parametric model that uses a distance function to evaluate the label of a new test point. It involves taking the average of predictions of k nearest points to the given test point. It often serves as a base model for many prediction tasks and often difficult to beat.

Given a set of train data-points,

\[\{(x_1, y_1), (x_2, y_2), \dots ,(x_n, y_n)\}\]

with \(x_i \in \mathbb{R}^d\), \(y_i \in \mathbb{R}\) and \(i = 1, 2, \dots, n\). There are \(n\) training examples each with d number of features. Given a new datapoint \(x^t\), how can we classify the point using k-nearest neighbor into its correct class?

K Nearest Neighbor

To classify a new test point into its correct label, we perform the following steps:

• Calculate the distance between each datapoint in the training example and the test datapoint
• Assign the test data point the label of the k datapoints with minimum distance. For a classification task, we can take the mode of the k classes, while for regression task, we average the predictions to get the prediction.
• k can range from 1 to n, but usually between 1 and 10.
• The distance function takes in each \(x_i\) and \(x^t\) and outputs a scalar. The distance function to use may depend on the task but a popular and common distance is the l2-distance. The l2-distance can be expressed as:

\[d_i = \sqrt{\sum_{j=1}^{d} (x_{ij} - x^t_j)^2}\]

Using the matrix notation,

\[d = \sqrt{\sum_{j=1}^{d} (X_j - 1_n x^t_j)^2}\]

where \(X = (x_1, x_2, \dots, x_n)^T \in \mathbb{R}^{n \times d}\), \(X_j \in \mathbb{R}^n\) is its \(j\)-th column, \(1_n\) is a vector of ones, \((x^t)^T \in \mathbb{R}^d\), and the square and square root are taken element-wise. To simplify notation, I will assume that \(x^t_j\) will be broadcasted along the column, which becomes simply:

\[d = \sqrt{\sum_{j=1}^{d} (X_j - x^t_j)^2}\]

Expressing KNN as a Neural Network

With the understanding of the distance function, we can break it apart to derive the parameters of our neural network.

From the distance function,

\[d_i^2 = \sum_{j=1}^{d} (x_{ij} - x^t_j)^2 = d'_i\]

Since the training point with the smallest \(d^2\) also has the smallest \(d\), we work with \(d^2\) instead, which we will call \(d'\).

Layer 1: Computing the distance function

Expanding the equation, we get:

\[d' = \sum_{j=1}^{d} \left((X_j - x^t_j) \odot (X_j - x^t_j)\right)\]

Note that: \(\odot\) is a Hadamard product, i.e., element-wise product between the two matrices.

\[\begin{aligned} d' &= \sum_{j=1}^{d} \left(X_j \odot X_j - 2x^t_j X_j + (x^t_j)^2\right) \\ &= -2Xx^t + \sum_{j=1}^{d} X_j \odot X_j + \lVert x^t \rVert^2 \end{aligned}\]

since \(\sum_{j=1}^{d} x^t_j X_j\) is exactly the matrix-vector product \(Xx^t\). The \(i\)-th entry is \(\lVert x_i \rVert^2 - 2x_i^T x^t + \lVert x^t \rVert^2\).

At this point we can easily extract our first layer, \(Z_1 = W_1x_1 + b\) where \(W_1 = -2X\), \(x_1 = x^t\) and \(b = \sum_{j=1}^{d} X_j \odot X_j\), i.e., \(b_i = \lVert x_i \rVert^2\). The last term, \(\lVert x^t \rVert^2\), depends on the test point rather than on the training data, so it is not a fixed bias. It adds the same value to every distance, and the softmax in the next layer is unchanged by a constant shift, so we can drop it: \(Z_1 = d' - \lVert x^t \rVert^2\).

Layer 2: Softmax Layer

After the previous step, we then need to find the datapoint with the closest distance to the test datapoint. This can be performed in two steps using the softmax layer:

• Negate the vector, so the datapoint with minimum distance, then have the maximum value.
• Multiply the vector by a large positive constant \(\lambda \rightarrow \infty\). This has the effect of shrinking small values and increases already large values. The intention is to have the neuron turned on for only the minimum value of the input \(Z_1\). This is equivalent to applying the softmax temperature on the vector. \(\lambda\) is a hyperparameter.

\[Z_2 = \operatorname{softmax}(-\lambda Z_1)\]

For a refresher on the softmax temperature, check my previous post on Softmax temperature

Layer 3: Prediction Layer

Before now, we have not really talked about the labels of the training examples. It comes in at this layer to support in prediction.

• For a regression task, this computation is almost done. We take the target of the training point with the largest value in \(Z_2\) (the minimum distance, as we have negated the distances). With the vector of training targets \(y \in \mathbb{R}^n\), this is \(Z_3 = y^T Z_2\).
• For a classification task, we can also take the label of the datapoint with the minimum distance or go a step further.

For a classification task, where \(Z_3 = W_3x_3 + b\), firstly, we perform one-hot encoding on the train labels, \(y_{\text{onehot}} \in \mathbb{R}^{n \times c}\), where \(c\) is the number of classes.

\[Z_3 = y_{\text{onehot}}^T Z_2\]

where \(W_3 = y_{\text{onehot}}^T\), \(x_3 = Z_2\) and \(b = 0\). The predicted class is the index of the largest entry of \(Z_3\).

Implementation

I created a Jupyter notebook to show predictions on the iris dataset. You can access the notebook via this link. Feel free to drop comments, and possibly give area for clarification or improvement. Let me try to explain the major parts of the implementation.

• Data: Loaded the iris dataset via the sklearn load dataset api.
• Preprocessing: Normalized the dataset (often a good thing to normalize) and converted each label into one-hot encoded vectors.
• Built a 3 layer neural network using the datapoints as parameters.

Future Work

A 1-Nearest Neighbor implementation was discussed here. This can be extended to k-nearest neighbors. How will you go about it?

Conclusion

In this article, we showed how a k-nearest neighbor classifier can be transformed into a neural network using the datapoints as parameters. This is also a non-parametric model and the weights of the model increase as the number of training points increases. Finally, neural network is a universal function approximator and can therefore be an exercise to represent other models in terms of a basic neural network model.

---