16
$\begingroup$

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?

$\endgroup$
17
$\begingroup$

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

$\endgroup$
  • 5
    $\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 '19 at 4:10
  • 1
    $\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 '19 at 6:00
  • $\begingroup$ @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). $\endgroup$ – Miles May 30 '20 at 5:35
  • $\begingroup$ @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. $\endgroup$ – Tim May 30 '20 at 7:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Miles May 30 '20 at 7:24
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user20160 Jun 1 '20 at 18:44
  • $\begingroup$ 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). $\endgroup$ – Miles Jun 2 '20 at 3:36
  • $\begingroup$ I found your answer very helpful I would really appreciate if you could help me answer this question too: Relevant question to the subject : stats.stackexchange.com/questions/501229/… $\endgroup$ – partizanos Dec 17 '20 at 5:05

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.