MACHINE LEARNING & BACKPROPAGATION

1. INTRODUCTION TO MACHINE LEARNING

What is Machine Learning?

Machine Learning is a method of teaching computers to:

• Learn from data - Extract patterns from examples
• Generalize to unseen data - Apply learned patterns to new situations
• Without explicit instructions - No need to manually program every rule

Core Philosophy

According to Rich Sutton (ACM A.M. Turing Award 2024 recipient):

"General methods that leverage computation and learning ultimately prove more effective than approaches relying on human knowledge and domain-specific expertise."

This is known as The Bitter Lesson - we should not assume models (e.g., linear or not), we should just have a general learning method leveraging computation (e.g., Neural Networks + Gradient Descent).

2. WHAT PROBLEMS CAN ML SOLVE?

Machine Learning excels when three conditions are met:

1. Many labeled examples - Abundant training data
2. Patterns in the data - Reusable regularities across samples
3. Complex relationships - Rules too intricate for manual programming

Examples

• Image classification (cats vs dogs, CIFAR-10)
• Object detection and segmentation
• Natural language processing
• Recommendation systems
• Game playing (AlphaGo, Chess)

3. MODELS: SIMPLIFICATION OF REALITY

What is a Model?

The Gravity Example

Given measurements of mass and force:

Goal: Find the relationship $y = ax$

Guesses:

• $a = 5$ → Poor fit
• $a = 12$ → Poor fit
• $a = 10$ → Better fit
• $a = 9.8$ → Best fit!

Model Notation

• $y$ = true output (observed data)
• $\hat{y}$ = predicted output (model prediction)
• Goal: Make $\hat{y} \approx y$

Key Insight

It suffices to approximate reality. We don't need Einstein's relativity formula:

where $c \approx 2.99 \times 10^8$ m/s

4. LOSS FUNCTIONS: MEASURING GOODNESS

What is a Good Approximation?

Question: Is it possible to evaluate "goodness"?

Answer: Yes! Using a loss function.

L2 (Euclidean) Loss

Interpretation: Distance from the data to the model.

L2 Loss Example

Using our gravity data:

Vector Form

For vector outputs:

Gradient with respect to predictions:

5. GRADIENT DESCENT: FINDING THE MINIMUM

The Problem

Question: How do we find the value for parameter $a$ that minimizes loss?

Answer: Gradient descent!

How Derivatives Show Influence

The derivative $\frac{\partial L}{\partial a}$ tells us:

• If positive: Increasing $a$ increases loss → decrease $a$
• If negative: Increasing $a$ decreases loss → increase $a$
• If zero: We're at a minimum (or maximum/saddle point)

The Gradient Descent Update Rule

where:

• $\eta$ = learning rate (chosen by us)
• $\frac{\partial L}{\partial a}$ = derivative of loss with respect to parameter

Example Iterations

Starting with $a = 8$:

Learning Rate Importance

• Too large: Steps overshoot minimum, oscillate
• Too small: Training is slow, may get stuck
• Just right: Smooth convergence

Multiple Parameters

For multiple parameters (e.g., $y = ax + b$):

6. STOCHASTIC GRADIENT DESCENT

The Data Loading Problem

Challenge: size of dataset $\gg$ computer memory

Solution: Batching!

Three Flavors of Gradient Descent

Mini-Batch SGD Checklist

1. Shuffle samples each epoch for unbiased batches
2. Normalize inputs so magnitudes are comparable
3. Track both training and validation metrics to detect overfitting

7. CHOOSING MODELS

The Spectrum of Models

For fitting data, we could choose:

• Linear model: $y = ax + b$
• Quadratic model: $y = ax^2 + bx + c$
• Cosine model: $y = a \cdot \cos(bx + c) + d$
• Polynomial model: $y = \sum a_i x^i$

The Overfitting Problem

For Complex Data (Images, Text, etc.)

Question: What model for CIFAR-10 images (cats, dogs, etc.)?

Answer: Neural Networks!

Why?

• Don't assume linear/quadratic/etc.
• Let the network learn the right representation
• Just need:
  • General learning method (backpropagation)
  • Computation (GPUs)
  • Data

8. NEURAL NETWORKS

Basic Architecture

Input (n features)
    ↓
Dense Layer: Z₁ = X·W₁ + b₁
    ↓
Activation: Z₂ = σ(Z₁)    [Non-linearity!]
    ↓
Dense Layer: Z₃ = Z₂·W₂ + b₂
    ↓
Output (m classes)
            

Why Non-linearities?

Key Components

1. Weights (W): Learned parameters
2. Biases (b): Learned offsets
3. Activations (σ): Non-linear functions (ReLU, sigmoid, tanh)
4. Loss function (L): Measures error
5. Optimizer: Updates parameters (SGD, Adam, etc.)

9. BACKPROPAGATION: THE CHAIN RULE

Computational Graph

For a simple scalar neural network:

X → [·W₁] → Z₁ → [+b₁] → Z₂ → [σ] → Z₃ → [·W₂] → Z₄ → [+b₂] → Yₚ → [Loss] → L
                                                                    ↑
                                                                    Y (true)
            

Forward Pass

Compute outputs from inputs:

1. $Z_1 = X \cdot W_1$
2. $Z_2 = Z_1 + b_1$
3. $Z_3 = \sigma(Z_2)$
4. $Z_4 = Z_3 \cdot W_2$
5. $Y_p = Z_4 + b_2$
6. $L = \frac{1}{2}(Y_p - Y)^2$

Backward Pass (Backpropagation)

Apply chain rule right-to-left:

Matrix/Vector Extension

For matrices and vectors, use:

• Jacobians instead of derivatives
• Matrix transposes for proper dimensionality

10. LOSS FUNCTION DERIVATIVES

Euclidean (MSE) Loss

Forward:

Backward:

Vector notation:

Softmax + Cross-Entropy Loss

Forward:

Logits → Softmax → Probabilities → Cross-Entropy → Loss
            

Backward (the beautiful simplification!):

Comparison: L2 vs Cross-Entropy for Classification

11. BACKPROPAGATION FOR CONVOLUTIONAL LAYERS

Setup

• Input: $I$ ($H \times W$ matrix)
• Kernel: $K$ ($h \times w$ matrix)
• Output: $J = I * K$ (convolution, size $(H-h+1) \times (W-w+1)$)

Assume: $H \geq h$ and $W \geq w$

Two Questions

Given $\frac{\partial L}{\partial J}$ (upstream gradient), find:

1. $\frac{\partial L}{\partial K}$ - To update kernel by gradient descent
2. $\frac{\partial L}{\partial I}$ - To backprop to previous layer

Derivation of ∂L/∂K

Forward:

Backward:

Derivation of ∂L/∂I

Backward:

Example of flip:

K = [1 3 5]    flip(K) = [6 4 2]
    [2 4 6]               [5 3 1]
            

Implementation Tips

1. Cache input patches or use im2col to vectorize
2. Reuse same stride/padding from forward pass
3. Mismatched shapes are the #1 error source!

12. BACKPROPAGATION FOR MAX POOLING

Setup

Key Idea

In case of a tie, choose a single index deterministically:

Backward Pass

Example: 2×2 MaxPool, stride 2

Forward:

x = [2  -3]    MaxPool    y = [5  6]
    [4   5]      →            [0  8]
    [6   5]

    [6  -7]
    [0  -1]

    [-2 -6]
    [3  -4]

    [6   8]
            

Backward:

δy = [δy₁  δy₂]
     [δy₃  δy₄]

δx = [0    0  ]
     [0   δy₁]
     [δy₃  0  ]

     [δy₂  0  ]
     [0    0  ]

     [0    0  ]
     [0    0  ]

     [0   δy₄]

Implementation

Pseudo-code:

# Forward pass: store argmax indices
for (i, j), pooling_region in enumerate(regions):
    argmax_cache[i, j] = argmax(pooling_region)
    output[i, j] = max(pooling_region)

# Backward pass: route gradient
for (i, j), grad in enumerate(dL_dOutput):
    (ii, jj) = argmax_cache[i, j]
    dL_dInput[ii, jj] += grad

13. BACKPROPAGATION FOR ReLU

Setup

Backward Pass

where $\odot$ is element-wise multiplication and $\mathbb{1}[\cdot]$ is indicator function.

Example

Forward:

x = [-5  4]    ReLU    y = [0  4]
    [ 0  2]      →        [0  2]
            

Backward:

δy = [δy₁  δy₂]    →    δx = [0     δy₂]
     [δy₃  δy₄]              [0     δy₄]

Implementation

Keep the boolean mask from forward pass:

# Forward
mask = (x > 0)
y = x * mask

# Backward
dx = dy * mask

14. PUTTING IT ALL TOGETHER

Example Network

Conv → ReLU → MaxPool → Loss
 ↓      ↓       ↓        ↓
 y      z       p        L
 ↑      ↑       ↑
 x      y       z
            

Training Algorithm

Initialize: Parameter $K$ (convolution kernel)

Iterate:

Step 1: Forward Pass

• 1a. Randomly choose training example $x$ and ideal output $q$
• 1b. Pass $x$ through Conv to get $y$
• 1c. Pass $y$ through ReLU to get $z$
• 1d. Pass $z$ through MaxPool to get $p$

Step 2: Compute Loss

Step 3: Backward Pass (Backpropagation)

• 3a. Compute $\delta p = \frac{\partial L}{\partial p} = p - q$
• 3b. Compute $\delta z$ given $\delta p$ (MaxPool backprop)
• 3c. Compute $\delta y$ given $\delta z$ (ReLU backprop)
• 3d. Compute $\delta K$ given $\delta y$ (Conv backprop)

Step 4: Update Parameters

15. ADVANCED TOPICS

Example 1: Conv → ReLU → MaxPool with Numbers

Given:

I = [1  3  2  4  6  4]
    [4  8  3  1  0  2]
    [2  1  4  3  9  1]
    [4  7  2  3  9  2]

W = [-1  0  1]    (edge detection kernel)
    [-1  0  1]
    [-1  0  1]

Task: Compute $J$, $K$, $O$ and backpropagation gradients.

Example 2: Shared Parameters

Network:

Loss: L2 between Y and X

Gradient:

Residual Connections

Network:

Backward:

Transformer Backpropagation

Complex architecture with:

• Multi-head attention
• Layer normalization
• Residual connections
• Feed-forward networks

16. SUMMARY & KEY TAKEAWAYS

The Big Picture

Data → Model → Loss → Optimization
         ↑                 |
         |---- Backprop ----
            

Core Concepts

1. Models approximate reality
   • Simplification of unknown data-generating process
   • Goal: generalize to unseen data
2. Loss functions quantify error
   • L2 loss for regression
   • Cross-entropy for classification
3. Gradient descent minimizes loss
   • Update rule: $\theta \leftarrow \theta - \eta \cdot \nabla L$
   • Mini-batch SGD is practical default
4. Neural networks are universal approximators
   • Don't assume model form
   • Let network learn representation
   • Need: data, computation, backpropagation
5. Backpropagation is chain rule
   • Forward: compute outputs
   • Backward: compute gradients right-to-left
   • Update: gradient descent

Layer-Specific Backprop Recipes

Practical Workflow

1. Data sanity: Visualize random samples after augmentation
2. Forward caches: Store intermediates for backward pass
3. Gradient checks: Compare manual gradients vs autograd
4. Learning rate sweeps: Try {1e-1, 1e-2, 1e-3}
5. Monitor metrics: Track train/val loss and accuracy

Common Pitfalls

Debugging Patterns

Lightweight instrumentation:

• Log loss, ||∇θ||₂, max|∂L/∂θ| per batch
• Plot running averages for train and validation
• Catch silent NaNs early

Autograd verification:

# Manual calculation
δW_manual = compute_gradient_manually()

# PyTorch autograd
loss.backward()
δW_auto = W.grad

# Compare
assert torch.allclose(δW_manual, δW_auto, atol=1e-5)

Next Steps

1. Review Anki cards (tagged by topic)
2. Re-implement Conv → ReLU → Pool example
3. Verify gradients numerically before scaling to datasets
4. Apply to Assignment 7 architecture

REFERENCES

• Slides-1-ML.pdf by Paulius Sasnauskas
• BackPropPractices.pdf by Nilanjan Ray
• Example_Solutions-Backprop.pdf (worked autograd checks)
• Andrej Karpathy's micrograd and backpropagation lecture
• Rich Sutton's The Bitter Lesson (2019)
• Google Machine Learning Crash Course