12.1 Statistical Introduction to Machine Learning

Introduction

Machine learning can be understood through the lens of statistical learning theory. This perspective provides rigorous foundations for understanding generalization, model complexity, and the fundamental trade-offs in learning from data.

1. The Statistical Learning Framework

We assume data comes from an unknown probability distribution $P(X, Y)$ where:

• $X \in \mathcal{X}$ is the input space (features)
• $Y \in \mathcal{Y}$ is the output space (labels or continuous values)
• We have a training sample $\mathcal{D} = \{(\mathbf{x}_1, y_1), \ldots, (\mathbf{x}_n, y_n)\}$ drawn i.i.d. from $P(X, Y)$

The Learning Goal

Find a function $f: \mathcal{X} \to \mathcal{Y}$ from a hypothesis class $\mathcal{H}$ that minimizes the expected risk (generalization error):

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

where $\ell(\cdot, \cdot)$ is a loss function measuring prediction error.

The Bayes Optimal Predictor

The best possible predictor (Bayes predictor) minimizes the expected risk:

$$f^* = \arg\min_{f} R(f)$$

For squared loss: $f^*(x) = \mathbb{E}[Y|X=x]$ (conditional expectation)

For 0-1 loss: $f^*(x) = \arg\max_y P(Y=y|X=x)$ (mode of conditional distribution)

The Bayes error $R(f^*)$ is the irreducible error due to noise in the problem.

2. Empirical Risk Minimization (ERM)

Since $P(X,Y)$ is unknown, we cannot compute $R(f)$ directly. Instead, we minimize the empirical risk:

$$\hat{R}(f) = \frac{1}{n}\sum_{i=1}^{n} \ell(y_i, f(\mathbf{x}_i))$$

The ERM principle selects:

$$\hat{f} = \arg\min_{f \in \mathcal{H}} \hat{R}(f)$$

The Fundamental Challenge

We care about $R(\hat{f})$ (generalization error), but we only have access to $\hat{R}(\hat{f})$ (training error). The gap between these is the generalization gap:

$$R(\hat{f}) - \hat{R}(\hat{f})$$

3. The Bias-Variance Decomposition

For squared loss, we can decompose the expected error of a learning algorithm into three components:

$$\mathbb{E}_{\mathcal{D}}[R(\hat{f})] = \text{Bias}^2 + \text{Variance} + \text{Noise}$$

Components

1. Bias: Error from approximating a complex function with a simpler model

$$\text{Bias}^2 = \mathbb{E}_{\mathcal{D}}[\hat{f}(\mathbf{x})] - f^*(\mathbf{x})$$

2. Variance: Error from sensitivity to training set fluctuations

$$\text{Variance} = \mathbb{E}_{\mathcal{D}}[(\hat{f}(\mathbf{x}) - \mathbb{E}_{\mathcal{D}}[\hat{f}(\mathbf{x})])^2]$$

3. Noise: Irreducible error from the problem itself

$$\text{Noise} = \mathbb{E}[(Y - f^*(\mathbf{x}))^2]$$

The Bias-Variance Tradeoff

• Simple models: High bias, low variance (underfitting)
• Complex models: Low bias, high variance (overfitting)
• Optimal model: Balances bias and variance

4. Overfitting and Underfitting

Underfitting

Model is too simple to capture the underlying pattern:

• High training error
• High test error
• High bias, low variance

Overfitting

Model learns noise in training data:

• Low training error
• High test error
• Low bias, high variance

Detecting Overfitting

Monitor both training and validation errors:

• Training error decreases continuously with model complexity
• Validation error decreases then increases (U-shaped curve)
• Large gap between training and validation error indicates overfitting

5. Regularization

Regularization adds a penalty term to control model complexity:

$$\min_{f \in \mathcal{H}} \hat{R}(f) + \lambda \Omega(f)$$

where $\Omega(f)$ measures model complexity and $\lambda > 0$ controls regularization strength.

Common Regularization Methods

L2 Regularization (Ridge)

$$\Omega(\mathbf{w}) = \|\mathbf{w}\|^2 = \sum_{j=1}^{d} w_j^2$$

Encourages small weights, smooth solutions. Shrinks all weights proportionally.

L1 Regularization (Lasso)

$$\Omega(\mathbf{w}) = \|\mathbf{w}\|_1 = \sum_{j=1}^{d} |w_j|$$

Encourages sparsity. Sets some weights exactly to zero, performing feature selection.

Elastic Net

$$\Omega(\mathbf{w}) = \alpha \|\mathbf{w}\|_1 + (1-\alpha) \|\mathbf{w}\|^2$$

Combines L1 and L2. Gets benefits of both sparsity and stability.

6. Model Capacity and VC Dimension

VC Dimension

The Vapnik-Chervonenkis (VC) dimension measures the capacity of a hypothesis class $\mathcal{H}$:

Definition: The largest number of points that can be shattered (perfectly separated for all possible labellings) by $\mathcal{H}$.

Examples

• Linear classifiers in $\mathbb{R}^d$: VC dimension = $d + 1$
• Decision stumps: VC dimension = 2
• Polynomial classifiers of degree $p$ in $\mathbb{R}^d$: VC dimension ≈ $\binom{d+p}{p}$

Generalization Bound

With probability at least $1 - \delta$:

$$R(\hat{f}) \leq \hat{R}(\hat{f}) + O\left(\sqrt{\frac{VC(\mathcal{H}) \log(n/VC(\mathcal{H})) + \log(1/\delta)}{n}}\right)$$

Key insights:

• Larger VC dimension → larger generalization gap
• More training data → smaller generalization gap ($\propto 1/\sqrt{n}$)
• Gap decreases as $O(1/\sqrt{n})$ with sample size

7. PAC Learning

Probably Approximately Correct (PAC) learning provides a formal framework for learnability.

Definition

A hypothesis class $\mathcal{H}$ is PAC-learnable if there exists an algorithm that, for any distribution $P(X,Y)$, any $\epsilon > 0$, and any $\delta > 0$, using

$$n = O\left(\frac{1}{\epsilon^2}\left(VC(\mathcal{H}) + \log\frac{1}{\delta}\right)\right)$$

training examples, outputs a hypothesis $\hat{f}$ such that with probability at least $1-\delta$:

$$R(\hat{f}) \leq R(f^*) + \epsilon$$

Sample Complexity

The number of samples needed to learn grows linearly with VC dimension and logarithmically with $1/\delta$.

8. No Free Lunch Theorem

The No Free Lunch (NFL) theorem states that averaged over all possible problems, every learning algorithm has the same performance.

Implications

• No universally best learning algorithm
• Algorithm performance depends on problem structure
• Inductive biases are necessary for learning
• Domain knowledge guides algorithm selection

In Practice

Real-world problems have structure that allows certain algorithms to excel. The goal is to match algorithm assumptions to problem characteristics.

9. Learning Curves

Learning curves show how performance changes with training set size:

$$\mathbb{E}[R(\hat{f}_n)] \quad \text{vs.} \quad n$$

Typical Behavior

• Small $n$: High variance, error dominated by estimation error
• Large $n$: Error approaches bias, cannot improve further without more complex model
• Optimal $n$: Depends on problem complexity and model capacity

10. Connection to LLMs

Statistical learning theory provides foundations for understanding LLMs:

• Scaling laws: LLM performance follows power laws in data size, model size, and compute
• Generalization: Despite massive overparameterization, LLMs generalize through implicit regularization
• Bias-variance: Pre-training reduces bias, fine-tuning controls variance
• Double descent: LLMs exhibit double descent phenomenon where performance improves again after classical overfitting region
• In-context learning: Can be viewed as empirical risk minimization over demonstration examples
• Transfer learning: Pre-trained models reduce effective VC dimension for downstream tasks

Key Takeaways

• Machine learning seeks functions that minimize expected risk over unknown distributions
• Bias-variance tradeoff is fundamental: simple models underfit, complex models overfit
• Regularization controls model complexity and improves generalization
• VC dimension measures hypothesis class capacity and bounds generalization error
• Generalization gap decreases as $O(1/\sqrt{n})$ with sample size
• PAC learning provides formal guarantees on sample complexity
• No algorithm is universally best; match algorithm to problem structure
• Statistical theory explains modern deep learning phenomena like double descent