The Bayes Classifier

Every classification algorithm—from logistic regression to deep neural networks—shares a common aspiration: to predict the correct class label for unseen data with the highest possible accuracy. But what does optimal classification actually mean? Is there a theoretical limit to how good any classifier can be? And if so, what classifier achieves it?

These questions lead us to one of the most profound results in statistical learning theory: the Bayes classifier and its associated Bayes decision rule. This isn't just another algorithm to add to your toolkit—it's the theoretical benchmark against which all classifiers are measured. Understanding it provides deep insight into the fundamental nature of classification and the irreducible limits imposed by inherent data uncertainty.

Before deriving the Bayes decision rule, let's establish the precise mathematical framework for classification. While you've likely encountered classification before, appreciating the Bayes classifier requires rigorous foundations.

The Probabilistic Classification Setup:

Consider a classification problem with:

• Feature space $\mathcal{X} \subseteq \mathbb{R}^d$: the set of all possible input feature vectors
• Label space $\mathcal{Y} = {1, 2, \ldots, K}$: the set of $K$ possible class labels
• Joint distribution $P(X, Y)$: the true (but typically unknown) probability distribution over feature-label pairs

Our goal is to construct a classifier $h: \mathcal{X} \to \mathcal{Y}$ that maps feature vectors to class labels. But what makes one classifier better than another?

The Risk Framework:

To compare classifiers, we need a measure of quality. The most natural choice is the probability of misclassification (0-1 loss):

$$L(y, \hat{y}) = \mathbb{1}[y \neq \hat{y}] = \begin{cases} 0 & \text{if } y = \hat{y} \ 1 & \text{if } y \neq \hat{y} \end{cases}$$

The risk (or expected loss) of a classifier $h$ is:

$$R(h) = \mathbb{E}_{(X,Y) \sim P}[L(Y, h(X))] = P(h(X) \neq Y)$$

This is simply the probability that the classifier makes an error on a randomly drawn data point. Our objective is to find the classifier $h^*$ that minimizes this risk:

$$h^* = \arg\min_h R(h) = \arg\min_h P(h(X) \neq Y)$$

The Key Insight: Pointwise Optimization

Here's the crucial observation that leads to the Bayes classifier. The risk can be written as an expectation over the feature space:

$$R(h) = \mathbb{E}X\left[\mathbb{E}{Y|X}[L(Y, h(X))]\right] = \int_{\mathcal{X}} \underbrace{P(h(x) \neq Y | X = x)}_{\text{conditional error at } x} \cdot p(x) , dx$$

Since $p(x) \geq 0$ for all $x$, minimizing the overall risk is equivalent to minimizing the conditional error at each point $x$ separately. This decomposition is powerful: instead of searching over all possible classifiers globally, we can optimize pointwise, choosing the best prediction for each $x$ independently.

Now we derive the optimal classifier from first principles. For a fixed feature vector $x$, we want to find the class label that minimizes the conditional probability of error:

$$h^*(x) = \arg\min_{k \in \mathcal{Y}} P(Y \neq k | X = x)$$

Since probabilities sum to one:

$$P(Y \neq k | X = x) = 1 - P(Y = k | X = x)$$

Minimizing this is equivalent to maximizing the posterior probability:

$$h^*(x) = \arg\max_{k \in \mathcal{Y}} P(Y = k | X = x)$$

This is the Bayes decision rule: classify each point $x$ to the class with the highest posterior probability.

Intuitive Interpretation:

The Bayes decision rule is remarkably intuitive. Given the evidence $x$, we're betting on the most likely class. If we had to make one prediction for each $x$ and wanted to maximize our expected accuracy, we'd pick the class with probability greater than all others.

Consider a medical diagnosis example:

• A patient presents with symptoms $x$
• We compute $P(\text{Disease} | x)$ and $P(\text{Healthy} | x)$
• If $P(\text{Disease} | x) = 0.7$ and $P(\text{Healthy} | x) = 0.3$, we classify as Disease
• This prediction will be correct 70% of the time for patients with these exact symptoms

By always picking the most probable class, we maximize our accuracy over the long run.

Formal Statement and Notation:

Let's formalize this with consistent notation. Define:

• Prior probability: $\pi_k = P(Y = k)$ — the overall prevalence of class $k$
• Class-conditional density: $p_k(x) = p(x | Y = k)$ — the feature distribution for class $k$
• Marginal density: $p(x) = \sum_{k=1}^K \pi_k \cdot p_k(x)$ — the overall feature distribution
• Posterior probability: $\eta_k(x) = P(Y = k | X = x)$ — the probability of class $k$ given features $x$

By Bayes' theorem:

$$\eta_k(x) = P(Y = k | X = x) = \frac{p(x | Y = k) \cdot P(Y = k)}{p(x)} = \frac{\pi_k \cdot p_k(x)}{\sum_{j=1}^K \pi_j \cdot p_j(x)}$$

The Bayes classifier becomes:

$$h^*(x) = \arg\max_k \eta_k(x) = \arg\max_k \frac{\pi_k \cdot p_k(x)}{p(x)} = \arg\max_k \left[ \pi_k \cdot p_k(x) \right]$$

Note that the denominator $p(x)$ is constant across classes and can be dropped from the argmax.

We've claimed that the Bayes classifier is optimal, but let's prove this rigorously and understand exactly what we mean by optimality.

Theorem (Optimality of the Bayes Classifier):

Let $h^*$ be the Bayes classifier and let $h$ be any other classifier. Then:

$$R(h^*) \leq R(h)$$

That is, the Bayes classifier achieves the lowest possible risk (error rate) among all classifiers.

Proof:

For any classifier $h$, the risk can be decomposed as:

$$R(h) = \int_{\mathcal{X}} P(Y \neq h(x) | X = x) \cdot p(x) , dx$$

At each point $x$, the conditional error is:

$$P(Y \neq h(x) | X = x) = 1 - P(Y = h(x) | X = x) = 1 - \eta_{h(x)}(x)$$

The Bayes classifier chooses $h^*(x) = \arg\max_k \eta_k(x)$, so for any other choice $h(x)$:

$$\eta_{h^*(x)}(x) \geq \eta_{h(x)}(x)$$

Therefore:

$$1 - \eta_{h^*(x)}(x) \leq 1 - \eta_{h(x)}(x)$$

Integrating over $x$:

$$R(h^) = \int (1 - \eta_{h^(x)}(x)) p(x) dx \leq \int (1 - \eta_{h(x)}(x)) p(x) dx = R(h) \quad \square$$

Understanding the Optimality:

The proof reveals something profound: no classifier can beat the Bayes classifier, regardless of how sophisticated or computationally expensive it is. Deep neural networks, ensemble methods, kernel machines—all are fundamentally limited by the Bayes error rate.

This might seem discouraging, but it's actually liberating. It tells us that:

1. There's a minimum achievable error set by the data itself
2. Our goal isn't to achieve zero error but to approach the Bayes error
3. If our classifier matches the Bayes error, we've solved the problem optimally

The Bayes classifier is theoretically realizable only when we have complete knowledge of the joint distribution $P(X, Y)$. Since this information is never available in practice, we use approximations—and that's where all of machine learning comes in.

Relating to Information Theory:

The optimality of the Bayes classifier has deep connections to information theory. The posterior $\eta_k(x)$ represents all the information that $x$ provides about $Y$. Any classifier that doesn't use the posterior optimally is, in some sense, throwing away information.

The Bayes decision rule is essentially asking: given everything the features tell us about the class, what's our best guess? By choosing the most probable class, we're making the decision that will be correct most often.

This connects to the concept of sufficient statistics: the posterior $\eta(x)$ is a sufficient statistic for deciding the class label. Any transformation of $x$ that doesn't change the posterior doesn't change the optimal decision.

The Bayes decision rule has an elegant geometric interpretation. It partitions the feature space $\mathcal{X}$ into $K$ decision regions, one for each class:

$$\mathcal{R}_k = {x \in \mathcal{X} : h^*(x) = k} = {x : \eta_k(x) \geq \eta_j(x) \text{ for all } j \neq k}$$

Each decision region $\mathcal{R}_k$ contains all points where class $k$ has the highest posterior probability. The boundaries between regions—where two or more classes have equal posterior probabilities—form the Bayes decision boundaries.

Decision Boundary Equations:

The boundary between classes $i$ and $j$ is the set where:

$$\eta_i(x) = \eta_j(x)$$

Using Bayes' theorem (and dropping the common denominator):

$$\pi_i \cdot p_i(x) = \pi_j \cdot p_j(x)$$

Taking logs:

$$\log \pi_i + \log p_i(x) = \log \pi_j + \log p_j(x)$$

Rearranging:

$$\log \frac{p_i(x)}{p_j(x)} = \log \frac{\pi_j}{\pi_i}$$

This is the log-likelihood ratio equals the log prior odds. The shape of this boundary depends entirely on the class-conditional distributions $p_i(x)$ and $p_j(x)$.

Visualizing the Bayes Classifier:

Consider binary classification in 2D with Gaussian class-conditionals:

• Class 0: $p_0(x) = \mathcal{N}(\mu_0, \Sigma_0)$ with $\mu_0 = (0, 0)^T$
• Class 1: $p_1(x) = \mathcal{N}(\mu_1, \Sigma_1)$ with $\mu_1 = (3, 0)^T$

If $\Sigma_0 = \Sigma_1 = I$ (equal covariances), the decision boundary is a straight line halfway between the means (adjusted for prior differences). The Bayes classifier assigns points to whichever Gaussian center is closer (in Mahalanobis distance).

If $\Sigma_0 \neq \Sigma_1$, the boundary becomes a quadratic curve—a hyperbola, ellipse, or parabola depending on the covariance matrices.

Binary classification ($K = 2$) is both the most common case and the one that admits the simplest analysis. Let's denote the classes as 0 and 1, with posterior:

$$\eta(x) \triangleq P(Y = 1 | X = x)$$

Then $P(Y = 0 | X = x) = 1 - \eta(x)$, and the Bayes decision rule simplifies to:

$$h^*(x) = \begin{cases} 1 & \text{if } \eta(x) \geq 0.5 \ 0 & \text{if } \eta(x) < 0.5 \end{cases}$$

Or equivalently:

$$h^*(x) = \mathbb{1}[\eta(x) \geq 0.5]$$

The decision boundary is the set where $\eta(x) = 0.5$, i.e., where both classes are equally likely.

The Threshold Perspective:

Binary classification can be viewed through the lens of thresholding a continuous score. The posterior $\eta(x)$ maps each point to $[0, 1]$, and we threshold at 0.5 to make the decision.

This perspective connects to:

• Logistic regression: Models $\eta(x) = \sigma(w^T x + b)$ and thresholds at 0.5
• ROC analysis: Studies performance across all thresholds
• Calibration: Ensures predicted probabilities match true frequencies

The threshold 0.5 is optimal only for 0-1 loss. Different thresholds become optimal when:

• The costs of false positives and false negatives differ
• Class imbalance affects practical decisions
• Operating constraints require specific sensitivity/specificity tradeoffs

Log-Odds Formulation:

Working with the log-odds (logit) is often more convenient:

$$\text{logit}(\eta(x)) = \log \frac{\eta(x)}{1 - \eta(x)} = \log \frac{P(Y = 1 | x)}{P(Y = 0 | x)}$$

Using Bayes' theorem:

$$\text{logit}(\eta(x)) = \log \frac{\pi_1 \cdot p_1(x)}{\pi_0 \cdot p_0(x)} = \underbrace{\log \frac{\pi_1}{\pi_0}}{\text{log prior odds}} + \underbrace{\log \frac{p_1(x)}{p_0(x)}}{\text{log-likelihood ratio}}$$

The decision boundary is where this equals zero:

$$\log \frac{p_1(x)}{p_0(x)} = \log \frac{\pi_0}{\pi_1}$$

This formulation is central to logistic regression and log-linear models.

The Bayes decision rule can be expressed in several equivalent forms, each offering different insights and computational advantages.

Formulation 1: Maximum A Posteriori (MAP)

$$h^*(x) = \arg\max_k P(Y = k | X = x) = \arg\max_k \eta_k(x)$$

This is the most direct expression: choose the class with maximum posterior probability.

Formulation 2: Maximum Posterior-Proportional Score

$$h^*(x) = \arg\max_k \left[ \pi_k \cdot p_k(x) \right]$$

Since the denominator $p(x)$ is constant across classes, we can drop it from the optimization.

Formulation 3: Maximum Log-Score

$$h^*(x) = \arg\max_k \left[ \log \pi_k + \log p_k(x) \right]$$

Taking logs doesn't change the argmax (log is monotonic) and turns products into sums, which is numerically more stable.

Formulation 4: Minimum Expected Loss

For general loss functions $L(y, \hat{y})$, the optimal decision at $x$ is:

$$h^*(x) = \arg\min_k \mathbb{E}{Y|X=x}[L(Y, k)] = \arg\min_k \sum{j=1}^K L(j, k) \cdot \eta_j(x)$$

For 0-1 loss, $L(j, k) = \mathbb{1}[j \neq k]$, so this reduces to:

$$h^*(x) = \arg\min_k \sum_{j \neq k} \eta_j(x) = \arg\min_k (1 - \eta_k(x)) = \arg\max_k \eta_k(x)$$

Recovering our earlier result. But this formulation generalizes to asymmetric costs and other loss functions.

There's a beautiful connection between the Bayes classifier and regression that provides additional insight.

The Regression Function:

In regression, we seek the function that minimizes mean squared error:

$$f^*(x) = \arg\min_f \mathbb{E}[(Y - f(X))^2 | X = x] = \mathbb{E}[Y | X = x]$$

The optimal regression function is the conditional expectation (conditional mean).

Binary Classification as Regression:

For binary classification with labels ${0, 1}$, the regression function is:

$$f^*(x) = \mathbb{E}[Y | X = x] = 1 \cdot P(Y = 1 | x) + 0 \cdot P(Y = 0 | x) = \eta(x)$$

The posterior probability is exactly the regression function! The Bayes classifier then thresholds this regression function at 0.5.

Multi-Class Extension:

For multi-class problems, consider the vector-valued regression function:

$$\boldsymbol{\eta}(x) = (\eta_1(x), \eta_2(x), \ldots, \eta_K(x))^T$$

where $\eta_k(x) = P(Y = k | X = x)$. This vector lies on the probability simplex (entries non-negative, sum to 1).

The Bayes classifier takes the argmax of this vector. Methods like softmax regression directly model this vector-valued function.

The Pointwise View:

This perspective emphasizes that classification is fundamentally about learning a function—the posterior probability function $\eta(x)$. Once we have $\eta(x)$, classification is trivial (just take argmax). The challenge of machine learning is estimating $\eta(x)$ accurately from finite data.

We've established the theoretical foundation for optimal classification through the Bayes decision rule. Let's consolidate the key insights:

What's Next:

The Bayes classifier is the theoretical gold standard, but it requires knowing the true posterior probabilities—which we never have in practice. In the next page, we'll explore the optimal classifier concept more deeply, including the Bayes error rate and the fundamental limits it imposes on any learning algorithm.