Classification Risk, Bayes Error, and Regret

Risk as a Population Quantity

A classifier assigns a label to a feature vector. Its performance depends not only on the decision rule, but also on the population distribution of features and labels to which the rule is applied. The central quantity in this tutorial is zero-one risk: the probability that the assigned label is wrong for a new observation from that population.

This is a population target, not the fraction of errors on the data used to construct the classifier. It is defined relative to a specified joint distribution and a specified set of available features. Even the best possible classifier can have positive risk when the features do not perfectly determine the label.

Definition: Let \(X\) take values in a measurable feature space and let \(Y\) take values in \(\{1,\ldots,K\}\), where \(K\) is finite. A classifier is a measurable function \(g\) from the feature space to \(\{1,\ldots,K\}\). Under the joint distribution of \((X,Y)\), its zero-one risk is

R(g)=P\{g(X)\ne Y\}=E[\mathbf{1}\{g(X)\ne Y\}].

The loss is one for an incorrect classification and zero for a correct one. In this tutorial, risk refers to this population probability unless another expectation is explicitly specified.

Write \(\eta_k(x)=P(Y=k\mid X=x)\) for a version of the conditional class probability, for \(k=1,\ldots,K\). These conditional probabilities are defined for almost every \(x\) under the distribution of \(X\). They sum to one. For a fixed feature value \(x\), assigning label \(j\) has conditional probability of error \(1-\eta_j(x)\). Thus the decision problem can be understood one feature value at a time.

Bayes Classifiers and Bayes Error

A Bayes classifier is any classifier that chooses a label with the largest conditional probability. When several labels tie, any one of the maximizing labels is a valid choice. Since there are finitely many labels, choosing the smallest maximizing index, for example, gives a measurable rule whenever the conditional probabilities are measurable.

Definition: For zero-one loss, the Bayes classifier \(g^*\) satisfies

g^*(x)\in\arg\max_{1\le k\le K}\eta_k(x).

The risk of any Bayes classifier is the Bayes error,

R^*=R(g^*)=E\!\left[1-\max_{1\le k\le K}\eta_k(X)\right].

The excess risk, or regret, of a classifier \(g\) is \(R(g)-R^*\), the amount by which its population risk exceeds the Bayes error.

Bayes error is the lowest zero-one risk achievable among measurable classifiers that use \(X\). It is not necessarily zero: if multiple labels retain positive conditional probability at the same feature values, no rule based only on those features can always be correct. The benchmark depends on the joint distribution and on what is included in \(X\); adding informative features can change it.

Theorem: Under the conditions above, every Bayes classifier minimizes zero-one risk over all measurable classifiers, and for every such classifier \(g\),

R(g)-R^* = E\!\left[\max_{1\le k\le K}\eta_k(X)-\eta_{g(X)}(X)\right]\ge 0.

Proof. Conditional expectation of the error indicator given \(X\) gives

R(g)=E\!\left[E\{\mathbf{1}(g(X)\ne Y)\mid X\}\right] =E[1-\eta_{g(X)}(X)].

Indeed, once \(X\) is fixed, \(g(X)\) is a fixed label, and the conditional probability that \(Y\) equals that label is \(\eta_{g(X)}(X)\). For a Bayes classifier, this conditional probability is \(\max_k\eta_k(X)\) almost surely, so \(R^*=E[1-\max_k\eta_k(X)]\). Subtracting the two expressions yields the displayed identity. Its integrand is nonnegative because \(\eta_{g(X)}(X)\le\max_k\eta_k(X)\). Therefore \(R(g)\ge R^*\), proving optimality as well. \(\square\)

The identity also clarifies what excess risk measures: at each feature value, it is the loss in conditional correctness probability from choosing a nonmaximizing class rather than a maximizing one, averaged over the feature distribution. Ties contribute no excess when the chosen label is among the maximizers.

Binary Classification

For two labels, take \(Y\in\{0,1\}\) and write \(\eta(x)=P(Y=1\mid X=x)\). The conditional error from predicting 1 is \(1-\eta(x)\); from predicting 0 it is \(\eta(x)\). Comparing these quantities gives a particularly simple Bayes rule.

Result: A binary Bayes classifier predicts 1 when \(\eta(x)>1/2\), predicts 0 when \(\eta(x)<1/2\), and may choose either label when \(\eta(x)=1/2\). Its Bayes error is

R^*=E[\min\{\eta(X),1-\eta(X)\}].

For any binary classifier \(g\), its excess risk is

R(g)-R^* = E\!\left[|2\eta(X)-1|\, \mathbf{1}\{g(X)\text{ disagrees with a Bayes choice at }X\}\right],

where disagreement at a tie, \(\eta(X)=1/2\), contributes zero.

To verify the binary identity, fix \(x\). The smaller conditional error is \(\min\{\eta(x),1-\eta(x)\}\). If \(g(x)\) chooses the other label, its conditional error is the larger of these two quantities. The difference is

|\eta(x)-(1-\eta(x))|=|2\eta(x)-1|.

If \(g(x)\) agrees with a Bayes choice, the difference is zero. Averaging these pointwise differences over \(X\) proves the result. \(\square\)

Worked Example: A Nonoptimal Threshold for Gaussian Classes

Suppose \(P(Y=0)=P(Y=1)=1/2\), with \(X\mid Y=0\sim N(0,1)\) and \(X\mid Y=1\sim N(2,1)\). Consider the rule \(g\) that predicts 1 when \(X>1.5\) and predicts 0 otherwise. Find its risk, the Bayes error, and its excess risk.

Risk of the stated rule. An error occurs either when \(Y=0\) and \(X>1.5\), or when \(Y=1\) and \(X\le1.5\). Let \(\Phi\) be the standard normal distribution function. Standardizing within each class gives

\begin{aligned} R(g) &=\tfrac12 P(X>1.5\mid Y=0)+\tfrac12 P(X\le1.5\mid Y=1)\\ &=\tfrac12[1-\Phi(1.5)]+\tfrac12\Phi(-0.5)\\ &\approx\tfrac12(0.0668072)+\tfrac12(0.3085375)\\ &\approx 0.18767. \end{aligned}

Bayes error. With equal priors and equal variances, the Bayes rule chooses the class with the larger class-conditional density. The log density ratio for class 1 against class 0 is

\log\frac{f_1(x)}{f_0(x)} =-\tfrac12(x-2)^2+\tfrac12x^2=2x-2.

It is positive exactly when \(x>1\), so the Bayes threshold is 1. The class-conditional error probabilities are both \(\Phi(-1)\), giving

R^*=\Phi(-1)\approx0.15865525\approx0.15866.

Therefore the excess risk of the threshold 1.5 rule is approximately \(0.18767237-0.15865525=0.02901712\), or 0.02902 to five decimal places. The nonzero gap reflects the decision rule’s threshold, not a change in the underlying class overlap.

Multiclass Risk in a Discrete Example

The same definitions apply without modification when there are more than two classes. The Bayes decision is the class with the largest posterior probability at the observed feature value, and the conditional Bayes error is one minus that largest probability. A classifier can incur excess risk even if it predicts a plausible class: what matters is whether its choice is as probable as the best available choice, on average over feature values.

Worked Example: Comparing Two Three-Class Rules

Let \(X\) take values \(a,b,c\), with probabilities \(0.5,0.3,0.2\), respectively. Suppose the conditional class-probability vectors \((\eta_1(x),\eta_2(x),\eta_3(x))\) are

Feature value	\(P(X=x)\)	\((\eta_1(x),\eta_2(x),\eta_3(x))\)
\(a\)	0.5	(0.7, 0.2, 0.1)
\(b\)	0.3	(0.1, 0.8, 0.1)
\(c\)	0.2	(0.2, 0.3, 0.5)

The Bayes classifier assigns \(a\) to class 1, \(b\) to class 2, and \(c\) to class 3. Its conditional error probabilities are \(0.3,0.2,0.5\), respectively. Thus

$$ R^*=0.5(0.3)+0.3(0.2)+0.2(0.5)=0.15+0.06+0.10=0.31. $$

Now consider the rule \(g\) that assigns \(a\) to class 2, \(b\) to class 2, and \(c\) to class 1. Its conditional error probabilities are \(0.8,0.2,0.8\), so

$$ R(g)=0.5(0.8)+0.3(0.2)+0.2(0.8)=0.40+0.06+0.16=0.62. $$

The excess risk is \(0.62-0.31=0.31\). Equivalently, the conditional probability gaps at \(a,b,c\) are \(0.7-0.2=0.5\), \(0.8-0.8=0\), and \(0.5-0.2=0.3\). Weighting them by the feature probabilities gives \(0.5(0.5)+0.3(0)+0.2(0.3)=0.31\), as the theorem predicts.

Irreducible Error and Error from Estimation

Bayes error and excess risk describe different sources of error. Bayes error is the minimum attainable under the true joint distribution when only the specified features are available. Excess risk is the additional population error of a particular rule relative to that benchmark. For a rule estimated from training data, the rule itself is random before the data are observed, so its risk can vary across training samples. Conditional on a realized training sample, however, its population risk is defined by evaluating it on a fresh observation from the population.

This distinction is useful because a classifier may perform poorly for either reason, or both: the features may leave substantial uncertainty about the label, or the fitted rule may fail to reach the best decision available from those features. The Bayes error is not an estimate of the error on a particular test set, and the excess risk is not the same as the observed training error.

Worked Example: A Classifier Chosen from One Training Label

Suppose \(X\) is constant, so it contains no information, and \(P(Y=1)=0.2\), \(P(Y=0)=0.8\). The Bayes classifier always predicts 0. Its Bayes error is \(R^*=0.2\). Now take one independent training label \(Y_1\), and define an estimated rule \(g_D\) that always predicts \(Y_1\). Calculate its risk for each possible training outcome and its expected risk over training samples.

If \(Y_1=0\), the fitted rule always predicts 0, so its risk on an independent population observation is \(0.2\), equal to the Bayes error. This training outcome has probability \(0.8\).

If \(Y_1=1\), the fitted rule always predicts 1, so its population risk is \(P(Y=0)=0.8\). This outcome has probability \(0.2\). Therefore the expected risk over the random training label is

$$ E_D[R(g_D)]=0.8(0.2)+0.2(0.8)=0.16+0.16=0.32. $$

Its expected excess risk is \(0.32-0.2=0.12\). The \(0.2\) Bayes error remains even for the best rule because the features reveal nothing about the label. The additional \(0.12\) in expected risk arises because this particular data-dependent procedure sometimes chooses the less common class. This example separates the population benchmark from the variation introduced by estimating a rule.

Common Pitfall: Calling Every Error “Irreducible”

A frequent mistake is to see that a classifier has positive error and conclude that the error is unavoidable because the classes overlap. Overlap may imply positive Bayes error, but it does not make every classifier’s full risk irreducible. The relevant comparison is with \(R^*\): for a specified feature distribution, the gap \(R(g)-R^*\) is the rule’s excess risk. Conversely, a classifier’s low observed error on its training data does not establish that its population risk is near the Bayes error.

These definitions use zero-one loss, which assigns equal cost to every incorrect label. If errors have different costs, the optimal decision need not select the class with the largest posterior probability; that is a different decision problem. For the present setting, keep the reference distribution, available features, and zero-one loss fixed when interpreting Bayes error and regret.

Key takeaway: Zero-one risk is the population probability of misclassification. Bayes error is the minimum such risk available from the specified features, and excess risk is the nonnegative gap between a rule’s risk and that minimum. For an estimated rule, uncertainty in the training sample can make this gap random.

Check Your Understanding

Use the definitions and results above to answer the following.

For a multiclass problem, why is the conditional error from predicting class \(j\) at \(x\) equal to \(1-\eta_j(x)\)?
If the largest conditional class probability at \(x\) is 0.6, what is the Bayes conditional error at \(x\)?
In binary classification, what happens to the excess-risk contribution at feature values where \(\eta(x)=1/2\), regardless of the predicted label?
Explain why a positive Bayes error does not imply that every classifier has zero excess risk.
In the one-training-label example, what is the risk conditional on observing \(Y_1=1\), and why is that not the Bayes error?