1
$\begingroup$

Why does logistic regression with a logarithmic cost function converge to the optimum for the classification problem (i.e. minimum number of mislabeled training samples)?

Put differently, why is the optimum for the probabilities $h_\Theta(x) = P(y = 1|x;\Theta)$ equivalent to the optimum for the classification problem?

My line of thought

For the terminology and formulas, see Andrew Ng coursera course on machine learning (relevant slides: https://github.com/vkosuri/CourseraMachineLearning/blob/master/home/week-3/lectures/pdf/Lecture6.pdf).

If we use the convex cost function $J(\Theta) = -1/m * \Sigma_{i=1}^m ( y^{(i)} log h_\Theta(x^{(i)}) + (1 - y^{(i)}) log (1 - h_\Theta(x^{(i)})) )$, we exponentially penalize higher differences between $h_\Theta(x)$ and $y$. Thus this logistic regression optimizes the parameters $\Theta$ for the probabilities $h_\Theta(x) = P(y = 1|x;\Theta)$.

But for the (in this example binary) classification problem, we use a threshold of $P=0.5$ to decide whether a sample is classified as positive or negative. So the classification problem does not care whether $P=0.4$ or $P=0$, however the cost function makes an exponential distinction. Thus I do not understand why logistic regression with a logarithmic cost function also converges to the optimum for the classification problem.

For example, $\Theta$ that yields many samples with $h_\Theta(x)=0.4$ and $y=1$, has lower cost (due to the exponential distinction) compared to $\Theta'$ that yields $(0.6,1)$ for most of those samples and $(0.1,1)$ for only few of those samples. So $J(\Theta')$ is higher, but $\Theta'$ classifies much better in terms of amount of false predictions over the training set.

Given one bad optimization step, logistic regression should not be able to converge to the optimal classification!?

Improve this question
$\endgroup$
5
  • $\begingroup$ When you say "the optimum," it's not clear what you mean. It seems to have something to do with choosing a cutoff for predicted probabilities, but it's not clear how they're related. For example, when logistic regression is strongly convex, we know that the trained regression weights are optimal in the sense that they have a lower loss (lower $J(\Theta)$) than any other choice weights. In what sense are you suggesting that a logistic regression that uses probability cutoffs at 0.5 is optimal? What expression is maximized or minimized? $\endgroup$
    – Sycorax ♦
    Nov 9, 2019 at 14:59
  • 2
    $\begingroup$ I think your question might be answered by stats.stackexchange.com/questions/312780/… and the observation that logistic regression is not particularly concerned about accuracy. $\endgroup$
    – Sycorax ♦
    Nov 9, 2019 at 15:05
  • $\begingroup$ @ReinstateMonica: By cutoff you mean threshold to decide when to label positive vs. when to label negative? I think your comment is exactly what I am struggling with: how is optimizing for the probabilities identical with optimizing for the classification, i.e. number of false predictions on the training set. This is not stated explicitly in Andrew Ng's cited course, but implicitly. $\endgroup$
    – DaveFar
    Nov 9, 2019 at 15:08
  • 1
    $\begingroup$ Yeah, cutoff is some $c$ s.t. you say "this observation is a positive" whenever $h_\Theta(x) > c$. But note that logistic regression doesn't actually coincide with optimizing accuracy for the exact reasons that you outline. Depending on the data, you might end up with all predictions, for positive and negative samples alike, well above 0.5, for instance. See: stats.stackexchange.com/questions/168929/… for some discussion. $\endgroup$
    – Sycorax ♦
    Nov 9, 2019 at 15:37
  • $\begingroup$ @ReinstateMonica: very helpful comments, thanks a lot. would you like to turn them into an answer? I think my question is not a duplicate of the links you mentioned, so I would rather accept your answer than delete my question. $\endgroup$
    – DaveFar
    Nov 9, 2019 at 19:30

1 Answer 1

Reset to default
3
$\begingroup$

Thus I do not understand why logistic regression with a logarithmic cost function also converges to the optimum for the classification problem.

Logistic regression isn't concerned with optimizing accuracy, but it's definitely optimizing the cross-entropy loss.

Another way to think about it is that accuracy is discarding all the fine-grained detail in the predicted probabilities. Accuracy treats $0.5+10^{-10}$ and $1.0-10^{-10}$ as exactly the same, because both are larger than 0.5, even though the latter describes the probability of the event with much more confidence than the former. By contrast, the cross-entropy loss $J$ will penalize predictions which are far from the label, and the size of the penalty increases the "more incorrect" that prediction is.

Because of this property, it's possible to have situations where a logistic regression will produce predicted probabilities that are all greater than 0.5 (or if we reverse the coding of the outcomes, all predicted probabilities are less than 0.5). This commonly arises when one class is much more prevalent than the other, and the features are, at best, weak predictors of the outcome. This clearly flies in the face of an expectation that the positive and negative examples should be on opposite sides of the 0.5 cutoff.

See the discussion at Logistic regression is predicting all 1, and no 0 for more detail.

See also: Why is accuracy not the best measure for assessing classification models?

Improve this answer
$\endgroup$

Your Answer

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

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