8
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ What are you optimising here? (Also probably you have a parenthesis missing...) $\endgroup$
    – usεr11852
    Mar 31, 2017 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$ Apr 1, 2017 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, 2017 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, 2017 at 4:11

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
8
  • $\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$ Apr 1, 2017 at 6:32
  • $\begingroup$ The hinge function is differentiable. $\endgroup$
    – thc
    Apr 1, 2017 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, 2017 at 7:10
  • 1
    $\begingroup$ @thc however the hinge function does have a non-differentiable point (that's where the "hinge" is), doesnt it? $\endgroup$ Apr 1, 2017 at 7:47
  • 1
    $\begingroup$ @AaronDefazio, it IS differentiable as defined in TensorFlow and probably other ML platforms. Check the source code: double PrimalLossDerivative(... if (label * wx < 1) { return -label * example_weight; } return 0; }}. At any rate, I find the distinction pedantic and not really insightful. $\endgroup$
    – thc
    Apr 1, 2017 at 9:25
3
$\begingroup$

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.

$\endgroup$
1
  • 7
    $\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, 2017 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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