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).

  • 4
    $\begingroup$ 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 $\endgroup$ – nikie Aug 4 at 4:10
  • $\begingroup$ @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. $\endgroup$ – Tim Aug 4 at 6:00

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.

  • 4
    $\begingroup$ 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). $\endgroup$ – Tim Aug 3 at 7:46
  • $\begingroup$ @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. $\endgroup$ – Alex R. Aug 3 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.