In a discussion, a friend mentioned that the function below cannot be optimized so it can't be used in a learning algorithm.

$$E_{in} = \frac{1}{N} \sum_{n=0}^N (h(x_n) \ne f(x_n))$$

Why can't this function be used as a loss function?

The Context

This is about machine learning and minimizing the error on a dataset $D$ of size $N$. I'm talking about comparing the algorithm predictions against the actual outcome recorded from the real world. Comparing a prediction against its real value using a cost function.

$f$ is the "true" mapping and $h$ is my "model".

$h$ should approximate $f$.

Would someone, please, explain why it isn't differentiable as well?

  • 4
    $\begingroup$ What are you optimising here? (Also probably you have a parenthesis missing...) $\endgroup$ – usεr11852 Mar 31 '17 at 23:23
  • 1
    $\begingroup$ How are we to understand $(h(x_n) \ne f(x_n))$? It is not clear what is the functional form here. $\endgroup$ – Alecos Papadopoulos Apr 1 '17 at 0:13
  • 2
    $\begingroup$ If what you're trying to say is that one of $h$ and $f$ is the "true" mapping and the other is your "model", and you are counting the proportion of exactly correctly modeled points, then yes you can "optimize" it. If there are no model constraints, any interpolant of the data will give you exactly 0 error (there are infinitely many). It's unlikely that a model chosen in this way will generalize well at all, however. $\endgroup$ – Chris Haug Apr 1 '17 at 1:52
  • 1
    $\begingroup$ Do you mean to have an indicator function or something inside the sum (so that you "count the misses")? It can be used as a loss function ,and it can be optimized ... but it doesn't have a derivative; it would require combinatorial-optimization methods (which are typically not practical for large problems) $\endgroup$ – Glen_b Apr 1 '17 at 4:11

The loss function in the original post seems like a 0-1 loss divided by $N$, which is in fact the ultimate goal of most of classification settings. Actually, 0-1 loss divided by $N$ is equivalent to the accuracy metric.

What your friend said is that it is difficult to use 0-1 loss directly for training a model. This is true for many reasons, but mostly because the loss is not differentiable. Many other loss functions used in classification, for example the likelihood of data, can be viewed as approximations of 0-1 loss.

However, since the 0-1 loss is so intuitive and straightforward, the loss function is often measured during the training and assessing models. For me, I would love to print out both likelihood and 0-1 loss.

  • $\begingroup$ It's not the differentiability that's the problem, but the lack of continuity. Non-differentiable loss functions are routinely used in machine learning, for instance, the hinge loss. $\endgroup$ – AaronDefazio Apr 1 '17 at 6:32
  • $\begingroup$ The hinge function is differentiable. $\endgroup$ – thc Apr 1 '17 at 6:57
  • $\begingroup$ You mentioned 0-1 can't be used then later on you mentioned it is just accuracy. Accuracy metrics is common. ???? I don't understand, $\endgroup$ – SmallChess Apr 1 '17 at 7:10
  • $\begingroup$ @AaronDefazio Thank you for pointing out. Yes, it is the lack of continuity that hinders the direct application of 0-1 loss, and I just put that in "many reasons" in my post. $\endgroup$ – Sangwoong Yoon Apr 1 '17 at 7:47
  • 1
    $\begingroup$ @thc however the hinge function does have a non-differentiable point (that's where the "hinge" is), doesnt it? $\endgroup$ – Sangwoong Yoon Apr 1 '17 at 7:47

A loss function must be differentiable to perform gradient descent. It seems like you're trying to measure some sort of 1-accuracy (e.g., the proportion of incorrectly labeled samples). This doesn't have a derivative, so you can't use it. Instead, use cross entropy.

  • 5
    $\begingroup$ Gradient decent is only one of the optimization algorithms, there is a huge number of them beyond GD. So it really doesn't matter if something works or not with GD unless this question asked about GD. $\endgroup$ – Tim Apr 1 '17 at 5:23

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.