# Does KNN have a loss function?

I didn't find a definition of loss function on wiki in the context of machine learning.

this one is less formal though, it is clear enough.

At its core, a loss function is incredibly simple: it’s a method of evaluating how well your algorithm models your dataset. If your predictions are totally off, your loss function will output a higher number. If they’re pretty good, it’ll output a lower number. As you change pieces of your algorithm to try and improve your model, your loss function will tell you if you’re getting anywhere.

it seems that the error rate of KNN is not the function that could guide the model itself optimize, such as Gradient Descent.

so, Does KNN have a loss function?

$$k$$-NN does not have a loss function that can be minimized during training. In fact, this algorithm is not trained at all. The only "training" that happens for $$k$$-NN, is memorising the data (creating a local copy), so that during prediction you can do a search and majority vote. Technically, no function is fitted to the data, and so, no optimization is done (it cannot be trained using gradient descent).

• kNN doesn't use a loss function during "training", but that doesn't mean there isn't a loss function that defines kNN. For example: It is well known that the median minimizes the mean absolute difference loss. But you don't ever calculate the mean abs loss, and you don't use optimization like gradient descent to calculate the median either. It's still a useful fact that it minimizes mean abs loss sometimes. In the same way, you could probably construct a loss function that kNN always minimizes – nikie Aug 4 '19 at 4:10
• @nikie that's true, but in kNN uses them just as local aggregation functions among the neighbors (hard to translate to overall loss to minimize). Also for k=1 you don't use any such function. Moreover it is not used for training. Calling it a loss function is merely a mental exercise to force kNN to fit some definition of classifier, I don't find compelling reasons for defining it that way. – Tim Aug 4 '19 at 6:00
• @nikie - I added the loss function in a new answer. Tim - the advantage of writing it this way is that it's easier to see how one can make the objective "softer" by switching from a top hat kernel (counting the number of points - the usual kNN) to a Gaussian kernel (weighting points by proximity). – Miles May 30 at 5:35
• @Miles it’s true, but it is not useful anyhow besides theoretical, academic, discussion. In practical terms, the algorithm is not trained using loss function and it wouldn’t be practical to do so. I’d say that talking about loss function for kNN is more confusing then helpful in most cases. – Tim May 30 at 7:10
• I thought the question seemed theoretical in nature, but you are right that there isn't any practical use in knowing the loss. Maybe OP was looking for something like neighborhood component analysis? I linked it in the answer. – Miles May 30 at 7:24

As an alternative to the accepted answer:

Every stats algorithm is explicitly or implicitly minimizing some objective, even if there are no parameters or hyperparameters, and even if the minimization is not done iteratively. The kNN is so simple that one does not typically think of it like this, but you can actually write down an explicit objective function:

$$\hat{t} = \text{argmax}_\mathcal{C} \sum_{i: x_i \in N_k(\{x\}, \hat{x})} \delta(t_i, \mathcal{C})$$

What this says it that the predicted class $$\hat{t}$$ for a point $$\hat{x}$$ is equal to the class $$\mathcal{C}$$ which maximizes the number of other points $$x_i$$ that are in the set of $$k$$ nearby points $$N_k(\{x\}, \hat{x})$$ that also have the same class, measured by $$\delta(t_i, \mathcal{C})$$ which is $$1$$ when $$x_i$$ is in class $$\mathcal{C}$$, $$0$$ otherwise.

The advantage of writing it this way is that one can see how to make the objective "softer" by weighting points by proximity. Regarding "training," there are no parameters here to fit. But one could tune the distance metric (which is used to define $$N_k$$) or the weighting of points in this sum to optimize some additional classification objective. This leads into Neighborhood Component Analysis: https://www.cs.toronto.edu/~hinton/absps/nca.pdf which learns a distance metric.

• You've written the decision rule for a KNN classifier as an optimization problem. This is a valid point, but seems somewhat different in spirit than what the question is asking. Typically, we define a hypothesis space of possible classifiers, and the loss function is defined on this space. I.e. it maps each possible classifier to a value measuring how good/bad it is. Learning then consists of selecting the classifier with minimal loss. Your objective function isn't defined on the space of classifiers, but on the space of class labels for a given input point. – user20160 Jun 1 at 18:44
• I agree–for real problems, one wants to use a classification objective. But this is the loss that gives us a kNN, just as, say, mean absolute error as a loss gives us the median. It's ambiguous what the original poster was actually looking for; this answer is my interpretation (but could be wrong). – Miles Jun 2 at 3:36

I disagree with the accepted answer (somewhat).

KNN is a classification algorithm, and it makes no sense to run a classification algorithm without a loss function: you'd be interested in how well the algorithm did. In the case of KNN, you could, for example, evaluate the quality of classifications by looking at the sum of average accuracies in each class. Or, you could focus solely on the precision of the algorithm.

The optimization method that powers KNN doesn't depend on the loss function, so during training, it never appeals to the loss function, and doesn't even use gradient-descent to train.

Contrast this with the following "K-nearest neighbor classifier": for $$K$$ classes, first train $$K$$-means, and then define the class of each point by the dominant number of points belonging to each centroid. You could for example train this algorithm with a step-wise minimization on the least-square error from each centroid (re-calculating centroids based on nearest neighbors), but at test time, your loss function would again be some form of accuracy on each class, despite the original algorithm having no dependence on this.

• A metric to assess performance of the algorithm and the loss to minimize are two different things. In fact, you can minimize loss that differs from the metric that you are after (e.g. for computational reasons). – Tim Aug 3 '19 at 7:46
• @Tim: I think we are on the same page as that’s exactly the point I’m trying to make in the last paragraph, where a metric is used to train. But, you still would like a loss function after training to evaluate the algorithm. A classification algorithm trained without appealing to some kind of loss function (during or after) on classes is by definition unsupervised. – Alex R. Aug 3 '19 at 20:07