Zero-One Loss

machine-learning

Definition

Zero-One Loss

The Zero-One Loss is a loss function used in classification tasks to measure prediction error. It is the most direct metric for misclassification, assigning a penalty of 1 for an incorrect prediction and 0 for a correct one.

Let $h(x)$ be the model’s predicted label for an input $x$, and let $y$ be the true label. The zero-one loss, denoted $L_{0-1}$, is defined as:

$L_{0-1}(h(x),y)=\{\begin{array}{ll}1& \text{if }h(x)\ne y\\ 0& \text{if }h(x)=y\end{array}$

This can be written more compactly using an indicator function $\mathbb{I}(\cdot )$:

$L_{0-1}(h(x),y)=\mathbb{I}(h(x)\ne y)$

Probabilistic View

Indicator Expectation (Misclassification Probability): Under 0-1 loss, the loss random variable equals an indicator of the error event. For $(X,Y)\sim P$,

$$L_{0-1}(h(X),Y)=1\{h(X)\ne Y\},$$

so its expectation is the probability of misclassification:

$${\mathbb{E}}_{(X,Y)\sim P}[L_{0-1}(h(X),Y)]=\mathbb{E}[1\{h(X)\ne Y\}]=\underset{(X,Y)\sim P}{\mathrm{Pr}}(h(X)\ne Y).$$

Risk Identity (True vs Empirical): This yields a direct interpretation of both true risk and empirical risk. The true risk is

$$R_P(h)=\underset{(X,Y)\sim P}{\mathrm{Pr}}(h(X)\ne Y),$$

while for a sample $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\},$$

which is exactly the observed misclassification rate.

Complement Event (Accuracy Form): Since correctness and error are complementary events,

$$\mathrm{Pr}(h(X)=Y)=1-\mathrm{Pr}(h(X)\ne Y)=1-R_P(h).$$

This identity is the key probabilistic step used in finite-class realisable PAC proofs, where one bounds the probability that a bad hypothesis is consistent on all sampled examples.

Properties and Role

• Direct Interpretation: The empirical risk calculated with zero-one loss is exactly the model’s error rate or misclassification rate on the dataset.
• Optimisation Challenge: The function is none-convex and non-differentiable. This makes it computationally intractable (NP-hard) to minimise directly with standard gradient-based optimisation algorithms.
• Practical Use: While minimising zero-one loss is the ultimate theoretical goal of classification, in practice, algorithms optimise a continuous and convex surrogate loss function (like Hinge loss or Cross-Entropy) instead. The zero-one loss is then used as a final evaluation metric to report the model’s performance.