Lecture 3: Linear Regression Plus

Feature Engineering & Regularization

Course: MPS311/439: Machine Learning
Week: 3 of 11
Lecturer: Dr. Wei Xing
Expected Reading Time: 90 minutes

Table of Contents

  1. Introduction & Motivation
  2. From Lines to Curves: Feature Engineering
  3. The Dark Side: When Power Becomes a Problem
  4. The Solution: Regularization
  5. Tuning λ: Cross-Validation
  6. Bringing It All Together
  7. Summary & The Bigger Picture
  8. Practice Problems
  9. Appendix: Advanced Topics for MPS439

1. Introduction & Motivation

1.1 The Netflix Prize: A Machine Learning Success Story

Between 2006 and 2009, Netflix ran one of the most famous machine learning competitions in history. The challenge was simple: improve their movie recommendation algorithm by at least 10%. The prize? $1 million.

Thousands of teams competed, and the winning solution didn't come from a revolutionary new algorithm. Instead, it came from two key insights:

  1. Sophisticated feature engineering - Creating powerful predictive features from basic user and movie data
  2. Ensemble methods with regularization - Combining multiple models while preventing overfitting

The difference between winning and losing wasn't access to better data or more computing power. It was understanding when to add complexity (feature engineering) and when to constrain it (regularization).

Key Lesson: In machine learning, how you transform and control your features is often more important than the base algorithm you choose.

1.2 Where We Are in the Course

Last week (Week 2):

This week:
We extend linear regression with two powerful techniques that work together:

  1. Feature Engineering - Transform simple inputs into powerful predictors
  2. Regularization - Prevent models from becoming too complex

The journey ahead:

1.3 Learning Objectives

By the end of these notes, you will be able to:

✓ Transform features to capture non-linear relationships using polynomial features and interactions
✓ Recognize and diagnose overfitting through train/test performance gaps
✓ Apply Ridge and Lasso regression to prevent overfitting while maintaining model power
✓ Use cross-validation to tune hyperparameters without touching the test set
✓ Implement the complete pipeline in sklearn with proper data handling

Let's begin our journey by understanding why basic linear regression sometimes isn't enough.

2. From Lines to Curves: Feature Engineering

2.1 The Limitation of Straight Lines

In Week 2, we learned that linear regression fits a straight line (or hyperplane) to our data:

y^=w1x1+w2x2+⋯+wpxp+w0\hat{y} = w_1 x_1 + w_2 x_2 + \cdots + w_p x_p + w_0

This works beautifully when the true relationship between features and target is linear. But what happens when it's not?

Example: House Prices vs. Age

Consider predicting house prices based on the age of the house. You might expect older houses to be cheaper (depreciation, outdated features). But let's look at real market data:

Curved Relationship
Figure 2.1: House prices don't follow a straight line. The relationship is U-shaped.

What's happening here?

A straight line fundamentally cannot capture this U-shaped relationship. No matter how we adjust w1w_1 (the slope), we're limited to predictions that either always increase or always decrease with age.

Mathematical perspective:

The natural question: How can we fit curves using linear regression?

2.2 The Brilliant Solution: Polynomial Features

Here's the key insight that unlocks tremendous power:

We can't make the model non-linear, but we can make the features non-linear!

2.2.1 The Core Transformation

Instead of using age directly, let's create new features:

Original feature:
x=[age]x = [\text{age}]

Polynomial features (degree 2):
x′=[age,age2]x' = [\text{age}, \text{age}^2]

Polynomial features (degree 3):
x′=[age,age2,age3]x' = [\text{age}, \text{age}^2, \text{age}^3]

Now our model becomes:

Degree 2 (Quadratic):
y^=w2⋅age2+w1⋅age+w0\hat{y} = w_2 \cdot \text{age}^2 + w_1 \cdot \text{age} + w_0

Degree 3 (Cubic):
y^=w3⋅age3+w2⋅age2+w1⋅age+w0\hat{y} = w_3 \cdot \text{age}^3 + w_2 \cdot \text{age}^2 + w_1 \cdot \text{age} + w_0

The critical insight (highlight this):

The model is still linear in the parameters w\mathbf{w}. We haven't changed the model class—we've only changed the input features!

This means:

2.2.2 Connection to Mathematics You Know

Taylor Series: From mathematical analysis, you know that any smooth function can be approximated by polynomials:

f(x)≈a0+a1x+a2x2+a3x3+⋯f(x) \approx a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots

Weierstrass Approximation Theorem: Every continuous function on a closed interval can be uniformly approximated by polynomials.

What we're doing in machine learning is learning the coefficients aia_i from data rather than deriving them analytically!

2.3 Seeing Polynomials in Action

Let's systematically explore what happens as we increase the polynomial degree. We'll use the same house price data throughout:

Polynomial Progression
Figure 2.2: Progressive polynomial fits showing increasing complexity. Notice how training performance improves but test performance eventually degrades.

Let's analyze each degree:

Degree 1: Linear (Underfitting)

Model: y^=w1⋅age+w0\hat{y} = w_1 \cdot \text{age} + w_0

Observations:

Diagnosis: High bias - Model is too simple to capture the true pattern

Degree 2: Quadratic (Just Right!)

Model: y^=w2⋅age2+w1⋅age+w0\hat{y} = w_2 \cdot \text{age}^2 + w_1 \cdot \text{age} + w_0

Observations:

Diagnosis: Sweet spot - Captures true relationship without overfitting

Degree 3: Cubic (Still Acceptable)

Model: y^=w3⋅age3+w2⋅age2+w1⋅age+w0\hat{y} = w_3 \cdot \text{age}^3 + w_2 \cdot \text{age}^2 + w_1 \cdot \text{age} + w_0

Observations:

Diagnosis: Starting to show signs of overfitting—training improved but test got worse

Degree 5: Noticeable Oscillations

Observations:

Diagnosis: Warning signs - Beginning to fit noise

Degree 10: Severe Overfitting

Observations:

Diagnosis: Severe overfitting - Model has memorized training data

2.4 The Pattern: Training vs. Test Performance

The key observation from Figure 2.2:

Training error (R²):

Test error (R²):

This divergence between training and test performance is the signature of overfitting.

2.5 Feature Explosion: The Combinatorial Problem

With multiple original features, polynomial features explode combinatorially. Consider a dataset with 8 features:

Original features:
size, bedrooms, bathrooms, age, location_score, garden, garage, stories\text{size, bedrooms, bathrooms, age, location\_score, garden, garage, stories}

Polynomial degree 2 includes:

  1. All originals: 8 features
  2. All squares: size², bedrooms², ..., stories² (8 more features)
  3. All interactions: size×bedrooms, size×bathrooms, ..., garage×stories
    • Number of pairs: (82)=28\binom{8}{2} = 28 features

Total for degree 2: 8 + 8 + 28 = 45 features

General formula:
The number of features with polynomial degree dd and pp original features:

Number of features=(p+dd)\text{Number of features} = \binom{p + d}{d}

Comparison table:

Original Features (p) Degree (d) Total Features Growth Factor
8 1 8 1×
8 2 45 5.6×
8 3 165 20.6×
8 5 1,001 125×
8 10 43,758 5,470×

The excitement:

The question:
With all this power to create features, are we done? Should we always use high-degree polynomials?

Let's look more carefully at what happens with these high-degree polynomials...

2.6 A Brief Note on Interaction Terms

Beyond polynomials of individual features, we can create interaction terms that multiply features together:

Example: For house prices, consider:

The effect of size depends on the number of bedrooms. We can capture this with:

interaction=size×bedrooms\text{interaction} = \text{size} \times \text{bedrooms}

Our model becomes:

y^=w1⋅size+w2⋅bedrooms+w3⋅(size×bedrooms)+w0\hat{y} = w_1 \cdot \text{size} + w_2 \cdot \text{bedrooms} + w_3 \cdot (\text{size} \times \text{bedrooms}) + w_0

The w3w_3 coefficient captures how the combined effect differs from the sum of individual effects.

Note: Interaction terms are automatically included when you use PolynomialFeatures(degree=2) in sklearn. For degree 2 with pp features, you get:

We'll explore interactions more in the lab, but the key point is: they give us even more features and even more modeling power!

3. The Dark Side: When Power Becomes a Problem

3.1 The Troubling Observations

Let's return to our degree 10 polynomial from Section 2.3. On the surface, it looks amazing:

But when we evaluate on the test set:

The puzzle: How can a model that fits training data so well perform so poorly on test data?

3.2 Understanding Overfitting

3.2.1 The Formal Definition

Overfitting occurs when a model learns the noise in the training data rather than the underlying signal, resulting in poor generalization to new data.

Components of any dataset:

Observed data=True signal+Random noise\text{Observed data} = \text{True signal} + \text{Random noise}

For our house prices:

What good models do:

What overfit models do:

3.2.2 The Memorization Analogy

Consider preparing for an exam:

Good learning (analogous to good fit):

Memorization (analogous to overfitting):

Overfitting is the machine learning equivalent of memorization without understanding.

3.3 The Bias-Variance Tradeoff

To understand overfitting deeply, we need to decompose prediction error into its components:

Bias-Variance Tradeoff
Figure 3.1: Decomposition of prediction error into bias, variance, and irreducible error.

Mathematical decomposition:

E[(True value−Prediction)2]=Bias2+Variance+Irreducible Error\mathbb{E}[(\text{True value} - \text{Prediction})^2] = \text{Bias}^2 + \text{Variance} + \text{Irreducible Error}

Let's understand each component:

Bias

Definition: Error from overly simplistic assumptions in the learning algorithm.

Characteristics:

Example: Using a straight line for a U-shaped relationship

Mathematical intuition: Bias = E[f^(x)]−f(x)\mathbb{E}[\hat{f}(x)] - f(x)

Variance

Definition: Error from sensitivity to small fluctuations in the training data.

Characteristics:

Example: Degree 10 polynomial

Mathematical intuition: Variance = E[(f^(x)−E[f^(x)])2]\mathbb{E}[(\hat{f}(x) - \mathbb{E}[\hat{f}(x)])^2]

Irreducible Error

Definition: Error that cannot be eliminated by any model.

Sources:

Important: This sets a lower bound on achievable error. Even perfect models can't eliminate this.

The Tradeoff

Here's the fundamental tension in machine learning:

Simple models (e.g., linear):

Complex models (e.g., degree 10 polynomial):

Optimal models:

Train and Test Error vs Complexity
Figure 3.2: The classic U-curve showing how training and test errors diverge with model complexity.

Interpreting the curves:

Training error (blue, decreasing):

Test error (orange, U-shaped):

The sweet spot:

3.4 Why Does Overfitting Happen?

The Degrees of Freedom Problem

Intuitive explanation: With nn data points and pp parameters:

Example:

With 165 parameters and only 50 data points, the model has so much freedom that it can fit almost anything—including noise.

Fitting Noise Instead of Signal

Concrete example:

Suppose the true relationship is:
price=300−5⋅age+0.05⋅age2+ϵ\text{price} = 300 - 5 \cdot \text{age} + 0.05 \cdot \text{age}^2 + \epsilon

where ϵ∼N(0,10,000)\epsilon \sim \mathcal{N}(0, 10,000) is random noise.

What a degree 2 polynomial learns:

What a degree 10 polynomial learns:

3.5 Recognizing Overfitting in Practice

Warning signs checklist:

✗ Large train/test performance gap:

Training R² = 0.95
Test R² = 0.60
Gap = 0.35  ← RED FLAG!

✗ Very large coefficient magnitudes:

w = [1,253,000, -1,187,000, 1,045,000, -998,000, ...]

These huge, oscillating values indicate the model is "fighting itself" to fit noise.

✗ Model is unstable:

✗ Predictions are erratic:

✗ Training performance "too good":

3.6 The Crisis

Where we stand:

✓ Feature engineering gave us the power to fit complex, non-linear patterns
✗ Too much power leads to overfitting
✗ Can't simply use all possible features

The fundamental question:

How do we keep the good (curve-fitting ability) without the bad (overfitting)?

What we need:

The answer: Regularization

In the next section, we'll discover how to constrain model complexity while preserving its expressive power.

4. The Solution: Regularization

4.1 The Core Intuition: Occam's Razor

William of Ockham (14th century):

"Entities should not be multiplied beyond necessity"

Modern interpretation:

Given multiple models that fit the data equally well, prefer the simpler one.

Why simplicity matters:

The machine learning implementation:

Instead of reducing the number of features (which we can't always do), we penalize complexity directly in the loss function.

Key Insight: We can't reduce features, but we can penalize large weights that indicate overfitting.

Analogy:

4.2 Ridge Regression (L2 Regularization)

4.2.1 The Modified Loss Function

Original loss function (from Week 2):

J(w)=1n∑i=1n(yi−y^i)2J(\mathbf{w}) = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2

This is just Mean Squared Error—we want to minimize prediction errors.

Ridge loss function (new):

JRidge(w)=1n∑i=1n(yi−y^i)2⏟Data Fit Term+λ∑j=1pwj2⏟Regularization Term\boxed{J_{\text{Ridge}}(\mathbf{w}) = \underbrace{\frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2}_{\text{Data Fit Term}} + \underbrace{\lambda \sum_{j=1}^{p} w_j^2}_{\text{Regularization Term}}}

Understanding each component:

Term 1: Mean Squared Error (Data Fit)

Term 2: L2 Penalty (Regularization)

The λ (lambda) hyperparameter:

Important note (highlight):

We typically don't penalize the bias term w0w_0. The regularization applies only to w1,w2,…,wpw_1, w_2, \ldots, w_p.

Why not penalize w0w_0?

4.2.2 Why Square the Weights?

Question: Why use wj2w_j^2 instead of ∣wj∣|w_j| or wj4w_j^4?

Reason 1: Smooth Optimization

Reason 2: Proportional Penalty

Let's see how the penalty scales:

Weight ww w2w^2 Penalty (λw2\lambda w^2 with λ=1\lambda=1)
Tiny 0.1 0.01 0.01 (very small)
Small 1.0 1.00 1.00
Medium 5.0 25.00 25.00
Large 10.0 100.00 100.00
Huge 50.0 2,500.00 2,500.00

Observation: Large weights are penalized disproportionately more!

Reason 3: Convexity

Reason 4: Connection to Gaussian Prior

4.2.3 The Modified Normal Equation

Let's derive the solution for Ridge regression, building on what we learned in Week 2.

Step 1: Write loss in matrix form

J(w)=1n(y−Xw)T(y−Xw)+λwTwJ(\mathbf{w}) = \frac{1}{n}(\mathbf{y} - \mathbf{Xw})^T(\mathbf{y} - \mathbf{Xw}) + \lambda \mathbf{w}^T\mathbf{w}

Note: wTw=∑j=1pwj2\mathbf{w}^T\mathbf{w} = \sum_{j=1}^p w_j^2 is just the L2 norm squared.

Step 2: Expand the MSE term (like Week 2)

J(w)=1n(yTy−2yTXw+wTXTXw)+λwTwJ(\mathbf{w}) = \frac{1}{n}(\mathbf{y}^T\mathbf{y} - 2\mathbf{y}^T\mathbf{Xw} + \mathbf{w}^T\mathbf{X}^T\mathbf{Xw}) + \lambda \mathbf{w}^T\mathbf{w}

Step 3: Take the gradient

Using matrix calculus rules:

∇wJ=2n(−XTy+XTXw)+2λw\nabla_{\mathbf{w}} J = \frac{2}{n}(-\mathbf{X}^T\mathbf{y} + \mathbf{X}^T\mathbf{Xw}) + 2\lambda\mathbf{w}

Step 4: Set gradient to zero

At the minimum: ∇wJ=0\nabla_{\mathbf{w}} J = \mathbf{0}

−XTy+XTXw+nλw=0-\mathbf{X}^T\mathbf{y} + \mathbf{X}^T\mathbf{Xw} + n\lambda\mathbf{w} = \mathbf{0}

Step 5: Rearrange

XTXw+nλw=XTy\mathbf{X}^T\mathbf{Xw} + n\lambda\mathbf{w} = \mathbf{X}^T\mathbf{y}

(XTX+nλI)w=XTy(\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I})\mathbf{w} = \mathbf{X}^T\mathbf{y}

Step 6: Solve for w

w^Ridge=(XTX+nλI)−1XTy\boxed{\mathbf{\hat{w}}_{\text{Ridge}} = (\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}}

Compare to standard Normal Equation:

Key difference: We add nλIn\lambda\mathbf{I} to XTX\mathbf{X}^T\mathbf{X}

Benefits of this modification:

✓ Always invertible: XTX+nλI\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I} is positive definite for any λ>0\lambda > 0
✓ Works even when p>np > n: Standard regression fails, Ridge works
✓ Numerical stability: Adding nλIn\lambda\mathbf{I} improves conditioning
✓ Closed-form solution: No iterative optimization needed

4.2.4 How Ridge Affects Coefficients

Let's visualize what happens to coefficients as we vary λ\lambda:

Ridge Coefficient Paths
Figure 4.1: Ridge coefficient paths showing smooth shrinkage toward zero as λ increases.

Reading the plot:

X-axis: log⁡10(λ)\log_{10}(\lambda) from -3 to 4

Y-axis: Coefficient values

Each colored line: One coefficient's path as λ\lambda changes

Key observations:

  1. λ=0\lambda = 0 (far left):

    • Some coefficients are very large (e.g., w3≈1000w_3 \approx 1000)
    • Others very negative (e.g., w5≈−950w_5 \approx -950)
    • Coefficients "fighting each other" to fit training data

  2. λ\lambda increases:

    • All coefficients shrink smoothly
    • Large coefficients shrink faster (quadratic penalty!)
    • Paths are continuous and smooth

  3. λ=100\lambda = 100:

    • All coefficients are moderate size
    • More balanced magnitudes
    • Still contributing to predictions

  4. λ=10,000\lambda = 10,000 (far right):

    • All coefficients ≈ 0
    • Model essentially predicts the mean
    • Underfitting

Critical property (highlight):

Ridge shrinks coefficients smoothly toward zero but never exactly to zero. All features remain in the model.

Why never exactly zero?

4.2.5 Geometric Interpretation

Ridge regression can be formulated as a constrained optimization problem:

Equivalent formulations:

Penalty form (what we've been using):
min⁡wMSE(w)+λ∑wj2\min_{\mathbf{w}} \text{MSE}(\mathbf{w}) + \lambda \sum w_j^2

Constraint form:
min⁡wMSE(w)subject to∑wj2≤t\min_{\mathbf{w}} \text{MSE}(\mathbf{w}) \quad \text{subject to} \quad \sum w_j^2 \leq t

For every λ\lambda, there's a corresponding tt (and vice versa).

Geometric picture (for p=2p=2 weights):

Ridge vs Lasso Comparison
Figure 4.2: Geometric interpretation showing why Ridge creates smooth shrinkage (circular constraint) and Lasso creates sparsity (diamond constraint with corners on axes).

Left panel (Ridge):

MSE contours (blue ellipses):

Constraint region (red circle):

Solution (green dot):

Why no sparsity?

4.3 Lasso Regression (L1 Regularization)

4.3.1 The L1 Penalty

Lasso stands for: Least Absolute Shrinkage and Selection Operator

The name hints at two properties: shrinkage (like Ridge) and selection (unique to Lasso).

Lasso loss function:

JLasso(w)=1n∑i=1n(yi−y^i)2+λ∑j=1p∣wj∣\boxed{J_{\text{Lasso}}(\mathbf{w}) = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda \sum_{j=1}^{p} |w_j|}

Key difference from Ridge:

Seems like a small change, but the consequences are profound!

4.3.2 The Sparsity Property

The remarkable feature of Lasso:

Lasso forces some coefficients to exactly zero, performing automatic feature selection!

Let's see this in action:

Lasso Coefficient Paths
Figure 4.3: Lasso coefficient paths showing coefficients hitting exactly zero, creating sparse solutions.

Reading the plot:

Progression as λ\lambda increases:

λ=0\lambda = 0 (far left):

λ=0.1\lambda = 0.1:

λ=1\lambda = 1:

λ=10\lambda = 10:

λ=100\lambda = 100:

The "wedge" pattern:

Why this is powerful:

✓ Automatic feature selection: Don't need to manually choose which features to include
✓ Interpretability: Sparse models are easier to understand and explain
✓ Efficiency: Fewer features → faster predictions
✓ Overfitting prevention: Using fewer features reduces model complexity

4.3.3 Why L1 Creates Sparsity: Geometric Intuition

Return to geometric interpretation (Right panel of Figure 4.2):

Constraint region (red diamond):

The key insight:

Because the constraint region has sharp corners at the axes, and because these corners are the "pointy bits" that stick out furthest in the axis directions, MSE ellipses are likely to touch the constraint region at a corner.

At corners:

Result: Sparse solutions naturally emerge from the geometry!

Contrast with Ridge:

In higher dimensions:

4.3.4 Mathematical Note: Non-Differentiability

Technical detail for mathematically inclined students:

The L1 penalty ∣w∣|w| has a problem: it's not differentiable at w=0w = 0!

ddw∣w∣={+1if w>0−1if w<0undefinedif w=0\frac{d}{dw}|w| = \begin{cases} +1 & \text{if } w > 0 \\ -1 & \text{if } w < 0 \\ \text{undefined} & \text{if } w = 0 \end{cases}

Consequences:

✗ No closed-form solution like Ridge
✗ Can't use Normal Equation
✓ Must use iterative optimization (coordinate descent, LARS algorithm)

The good news:

Why this creates sparsity:

4.4 Ridge vs. Lasso: When to Use Which?

Let's synthesize everything into practical guidance:

Comparison table:

Aspect Ridge (L2) Lasso (L1)
Penalty λ∑wj2\lambda \sum w_j^2 λ∑∣wj∣\lambda \sum |w_j|
Sparsity No (all weights non-zero) Yes (some weights exactly zero)
Feature selection No Yes (automatic)
Solution Closed-form (fast) Iterative (slower)
Stability with correlated features Good Can be unstable
Interpretability All features matter (harder to explain) Few features (easier to explain)
Use when All features likely relevant Many irrelevant features suspected

Decision framework:

Use Ridge when:

Example: Medical diagnosis with many biomarkers, most of which have some predictive value

Use Lasso when:

Example: Gene expression data with 10,000 genes but only a handful relevant to disease

Try both when:

The safe default:

4.5 Example: Regularization in Action

Let's see concrete results on our house price dataset:

Regularization Results
Figure 4.4: Performance comparison showing how regularization reduces train/test gap.

Results summary:

Model Features Used Train R² Test R² Train-Test Gap
Linear (baseline) 8 0.60 0.58 0.02
Polynomial deg 3 165 0.98 0.42 0.56 ⚠️
Ridge (λ=10) 165 0.82 0.77 0.05 ✓
Lasso (λ=1) 23 of 165 0.80 0.76 0.04 ✓

Key observations:

  1. Unregularized polynomial:

    • Excellent training performance (R² = 0.98)
    • Terrible test performance (R² = 0.42)
    • Huge gap of 0.56 → Classic overfitting!

  2. Ridge with λ=10:

    • Training performance decreased (R² = 0.82)
    • But test performance increased (R² = 0.77)!
    • Small gap of 0.05 → Good generalization
    • Uses all 165 features but with small coefficients

  3. Lasso with λ=1:

    • Similar performance to Ridge (R² = 0.76 on test)
    • Uses only 23 out of 165 features
    • Much simpler, more interpretable model
    • Small gap of 0.04 → Good generalization

The lesson:

Regularization trades a small decrease in training performance for a large improvement in test performance. This is exactly what we want!

Coefficient comparison:

Unregularized:

w = [1253, -1187, 1045, -998, 876, -823, ...]

Large, oscillating values indicating overfitting.

Ridge (λ=10):

w = [12.5, -10.3, 8.7, -6.2, 4.8, -3.9, ...]

Small, controlled values. All features contribute modestly.

Lasso (λ=1):

w = [15.3, -11.2, 0, 0, 9.1, 0, 0, 7.8, ...]

Sparse! Many exact zeros. Only important features survive.

5. Tuning λ: Cross-Validation

5.1 The Hyperparameter Problem

We've introduced regularization to control overfitting. But now we face a new challenge:

How do we choose the right value of λ?

What happens with different λ values:

What doesn't work:

❌ Maximize training performance:

❌ Maximize test performance:

What we need:

The solution: Cross-validation

5.2 K-Fold Cross-Validation

5.2.1 The Core Idea

Cross-validation cleverly splits the training data to simulate having a separate validation set:

Use part of the training data for training, part for validation, and rotate which part is used for validation.

K-Fold Illustration
Figure 5.1: 5-fold cross-validation showing how data is split and rotated.

5.2.2 The Algorithm (K=5 example)

Step 1: Split training data into K=5 equal folds

Suppose we have 1000 training examples:

Step 2: Train and validate K times, rotating the validation fold

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Step 3: Average the scores

CV Score=Score1+Score2+Score3+Score4+Score55\text{CV Score} = \frac{\text{Score}_1 + \text{Score}_2 + \text{Score}_3 + \text{Score}_4 + \text{Score}_5}{5}

Often also report standard deviation: CV Score±Std\text{CV Score} \pm \text{Std}

5.2.3 Why Cross-Validation Works

Key properties:

✓ Every data point is validated exactly once

✓ Uses all training data efficiently

✓ Reduces variance in estimates

✓ No information leakage from test set

Statistical perspective:

Think of each fold's validation score as a sample from the distribution of possible validation scores. By averaging K samples, we get a more stable estimate of the true expected performance.

5.2.4 Choosing K

Common choices:

K = 5 (most common):

K = 10:

K = n (Leave-One-Out Cross-Validation):

Practical advice:

5.3 Grid Search: Finding Optimal λ

5.3.1 The Grid Search Process

Now we combine cross-validation with systematic exploration of λ values:

Step 1: Define grid of λ values to try

Use logarithmic spacing to cover wide range:

λ_values = [0.001, 0.01, 0.1, 1, 10, 100, 1000]

Why logarithmic?

Step 2: For each λ, run K-fold cross-validation

For λ = 0.001:
    Run 5-fold CV → CV Score = 0.654 ± 0.031
    
For λ = 0.01:
    Run 5-fold CV → CV Score = 0.702 ± 0.028
    
For λ = 0.1:
    Run 5-fold CV → CV Score = 0.748 ± 0.024
    
For λ = 1:
    Run 5-fold CV → CV Score = 0.771 ± 0.022
    
For λ = 10:
    Run 5-fold CV → CV Score = 0.778 ± 0.020  ← Best!
    
For λ = 100:
    Run 5-fold CV → CV Score = 0.742 ± 0.025
    
For λ = 1000:
    Run 5-fold CV → CV Score = 0.623 ± 0.029

Step 3: Select λ with best CV score

λ∗=10\lambda^* = 10 (highest CV R²)

Step 4: Retrain on full training set

Step 5: Evaluate on test set (once!)

5.3.2 Visualizing the Results

CV Error vs Lambda
Figure 5.2: Cross-validation error showing U-shaped curve with optimal λ marked.

Reading the plot:

X-axis: log⁡10(λ)\log_{10}(\lambda) from -3 to 3

Y-axis: Mean Squared Error (or could be R², depending on metric)

Two curves:

Training error (blue circles):

CV error (orange squares):

Optimal point (green vertical line):

Error bars:

Key observations:

  1. The U-curve reappears!

    • Left: Underfitting (too little regularization)
    • Right: Overfitting (too much regularization)
    • Middle: Sweet spot

  2. Training error always increases

    • Regularization constrains the model
    • Necessarily reduces training performance
    • This is the "cost" we pay for better generalization

  3. CV error provides guidance

    • Reliably identifies optimal λ
    • Prevents both overfitting (left) and underfitting (right)

5.4 The Three-Dataset Paradigm

We now work with three distinct datasets:

1. Training Set (60-70% of data)

2. Validation Set (implicit in cross-validation)

3. Test Set (20-30% of data)

The critical rule (highlight):

NEVER touch the test set until you have finalized your model and all hyperparameters!

Why this matters:

If you tune λ based on test performance:

The proper workflow:

1. Split data → Train (70%) | Test (30%)
2. Use ONLY training data for everything up to final evaluation
3. Within training data, use cross-validation
4. Select best λ based on CV performance
5. Retrain final model on full training set with best λ
6. Evaluate ONCE on test set
7. Report test performance as expected performance on new data

5.5 Practical Implementation Notes

Computational cost:

Grid search with:

This is usually affordable for linear models (fast to train).

Stratification:

For classification tasks:

For regression tasks:

Reproducibility:

Always set a random seed:

np.random.seed(42)

This ensures:

Parallel computation:

Cross-validation is "embarrassingly parallel":

6. Bringing It All Together

6.1 The Complete Machine Learning Pipeline

Let's synthesize everything into a comprehensive workflow:

Step-by-step pipeline:

1. Load and explore data
   - Understand features and target
   - Check for missing values, outliers
   - Visualize relationships
   
2. Split into train and test (FIRST THING!)
   - Typically 80/20 or 70/30 split
   - Stratify if classification
   - Set random seed for reproducibility
   
3. Feature engineering (on training data only!)
   - Create polynomial features
   - Create interaction terms
   - Compute feature statistics (mean, std) from training data
   
4. Feature scaling (critical for regularization!)
   - Fit scaler on training data
   - Transform both train and test using fitted scaler
   
5. Model selection via cross-validation
   - Try different λ values
   - Run K-fold CV for each
   - Select best λ based on CV score
   
6. Final model training
   - Retrain on full training set
   - Use optimal λ
   
7. Final evaluation
   - Evaluate on test set (once!)
   - Report performance
   - Compare to baseline

Critical principle (highlight):

Everything learned from data (feature statistics, optimal λ, model weights) must be learned from the training set only!

6.2 Why Feature Scaling is Critical for Regularization

This is one of the most important practical details!

The problem with unscaled features:

Consider predicting house prices with two features:

To increase predicted price by £100,000, the model could:

Option A: Increase size coefficient

Option B: Increase bedroom coefficient

The problem: Bedroom coefficient is penalized 250,000× more harshly!

This is unfair—the model will artificially favor using size over bedrooms, not because size is more predictive, but purely due to scale differences.

The solution: Standardization

Transform each feature to have mean = 0 and standard deviation = 1:

xscaled=x−μσx_{\text{scaled}} = \frac{x - \mu}{\sigma}

where μ\mu is the mean and σ\sigma is the standard deviation of the training data.

After scaling:

Critical implementation detail (highlight):

Fit the scaler on training data only, then apply to both train and test!

Why?

# WRONG - leaks information from test set
scaler.fit(np.concatenate([X_train, X_test]))

# CORRECT - only uses training data
scaler.fit(X_train)
X_train_scaled = scaler.transform(X_train)
X_test_scaled = scaler.transform(X_test)

Using test statistics would:

6.3 Implementation with sklearn

6.3.1 Key sklearn Components

Preprocessing:

from sklearn.preprocessing import PolynomialFeatures, StandardScaler

Models:

from sklearn.linear_model import Ridge, Lasso, ElasticNet

Model Selection:

from sklearn.model_selection import (
    train_test_split, 
    cross_val_score, 
    GridSearchCV
)

Pipelines:

from sklearn.pipeline import Pipeline

6.3.2 Why Use Pipelines?

Pipelines ensure correct order of operations and prevent data leakage:

Without pipeline (error-prone):

# Easy to make mistakes here!
poly = PolynomialFeatures(degree=2)
X_train_poly = poly.fit_transform(X_train)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train_poly)
# What if you forget to transform test set the same way?

With pipeline (safe):

pipeline = Pipeline([
    ('poly', PolynomialFeatures(degree=2)),
    ('scaler', StandardScaler()),
    ('ridge', Ridge(alpha=1.0))
])

# Everything happens in correct order automatically
pipeline.fit(X_train, y_train)
predictions = pipeline.predict(X_test)

Benefits:

6.3.3 Complete Example (Conceptual)

Here's the structure of a complete implementation:

# Step 1: Load data
from sklearn.datasets import fetch_california_housing
X, y = fetch_california_housing(return_X_y=True)

# Step 2: Train/test split
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# Step 3: Define pipeline
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures, StandardScaler
from sklearn.linear_model import Ridge

pipeline = Pipeline([
    ('poly', PolynomialFeatures(degree=2)),
    ('scaler', StandardScaler()),
    ('ridge', Ridge())
])

# Step 4: Grid search with cross-validation
from sklearn.model_selection import GridSearchCV

param_grid = {
    'ridge__alpha': [0.01, 0.1, 1, 10, 100, 1000]
}

grid_search = GridSearchCV(
    pipeline, 
    param_grid, 
    cv=5,  # 5-fold cross-validation
    scoring='r2',
    return_train_score=True
)

# Step 5: Fit (this does all the CV)
grid_search.fit(X_train, y_train)

# Step 6: Examine results
print(f"Best λ: {grid_search.best_params_['ridge__alpha']}")
print(f"Best CV R²: {grid_search.best_score_:.3f}")

# Step 7: Final evaluation on test set
test_r2 = grid_search.score(X_test, y_test)
print(f"Test R²: {test_r2:.3f}")

Note: Full working code with detailed explanations will be provided in the lab session. This conceptual overview shows the structure.

6.4 Interpreting Results

6.4.1 Performance Metrics Comparison

What to report:

Model: Ridge Regression with Polynomial Features (degree=2)
Regularization: λ = 10 (selected via 5-fold CV)

Performance:
- Training R²: 0.823
- CV R²: 0.778 ± 0.023
- Test R²: 0.771

Interpretation:
Model explains 77% of variance in target variable on unseen data.
Small train/test gap (5%) indicates good generalization without overfitting.
Cross-validation uncertainty (±0.023) shows results are stable.

Red flags to watch for:

✗ Large train/test gap: Training R² = 0.95, Test R² = 0.60

✗ Both scores low: Training R² = 0.55, Test R² = 0.52

✗ High CV uncertainty: CV R² = 0.70 ± 0.15

6.4.2 Coefficient Analysis

Ridge coefficients (λ = 10):

Feature          Coefficient    Interpretation
-------------------------------------------------
size             125.3          +£125 per sq ft
bedrooms         -15.7          -£16 per bedroom (holding size constant)
bathrooms        45.2           +£45 per bathroom
age              -2.8           -£3 per year older
size²            0.03           Quadratic effect of size
size×bedrooms    -0.5           Interaction effect

Why is bedrooms coefficient negative?

Comparing regularization strengths:

λ Size coef Bedroom coef L2 Norm
0.1 187.3 -89.2 245.6
1 152.1 -45.3 178.9
10 125.3 -15.7 128.4
100 67.8 -5.3 69.2

All coefficients shrink proportionally as λ increases.

6.4.3 Lasso's Feature Selection

Lasso with λ = 1:

Features that survived (non-zero coefficients):

  1. size
  2. size²
  3. bedrooms
  4. bathrooms
  5. size × bedrooms
  6. size × bathrooms
  7. bedrooms²
  8. age

Total: 8 features used (out of 45 available)

Features eliminated (zero coefficients):

Interpretation:

6.5 Common Pitfalls

Pitfall 1: Data leakage through scaling

# WRONG
scaler = StandardScaler()
X_all_scaled = scaler.fit_transform(np.vstack([X_train, X_test]))

# CORRECT
scaler = StandardScaler()
scaler.fit(X_train)
X_train_scaled = scaler.transform(X_train)
X_test_scaled = scaler.transform(X_test)

Pitfall 2: Tuning λ on test set

# WRONG
best_lambda = None
best_test_r2 = -np.inf
for lambda_val in [0.1, 1, 10, 100]:
    model = Ridge(alpha=lambda_val)
    model.fit(X_train, y_train)
    test_r2 = model.score(X_test, y_test)
    if test_r2 > best_test_r2:
        best_lambda = lambda_val
        best_test_r2 = test_r2

# CORRECT - use cross-validation on training set

Pitfall 3: Forgetting to scale before regularization

# WRONG - regularization without scaling
model = Ridge(alpha=1.0)
model.fit(X_train, y_train)

# CORRECT - scale first
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('ridge', Ridge(alpha=1.0))
])
pipeline.fit(X_train, y_train)

Pitfall 4: Using wrong metric consistently

# WRONG - mixed metrics
cv_score = cross_val_score(model, X_train, y_train, scoring='neg_mean_squared_error')
test_score = model.score(X_test, y_test)  # This returns R²!

# CORRECT - same metric throughout
cv_score = cross_val_score(model, X_train, y_train, scoring='r2')
test_score = model.score(X_test, y_test)  # Also R²

7. Summary & The Bigger Picture

7.1 The Journey Recapped

Let's trace the narrative arc of this lecture:

Act 1: Discovery (Feature Engineering)

Act 2: Crisis (Overfitting)

Act 3: Resolution (Regularization)

The synthesis:

Feature engineering + Regularization = Powerful yet controlled models

7.2 Core Takeaways

Box 1: Feature Engineering

Box 2: Overfitting

Box 3: Regularization

Box 4: Cross-Validation

7.3 The Bias-Variance Spectrum Revisited 

Underfitting          Sweet Spot          Overfitting
(High Bias)        (Balanced)          (High Variance)
     ↑                  ↑                    ↑
  λ → ∞           λ optimal              λ → 0
  
Too simple       Just right           Too complex
Misses patterns  Captures signal      Fits noise
Poor train perf  Good both perf      Great train, poor test

Regularization as the control knob:

7.4 Practical Wisdom

When starting a new project:

  1. ✓ Start simple: Begin with baseline linear regression
  2. ✓ Add complexity gradually: Try degree 2, then degree 3 if needed
  3. ✓ Default to Ridge: More stable than Lasso
  4. ✓ Use Lasso for interpretability: When stakeholders need simple explanations
  5. ✓ Always scale: Before any regularization
  6. ✓ Use CV religiously: Never tune on test set
  7. ✓ Monitor gaps: Watch train/test performance difference
  8. ✓ Be suspicious of perfection: Training R² = 1.0 is a red flag

Decision framework:

Do you need many polynomial/interaction features?
  ├─ No → Stick with linear regression
  └─ Yes → Use feature engineering
       ↓
       Is there overfitting (large train/test gap)?
       ├─ No → You're done!
       └─ Yes → Apply regularization
            ↓
            Need feature selection / interpretability?
            ├─ Yes → Try Lasso
            └─ No → Try Ridge
                 ↓
                 Use cross-validation to find optimal λ

7.5 Connection to the Universal ML Framework

Recall from Week 2:

MODEL → LOSS → OPTIMIZATION

This week's instantiation:

MODEL (extended):

LOSS (enhanced):

OPTIMIZATION (adapted):

This pattern repeats throughout ML:

7.6 Looking Ahead: Week 4 Preview

Transition from regression to classification:

This week (Regression):

Next week (Classification):

What carries over:

What changes:

The continuity:
All the hard work learning regularization and cross-validation pays off—we'll use these concepts again and again!

7.7 Final Thought

"The art of machine learning is knowing when to add complexity and when to constrain it. Feature engineering gives you the brush; regularization gives you the discipline."

The essence:

You now have both tools. Use them wisely!

8. Practice Problems

Conceptual Questions

Question 1: Explain in your own words why a degree 10 polynomial can have worse test performance than a degree 2 polynomial, despite fitting the training data much better.

Question 2: Why do we square the penalty term in Ridge regression (w2w^2) rather than using the absolute value (∣w∣|w|)? What would be different if we used w4w^4?

Question 3: A colleague says: "I'm getting perfect performance on my training set (R² = 1.0), so my model is perfect!" What would you tell them?

Question 4: Explain why we fit the StandardScaler on training data only, but then transform both training and test data using that fitted scaler.

Question 5: When would you choose Lasso over Ridge? When would you choose Ridge over Lasso?

Mathematical Problems

Problem 1: Given the following data points: (1, 3), (2, 5), (3, 4), manually compute the Ridge regression solution for a degree 1 model with λ = 1. Show all steps.

Problem 2: Consider polynomial features of degree 2 with 3 original features. How many total features will you have? List them explicitly.

Problem 3: A model has 100 features and 50 training examples. Explain why this might be problematic and how regularization helps.

Computational Problems

Problem 4: Load the sklearn diabetes dataset.

Problem 5: Generate synthetic data with a known U-shaped relationship:

y = 5 - 2*x + 0.3*x² + noise

Problem 6: Implement 5-fold cross-validation from scratch (don't use sklearn's cross_val_score). Verify your implementation gives similar results to sklearn.

Interpretation Problems

Problem 7: You train two models on the same data:

Ridge (λ=10): Train R² = 0.85, Test R² = 0.82
Lasso (λ=1):  Train R² = 0.83, Test R² = 0.81, Features used: 15/50

Which model would you choose and why?

Problem 8: After cross-validation, you get these results:

λ = 0.1:  CV R² = 0.70 ± 0.15
λ = 1:    CV R² = 0.75 ± 0.08
λ = 10:   CV R² = 0.74 ± 0.09
λ = 100:  CV R² = 0.68 ± 0.07

Which λ would you choose? Explain your reasoning considering both the mean and standard deviation.

9. Appendix: Advanced Topics for MPS439

This appendix contains advanced material for MPS439 students. MPS311 students are welcome to read this for enrichment, but it's not required.

9.1 Rigorous Derivation of Ridge Regression with Lagrange Multipliers

Constrained optimization formulation:

min⁡w1n∑i=1n(yi−wTxi)2subject to∑j=1pwj2≤t\min_{\mathbf{w}} \frac{1}{n}\sum_{i=1}^{n} (y_i - \mathbf{w}^T\mathbf{x}_i)^2 \quad \text{subject to} \quad \sum_{j=1}^{p} w_j^2 \leq t

Form the Lagrangian:

L(w,λ)=1n∑i=1n(yi−wTxi)2+λ(∑j=1pwj2−t)\mathcal{L}(\mathbf{w}, \lambda) = \frac{1}{n}\sum_{i=1}^{n} (y_i - \mathbf{w}^T\mathbf{x}_i)^2 + \lambda\left(\sum_{j=1}^{p} w_j^2 - t\right)

KKT (Karush-Kuhn-Tucker) conditions:

  1. Stationarity: ∇wL=0\nabla_{\mathbf{w}} \mathcal{L} = \mathbf{0}
  2. Primal feasibility: ∑wj2≤t\sum w_j^2 \leq t
  3. Dual feasibility: λ≥0\lambda \geq 0
  4. Complementary slackness: λ(∑wj2−t)=0\lambda(\sum w_j^2 - t) = 0

Solving stationarity condition:

∂L∂w=2nXT(Xw−y)+2λw=0\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \frac{2}{n}\mathbf{X}^T(\mathbf{Xw} - \mathbf{y}) + 2\lambda\mathbf{w} = \mathbf{0}

XTXw+nλw=XTy\mathbf{X}^T\mathbf{Xw} + n\lambda\mathbf{w} = \mathbf{X}^T\mathbf{y}

(XTX+nλI)w=XTy(\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I})\mathbf{w} = \mathbf{X}^T\mathbf{y}

w=(XTX+nλI)−1XTy\mathbf{w} = (\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}

Penalty-constraint equivalence:

For every constraint bound tt, there exists a Lagrange multiplier λ\lambda such that the constrained problem's solution equals the penalized problem's solution. The mapping between tt and λ\lambda is:

t=∥w∗(λ)∥22t = \|\mathbf{w}^*(\lambda)\|_2^2

where w∗(λ)\mathbf{w}^*(\lambda) is the Ridge solution for penalty λ\lambda.

9.2 Lasso Optimization via Coordinate Descent

The challenge: L1 penalty ∣w∣|w| is not differentiable at w=0w = 0.

Subgradient at zero:

∂∣w∣={{1}if w>0[−1,1]if w=0{−1}if w<0\partial |w| = \begin{cases} \{1\} & \text{if } w > 0 \\ [-1, 1] & \text{if } w = 0 \\ \{-1\} & \text{if } w < 0 \end{cases}

Coordinate descent algorithm:

Initialize: w = 0 (or random)
Repeat until convergence:
    For j = 1 to p:
        # Compute residual excluding feature j
        r_j = y - X_{-j}w_{-j}
        
        # Compute OLS coefficient for feature j
        w_j^OLS = (X_j^T r_j) / (X_j^T X_j)
        
        # Apply soft-thresholding
        w_j^new = sign(w_j^OLS) * max(|w_j^OLS| - λ/||X_j||², 0)

Soft-thresholding operator:

soft(z,γ)={z−γif z>γ0if ∣z∣≤γz+γif z<−γ\text{soft}(z, \gamma) = \begin{cases} z - \gamma & \text{if } z > \gamma \\ 0 & \text{if } |z| \leq \gamma \\ z + \gamma & \text{if } z < -\gamma \end{cases}

Why this creates sparsity:

If ∣wjOLS∣<λ/∥Xj∥2|w_j^{\text{OLS}}| < \lambda/\|X_j\|^2, then wjnew=0w_j^{\text{new}} = 0 exactly.

Coefficients below the threshold are set to zero, not just made small.

9.3 Elastic Net

Motivation: Combine advantages of Ridge and Lasso

Loss function:

J(w)=1n∑i=1n(yi−y^i)2+λ1∑j=1p∣wj∣+λ2∑j=1pwj2J(\mathbf{w}) = \frac{1}{n}\sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda_1 \sum_{j=1}^{p} |w_j| + \lambda_2 \sum_{j=1}^{p} w_j^2

Alternative parameterization:

J(w)=1n∑i=1n(yi−y^i)2+λ[α∥w∥1+(1−α)∥w∥22]J(\mathbf{w}) = \frac{1}{n}\sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda \left[\alpha \|w\|_1 + (1-\alpha)\|w\|_2^2\right]

where:

Properties:

✓ Encourages grouped selection of correlated features (unlike Lasso which picks one arbitrarily)
✓ Produces sparsity like Lasso
✓ Stable like Ridge
✓ Works well with p>np > n

When to use:

9.4 Bayesian Interpretation

Ridge as MAP with Gaussian Prior:

Assume prior on weights: wj∼N(0,τ2)w_j \sim \mathcal{N}(0, \tau^2)

Maximum a posteriori (MAP) estimate:

wMAP=arg⁡max⁡wp(w∣y,X)\mathbf{w}_{\text{MAP}} = \arg\max_{\mathbf{w}} p(\mathbf{w}|\mathbf{y}, \mathbf{X})

Using Bayes rule and taking negative log:

−log⁡p(w∣y,X)∝∑(yi−wTxi)2+σ2τ2∑wj2-\log p(\mathbf{w}|\mathbf{y}, \mathbf{X}) \propto \sum(y_i - \mathbf{w}^T\mathbf{x}_i)^2 + \frac{\sigma^2}{\tau^2}\sum w_j^2

This is exactly Ridge with λ=σ2/τ2\lambda = \sigma^2/\tau^2!

Lasso as MAP with Laplace Prior:

Assume prior: wj∼Laplace(0,b)w_j \sim \text{Laplace}(0, b)

Density: p(w)=12be−∣w∣/bp(w) = \frac{1}{2b}e^{-|w|/b}

MAP estimate leads to Lasso with λ=σ2/b\lambda = \sigma^2/b.

Interpretation:

9.5 Computational Complexity

Ridge Regression:

Lasso Regression:

Practical guidelines:

9.6 Extensions

Group Lasso:

Fused Lasso:

Adaptive Lasso:

End of Lecture Notes

Suggested next steps:

  1. Review these notes at your own pace
  2. Work through the practice problems
  3. Attend the lab session for hands-on implementation
  4. Start thinking about Assessment 1 (due Week 6)

Resources:

Good luck with your learning journey! Remember: understanding comes from doing. Practice implementing these concepts, experiment with different datasets, and don't hesitate to ask questions.