# Does zero-one loss correspond to any maximum likelihood procedure? [duplicate]

Squared loss for linear regression corresponds to a MLE of a Gaussian model, and cross entropy loss corresponds to MLE of a logistic model with discrete probabilities.

Can zero-one loss be justified by MLE of any probability model? Why or why not?

That's the main question. This question also has to do with intuition for zero-one loss, but doesn't have anything to do with MLE. but also I'd like to state some things I believe are true about zero-one loss, and please correct me if I'm wrong:

• MAP is Bayes optimal for zero-one loss
• Logistic regression models probabilities directly, and classifies to the largest, but its parameters are optimized based on maximum likelihood (leading to cross-entropy) rather than optimizing zero-one loss directly
• The performance of logistic regression could be improved by using zero-one loss, or you could ditch logistic regression entirely and use frequency tables to approximate $$P(\text{class} | X)$$, though both of these options are entirely intractable

## marked as duplicate by Ben, kjetil b halvorsen, Michael Chernick, Siong Thye Goh, SycoraxMay 3 at 21:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Can you explain why you would think logistic regression could be improved using zero-one loss? – Cliff AB Apr 24 at 23:03
• I believe the performance of logistic regression as a classifier would improve if we optimize by zero-one loss, since its performance as a classifier is measured using zero-one loss. – Drew N Apr 25 at 4:23
• Zero-one loss is usually too hard to optimize, which is why surrogate losses are always used for training. – Frans Rodenburg Apr 29 at 13:54

## 2 Answers

Minimizing the zero-one loss $$L(\theta, \widehat{\theta}) = 1 - \mathbf{1}_{\{\theta\}}(\widehat{\theta}) = \begin{cases} 0 & \text{if \theta = \widehat{\theta}} \\ 1 & \text{otherwise} \end{cases}$$ is the same as maximum likelihood estimation with a family of Dirac distributions: discrete distributions with probability mass function $$p(x \mid \theta) = \mathbf{1}_{\{\theta\}}(x) = \begin{cases} 1 & \text{if x = \theta} \\ 0 & \text{otherwise.} \end{cases}$$ Here $$\mathbf{1}_A$$ denotes the indicator function of a set $$A$$.

Regarding your beliefs about zero-one loss:

MAP is Bayes optimal for zero-one loss

Consider a parametric family of distributions $$\{P_\theta : \theta \in \Omega\}$$ and a prior $$\pi$$. The risk of any estimator $$\widehat{\theta}$$ of $$\theta$$ is \begin{aligned} R(\theta, \widehat{\theta}) &= E_\theta[L(\theta, \widehat{\theta})] \\ &= E_\theta[1 - \mathbf{1}_{\{\theta\}}(\widehat{\theta})] \\ &= P_\theta(\widehat{\theta} \neq \theta), \end{aligned} and so the Bayes risk is \begin{aligned} R_\pi(\widehat{\theta}) &= \int_\Omega R(\theta, \widehat{\theta}) \, d\pi(\theta) \\ &= \int_\Omega P_\theta(\widehat{\theta} \neq \theta) \, d\pi(\theta). \end{aligned} A priori it is not clear to me why a MAP estimator $$\widehat{\theta}$$ would minimize this Bayes risk in this general setup.

Logistic regression models probabilities directly, and classifies to the largest, but its parameters are optimized based on maximum likelihood (leading to cross-entropy) rather than optimizing zero-one loss directly

This is correct.

The performance of logistic regression could be improved by using zero-one loss, or you could ditch logistic regression entirely and use frequency tables to approximate P(class|X), though both of these options are entirely intractable

Zero-one loss is not differentiable and not convex, so the tradiitonal optimization methods used to train models like logistic regression don't apply to it. The problem with frequency tables is that as soon as you have a point X that isn't in the training data, you can't make any inference about P(class|X) as you would like.

• That's a good point about frequency tables, and it also applies to Naive Bayes. What they do to avoid zero probabilities there is add a pseudocount to both the numerator and denominator, called "additive smoothing". – Drew N Apr 25 at 22:02
• I looked over some of my reading and I can answer why MAP yields the Bayes decision rule in a prediction problem. Your answer is phrased for estimation problems; I didn't realize at the time my question could be interpreted both ways. I'll post my own answer tying those together later. – Drew N Apr 25 at 22:07

In general surrogate losses used in place of 0-1 loss are chosen to be Fisher consistent. There are established results regarding this matter:

http://statistics.berkeley.edu/sites/default/files/tech-reports/638.pdf

This means that optimization using the surrogate loss will yield the model that will also minimize the expected 0-1 loss. From this perspective we are safe.

On the other hand there is the topic of efficiency. In order for estimation using 0-1 loss to be more efficient compared to its surrogate loss the underlying probability distribution needs to match. As it is shown in the other answer this case belongs to deterministic function learning (no uncertainty around the point) . For this reason I don't see any benefit in terms of statistical efficiency as achieving 0 error on training is also possible for example with squared loss with the same amount of training data.