Machine Learning

Complete Notes for 3rd Year [Link]

Module 3 & Module 4 (July 2023 Syllabus)

Modules at a Glance
Module 3 [9L]: The Linear Model II (Logistic Regression, Likelihood, Gradient
Descent) & Neural Networks (Model, Backpropagation, RBF, RNN, CNN, DNN)
Module 4 [9L]: Support Vector Machines (Margin, Kernel Methods, Soft-margin)
& Overfitting & Regularisation (Weight Decay, Regularizer choice)

Compiled for academic use

Contents
MODULE 3 2

1 The Linear Model II 2

1.1 Logistic Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Motivation: Beyond Hard Classification . . . . . . . . . . . . . . . 2
1.1.2 The Sigmoid Function . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 The Probabilistic Model . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Likelihood Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Maximum Likelihood Estimation (MLE) . . . . . . . . . . . . . . 3
1.2.2 Log-Likelihood and Cross-Entropy Loss . . . . . . . . . . . . . . . 3
1.3 Gradient Descent for Logistic Regression . . . . . . . . . . . . . . . . . . 3
1.3.1 Why Gradient Descent? . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.2 Computing the Gradient . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.3 Gradient Descent Update Rule . . . . . . . . . . . . . . . . . . . 4

2 Neural Networks 4
2.1 Neural Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 The Artificial Neuron . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Activation Functions . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.4 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Backpropagation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 The Chain Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Backpropagation Steps . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Practical Considerations in Training . . . . . . . . . . . . . . . . 7
2.3 Introduction to Radial Basis Function (RBF) Networks . . . . . . . . . . 7
2.4 Recurrent Neural Networks (RNN) . . . . . . . . . . . . . . . . . . . . . 8
2.4.1 RNN Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.2 LSTM and GRU . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Convolutional Neural Networks (CNN) . . . . . . . . . . . . . . . . . . . 9
2.5.1 Key CNN Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5.2 Typical CNN Architecture . . . . . . . . . . . . . . . . . . . . . . 9
2.6 Deep Neural Networks (DNN) . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6.1 Why Depth Helps . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6.2 Challenges of Deep Learning . . . . . . . . . . . . . . . . . . . . . 10
2.6.3 Key Deep Learning Components Summary . . . . . . . . . . . . . 10

MODULE 4 11

3 Support Vector Machines (SVM) 11

3.1 The Margin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Maximising the Margin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.1 The Primal Optimisation Problem . . . . . . . . . . . . . . . . . 11
3.2.2 The Dual Problem (Lagrangian Formulation) . . . . . . . . . . . 12
3.2.3 The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Support Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Nonlinear Transform with SVMs . . . . . . . . . . . . . . . . . . . . . . . 12

1
Machine Learning — Modules 3 & 4 3rd Year [Link]

3.5 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.5.1 Common Kernel Functions . . . . . . . . . . . . . . . . . . . . . . 13
3.6 Soft-Margin SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Overfitting 14
4.1 What is Overfitting? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Causes of Overfitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Dealing with Overfitting . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3.1 Early Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3.2 Cross-Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Regularisation 16
5.1 Informal View of Regularisation . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 Formal Regularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2.1 Bias-Variance View . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.3 Weight Decay (L2 Regularisation / Ridge) . . . . . . . . . . . . . . . . . 16
5.4 L1 Regularisation (Lasso) . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5 Choosing a Regulariser . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5.1 L1 vs. L2 Comparison . . . . . . . . . . . . . . . . . . . . . . . . 18
5.5.2 Elastic Net . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.5.3 Choosing λ: Cross-Validation . . . . . . . . . . . . . . . . . . . . 18
5.5.4 Other Regularisation Strategies . . . . . . . . . . . . . . . . . . . 18

6 Quick Reference Summary 18

2
Machine Learning — Modules 3 & 4 3rd Year [Link]

0 MODULE 3 [9 Lectures]
1 The Linear Model II
1.1 Logistic Regression
1.1.1 Motivation: Beyond Hard Classification
The Perceptron outputs a hard {+1, −1} decision. But in many real problems we want
a probability: “What is the probability that this customer will default?”

Logistic Regression is a probabilistic binary classifier. Instead of predicting a class

label, it outputs the probability that the input belongs to class +1:
1
h(x) = θ(wT x) = ∈ (0, 1)
1 + e−wT x
1
where θ(s) = 1+e−s
is the sigmoid (logistic) function.

1.1.2 The Sigmoid Function

1
θ(s) = , s ∈ R, θ(s) ∈ (0, 1)
1 + e−s
Key properties:
ˆ θ(0) = 0.5; output is 0.5 on the decision boundary.
ˆ θ(s) → 1 as s → +∞; θ(s) → 0 as s → −∞.
ˆ Smooth, differentiable everywhere (unlike the sign function).
ˆ Derivative: θ′ (s) = θ(s) (1 − θ(s)) — very convenient for calculus.

Geometric interpretation: The linear score s = wT x is a real number. The

sigmoid “squashes” it into (0, 1), giving a valid probability. A large positive score
gives probability near 1 (strong positive class); large negative gives near 0 (strong
negative class).

1.1.3 The Probabilistic Model

We model the conditional probability:

P (y = +1 | x) = h(x) = θ(wT x)

P (y = −1 | x) = 1 − h(x) = θ(−wT x)

These two can be written compactly as:

P (y | x) = θ(y · wT x)

3
Machine Learning — Modules 3 & 4 3rd Year [Link]

1.2 Likelihood Measure

1.2.1 Maximum Likelihood Estimation (MLE)
The likelihood of the training data D = {(xn , yn )}N
n=1 given weights w is the prob-
ability of observing exactly the given labels:
N
Y N
Y
L(w) = P (yn | xn ; w) = θ(yn wT xn )
n=1 n=1

MLE: Find w that maximises L(w), i.e., makes the observed data most probable.

1.2.2 Log-Likelihood and Cross-Entropy Loss

Maximising L is equivalent to maximising the log-likelihood (log is monotone):
N
X
ln L(w) = ln θ(yn wT xn )
n=1

Equivalently, we minimise the cross-entropy loss (negative log-likelihood):

N N
1 X  −yn wT xn
 1 X
Ein (w) = ln 1 + e = ℓ(yn , h(xn ))
N n=1 N n=1

where ℓ(y, h) = ln(1 + e−yh ) is the logistic loss (log-loss).

Why cross-entropy?
ˆ It is a convex function of w — no local minima, gradient descent is guaranteed to
find the global minimum.
ˆ Penalises confident wrong predictions very heavily.
ˆ Preferred over MSE for classification because it has better gradient behaviour.
Linear Regression Logistic Regression
Output Real number wT x Probability θ(wT x) ∈ (0, 1)
Loss function Mean Squared Error Cross-entropy (log-loss)
Task Regression Binary classification
Solution Closed-form (X† y) Iterative (gradient descent)
Decision boundary N/A wT x = 0

1.3 Gradient Descent for Logistic Regression

1.3.1 Why Gradient Descent?
Unlike linear regression, the logistic loss has no closed-form solution. We use gradient
descent to iteratively minimise Ein (w).

4
Machine Learning — Modules 3 & 4 3rd Year [Link]

1.3.2 Computing the Gradient

The gradient of the cross-entropy loss with respect to w is:
N
1 X
yn xn θ −yn wT xn


∇w Ein (w) = −
N n=1

Intuitively: misclassified points (where θ(−yn wT xn ) is large, i.e., near 1) contribute

most to the gradient.

1.3.3 Gradient Descent Update Rule

Batch Gradient Descent: Update using all N training samples at each step:

w(t+1) ← w(t) − η∇w Ein (w(t) )

Stochastic Gradient Descent (SGD): Update using one random sample (xn , yn ):

w ← w + η · yn xn · θ(−yn wT xn )

Mini-batch GD: Update using a small batch (e.g., 32 or 64 samples). Balance

between batch and stochastic.

Choosing the learning rate η:

ˆ Too large: overshoots, may diverge.
ˆ Too small: very slow convergence.
ˆ Learning rate schedules: Decrease η over time (step decay, cosine annealing).
ˆ Adaptive methods: Adam, RMSProp, Adagrad — automatically adjust η per pa-
rameter.

Convergence: Since cross-entropy is convex, gradient descent is guaranteed to con-

verge to the global minimum (assuming appropriate η). The solution may not be
unique if data is linearly separable (weights can grow to infinity).

2 Neural Networks
2.1 Neural Network Model
2.1.1 Motivation
Linear models (perceptron, logistic regression) can only learn linear decision boundaries.
Real-world data is often highly nonlinear. Neural Networks stack multiple layers of
linear + nonlinear transformations to learn arbitrarily complex functions.

5
Machine Learning — Modules 3 & 4 3rd Year [Link]

An Artificial Neural Network (ANN) is a computational model loosely inspired

by the biological brain. It consists of layers of nodes (neurons), each performing a
simple computation. By composing many such layers, the network can approximate
any continuous function (Universal Approximation Theorem).

2.1.2 The Artificial Neuron

A single neuron computes:

d
!
X
z=ϕ wi xi = ϕ(wT x)
i=0

where ϕ is the activation function and w0 is the bias term (with x0 = 1).

2.1.3 Activation Functions

Activation functions introduce nonlinearity into the network. Without them, a stack
of linear layers collapses to a single linear layer.
Name Formula Range Use / Notes
Sigmoid σ(s) = 1+e1 −s (0, 1) Output layer (binary
prob); vanishing gra-
dient
es −e−s
Tanh tanh(s) = es +e−s
(−1, 1) Hidden layers; zero-
centred; still vanish-
ing grad
ReLU max(0, s) [0, ∞) Most popular; fast;
dying ReLU problem
Leaky ReLU max(0.01s, s) R Fixes dying ReLU;
small slope for s < 0
s
Softmax Pe ksj (0, 1), sums to 1 Output layer (multi-
je
class)
Linear s R Regression output
layer only

2.1.4 Network Architecture

A feedforward neural network (also called Multi-Layer Perceptron, MLP) is or-
ganised into:
ˆ Input layer: Receives features x ∈ Rd . No computation performed.
ˆ Hidden layers: One or more layers that perform nonlinear transformations.
Each hidden unit applies an activation function to a weighted sum of its inputs.
ˆ Output layer: Produces the final prediction (class probabilities or regression
values).

Notation: An L-layer network has L − 1 hidden layers and 1 output layer. Let n[l]
denote the number of neurons in layer l.

6
Machine Learning — Modules 3 & 4 3rd Year [Link]

Forward pass through layer l:

z[l] = W[l] a[l−1] + b[l] , a[l] = ϕ(z[l] )

where W[l] is the weight matrix (n[l] × n[l−1] ), b[l] is the bias vector, and a[0] = x.

Universal Approximation Theorem: A single hidden layer network with enough

neurons can approximate any continuous function to arbitrary precision. More depth
(layers) is generally better in practice than extreme width.

2.2 Backpropagation Algorithm

Backpropagation is the algorithm used to efficiently compute the gradient of the
loss with respect to every weight in the network, using the chain rule of calculus.
It makes training deep networks computationally feasible.

2.2.1 The Chain Rule

If E = E(a[L] ), and a[L] depends on z[L] , which depends on W[L] , then:

∂E ∂E ∂z[l]
= ·
∂W[l] ∂z[l] ∂W[l]

Backprop propagates the error signal (δ) backward through the network, layer by layer.

2.2.2 Backpropagation Steps

1. Forward Pass: Compute z[l] and a[l] for every layer l = 1, . . . , L. Store all interme-
diate values.
2. Compute Output Error:
∂E
δ [L] = [L]
= ∇a[L] E ⊙ ϕ′ (z[L] )
∂z
(For cross-entropy + softmax: δ [L] = ŷ − y, very clean!)
3. Backpropagate the Error: For l = L − 1, L − 2, . . . , 1:

δ [l] = (W[l+1] )T δ [l+1] ⊙ ϕ′ (z[l] )

4. Compute Gradients:
∂E ∂E
= δ [l] (a[l−1] )T , = δ [l]
∂W[l] ∂b[l]

5. Update Weights (gradient descent):

∂E
W[l] ← W[l] − η
∂W[l]

7
Machine Learning — Modules 3 & 4 3rd Year [Link]

Simple 2-layer network example:

W[1] W[2]
Input x −−→ hidden a[1] −−→ output ŷ
Forward: z[1] = W[1] x, a[1] = ReLU(z[1] ), ŷ = σ(W[2] a[1] )
Loss: E = −[y log ŷ + (1 − y) log(1 − ŷ)]
Backward: δ [2] = ŷ − y; δ [1] = (W[2] )T δ [2] ⊙ 1[z[1] > 0]

2.2.3 Practical Considerations in Training

ˆ Vanishing gradients: With many layers and sigmoid/tanh activations, δ shrinks
exponentially during backprop. Fix: use ReLU, batch normalisation, residual connec-
tions.
ˆ Exploding gradients: Gradients grow exponentially. Fix: gradient clipping, careful
weight initialisation.
ˆ Weight initialisation: Never initialise all weights to zero (symmetry breaking prob-
lem). Use Xavier or He initialisation.
ˆ Batch Normalisation: Normalise activations within a mini-batch to stabilise and
speed up training.
ˆ Dropout: Randomly “drop” neurons during training with probability p; prevents
overfitting.

2.3 Introduction to Radial Basis Function (RBF) Networks

A Radial Basis Function (RBF) Network is a neural network that uses radial
basis functions as activation functions in the hidden layer. The output of each
hidden neuron depends only on the distance between the input and a centre point
µk :
∥x − µk ∥2
 
ϕk (x) = exp −
2σk2

Architecture:
1. Input layer: Receives input x.
2. Hidden layer: Each neuron k computes ϕk (x) — a Gaussian centred at µk with
spread σk . The neuron activates strongly when x is close to its centre.
3. Output layer: A linear combination of the RBF activations:
K
X
ŷ = wk ϕk (x) + w0
k=1

Training:
ˆ Centres µk : Chosen by K-means clustering on the training data, or randomly from
training examples.
ˆ Widths σk : Typically set heuristically (e.g., mean distance between centres).

8
Machine Learning — Modules 3 & 4 3rd Year [Link]

ˆ Output weights wk : Solved with linear regression (closed-form).

RBF vs. MLP:
MLP RBF Network
Hidden activation Sigmoid / ReLU Gaussian (radial)
Training Backpropagation K-means + linear regression
Approximation type Global (hyperplane-based) Local (proximity-based)
Extrapolation Can extrapolate Poor extrapolation
Training speed Slower Faster

2.4 Recurrent Neural Networks (RNN)

A Recurrent Neural Network (RNN) is a neural network designed for sequen-
tial data (time series, text, speech). It has feedback connections: the output (or
hidden state) of a neuron at time t is fed back as an input at time t + 1.

2.4.1 RNN Computation

At each time step t, given input xt and previous hidden state ht−1 :

ht = ϕ(Wh ht−1 + Wx xt + b)
ŷt = Wy ht + by
Weights Wh , Wx , Wy are shared across all time steps.

Training: Backpropagation Through Time (BPTT) — unroll the RNN across T time
steps and apply standard backprop on the unrolled graph.
Problem: Vanilla RNNs suffer from the vanishing/exploding gradient problem
over long sequences.

2.4.2 LSTM and GRU

LSTM (Long Short-Term Memory): A gated RNN variant with a cell state
(long-term memory) and three gates: input gate, forget gate, output gate. The
forget gate decides what to erase from memory; input gate decides what to write;
output gate decides what to output. Solves long-term dependency problem.
GRU (Gated Recurrent Unit): A simplified LSTM with two gates (update and
reset). Faster to train; comparable performance to LSTM.

Applications of RNNs:
ˆ Language modelling and text generation
ˆ Machine translation (seq2seq)
ˆ Speech recognition
ˆ Time series prediction (stock prices, weather)
ˆ Video captioning

9
Machine Learning — Modules 3 & 4 3rd Year [Link]

2.5 Convolutional Neural Networks (CNN)

A Convolutional Neural Network (CNN) is a specialised neural network de-
signed for grid-structured data (images, audio spectrograms). It uses convolu-
tion operations to automatically learn spatial features (edges, textures, shapes)
with far fewer parameters than a fully connected network.

2.5.1 Key CNN Layers

(a) Convolutional Layer:
ˆ A filter (kernel) F of size k × k slides across the input image, computing a dot
product at each position.
ˆ Each filter detects a specific local feature (e.g., a horizontal edge).
ˆ Multiple filters produce multiple feature maps.
ˆ Key parameters: Filter size (k), stride (s), padding (p).

Output feature map size: n+2p−k

 
s
+1
where n = input size, p = padding, k = kernel size, s = stride.

Properties of convolution:
ˆ Local connectivity: Each neuron connects to only a small local region (receptive
field).
ˆ Parameter sharing: The same filter weights are used across all positions — dra-
matically reduces parameters.
ˆ Translation equivariance: If the input shifts, the feature map shifts correspond-
ingly.
(b) Pooling Layer: Reduces spatial dimensions (downsampling), providing spatial in-
variance:
ˆ Max pooling: Takes the maximum value in each pooling window. Most common.
ˆ Average pooling: Takes the average value.
(c) Fully Connected (FC) Layer: After several conv+pool layers, the feature maps
are flattened and fed into one or more FC layers for final classification.

2.5.2 Typical CNN Architecture

Input → [Conv → ReLU → Pool]×L → Flatten → [FC → ReLU]×M → Softmax Output

Famous CNNs:
LeNet-5 (1998): 5 layers; pioneered CNNs for digit recognition.
AlexNet (2012): Deep CNN that won ImageNet; introduced ReLU, dropout.
VGG (2014): Very deep (16–19 layers) with small 3 × 3 filters.

10
Machine Learning — Modules 3 & 4 3rd Year [Link]

ResNet (2015): 152 layers; introduced residual connections to skip layers.

Applications: Image classification, object detection, face recognition, medical imaging,

autonomous driving.

2.6 Deep Neural Networks (DNN)

A Deep Neural Network (DNN) is a neural network with many hidden lay-
ers (typically more than 2). “Deep learning” refers to the use of DNNs to learn
hierarchical feature representations from raw data.

2.6.1 Why Depth Helps

Each layer learns increasingly abstract representations:
ˆ Layer 1: Learns edges and simple patterns
ˆ Layer 2: Learns shapes and textures from combinations of edges
ˆ Layer 3+: Learns high-level concepts (faces, objects, semantic meaning)
A deep network with k layers can represent functions that would require an exponentially
wide shallow network.

2.6.2 Challenges of Deep Learning

ˆ Vanishing/Exploding Gradients: Addressed by ReLU, batch norm, residual con-
nections.
ˆ Overfitting: Addressed by dropout, data augmentation, regularisation.
ˆ Computational cost: Requires GPUs/TPUs and large datasets.
ˆ Hyperparameter tuning: Number of layers, neurons, learning rate, etc.

2.6.3 Key Deep Learning Components Summary

Architecture Designed For Key Innovation
MLP / DNN Tabular / general data Multiple hidden layers
CNN Images / spatial data Convolution + weight sharing
RNN / LSTM Sequences / time series Recurrent hidden state
RBF Network Proximity-based tasks Radial basis activations
Transformer NLP / sequences Self-attention mechanism

11
Machine Learning — Modules 3 & 4 3rd Year [Link]

2 MODULE 4 [9 Lectures]
3 Support Vector Machines (SVM)
3.1 The Margin
For a linearly separable dataset, there are infinitely many hyperplanes that cor-
rectly classify all training data. An SVM finds the optimal separating hyper-
plane — the one that maximises the margin: the perpendicular distance between
the hyperplane and the nearest data points of each class.

Setup: Binary classification with labels yn ∈ {+1, −1} and inputs xn .

The separating hyperplane is: wT x + b = 0
Distance from point xn to the hyperplane:

|wT xn + b| yn (wT xn + b)
distance = =
∥w∥ ∥w∥
(The second equality uses the fact that yn and wT xn + b have the same sign for
correctly classified points.)

Margin definition: The margin ρ is twice the distance from the hyperplane to the
nearest point (the support vectors):

2
ρ=
∥w∥
(after normalising so that yn (wT xn + b) ≥ 1 for all training points, with equality for
support vectors.)

Intuition: A larger margin means the classifier is more confident and less sensitive to
noise in the training data. The SVM maximises ρ = maximises generalisation.

3.2 Maximising the Margin

3.2.1 The Primal Optimisation Problem
Hard-Margin SVM (Primal form):
1
min ∥w∥2
w,b 2

subject to yn (wT xn + b) ≥ 1, n = 1, . . . , N
Maximising ρ = 2/∥w∥ is equivalent to minimising 12 ∥w∥2 .

This is a quadratic programming (QP) problem — convex, with a unique global

solution.

12
Machine Learning — Modules 3 & 4 3rd Year [Link]

3.2.2 The Dual Problem (Lagrangian Formulation)

Using Lagrange multipliers αn ≥ 0 for each constraint:

Lagrangian:
N
1 X
L(w, b, α) = ∥w∥2 − αn yn (wT xn + b) − 1
 
2 n=1

Dual problem (after eliminating w and b):

N N N
X 1XX
max αn − αn αm yn ym xTn xm
α
n=1
2 n=1 m=1

N
X
subject to αn ≥ 0, αn y n = 0
n=1

3.2.3 The Solution

From the KKT (Karush-Kuhn-Tucker) conditions:

N
X
∗
w = αn yn xn
n=1

The optimal weight vector is a linear combination of training points!

The final classifier: !
N
X
h(x) = sign αn yn xTn x + b
n=1

3.3 Support Vectors

Support Vectors are the training points that lie exactly on the margin bound-
ary: yn (wT xn + b) = 1. They are the only points with αn > 0.

Key insight: The optimal hyperplane is completely determined by the support vectors
alone. All other training points (with αn = 0) can be removed without changing the
solution. This is why SVMs are called sparse classifiers.

Why SVMs generalise well: The VC bound says Eout ≤ Ein + O(dV C /N ). SVMs
don’t just minimise Ein ; they simultaneously minimise model complexity by
maximising the margin. Larger margin ⇒ fewer support vectors ⇒ lower effective
dV C ⇒ better generalisation. This is Structural Risk Minimisation (SRM).

3.4 Nonlinear Transform with SVMs

What if data is not linearly separable? Map to a higher-dimensional feature space Z
using Φ : X → Z, then find a linear separator there.

13
Machine Learning — Modules 3 & 4 3rd Year [Link]

The dual problem becomes:

X 1X
max αn − αn αm yn ym Φ(xn )T Φ(xm )
α
n
2 n,m

Note that xTn xm has been replaced by Φ(xn )T Φ(xm ) — the inner product in Z-space.

3.5 Kernel Methods

A kernel function K(x, x′ ) computes the inner product in the feature space without
explicitly computing Φ(x):

K(x, x′ ) = Φ(x)T Φ(x′ )

This is the kernel trick: work in a potentially infinite-dimensional feature space at

the cost of an N × N kernel matrix computation.

The Kernel SVM dual problem:

N
X 1X
max αn − αn αm yn ym K(xn , xm )
α
n=1
2 n,m
N
!
X
h(x) = sign αn yn K(xn , x) + b
n=1

3.5.1 Common Kernel Functions

Kernel Formula Feature Space
Linear K(x, x′ ) = xT x′ Original space Rd
Polynomial K(x, x′ ) = (xT x′ + c)p All polynomials up to degree p
′ 2
RBF / Gaussian K(x, x′ ) = e−γ∥x−x ∥ Infinite-dimensional
Sigmoid K(x, x′ ) = tanh(κxT x′ + c) Approximates neural network
Mercer’s Theorem: A function K(x, x′ ) is a valid kernel if and only if the kernel matrix
K (where Knm = K(xn , xm )) is positive semi-definite for all sets of inputs.
′ 2
RBF Kernel intuition: K(x, x′ ) = e−γ∥x−x ∥ is large when x and x′ are close; near
zero when they are far apart. It corresponds to an infinite-dimensional polynomial
feature space, giving enormous flexibility.

3.6 Soft-Margin SVM

Soft-Margin SVM relaxes the hard-margin requirement by allowing some training
points to violate the margin (i.e., be misclassified or inside the margin), introducing
slack variables ξn ≥ 0.

14
Machine Learning — Modules 3 & 4 3rd Year [Link]

Soft-Margin Primal:
N
1 2
X
min ∥w∥ + C ξn
w,b,ξ 2
n=1

subject to yn (wT xn + b) ≥ 1 − ξn , ξn ≥ 0

Meaning of ξn :
ˆ ξn = 0: point correctly classified and outside the margin.
ˆ 0 < ξn < 1: point inside the margin but correctly classified.
ˆ ξn = 1: point exactly on the decision boundary.
ˆ ξn > 1: point misclassified.
The hyperparameter C:
ˆ Large C: Small tolerance for violations; near hard-margin; may overfit.
ˆ Small C: Large tolerance; wider margin; more regularisation; may underfit.
ˆ C is chosen by cross-validation.
Hard-Margin SVM Soft-Margin SVM
Data requirement Linearly separable Any (allows violations)
Slack variables No Yes (ξn )
Hyperparameter None C (controls trade-off)
Robustness to noise Low (outliers ruin solution) High (tolerates outliers)

4 Overfitting
4.1 What is Overfitting?
Overfitting occurs when a model learns the training data too well, including its
noise and random fluctuations, and performs worse on new (unseen) data than
a simpler model would.

Overfitting ⇐⇒ Ein (g) < Ein (h) but Eout (g) > Eout (h)

where g is the complex model and h is the simpler model.

Signs of overfitting:
ˆ Very low training error but high test/validation error.
ˆ Large gap between Ein and Eout .
ˆ Validation error increases while training error continues to decrease.

15
Machine Learning — Modules 3 & 4 3rd Year [Link]

4.2 Causes of Overfitting

1. Model too complex: Too many parameters relative to training data size (dV C ≫
N ).
2. Too little data: Insufficient training examples for the model’s complexity.
3. Noisy data: Model fits the noise in the training labels.
4. Training too long: Neural networks can overfit if trained for too many epochs.
Fitting a degree-10 polynomial to 5 data points: The polynomial passes ex-
actly through all 5 points (Ein = 0) but oscillates wildly between them. Eout is
enormous.

4.3 Dealing with Overfitting

Strategy Description
Get more data Most effective fix; reduces variance without affecting bias
Regularisation Add penalty term to the loss to constrain model complex-
ity
Early stopping Stop training when validation error starts increasing
Dropout Randomly disable neurons during training (neural net-
works)
Data augmentation Create synthetic training samples (flip, crop, rotate im-
ages)
Reduce model complexity Use fewer parameters / layers
Cross-validation Use held-out validation set to detect and prevent overfit-
ting
Ensemble methods Average predictions of multiple models (bagging, boost-
ing)

4.3.1 Early Stopping

Early Stopping monitors the validation error during training. Training is stopped
when the validation error stops decreasing (or starts increasing), even if the train-
ing error is still decreasing. The model at the best validation error checkpoint is
saved.

Early stopping is a form of implicit regularisation. As training progresses, the model

moves from underfitting → good fit → overfitting. Early stopping captures the model
at the optimal point on this curve.

4.3.2 Cross-Validation
k-Fold Cross-Validation: Split the training data into k equal folds. Train on k − 1
folds and validate on the remaining fold. Repeat k times. The final performance
estimate is the average validation error across all k folds.

Special case: Leave-One-Out (LOO) Cross-Validation — k = N . Use N − 1 points

for training, 1 for validation, repeat N times. Unbiased but computationally expensive.

16
Machine Learning — Modules 3 & 4 3rd Year [Link]

5 Regularisation
5.1 Informal View of Regularisation
Regularisation is any technique that reduces overfitting by constraining, penal-
ising, or adding information to the model, at the cost of slightly increased bias. It
discourages the model from memorising the training data.

Informal principle: Among all hypotheses that fit the data roughly equally well, prefer
the simpler one (Occam’s Razor). Regularisation implements this preference mathemat-
ically by adding a complexity penalty to the loss.

5.2 Formal Regularisation

Regularised Objective: Instead of minimising Ein (w) alone, minimise:

λ
Ereg (w) = Ein (w) + Ω(w)
N
where Ω(w) is the regulariser (penalty term) and λ > 0 is the regularisation
parameter controlling the trade-off.

Effect: The penalty Ω(w) discourages large or complex weight vectors. The model is
constrained to a simpler region of hypothesis space.

5.2.1 Bias-Variance View

ˆ Larger λ ⇒ heavier penalty ⇒ smaller weights ⇒ simpler model ⇒ higher bias, lower
variance.
ˆ Smaller λ → 0 ⇒ no regularisation ⇒ full model complexity ⇒ lower bias, higher
variance.
ˆ λ is a hyperparameter chosen by cross-validation.

5.3 Weight Decay (L2 Regularisation / Ridge)

Weight Decay (Ridge Regression) uses the L2 norm of the weights as the
regulariser:
Xd
2
Ω(w) = ∥w∥ = wi2
i=0

λ
Ereg (w) = Ein (w) + ∥w∥2
N

Effect on gradient descent: The gradient update becomes:

17
Machine Learning — Modules 3 & 4 3rd Year [Link]

 
2ηλ 2ηλ
w ← w − η∇Ein (w) − w =w 1− − η∇Ein (w)
N N
Each weight is “decayed” (shrunk) at every step — hence the name weight decay.

Closed-form solution for Ridge Regression:

−1 T
w∗ = XT X + λI X y
The λI term makes the matrix invertible even when XT X is singular.

Properties of L2 regularisation:
ˆ Shrinks all weights toward zero, but never exactly to zero.
ˆ Differentiable everywhere; easy to optimise.
ˆ Prefers many small weights over few large ones.
ˆ Equivalent to placing a Gaussian prior on weights in a Bayesian framework.

5.4 L1 Regularisation (Lasso)

Lasso (Least Absolute Shrinkage and Selection Operator) uses the L1 norm:
d
X
Ω(w) = ∥w∥1 = |wi |
i=0

λ
Ereg (w) = Ein (w) + ∥w∥1
N

Properties of L1 regularisation:
ˆ Produces sparse weight vectors: many weights become exactly zero.
ˆ Acts as automatic feature selection: irrelevant features have weight set to 0.
ˆ Not differentiable at zero; requires subgradient or coordinate descent.
ˆ Equivalent to placing a Laplace prior on weights.

5.5 Choosing a Regulariser

18
Machine Learning — Modules 3 & 4 3rd Year [Link]

5.5.1 L1 vs. L2 Comparison

L2 (Ridge / Weight Decay) L1 (Lasso)
Penalty ∥w∥2 ∥w∥1
Solution Dense (small but non-zero Sparse (many zero weights)
weights)
Feature selection No Yes (automatically)
Differentiable Yes No (at wi = 0)
Bayesian prior Gaussian Laplace
Best when All features relevant Many irrelevant features
Closed form Yes No (iterative only)

5.5.2 Elastic Net

Combines L1 and L2:
Ω(w) = α∥w∥1 + (1 − α)∥w∥2
Gets feature selection from L1 and stability from L2. Useful when there are groups of
correlated features.

5.5.3 Choosing λ: Cross-Validation

The regularisation parameter λ is a hyperparameter — not learned from training, but
chosen externally:
ˆ Use k-fold cross-validation: train with different values of λ, pick the one with lowest
validation error.
ˆ Common approach: search on a logarithmic scale (e.g., λ ∈ {0.001, 0.01, 0.1, 1, 10}).

5.5.4 Other Regularisation Strategies

ˆ Dropout (Neural Networks): During training, randomly set activations to 0 with
probability p. At test time, scale activations by (1 − p). Effectively trains an ensemble
of sub-networks.
ˆ Batch Normalisation: Normalises layer inputs; has a regularising effect.
ˆ Max-Norm Regularisation: Clip the L2 norm of weight vectors to not exceed a
threshold c: ∥w∥2 ≤ c.
ˆ Data Augmentation: Artificially increase training set size by creating modified
copies of data (rotations, flips, noise). Reduces effective variance.
ˆ Label Smoothing: Replace hard labels {0, 1} with soft labels {ϵ, 1 − ϵ}. Prevents
overconfidence.

6 Quick Reference Summary

Module 3 Key Takeaways:
ˆ Logistic Regression: h(x) = θ(wT x) ∈ (0, 1). Loss = cross-entropy (log-loss).

19
Machine Learning — Modules 3 & 4 3rd Year [Link]

No closed form; use gradient descent. Update: w ← w + ηyn xn θ(−yn wT xn )

(SGD).
ˆ MLP/DNN: Layers of neurons with activation functions. Backprop = chain
rule applied layer by layer. Use ReLU to avoid vanishing gradients.
ˆ Backprop steps: Forward pass (store activations) → output delta → backprop-
agate deltas → compute gradients → update weights.
ˆ RBF Network: Hidden neurons use Gaussian activations based on distance
from centres. Centres via K-means; output weights via linear regression.
ˆ RNN/LSTM: For sequential data; shares weights across time; LSTM uses gates
to handle long-term dependencies.
ˆ CNN: For spatial data; convolution (local, shared weights) + pooling + FC
layers. Feature hierarchy: edges → shapes → objects.

Module 4 Key Takeaways:

ˆ SVM: Finds the maximum-margin hyperplane. Margin ρ = 2/∥w∥. Minimise
1
2
∥w∥2 s.t. yn (wT xn + b) ≥ 1.
ˆ Support vectors: Points on the margin (αn > 0). Solution: w∗ =
P
α n y n xn .
′ 2
ˆ Kernel trick: Replace xT x′ with K(x, x′ ) = Φ(x)T Φ(x′ ). RBF kernel = e−γ∥x−x ∥
gives infinite-dimensional features.
ˆ Soft-margin SVM: Add slack ξn ; penalty C ξn . Large C = strict; small C
P
= lenient.
ˆ Overfitting: Ein ≪ Eout ; model learns noise. Fix: more data, regularisation,
early stopping, dropout, cross-validation.
ˆ L2 (Weight Decay): Ω = ∥w∥2 ; shrinks all weights; dense solution; closed form
(X T X + λI)−1 X T y.
ˆ L1 (Lasso): Ω = ∥w∥1 ; produces sparse weights (feature selection); no closed
form.
ˆ λ tuning: Larger λ = more bias, less variance. Always choose λ via cross-
validation.

End of Machine Learning Notes (Modules 3 & 4) — Good luck in your examinations!

20