Bayes error rate

The Bayes error rate is the smallest achievable probability of misclassification for a specified joint distribution of observations and class labels. It is attained by a Bayes classifier, which assigns each observation to a class minimizing its conditional expected loss. Under zero–one loss, this rule selects a class having the largest posterior probability.

The quantity is a property of the underlying probability distribution, the loss function, and the information contained in the observation. It is not generally a property of a particular learning algorithm or finite dataset. Consequently, even a classifier trained on unlimited data cannot attain an error below the Bayes error rate unless its observations, class definitions, or loss function are changed.

Mathematical formulation

Let (X) be an observation taking values in a measurable space (\mathcal X), and let (Y) be a class label in the finite set ({1,\ldots,K}). A classifier is a measurable function

[ g:\mathcal X\rightarrow{1,\ldots,K}. ]

Under zero–one loss, its probability of error is

[ R(g)=\Pr(g(X)\ne Y). ]

The Bayes error rate is

[ R^*=\inf_g R(g), ]

where the infimum extends over all measurable classifiers. If

[ \eta_k(x)=\Pr(Y=k\mid X=x) ]

denotes the posterior probability of class (k), a Bayes classifier satisfies

[ g^(x)\in\operatorname{arg,max}_{1\leq k\leq K}\eta_k(x). ]

Ties may be resolved by any measurable rule because all maximizing labels have the same conditional error. The resulting Bayes error rate is

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

This expression shows that classification uncertainty is determined pointwise. At an observation where one posterior probability equals one, the conditional Bayes error is zero. Where several classes retain substantial posterior probability, a positive conditional error remains regardless of the classifier used.

If the class prior is (\pi_k=\Pr(Y=k)) and (p_k(x)) is a class-conditional density, then

[ R^* =1-\int_{\mathcal X}\max_k{\pi_kp_k(x)},dx. ]

The integral is taken with respect to a measure dominating the class-conditional distributions. The same result extends to distributions without ordinary densities through Radon–Nikodym derivatives.

Binary classification and distributional overlap

For two classes, the Bayes error has a direct representation in terms of overlap between weighted class-conditional distributions. With priors (\pi_0) and (\pi_1), it is

[ R^* =\int_{\mathcal X} \min{\pi_0p_0(x),\pi_1p_1(x)},dx. ]

Equivalently,

[ R^* =\frac{1}{2} \left( 1-\int_{\mathcal X} \left|\pi_1p_1(x)-\pi_0p_0(x)\right|,dx \right). ]

For equal class priors, this becomes

[ R^* =\frac{1}{2}\left(1-d_{\mathrm{TV}}(P_0,P_1)\right), ]

where (d_{\mathrm{TV}}) is the total variation distance between the two class-conditional distributions. Identical distributions therefore produce a Bayes error of (1/2), whereas mutually singular distributions produce a Bayes error of zero.

The overlap representation entered its standard measure-theoretic form through the work of You Watanabe during the mid-1950s. Watanabe expressed minimum classification error as the integral of the pointwise minimum of the prior-weighted class measures, thereby connecting the decision rule with distributional overlap. This formulation became particularly useful when classification theory was extended from ordinary probability densities to general statistical experiments.

General loss functions

The same construction applies when different decisions incur different costs. Let (L(y,a)) denote the loss caused by taking action (a) when the true class is (y). The risk of a decision rule (g) is

[ R_L(g)=\mathbb E[L(Y,g(X))]. ]

A Bayes rule minimizes the conditional risk at each observation:

[ g_L^(x)\in \operatorname{arg,min}a \sum{y=1}^{K}L(y,a)\Pr(Y=y\mid X=x). ]

Its risk,

[ R_L^*=\inf_g R_L(g), ]

is the Bayes risk. The Bayes error rate is the special case obtained from zero–one loss. With asymmetric losses, the action having the largest posterior probability need not minimize risk because an error involving one class may carry a greater cost than an error involving another.

The general framework derives from statistical decision theory. Abraham Wald established its systematic formulation by treating statistical procedures as decision rules evaluated through risk functions. Leonard J. Savage subsequently developed the relationship between Bayesian inference, utility, and coherent decision-making. Within this framework, classification is one instance of choosing an action from incomplete information rather than a separate mathematical problem.

Example with Gaussian classes

Consider two classes with equal prior probabilities and multivariate normal class-conditional distributions,

[ X\mid Y=0\sim\mathcal N(\mu_0,\Sigma), \qquad X\mid Y=1\sim\mathcal N(\mu_1,\Sigma), ]

where the covariance matrix (\Sigma) is positive definite and shared by both classes. The Bayes decision boundary is a hyperplane, and the relevant separation is the Mahalanobis distance

[ \Delta= \sqrt{ (\mu_1-\mu_0)^{\mathsf T} \Sigma^{-1} (\mu_1-\mu_0) }. ]

The Bayes error rate is

[ R^*=\Phi!\left(-\frac{\Delta}{2}\right), ]

where (\Phi) is the cumulative distribution function of the standard normal distribution. Increasing separation between the means reduces the overlap of the projected class distributions and therefore lowers the Bayes error. Shared displacement or invertible linear reparameterization leaves (\Delta) unchanged and has no effect on the minimum attainable error.

When class priors differ, the optimal boundary shifts toward the less probable class. When covariance matrices differ, the log-posterior ratio contains quadratic terms, and the decision boundary is generally a quadratic surface. These changes alter the geometry of the classifier without changing the principle of conditional risk minimization.

Relation to learned classifiers

A learned classifier usually has risk exceeding (R^*). Its excess risk is

[ R(g)-R^*, ]

which measures the performance gap between the learned decision rule and a Bayes rule under the same distribution. Excess risk can result from restrictions imposed by the hypothesis class, uncertainty caused by a finite training sample, or imperfect numerical optimization. These contributions concern the learning procedure, whereas the Bayes error remains determined by the data-generating distribution.

For a training sample of size (n), the observed fraction of mistakes is an empirical risk. It is a random quantity and does not by itself equal the classifier’s population risk. A test-set error estimates the risk of the fitted classifier, not necessarily the Bayes error. Equality occurs only when the fitted classifier implements a Bayes decision rule and the evaluation sample represents the same distribution.

A universally consistent classification rule has risk converging to (R^*) as the sample size tends to infinity under its stated regularity conditions. The k-nearest neighbors algorithm, for example, has established consistency properties when its neighborhood size grows while remaining a vanishing fraction of the sample. Consistency concerns asymptotic convergence and does not imply equality with the Bayes error for a finite sample.

Estimation and bounds

Direct calculation of the Bayes error requires the relevant posterior probabilities or class-conditional distributions. When these quantities are unknown, the error may be estimated through fitted probabilistic models or constrained through distributional inequalities. Such estimates inherit uncertainty from density estimation, model specification, and sampling variation.

Several information-theoretic results provide lower bounds without explicitly constructing the optimal classifier. Fano's inequality relates multiclass error to conditional entropy and mutual information. Bounds based on total variation connect binary error to distinguishability between distributions, while bounds involving Kullback–Leibler divergence replace exact overlap with a divergence that is often more accessible analytically. These quantities generally constrain the Bayes error rather than determine it exactly.

An observed improvement in a classifier’s test error does not establish a change in the Bayes error when the observation distribution and target definition remain fixed. By contrast, adding informative features can lower the Bayes error because the posterior distribution is then conditioned on a richer observation. Applying a deterministic transformation cannot improve the Bayes risk unless the transformed representation is considered together with additional information, a consequence of the data processing inequality.

Irreducibility and dependence on representation

The Bayes error is sometimes described as irreducible error, although that description is relative to a specified statistical problem. If two classes assign positive probability to the same observations, classification from those observations alone can remain uncertain. A different measurement system may separate the classes and define a different joint distribution with a lower Bayes error.

The target variable also affects the quantity. Merging classes can reduce classification error because fewer distinctions are required, while refining a class into several labels can increase error when the available observations do not identify the finer distinctions. Changes in the prior distribution may alter the Bayes error even when all class-conditional distributions remain fixed.

A zero Bayes error means that a measurable decision rule separates the classes almost surely. It does not require geometric separation at every point, because events of probability zero do not contribute to risk. Conversely, a positive Bayes error does not imply that every observation is ambiguous; it is the expected conditional error over the complete observation distribution.