In the previous page, we derived the Bayes decision rule and claimed it produces an optimal classifier. But what exactly does "optimal" mean in machine learning? The term risks being vague or marketing-speak unless we pin it down precisely.

This page dives deep into the formal definition of optimality, exploring why the Bayes classifier achieves it, what assumptions are required, and how this concept guides the design of practical classifiers. We'll also see how optimal can coexist with imperfect—understanding that even the best possible classifier can still make errors.

To make "optimality" precise, we need a mathematical framework for comparing classifiers. This is the statistical decision theory framework, which formalizes learning as risk minimization.

Core Components:

1. Data Distribution: $(X, Y) \sim P$, the true (unknown) joint distribution
2. Hypothesis Space: $\mathcal{H}$, the set of all classifiers we consider
3. Loss Function: $L: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\geq 0}$, measuring error
4. Risk Functional: $R: \mathcal{H} \to \mathbb{R}_{\geq 0}$, the expected loss

The risk of classifier $h$ is defined as:

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

A classifier $h^*$ is optimal if it minimizes the risk over all possible classifiers:

$$R(h^*) = \inf_{h: \mathcal{X} \to \mathcal{Y}} R(h)$$

The Unrestricted Hypothesis Space:

A crucial point is that we're optimizing over all measurable functions $h: \mathcal{X} \to \mathcal{Y}$. This is an infinite, uncountably large space. We're not restricting ourselves to linear classifiers, decision trees, or neural networks—we're considering every possible way to map features to labels.

The remarkable fact is that despite this vast search space, the optimal solution has a simple, explicit form: the Bayes classifier.

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

This is possible because the problem decomposes pointwise: the optimal prediction at each $x$ can be made independently of other points.

Why Pointwise Decomposition Works:

Let's revisit this crucial insight. The risk can be written as:

$$R(h) = \int_{\mathcal{X}} \mathbb{E}[L(Y, h(X)) | X = x] \cdot p(x) , dx$$

For each fixed $x$, the integrand $\mathbb{E}[L(Y, h(x)) | X = x]$ depends only on the choice of $h(x)$ at that point. Since $p(x) \geq 0$, minimizing the overall integral is equivalent to minimizing the integrand at each $x$ separately.

This is a "separate optimization" result: the global minimum is achieved by optimizing locally everywhere. Such decomposition is rare in optimization and is a special property of the risk functional with additive loss.

The most natural loss function for classification is 0-1 loss (also called misclassification loss):

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

This loss treats all errors equally: every mistake costs 1, every correct prediction costs 0. The corresponding risk is simply the probability of error:

$$R_{0-1}(h) = P(h(X) eq Y)$$

Minimizing this risk is equivalent to maximizing accuracy.

Deriving the Optimal Classifier:

For a fixed point $x$, the conditional risk is:

$$\mathbb{E}[L_{0-1}(Y, h(x)) | X = x] = P(Y eq h(x) | X = x) = \sum_{k eq h(x)} P(Y = k | X = x)$$

This is minimized when we choose $h(x)$ to be the class with the largest posterior:

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

Because: $$P(Y eq h^*(x) | X = x) = 1 - \max_k P(Y = k | X = x) \leq 1 - P(Y = k | X = x) = P(Y eq k | X = x)$$

for any other choice $k$. This proves the Bayes classifier minimizes 0-1 risk pointwise, hence globally.

Uniqueness:

The Bayes classifier is essentially unique. More precisely:

• At any point $x$ where one class has strictly higher posterior than all others, the Bayes classifier must choose that class
• At points where multiple classes tie for maximum posterior (a set of measure zero for continuous distributions), any of the tied classes is optimal

In practice, ties are infinitely improbable for continuous distributions, so the Bayes classifier is unique almost everywhere.

While 0-1 loss is the most common, different applications call for different loss functions. The general framework still applies: the optimal classifier minimizes expected loss, but the form of the optimal decision changes.

The General Optimal Decision Rule:

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

$$h^*(x) = \arg\min_k \sum_{j=1}^K L(j, k) \cdot P(Y = j | X = x) = \arg\min_k \sum_{j=1}^K L(j, k) \cdot \eta_j(x)$$

This is the prediction that minimizes expected loss given the observed features.

Example: Asymmetric Binary Classification

Consider medical diagnosis where:

• False negative (missing disease) has high cost $c_{FN}$
• False positive (unnecessary treatment) has lower cost $c_{FP}$

The optimal decision rule becomes:

$$h^*(x) = \begin{cases} 1 \text{ (disease)} & \text{if } \eta(x) \cdot c_{FN} > (1 - \eta(x)) \cdot c_{FP} \ 0 \text{ (healthy)} & \text{otherwise} \end{cases}$$

Simplifying: $$h^(x) = 1 \iff \eta(x) > \frac{c_{FP}}{c_{FP} + c_{FN}} = \tau^$$

With $c_{FN} = 10$ and $c_{FP} = 1$, we get $\tau^* = \frac{1}{11} \approx 0.09$. We classify as "disease" even when the posterior probability is just 10%, because missing the disease is so costly.

The Bayes classifier is sometimes called an oracle classifier because it requires knowledge we never have in practice: the true posterior probabilities $P(Y = k | X = x)$.

Why We Never Know the True Posterior:

1. The joint distribution $P(X, Y)$ is unknown. It's the very thing we're trying to learn about.

2. We only have samples, not the distribution itself. From $n$ data points, we must infer properties of the underlying distribution.

3. The feature space is continuous. For a specific $x$, there may be zero or one training example at exactly that location, making direct estimation impossible.

4. The posterior varies smoothly but complexly. Its shape depends on the (unknown) class-conditional distributions and priors.

The Fundamental Task of Machine Learning:

Viewed through this lens, supervised learning is the task of approximating the Bayes classifier from finite data. Every classification algorithm can be understood as proposing a specific method for estimating the posterior (or the decision boundary directly):

• Logistic regression: Assumes log-odds is linear in $x$, estimates $\eta(x) = \sigma(w^T x + b)$
• K-nearest neighbors: Estimates $\eta(x)$ by voting among nearby training points
• Decision trees: Partition space and estimate $\eta(x)$ as class proportions in each leaf
• Neural networks: Learn flexible function $\eta(x)$ via function approximation
• Naive Bayes: Estimates class-conditionals, computes posterior via Bayes' theorem

The Approximation Gap:

For any practical classifier $\hat{h}$ built from data:

$$R(\hat{h}) = R^* + \underbrace{(R(\hat{h}) - R^*)}_{\text{excess risk}}$$

where $R^* = R(h^*)$ is the Bayes risk. The excess risk measures how far our practical classifier is from optimal. It has two sources:

1. Approximation error: The best classifier in our hypothesis class might not match the Bayes classifier
2. Estimation error: Even the best-in-class classifier must be estimated from finite data

Understanding these errors is central to statistical learning theory.

In practice, we don't search over all possible classifiers. We restrict to a hypothesis class $\mathcal{H}$—a subset of all possible functions from $\mathcal{X}$ to $\mathcal{Y}$.

Examples:

• $\mathcal{H}_{\text{linear}}$: Linear classifiers $h(x) = \text{sign}(w^T x + b)$
• $\mathcal{H}_{\text{tree}}$: Decision trees with at most $d$ depth
• $\mathcal{H}_{\text{NN}}$: Neural networks with specific architecture

Within a hypothesis class, we can define a restricted Bayes risk:

$$R^*{\mathcal{H}} = \inf{h \in \mathcal{H}} R(h)$$

A classifier that achieves this is optimal within $\mathcal{H}$, but may be far from the true Bayes classifier.

The Approximation-Estimation Trade-off:

The choice of hypothesis class creates a fundamental trade-off:

• Large $\mathcal{H}$ (e.g., deep neural networks):

  • Small approximation error: Can approximate complex Bayes classifiers
  • Large estimation error: Many parameters to estimate from finite data
  • Risk of overfitting

• Small $\mathcal{H}$ (e.g., logistic regression):

  • Large approximation error: May not capture complex decision boundaries
  • Small estimation error: Few parameters, stable estimates
  • Risk of underfitting

The optimal hypothesis class depends on the data distribution and sample size.

A central question in learning theory: Can we approach the Bayes classifier as we collect more data? This leads to the concept of consistency.

Definition: Universal Consistency

A classification method is universally consistent if, for any data distribution $P$:

$$R(\hat{h}_n) \to R^* \text{ as } n \to \infty$$

where $\hat{h}_n$ is the classifier learned from $n$ training examples and $R^*$ is the Bayes risk.

Universal consistency means the method will eventually learn the optimal classifier given enough data, regardless of the (unknown) underlying distribution.

Which Methods Are Universally Consistent?

Some classical results:

• K-NN with $k \to \infty$ and $k/n \to 0$: Universally consistent. As $n$ grows, we use more neighbors (reducing variance) but still a vanishing fraction (maintaining locality).

• Decision trees with proper pruning: Universally consistent under certain growing schemes.

• Neural networks with growing architecture: Can be universally consistent with proper regularization.

• Fixed-capacity models: Generally NOT universally consistent. A linear classifier can never learn a nonlinear Bayes boundary, no matter how much data.

• Naive Bayes: NOT universally consistent in general, because the conditional independence assumption may be wrong.

Rates of Convergence:

Beyond consistency, we can ask how fast the excess risk decreases. For well-specified models and smooth distributions:

$$R(\hat{h}_n) - R^* = O(n^{-\alpha})$$

where $\alpha$ depends on the smoothness of the boundary and the method's complexity. Typical rates range from $O(n^{-1/2})$ (parametric) to $O(n^{-1/d})$ (nonparametric in $d$ dimensions, showing the curse of dimensionality).

These rates quantify the practical value of additional data and inform sample size requirements.

Given that we can never compute the Bayes classifier, why study it? Its value lies in several practical applications:

1. Benchmarking and Lower Bounds

The Bayes error provides a lower bound on achievable error. If we know or can estimate the Bayes error for a problem, we can:

• Assess whether our current classifier is close to optimal
• Decide whether to invest in more complex models or more data
• Set realistic expectations for model performance

2. Model Debugging

If a classifier's error greatly exceeds a reasonable estimate of the Bayes error, something is wrong—perhaps the features aren't informative, the model is too simple, or there's a bug in the training pipeline.

3. Feature Evaluation

Features that reduce the Bayes error are "worth collecting." The Bayes error with an additional feature set $X'$ is:

$$R^(X, X') \leq R^(X)$$

Equality holds when $X'$ provides no additional information about $Y$ given $X$. This guides feature engineering.

4. Algorithm Design Principles

The Bayes classifier suggests design principles:

• Classifiers should estimate or approximate posteriors
• Flexible models should be able to represent complex posteriors
• Regularization prevents overfitting to empirical posteriors

5. Theoretical Analysis

Many theoretical results (generalization bounds, convergence rates) are stated in terms of excess risk over the Bayes risk. The Bayes classifier provides the reference point.

We've explored the deep meaning of optimality in classification and the Bayes classifier's role as the theoretical gold standard. Let's consolidate:

What's Next:

The optimal classifier achieves the best possible accuracy, but even it makes errors when classes overlap in feature space. In the next page, we'll explore the Bayes error rate—the irreducible error that no classifier can surpass—and understand what it tells us about the fundamental difficulty of a classification problem.