Zero-One Loss

machine-learning classification learning-theory

Definition

Zero-One Loss

Zero-one loss is the loss function for classification that charges one unit for a wrong label and zero units for a correct label.

For a classifier $h:\mathcal{X}\to \mathcal{Y}$, an input $x\in \mathcal{X}$, and a true label $y\in \mathcal{Y}$, it is defined by

$${\ell }_{0/1}(h(x),y)=\{\begin{array}{ll}0& \text{if }h(x)=y,\\ 1& \text{if }h(x)\ne y.\end{array}$$

Equivalently, using an indicator function,

$${\ell }_{0/1}(h(x),y)=1\{h(x)\ne y\}.$$

Zero-one loss records only whether the prediction is correct. It does not care how confident the classifier was, how close the decision was, or which wrong label was chosen.

Risk

For a data-generating distribution $P$ over pairs $(X,Y)$, the true risk under zero-one loss is the probability of misclassification:

$$R_P(h)={\mathbb{E}}_{(X,Y)\sim P}[{\ell }_{0/1}(h(X),Y)]=P(h(X)\ne Y).$$

For a training dataset $S=\{(x_i,y_i){\}}_{i=1}^m$, the empirical risk is

$$R_S(h)=\frac{1}{m}\sum _{i=1}^{m}1\{h(x_i)\ne y_i\}.$$

This is exactly the observed misclassification rate on the sample. Its complement is accuracy:

$$\mathrm{Accuracy}(h)=1-R_S(h).$$

Optimisation Difficulty

Zero-one loss is the evaluation target one often cares about, but it is hard to optimise directly. As a function of model parameters, it is usually flat over large regions and jumps only when a point crosses a decision boundary.

This makes it non-differentiable and poorly suited for gradient-based optimisation. Small parameter changes often give no training signal at all. This is why practical classifiers usually optimise a smooth surrogate loss, such as cross-entropy loss or hinge loss, and then report zero-one loss or accuracy as an evaluation metric.

The key mismatch is:

$$\text{training objective}\ne \text{classification error}.$$

A surrogate may be easier to optimise, but minimising it need not minimise zero-one loss exactly.