Zero-One Loss and the Bayes Classifier

From Class Probabilities to Classification Decisions

A classifier must turn information about an observation into a label. When the only penalty is whether that label is wrong, the decision rule has a particularly direct form: choose a class that has the greatest conditional probability given the observed features. The reason is precise: under zero-one loss, the conditional risk of choosing a class is one minus that class’s posterior probability.

This rule is sometimes called the Bayes classifier. It is a population-level benchmark: it uses the true conditional class probabilities, not estimates learned from a finite training sample. The derivation below identifies both its conditional risk at a feature value and its average risk over the feature distribution.

Definition: Let $Y$ be a class label taking values in the finite set $\{1,\ldots,K\}$, and let $X$ be the observed feature vector. A classifier is a measurable rule $g$ that assigns a class $g(X)$ to each observation. Under zero-one loss, the loss for predicting class $a$ when the true class is $y$ is $$ L(y,a)=\mathbf{1}\{y\ne a\}. $$ The posterior class probability for class $k$ is $\eta_k(x)=P(Y=k\mid X=x)$, using a measurable version of the conditional probability.

Assume the feature space is standard Borel, so the conditional class probabilities can be represented by measurable functions of $x$. For each $x$, the values $\eta_1(x),\ldots,\eta_K(x)$ are nonnegative and sum to one. The conditional risk of choosing class $a$ is the expected loss after observing $X=x$:

R(a\mid x)=E[L(Y,a)\mid X=x].

The risk depends on the chance that class $a$ is incorrect. Since the loss is exactly one for an incorrect prediction and zero for a correct one, this chance is $1-\eta_a(x)$.

Deriving the Bayes Classifier

Theorem: Under zero-one loss with $K$ possible classes, the conditional risk of predicting class $a$ is $$ R(a\mid x)=1-\eta_a(x). $$ Consequently, any measurable classifier that chooses a class with greatest posterior probability minimizes conditional risk at each $x$. Its minimum conditional risk is $1-\max_{1\le k\le K}\eta_k(x)$.

Proof. Conditional on $X=x$, the loss is one precisely on the event $Y\ne a$. Therefore

R(a\mid x) =E[\mathbf{1}\{Y\ne a\}\mid X=x] =P(Y\ne a\mid X=x) =1-P(Y=a\mid X=x) =1-\eta_a(x).

The quantity $1-\eta_a(x)$ decreases as $\eta_a(x)$ increases. Thus a class that maximizes $\eta_a(x)$ also minimizes $R(a\mid x)$, and the minimum value is $1-\max_k\eta_k(x)$.

A measurable choice can be made without extra assumptions about how the maximum varies with $x$. For example, choose the smallest index attaining the maximum. Each $\eta_k$ is measurable, as is $m(x)=\max_k\eta_k(x)$. The set on which this rule chooses $k$ is

\{x:\eta_k(x)=m(x)\}\cap \bigcap_{j<k}\{x:\eta_j(x)<m(x)\},

which is measurable. Thus the pointwise minimizing choice is a valid classifier. This proves the result. $\square$

Worked Example: A Binary Classification Decision

At a particular feature value $x$, suppose the two possible labels are 0 and 1, with $P(Y=1\mid X=x)=0.73$. Find the conditional risk of each prediction and select the Bayes class.

The two posterior probabilities are $\eta_1(x)=0.73$ and $\eta_0(x)=1-0.73=0.27$. If we predict 1, the prediction is wrong when $Y=0$, so

R(1\mid x)=1-0.73=0.27.

If we predict 0, the prediction is wrong when $Y=1$, giving

R(0\mid x)=1-0.27=0.73.

Because $0.73>0.27$, the Bayes classifier predicts class 1. Its conditional error probability is $0.27$, not $0.73$: the larger number is the probability of the class it predicts, while the conditional risk is the probability that prediction is wrong.

For two classes, the rule can be expressed as a threshold on one posterior probability. Write $\eta(x)=P(Y=1\mid X=x)$, so $P(Y=0\mid X=x)=1-\eta(x)$. The risks of predicting 1 and 0 are $1-\eta(x)$ and $\eta(x)$, respectively. Prediction 1 minimizes risk when $1-\eta(x)\le\eta(x)$, equivalently when $\eta(x)\ge 1/2$. The value $1/2$ follows from equal costs for the two types of error; it is not a universal threshold for other loss functions.

Worked Example: The Binary Threshold in Both Directions

Suppose $Y\in\{0,1\}$. At $x_A$, let $P(Y=1\mid X=x_A)=0.42$; at $x_B$, let $P(Y=1\mid X=x_B)=0.81$. Apply the zero-one Bayes rule and calculate the conditional risks.

At $x_A$, the posterior for class 0 is $1-0.42=0.58$. Predicting 0 has risk $1-0.58=0.42$, while predicting 1 has risk $1-0.42=0.58$. The Bayes prediction is 0, with conditional risk $0.42$.

At $x_B$, the posterior for class 0 is $1-0.81=0.19$. Predicting 1 has risk $1-0.81=0.19$, while predicting 0 has risk $1-0.19=0.81$. The Bayes prediction is 1, with conditional risk $0.19$.

In each case, the conditional risk is the posterior probability of the other class. The rule predicts 1 when its posterior exceeds one half and 0 when it falls below one half.

Conditional Risk and Bayes Risk

The pointwise result also determines the best achievable average error. For a classifier $g$, define its population risk by $R(g)=E[L(Y,g(X))]$. The Bayes risk is the smallest population risk among measurable classifiers. The next result connects these quantities.

Result: For any measurable classifier $g$, $$ R(g)=E[1-\eta_{g(X)}(X)]. $$ A Bayes classifier $g^*$ that maximizes the posterior class probability has Bayes risk $$ R^*=E[1-\max_{1\le k\le K}\eta_k(X)]. $$

Derivation. Because the label set is finite, the loss can be written as a finite sum over the possible predicted classes:

L(Y,g(X)) =\sum_{k=1}^K \mathbf{1}\{g(X)=k\}\mathbf{1}\{Y\ne k\}.

Each indicator $\mathbf{1}\{g(X)=k\}$ is determined by $X$, so it can be taken outside the conditional expectation given $X$. Applying the conditional-risk calculation gives

E[L(Y,g(X))\mid X] =\sum_{k=1}^K \mathbf{1}\{g(X)=k\}(1-\eta_k(X)) =1-\eta_{g(X)}(X).

Taking expectations and using the law of total expectation yields $R(g)=E[1-\eta_{g(X)}(X)]$. For a Bayes classifier $g^*$, its selected posterior probability is $\max_k\eta_k(X)$ at each $X$. Substituting this into the risk expression gives $R^*=E[1-\max_k\eta_k(X)]$. Since every classifier has conditional risk at least $1-\max_k\eta_k(X)$, no classifier can have a smaller population risk. $\square$

Worked Example: Averaging Conditional Errors Across Feature Values

Suppose $X$ takes two values, $u$ and $v$, with $P(X=u)=0.40$ and $P(X=v)=0.60$. There are three classes, and the posterior probabilities are:

Feature value	$P(Y=1\mid X)$	$P(Y=2\mid X)$	$P(Y=3\mid X)$
$u$	0.50	0.30	0.20
$v$	0.10	0.25	0.65

At $u$, the largest posterior is $0.50$, so the Bayes prediction is class 1 and its conditional risk is $1-0.50=0.50$. At $v$, the largest posterior is $0.65$, so the Bayes prediction is class 3 and its conditional risk is $1-0.65=0.35$.

Average these errors using the probabilities of the feature values:

$$ R^*=P(X=u)(0.50)+P(X=v)(0.35) =0.40(0.50)+0.60(0.35) =0.20+0.21 =0.41. $$

Thus the minimum overall misclassification probability is $0.41$. The posterior probabilities sum to one in each row, and the feature probabilities also sum to one, so both parts of the calculation form valid probability distributions.

Computing Posteriors From a Joint Distribution

Posterior probabilities may be supplied directly, or they may need to be calculated from a joint distribution. For a discrete feature $X$, whenever $P(X=x)>0$,

P(Y=k\mid X=x)=\frac{P(Y=k,X=x)}{P(X=x)}, \qquad P(X=x)=\sum_{j=1}^K P(Y=j,X=x).

The denominator is essential: the joint probabilities in one row need not sum to one until they are divided by the probability of that feature value.

Worked Example: Finding the Bayes Risk From Joint Probabilities

Let $X\in\{u,v\}$ and $Y\in\{1,2,3\}$. The joint probabilities are shown below.

	$Y=1$	$Y=2$	$Y=3$	Row total
$X=u$	0.18	0.12	0.06	0.36
$X=v$	0.08	0.16	0.40	0.64

The entries total $0.18+0.12+0.06+0.08+0.16+0.40=1.00$. For $X=u$, the row total is $0.36$, so the posterior probabilities are $0.18/0.36=0.50$, $0.12/0.36=1/3$, and $0.06/0.36=1/6$. The largest is $0.50$, and the conditional Bayes risk is $1-0.50=0.50$.

For $X=v$, divide each entry by $0.64$. The posteriors are $0.08/0.64=0.125$, $0.16/0.64=0.25$, and $0.40/0.64=0.625$. The Bayes prediction is class 3, and its conditional risk is $1-0.625=0.375$.

Weight these conditional risks by $P(X=u)=0.36$ and $P(X=v)=0.64$:

$$ R^*=0.36(0.50)+0.64(0.375) =0.18+0.24 =0.42. $$

As a check, the corresponding Bayes predictions incur joint error probability $0.12+0.06=0.18$ when $X=u$, and $0.08+0.16=0.24$ when $X=v$. Their total is $0.18+0.24=0.42$, agreeing with the conditional-risk calculation.

Common Mistakes and Why the Rule Matters

The Bayes classifier provides a reference point for classification: it is the best possible rule under the assumed class probabilities and zero-one loss. In practice, those probabilities are usually unknown and must be estimated. The rule clarifies what an ideal decision would do with them, while the Bayes risk describes the smallest error rate available even with perfect knowledge of the conditional distribution.

Reporting the selected posterior as the risk. If the selected class has probability $0.8$, its conditional risk is $1-0.8=0.2$, not $0.8$.
Choosing the smallest posterior. Under zero-one loss, a larger posterior probability means a smaller chance of error. The minimizing class is a maximizer of the posterior, not a minimizer.
Using a one-half threshold for every classification problem. The threshold describes the binary case with equal penalties for both error types. With more than two classes, compare all class probabilities; with other losses, the decision rule can change.
Averaging conditional risks without weighting by $X$. The Bayes risk averages over the feature distribution. Feature values that occur more often contribute more to the population risk.

Key takeaway: Under zero-one loss, predicting class $a$ at $x$ has conditional risk $1-\eta_a(x)$. Therefore, choose a class with the largest posterior probability; the resulting Bayes risk is the expected value of one minus the largest posterior probability.

Check Your Understanding

Use the zero-one-loss rule and show the calculations that support your answers.

At a feature value $x$, three class probabilities are $0.15$, $0.55$, and $0.30$. Which class does the Bayes classifier predict, and what is its conditional risk?
In the binary case, let $P(Y=1\mid X=x)=0.36$. Find the conditional risk of predicting each class and identify the Bayes decision.
Why must conditional risks be weighted by the probabilities of feature values when computing the Bayes risk?
For a discrete feature value with joint probabilities $0.10$, $0.20$, and $0.10$ across three classes, calculate the posterior probabilities and the minimum conditional risk.
Explain why a class’s posterior probability and the risk of predicting that class are not the same quantity under zero-one loss.

Feature value	\(P(Y=1\mid X)\)	\(P(Y=2\mid X)\)	\(P(Y=3\mid X)\)
\(u\)	0.50	0.30	0.20
\(v\)	0.10	0.25	0.65