Even the perfect classifier makes mistakes. This counterintuitive fact lies at the heart of probabilistic classification: when classes overlap in feature space, some errors are unavoidable. No algorithm, no amount of data, no computational power can reduce error below a certain threshold.

This threshold is the Bayes error rate—the error achieved by the Bayes classifier. Understanding this fundamental limit is crucial for setting realistic expectations, diagnosing model performance, and knowing when to seek better features versus better algorithms.

The Bayes error rate (also called Bayes risk or Bayes optimal error) is the expected error of the Bayes classifier:

$$R^* = R(h^) = \mathbb{E}_{(X,Y)}[\mathbb{1}[h^(X) \neq Y]] = P(h^*(X) \neq Y)$$

where $h^*(x) = \arg\max_k P(Y = k | X = x)$ is the Bayes classifier.

Alternatively, using the posterior probabilities:

$$R^* = \mathbb{E}_X\left[1 - \max_k P(Y = k | X = x)\right] = \mathbb{E}_X\left[\min_k P(Y \neq k | X = x)\right]$$

Key Properties of the Bayes Error Rate:

1. It's Irreducible

• No classifier (of any form, trained on any amount of data) can achieve lower error
• It represents the fundamental uncertainty in the data itself

2. It's Non-Negative

• $R^* \geq 0$, with equality iff classes are perfectly separable

3. It's Bounded Above

• For $K$ classes with random guessing: $R^* \leq 1 - \frac{1}{K}$
• For binary classification: $R^* \leq 0.5$

4. It Depends Only on the Data Distribution

• $R^*$ is a property of $P(X, Y)$, not of any algorithm
• Different problems have different Bayes error rates

The Bayes Error Formula (Binary Case):

For binary classification with posterior $\eta(x) = P(Y = 1 | X = x)$:

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

This formula shows that the error at each point is the probability of the minority class. When $\eta(x) = 0.7$, the Bayes classifier predicts class 1, but is wrong 30% of the time for such points. The Bayes error is the average of these pointwise error rates.

The Bayes error has a beautiful geometric interpretation in terms of class distribution overlap.

Class-Conditional Perspective:

Using class-conditional densities and Bayes' theorem:

$$P(Y = k | X = x) = \frac{\pi_k \cdot p_k(x)}{\sum_j \pi_j \cdot p_j(x)}$$

The Bayes error occurs where the "wrong" class has significant probability. For binary classification:

$$R^* = \int_{\mathcal{X}} \min(\pi_0 p_0(x), \pi_1 p_1(x)) , dx$$

This is the probability mass in the overlap region where one class's weighted density intrudes on the other's.

Visualizing the Overlap:

Imagine two Gaussian distributions in 1D:

• Class 0: $\mathcal{N}(0, 1)$ with prior $\pi_0 = 0.5$
• Class 1: $\mathcal{N}(3, 1)$ with prior $\pi_1 = 0.5$

The weighted densities are $0.5 \cdot p_0(x)$ and $0.5 \cdot p_1(x)$. The decision boundary is at $x = 1.5$ (midpoint). The Bayes error is the area where the curves cross—the probability mass assigned to the "wrong" class.

As the means move closer, overlap increases, and Bayes error rises. As they separate, overlap decreases, and Bayes error falls. When distributions are identical, Bayes error is 0.5 (random guessing).

Multi-Class Geometry:

For $K$ classes, the feature space is partitioned into $K$ decision regions. The Bayes error is the sum of probability masses where each class intrudes on another's region:

$$R^* = \sum_{k=1}^K \int_{\mathcal{R}_j, j \neq k} \pi_k \cdot p_k(x) , dx$$

This is the total "misplaced" probability—class $k$ points that fall in region $j$'s territory.

In special cases, the Bayes error can be computed exactly. These closed-form solutions provide valuable benchmarks and intuition.

Case 1: Univariate Gaussians with Equal Variance

For binary classification with:

• Class 0: $\mathcal{N}(\mu_0, \sigma^2)$, prior $\pi_0$
• Class 1: $\mathcal{N}(\mu_1, \sigma^2)$, prior $\pi_1$

The decision boundary is at: $$x^* = \frac{\mu_0 + \mu_1}{2} + \frac{\sigma^2}{\mu_1 - \mu_0} \log \frac{\pi_0}{\pi_1}$$

The Bayes error is: $$R^* = \pi_0 \cdot \Phi\left(\frac{x^* - \mu_0}{\sigma}\right) + \pi_1 \cdot \left(1 - \Phi\left(\frac{x^* - \mu_1}{\sigma}\right)\right)$$

where $\Phi$ is the standard normal CDF.

Case 2: Equal Priors Simplification

With equal priors ($\pi_0 = \pi_1 = 0.5$) and equal variances, the boundary is the midpoint $x^* = (\mu_0 + \mu_1)/2$, and:

$$R^* = \Phi\left(-\frac{|\mu_1 - \mu_0|}{2\sigma}\right) = \Phi\left(-\frac{d}{2}\right)$$

where $d = |\mu_1 - \mu_0|/\sigma$ is the standardized distance between means.

Case 3: Multivariate Gaussians (LDA Setting)

For $d$-dimensional Gaussians with shared covariance $\Sigma$: $$R^* = \Phi\left(-\frac{\Delta}{2}\right)$$

where $\Delta = \sqrt{(\mu_1 - \mu_0)^T \Sigma^{-1} (\mu_1 - \mu_0)}$ is the Mahalanobis distance.

This formula shows that Bayes error depends on the statistical distance between classes, not just Euclidean distance.

When analytic computation isn't possible, we can derive bounds on the Bayes error using information-theoretic and distribution-based arguments.

Upper Bounds:

1. Prior-Based Bound $$R^* \leq \min_k \pi_k = 1 - \max_k \pi_k$$

A classifier that always predicts the most common class achieves this error. The Bayes classifier must do at least as well.

2. Random Guessing Bound $$R^* \leq 1 - \frac{1}{K}$$

Uniform random guessing achieves this for $K$ classes. For binary: $R^* \leq 0.5$.

3. Total Variation Bound For binary classification: $$R^* \leq \frac{1 - \text{TV}(P_0, P_1)}{2}$$ where $\text{TV}(P_0, P_1) = \frac{1}{2}\int |p_0(x) - p_1(x)| dx$ is the total variation distance.

Lower Bounds:

1. Entropy-Based Bound $$R^* \geq H_b^{-1}\left(H(Y|X)\right)$$

where $H(Y|X)$ is the conditional entropy and $H_b^{-1}$ is the inverse binary entropy function. This bound connects Bayes error to information theory.

2. Hellinger Distance Bound $$R^* \geq \frac{1 - H(P_0, P_1)^2}{2}$$

where $H(P_0, P_1) = \sqrt{1 - \int \sqrt{p_0(x) p_1(x)} dx}$ is the Hellinger distance.

3. KL Divergence Bound (Bretagnolle-Huber) $$R^* \geq \frac{1}{2} \exp\left(-D_{KL}(P_0 | P_1)\right)$$

where $D_{KL}$ is the Kullback-Leibler divergence.

In practice, we don't know the true distribution, so we must estimate the Bayes error from data. This is challenging because we're trying to estimate the performance of an unknown optimal classifier.

Method 1: Plug-In Estimation

1. Estimate the class-conditional densities $\hat{p}_k(x)$ and priors $\hat{\pi}_k$
2. Compute the estimated posterior $\hat{\eta}_k(x) = \frac{\hat{\pi}_k \hat{p}_k(x)}{\sum_j \hat{\pi}_j \hat{p}_j(x)}$
3. Construct the plug-in Bayes classifier $\hat{h}^*(x) = \arg\max_k \hat{\eta}_k(x)$
4. Estimate Bayes error as $\hat{R}^* = \frac{1}{n} \sum_{i=1}^n \left(1 - \max_k \hat{\eta}_k(x_i)\right)$

This approach's accuracy depends heavily on the quality of density estimation.

Method 2: K-NN Based Estimation

The K-NN classifier provides a natural Bayes error estimator. With appropriate $k$:

$$\hat{R}^*{\text{NN}} = \frac{1}{n} \sum{i=1}^n \left(1 - \frac{1}{k} \sum_{j \in N_k(x_i)} \mathbb{1}[y_j = \hat{y}_i]\right)$$

where $N_k(x_i)$ is the set of $k$ nearest neighbors.

Key result (Cover & Hart, 1967): For 1-NN: $$R^* \leq R_{\text{1-NN}} \leq 2R^(1 - R^) \leq 2R^*$$

The 1-NN error is at most twice the Bayes error. As $n \to \infty$ and $k/n \to 0$ with $k \to \infty$, the K-NN error converges to $R^*$.

Method 3: Cross-Validation with Flexible Classifiers

If we use a very flexible classifier (e.g., large random forest, well-tuned neural network) with proper regularization:

$$\hat{R}^* \approx R_{\text{CV}}(\text{flexible classifier})$$

The test error of a highly flexible, properly regularized classifier serves as an upper bound on the Bayes error. This is a practical approach used in deep learning.

Method 4: Human Performance Baseline

For tasks where human labels define ground truth, human error rate provides an estimate:

$$R_{\text{human}} \approx R^* + \text{human-specific errors}$$

If humans achieve 95% accuracy on image classification, the Bayes error is at most 5%.

Understanding the Bayes error has profound implications for how we approach machine learning problems.

1. Setting Realistic Expectations

If the Bayes error is 20%, no amount of algorithmic sophistication will achieve 1% error. Knowing the approximate Bayes error helps set realistic targets and allocate resources wisely.

• Error >> estimated Bayes error → Model/algorithm can be improved
• Error ≈ estimated Bayes error → Near optimal; seek better features
• Error < estimated Bayes error → Overfitting or measurement error

2. Features vs. Algorithms

The Bayes error is determined by the features, not the algorithm. This insight redirects effort:

• High Bayes error with current features → Collect better features
• Low model error far from Bayes → Improve model/algorithm

Feature engineering attacks the problem at its root—reducing the irreducible error itself.

3. Data Quality Assessment

Bayes error reveals data quality issues:

• Very high Bayes error → Features may not be predictive of labels
• High label noise → Artificial inflation of Bayes error
• Missing important features → Bayes error higher than necessary

Multi-class classification ($K > 2$) introduces additional complexity to Bayes error analysis.

General Formula:

$$R^* = \mathbb{E}X\left[1 - \max{k=1}^K P(Y = k | X)\right] = 1 - \mathbb{E}_X\left[\max_k \eta_k(X)\right]$$

The error at each point is $1$ minus the largest class probability.

Baseline Comparisons:

• Random guessing: $R_{\text{random}} = 1 - 1/K = (K-1)/K$
• Always predict most common: $R_{\text{majority}} = 1 - \max_k \pi_k$
• Bayes error: $R^* \leq \min(R_{\text{random}}, R_{\text{majority}})$

Confusion Patterns:

In multi-class problems, Bayes error often concentrates at specific class boundaries:

• Similar classes (e.g., cat vs. dog) may have high pairwise Bayes error
• Dissimilar classes (e.g., cat vs. car) may be nearly perfectly separable

This motivates hierarchical classification and confusion analysis.

Per-Class Bayes Error:

We can define class-specific error rates: $$R^_k = P(h^(X) \neq k | Y = k) = \mathbb{E}[1 - \mathbb{1}[\arg\max_j \eta_j(X) = k] | Y = k]$$

This helps identify which classes are inherently hard to classify.

We've explored the Bayes error rate as the fundamental limit on classification accuracy. Let's consolidate the key insights:

What's Next:

We've established the theoretical framework: the Bayes classifier maximizes posterior probabilities to achieve the Bayes error rate. The fundamental challenge is that computing posteriors requires the unknown distribution. In the next page, we'll explore posterior computation—how to calculate and approximate posteriors in practice, setting the stage for practical generative classifiers like Naive Bayes.