14 Bias and Variance Analysis

Two Perspective on Learning: VS vs. Bias-Variance

Learning theory provides two distinct frameworks for understanding why models succeed or fail:

VC Analysis (The “Worst Case” View)

• Goal: To provide a uniform bound on error that holds for any training set $D$.\
• Loss Function: Typically uses 0-1 loss (classification)
• Intuition: $E_{out}\le E_{in}+\Omega$, where $\Omega$ is a penalty for model complexity.

Bias-Variance Analysis (The “Average Case” View)

• Goal: To decompose the average out-of-sample error across all possible training sets.
• Loss Function: Uses squared error loss, as its differentiability allows for cleaner mathematical decomposition
• Applicability: Primarily used for real-valued target functions.

Mathematical Decomposition of Error

To quantify the tradeoff, we assume the existence of an average hypothesis $\bar{g}(x)$, which is what you would get if you trained on an infinite number of different datasets.

The Average Hypothesis

$$\bar{g}(x)={\mathbb{E}}_{\mathcal{D}}[g^{(\mathcal{D})}(x)]\approx \frac{1}{K}\sum _{k=1}^K{g}^{({\mathcal{D}}_k)}(x)$$

The Three Components of $E_{out}$

The expected out-of-sample error at a point $x$ can be broken down into three distinct parts

1. Bias: $(\bar{g}(x)-f(x){)}^2$. This is how far the “average” prediction is from the truth.
2. Variance: ${\mathbb{E}}_{\mathcal{D}}[(g^{(\mathcal{D})}(x)-\bar{g}(x){)}^2]$. This is the fluctuation of individual models around their average.
3. Noise (${\sigma }^2$): ${\mathbb{E}}_{\mathbf{x},ϵ}[ϵ(\mathbf{x}{)}^2]$. This is the inherent randomness in the target distribution $P(y|x)$.

Intuition

Think of a dartboard. Low Bias/Low Var is a tight cluster at the bullseye. High Bias/Low Var is a tight cluster far from the bullseye. Low Bias/High Var is a loose cluster centered around the bullseye

The Complexity Tradeoff

Model complexity directly impacts the balance between bias and variance:

• Simple Models ($\downarrow$ Complexity):
• Have High Bias (cannot represent complex target functions).
• Have Low Variance (very stable; predictions don’t change much with different data).
• Complex Models ($\uparrow$ Complexity):
• Have Low Bias (can fit almost any pattern).
• Have High Variance (highly sensitive to noise; “behave wildly” after seeing specific data).

Example: Learning $\sin (\pi x)$ with $N=2$

Consider fitting two points from a sine wave:

• Model 0 (${\mathcal{H}}_0$ - Constant line): High bias (0.50) but low variance (0.25). Resulting $E_{out}=0.75$.
• Model 1 (${\mathcal{H}}_1$ - Linear line): Lower bias (0.21) but massive variance (1.69). Resulting $E_{out}=1.90$.
• Insight: In this small-data scenario, the simpler model actually performs better because its variance is so much lower.

Learning Curves

Learning curve tracks how $E_{in}$ and $E_{out}$ change as the number of training points $N$ increases

• As $N\to \infty$: Both $E_{in}$ and $E_{out}$ converge toward the noise level ${\sigma }^2$.
• Linear Regression Case:
  • $E_{in}\approx {\sigma }^2(1-\frac{d+1}{N})$
  • $E_{out}\approx {\sigma }^2(1+\frac{d+1}{N})$
  • Generalisation Error $\approx 2{\sigma }^2(\frac{d+1}{N})$.