The Bayes Classifier

The Bayes classifier is theoretically optimal, and we know how to compute posteriors via Bayes' theorem. So why don't we just use it for everything? The answer reveals some of the most fundamental challenges in machine learning—challenges that shape nearly every algorithm you'll encounter.

The gap between the beautiful theory of Bayesian classification and practical implementation is vast. Understanding this gap explains why approximations like Naive Bayes exist, why different classifiers excel in different scenarios, and why machine learning remains a field of active research.

The curse of dimensionality refers to a collection of phenomena that arise when analyzing data in high-dimensional spaces—phenomena that make our low-dimensional intuitions fail catastrophically.

The Core Problem:

To compute posterior probabilities, we need to estimate class-conditional densities $p_k(x)$. These are functions over the $d$-dimensional feature space. As $d$ increases:

1. Data becomes sparse: Points spread out exponentially, leaving vast empty regions
2. Estimation becomes unreliable: Too few samples in any local region
3. Computation becomes intractable: Density over $d$-dimensional space requires exponential resources

Geometric Intuition: Volume Explodes

Consider a unit hypercube $[0, 1]^d$ in $d$ dimensions:

• Its volume is always 1
• But its "corners" dominate as $d$ increases

The fraction of volume within distance $\epsilon$ of the boundary: $$\text{Shell fraction} = 1 - (1 - 2\epsilon)^d \xrightarrow{d \to \infty} 1$$

For $\epsilon = 0.01$ and $d = 500$: nearly 100% of the volume is in the outer shell. All points are "near the boundary" in high dimensions—there's no "interior" to estimate density reliably.

The Bayes classifier requires knowing $p_k(x)$ for each class $k$. Let's see why estimating this becomes impossible in high dimensions.

Non-Parametric Density Estimation:

Kernel density estimation (KDE) estimates: $$\hat{p}(x) = \frac{1}{n h^d} \sum_{i=1}^n K\left(\frac{x - x_i}{h}\right)$$

where $K$ is a kernel function and $h$ is the bandwidth.

The Problem:

• The effective volume of the kernel is $\propto h^d$ (exponential in $d$)
• Expected number of points in this volume is $n \cdot h^d / V$
• For accurate estimation, we need many points → $n \cdot h^d$ must be large
• But small $h$ is needed for local estimation → contradiction

Sample Complexity of Non-Parametric Methods:

For non-parametric density estimation with error $\epsilon$, the sample size required is:

$$n = O\left(\epsilon^{-(d + 4)/2}\right)$$

This is exponential in $d$! For $d = 100$ dimensions and $\epsilon = 0.1$: $$n \approx 0.1^{-52} \approx 10^{52}$$

That's more samples than atoms in the observable universe.

Parametric Models Offer Partial Relief:

Parametric models (e.g., Gaussian) reduce the problem from estimating a function to estimating parameters:

• Gaussian mean: $d$ parameters
• Gaussian (full) covariance: $d(d+1)/2$ parameters
• Total: $O(d^2)$ parameters

Still challenging, but polynomial rather than exponential.

Even with parametric models, the Bayes classifier faces a fundamental complexity challenge: specifying the joint distribution of all features.

The Full Covariance Problem:

A full Gaussian model for $d$ features requires:

• Mean: $d$ parameters
• Covariance: $d(d+1)/2 \approx d^2/2$ parameters (symmetric matrix)

For $K$ classes: $O(K d^2)$ total parameters

The Numbers Quickly Become Infeasible:

For a 1000-feature problem with 10 classes, we need to estimate 5 million parameters!

Sample Size Requirements:

Reliable covariance estimation requires $n \gg d^2$ samples (a common rule of thumb is $n \geq 10 \cdot (\text{number of parameters})$).

For $d = 100$:

• Full covariance: $\sim 5000$ parameters → need $\sim 50,000$ samples per class
• With 10 classes: $\sim 500,000$ total samples

Most real-world datasets don't have this much data!

Ill-Conditioned Covariance Matrices:

Even when we have enough data, estimated covariance matrices are often:

• Singular (non-invertible) when $n < d$
• Ill-conditioned when $n \approx d$, leading to unstable inverses

Since the Gaussian density involves $\Sigma^{-1}$, this causes numerical disasters.

For discrete features, the challenge takes a different but equally severe form: combinatorial explosion.

The Full Discrete Model:

With $d$ binary features, the full joint distribution has: $$2^d - 1 \text{ free parameters per class}$$

(The probability of each of the $2^d$ configurations, minus one for normalization)

The Numbers:

For a text classification problem with 10,000 vocabulary words (each binary: present/absent), there are $2^{10000}$ possible documents—vastly more than atoms in the universe.

The Data Sparsity Problem:

With $2^d$ possible configurations but only $n$ training samples:

• Almost all configurations are never observed
• Maximum likelihood assigns probability 0 to unseen configurations
• Any test document with a novel word combination gets probability 0

Example: Document Classification

Consider classifying emails as spam/not-spam with 1000 word features:

• Total possible documents: $2^{1000} \approx 10^{301}$
• Training emails: maybe 10,000
• Coverage: $10^{-297}$%

We've observed an infinitesimally small fraction of possible documents. Direct density estimation is hopeless.

Smoothing Doesn't Fully Solve This:

Smoothing (e.g., Laplace smoothing) prevents zero probabilities but doesn't solve the fundamental estimation problem. With $2^d$ configurations and only $n$ samples:

• Each smoothing pseudo-count is spread across $2^d$ outcomes
• Effective sample size per configuration: $\frac{n + \alpha}{2^d}$
• For $d = 100$: effectively 0 samples per configuration

The only practical solution is to impose structure—assumptions that reduce the effective number of parameters.

Statistical learning theory provides rigorous bounds on how much data is needed to learn accurately. These results formalize the challenges we've discussed.

PAC Learning Framework:

A classifier is probably approximately correct (PAC) if, with high probability (≥ $1-\delta$), its error is close to optimal (within $\epsilon$ of Bayes error).

The sample complexity is the number of samples $n$ needed to achieve this.

Theorem (Informal):

For a hypothesis class with VC dimension $d_{VC}$: $$n = O\left(\frac{d_{VC} + \log(1/\delta)}{\epsilon^2}\right)$$

The sample complexity is linear in the model's complexity (VC dimension) but only logarithmic in the confidence parameter.

VC Dimension Examples:

Implications:

1. Simple models (low VC) need less data but may underfit
2. Complex models (high VC) can represent more but risk overfitting
3. The Bayes classifier (unrestricted) has infinite VC dimension—not learnable without structural assumptions

The No Free Lunch Theorem:

There's no universally best learning algorithm. Averaged over all possible data distributions:

• Every algorithm performs equally (random guessing)
• Success on one distribution implies failure on another

Implication: We must make assumptions that match real-world data. The Bayes classifier assumes nothing about the distribution's structure—which is why it can't be learned in general. Practical algorithms succeed by embedding assumptions that hold approximately in practice.

Beyond statistical challenges, exact Bayesian classification can be computationally intractable.

Computing the Evidence:

The evidence (marginal likelihood) requires summing over all classes: $$p(x) = \sum_{k=1}^K \pi_k \cdot p_k(x)$$

For $K$ classes, this is $O(K)$ per prediction—usually manageable.

But if we model feature dependencies (not Naive Bayes), computing $p_k(x)$ itself becomes the bottleneck.

Graphical Models and Inference:

If we model $p_k(x)$ using a general probabilistic graphical model (Bayesian network or Markov random field), exact inference can be:

• Polynomial for tree-structured dependencies
• NP-hard for general graphs

The complexity depends on the graph's treewidth—a measure of how tree-like it is.

Why Naive Bayes is Fast:

Naive Bayes assumes all features are conditionally independent given the class: $$p_k(x) = \prod_{j=1}^d p_k(x_j)$$

This transforms a $d$-dimensional density estimation into $d$ one-dimensional problems. Each $p_k(x_j)$ requires only:

• Single parameter (Bernoulli)
• Two parameters (Gaussian: mean and variance)
• $V$ parameters (multinomial with $V$ outcomes)

Total computation: $O(d)$ per class, $O(Kd)$ overall—linear in both number of features and classes!

Let's see how these theoretical challenges manifest in practical machine learning scenarios.

Scenario 1: Medical Diagnosis

• Features: Hundreds of lab tests, symptoms, genetic markers
• Problem: Many tests are correlated (e.g., kidney function tests). Full covariance estimation requires more patients than most studies have.
• Solution: Feature selection, domain knowledge to group related tests, or independence assumptions

Scenario 2: Spam Detection

• Features: Presence/absence of 50,000+ words
• Problem: $2^{50000}$ possible emails. No email ever seen twice with exact same words.
• Solution: Naive Bayes with Laplace smoothing. Independence assumption is wrong ("Nigerian" correlates with "prince") but works well in practice.

Scenario 3: Image Classification

• Features: Millions of pixels, each with RGB values
• Problem: Natural images occupy a tiny manifold in pixel space. Estimating density over $\mathbb{R}^{3 \times 1000000}$ is hopeless.
• Solution: Learned representations (CNNs) that extract low-dimensional features. Classification happens in the learned feature space, not pixel space.

Scenario 4: Recommendation Systems

• Features: User-item interaction matrix (millions of users × millions of items)
• Problem: Extreme sparsity (each user rates tiny fraction of items). Can't estimate joint distribution.
• Solution: Matrix factorization, collaborative filtering—strong assumptions about low-rank structure.

The challenges we've explored don't mean the Bayes classifier is useless—they inform how we build practical systems.

Design Principles Emerging from These Challenges:

1. Assumption Selection Choose assumptions that:

• Reduce model complexity sufficiently for your data size
• Approximately match domain knowledge
• Fail gracefully when violated

2. Regularization Always regularize:

• Shrink toward simpler models (diagonal covariance, uniform priors)
• Use Bayesian priors that encode "typical" structure
• Cross-validate regularization strength

3. Model Class Selection

Match model to data characteristics:

• Small data + domain knowledge → Strong assumptions (Naive Bayes, LDA)
• Large data + complex patterns → Flexible models (Neural networks, ensembles)
• Interpretability needed → Structured models (Trees, GAMs)

4. Ensemble Methods

Combine multiple simple models:

• Each model's assumptions may be wrong differently
• Averaging reduces the impact of any single wrong assumption
• Random forests, boosting—combine many weak learners

5. Hybrid Approaches

Combine generative and discriminative:

• Use generative model for prior and structure
• Fine-tune discriminatively for the classification objective
• Example: Generative pre-training in NLP

We've explored the formidable challenges that separate the theoretically optimal Bayes classifier from practical implementation. Let's consolidate:

What's Next:

This module has established the theoretical foundation of Bayesian classification. We've seen what optimal looks like (Bayes classifier), what limits performance (Bayes error rate), how to compute posteriors in principle (Bayes' theorem), and why direct implementation fails (the challenges we've explored).

In the next module, we'll introduce Naive Bayes—the most successful practical approximation to the Bayes classifier. By assuming conditional independence of features, Naive Bayes sidesteps the challenges we've discussed, enabling fast, scalable classification that works surprisingly well in practice.