Lecture 8: Neural Networks and
Unsupervised Learning
Matt Ellis and Mike Smith
1
Session outline
Neural networks
• Recap
• Convolutional operations and networks
Unsupervised learning: Dimensional reduction
• Principal component analysis (PCA)
2
Learning Objectives
By the end of this session you should be able to:
1. Explain the structure and training of convolutional neural networks.
2. Understand what pooling, padding and strides mean for CNNs.
3. Explain the method of PCA for dimensionality reduction.
4. Recall the criterion function for the 1st principal component.
3
Neural Networks
4
Artificial Neurons
Activation function
Output
Bias Unit (1)
yi O On
inputs
Σ output
xj
Threshold Input
wij
∑
(Synaptic) weight yi = f wij xj
from j to i
j
5
f
Common activation functions
6
Computation in neural networks
Make predictions (decisions)
Forward pass
Plug in x to get y
Input Hidden Output
(1) Hidden layer neurons:
W
h = f (W x + b )
(2)
W (1) (1)
x y Output layer neurons:
y = f (W h + b )
(2) (2)
h
Compute gradients of the cost (error or
Backward pass loss) w.r.t weights to nd optimal values.
7
fi
Image classification with neural networks
NN predicts class:
Input Hidden Output 1 output neuron per class
(1)
(one hot encoding)
W
W (2)
x y c = arg max (yi)
i
Flatten to a 1D array/vector. Some models convert y into a
probability, e.g softmax
N x N image to a N2 x 1 vector.
Cross entropy loss is suitable for
multi class predictions.
8
Decision boundaries
0 hidden layers - linear classi er
Decision boundary
Decision boundary
9
fi
Decision boundaries
1 hidden layer - boundary of a convex region (open or closed)
Decision boundary
Decision boundary
10
Different levels of abstraction
Output
Hidden layer 3
Hidden layer 2
Hidden layer 1
Input
Example from Honglak Lee (NeurIPS 2010) 11
Batches!
Predict for multiple inputs at once, update weights after each batch.
1 sample NB samples All samples
Stochastic Mini-Batch Batch
More ‘noise’ Compromise Smooth
Quick updates Slow updates
This means we have to modify
The convention used for PyTorch is our linear operation to make sure
number of samples as rst dimension. the matrix dimensions match!
T
[Link] = (NB = batch_size, Nin = input_features) y = xW + b
(NB x Nout) = (NB x Nin) @ ( Nin x Nout )
12
fi
Overfitting
The danger with too many parameters is that we learn
‘noisy’ features of the data and can’t generalise.
Image credit: Mathworks, [Link] [Link]
13
fi
Overfitting = poor generalisation
Error Techniques:
Validation
• Early stopping
• Cross-validation to nd
optimal number of epochs
• Dropout
Training • Regularisation terms
Epochs • Smaller models
14
fi
Example for a multi-layer network
class neural_network([Link]):
def __init__(self, in_features, hidden_features, out_features, bias=True):
super().__init__()
self.lin1 = [Link]( in_features, hidden_features, bias)
self.act_func1 = [Link]()
self.lin2 = [Link]( hidden_features, out_features, bias)
self.act_func2 = [Link]()
def forward(self, x):
h = self.act_func1(self.lin1(x))
return self.act_func2(self.lin2(h))
15
Simplify using [Link]
If we are chaining together layers, we can use the built in Sequential class:
model = [Link](
[Link](in_features, hidden_features),
[Link](),
[Link](hidden_features, out_features),
[Link]()
)
In each case we can use the model to predict using:
y_approx = model(x)
16
Fully connected layers
What if our network was bigger?
• Input image: 200 x 200 pixels, rst hidden layer: 500 neurons
Q: How many weights from input to rst hidden layer?
• 200 x 200 x 500 = 20 million
Q: Why might a FC layer be problematic for images?
• Lots of weights = long computation.
• Needs lots of training data to avoid over- tting.
• Small shift in weights can lead to a large change in prediction.
• Not making use of geometry.
17
fi
fi
fi
Convolutional Neural Networks
18
Imagenet Large Scale Visual Recognition Challenge
Alexnet - rst to achieve sub-25% error rate
Input Fully
image 5 Convolutional layers connected 1000-way
(pixels) with max pooling layers softmax
19
fi
Convolutional neural network
Locally connected layers: look for local features in small regions of the image
Weight sharing: detect the same local features across the whole image
20
Weight sharing
Each neuron in the higher layer detects the same
feature, but in a di erent location in the lower
layer.
Detection - the output (activation) is high if the
feature is present.
Feature - something in the image (shape, blob,
line) that we want to detect.
21
ff
Convolutional filters
Convolutional operation (b is bias):
y, Output image
y=b+W⋆x
W Convolution lter is applied as a moving
Convolutional window over the 2D input image.
lter
F−1 F−1
∑∑
yij = b + Wkl xi+k,j+l
k=0 l=0
x, Input image (1 channel)
Vincent Dumoulin, Francesco Visin - A guide to convolution arithmetic for deep learning
22
fi
fi
Forward pass example
3 x 3 lter/kernel Input Image Output Image
1 1 1 0 0
1 0 1 0 1 1 1 0 4 ? ?
0 1 0 ⋆ 0 0 1 1 1 = ? ? ?
1 0 1 0 0 1 1 0 ? ? ?
0 1 1 0 0
Exercise
How many trainable weights?
What are the values of the bottom output row?
Why is the output size 3 x 3?
23
fi
Forward pass example
3 x 3 lter/kernel Input Image Output Image
1 1 1 0 0
1 0 1 0 1 1 1 0 4 ? ?
0 1 0 ⋆ 0 0 1 1 1 = ? ? ?
1 0 1 0 0 1 1 0 ? ? ?
0 1 1 0 0
Exercise
How many trainable weights? 9 + bias (if using)
What are the values of the bottom output row? 2, 3, 4
Why is the output size 3 x 3? The kernel can only move 2 steps up/down.
24
fi
Strided convolutions
Shift the kernel by multiple pixels when computing the output feature:
Stride = 2
Objective: to consolidate (summarise) information.
25
Size of output
Output size = (N - F + 2P)/S + 1
N
S = stride
P = padding
F
Example
N F N = 7, F = 3, P = 0
Stride = 1 → O = (7-3)/1 + 1 = 5
Stride = 2 or 3 ?
26
Size of output
Output size = (N - F + 2P)/S + 1
N
S = stride
P = padding
F
Example
N F N = 7, F = 3, P = 0
Stride = 1 → O = (7-3)/1 + 1 = 5
Stride = 2 → O = (7-3)/2 + 1 = 3
Stride = 3 → O = (7-3)/3 + 1 = 2.333
27
Convolutions for colour images
H
H
W W
3 Kernel is also a 3D tensor. This
2D image with 3 channels (RGB) example is 3 x 3 x 3
A tensor!: PyTorch uses (NB,C,H,W) shape Number of input channels or
feature maps
28
Detecting multiple features
Given a single lter map, how many features are being detected?
Have multiple lter maps to detect di erent features.
Example:
Input image size: 3 x 32 x 32
Convolutional kernel (4D): 3 x 3 x 3 x 5
3 : number of input channels or input feature maps
5 : number of output channels or output feature maps
29
fi
fi
ff
Zero padding and pooling
Add zeros around the edge of the input Downsample the feature maps by using
image. Common padding size is (F-1)/2. either a max or average operation.
What are the bene ts of these operations?
30
fi
Rationale for zero padding and pooling
Zero padding: Pooling:
To preserve the shape of the Dimension reduction - make the
image. representations smaller and more
manageable
To keep information that is around
the edges. Operate over each feature map
independently.
Common types are Max or Average.
31
Max pool example
What is the output?
Image credit: Wikimedia ([Link]
32
Exercise
Input volume = 3 x 32 x 32; 10 lters, 5 x 5 shape with stride = 1, pad = 2
N − F + 2P
Remember: O = +1
S
How many input and output channels? 3 input channels, 10 output channels
What is the output volume size? 10 x 32 x 32
How many parameters are in this layer? 10 x 3 x 5 x 5 lters = 750 weights
33
fi
fi
Take home messages
• Neurons perform a weighted sum of inputs followed by a non-linear function
• Neural networks connect many neurons together, the non-linearity allows for
complex decision boundaries or functions to be learned.
• Deeper layers in a network detect smaller features of the input.
• Convolutional networks (generally) better for image data than fully connected
layers.
• Convolutional layers share weights ( lters) which detect whether features are
within a local region.
• Zero padding, pooling and strides can be used to consolidate information.
34
fi
Reading
Chapter 9 of Deep Learning by Goodfellow.
Available at [Link]
35
Exercise
You are given a data set of 1000 colour images shaped
1024 by 1024 pixels of 25 di erent animal species.
Over the break discuss, possible architectures (both
CNN and FC) that you could design to classify these
images. This could be quite general but think of what key
points you would need.
36
ff
Unsupervised Learning
37
Supervised vs Unsupervised
Machine Learning
Supervised Learning Unsupervised Learning
38
Supervised vs Unsupervised
Machine Learning
Supervised Learning Unsupervised Learning
Dimensionality
Classi cation Regression Clustering
Reduction
• Click-through-rate
• Big data visualisation • Customer segmentation
• Image classi cation • Market forecasting • Feature discovery • Targeted marketing
• Diagnostics • Ad popularity • Structure discovery • Recommendation
• Fraud detection
39
fi
fi
Unsupervised Learning
Supervised: each data point has a label (desired output)
Unsupervised: No labels for the data
ML Supervised Unsupervised
Discrete output Classi cation Clustering
Dimensionality
Continuous output Regression
Reduction
40
fi
Dimensionality Reduction
High dimensional data Low dimensional data
41
Why apply dimensionality reduction?
• Curse of dimensionality • Visualisation
• Reduce redundancy
42
Question
USPS handwritten digit dataset:
Image size: 64 by 57
Black or white pixels (1 bit)
How many dimensions is a single image?
How many possible images?
43
Question
USPS handwritten digit dataset:
Image size: 64 by 57
Black or white pixels (1 bit)
How many dimensions is a single image?
64 × 57 = 3648
How many possible images?
64×57 3648
2 =2 =?
44
Projection mapping
45
Low-D Subspace or Manifolds
For high dimensional data with structure:
Fewer variations than dimensions
Data lives on a lower dimensional manifold
→ Deal with them by looking for a lower dimensional embedding (or
projection)
46
Principal Component Analysis
47
PCA Demo
Demonstration:
[Link] [Link]/
48
fl
Finding a basis to best represent data
PCA
1. Rotate the data with some rotation
matrix (linear transformation) so that
features are uncorrelated.
2. Keep the dimensions with highest
variance for DR.
Adapted from Neural Networks and
Learning Machines by Simon Haykin
(Pearson 2009) Unit vectors that
form the basis
49
Basis vectors for datapoints
A point in space is described by its projections on a set of basis vectors.
Datapoint Datapoint in transformed basis
x = ax̂1 + bx̂2 x = cu1 + du2
bx̂2
u2 cu1
x̂2
ax̂1
du2 u1
x̂1
T T
Projections on a = x̂1 x Projections on c = u1 x
T T
basis vectors b = x̂2 x basis vectors d = u2 x
T T
Datapoint vector = [a, b] Datapoint vector in new basis = [c, d]
50
Rotating the basis as a transformation
Data Space Feature Space
Transformation
T
[u2 x]
u1 x
x=[ ] y=[ ]=
a c
b d T
Transformation (rotation) matrix
T
[u2 ]
T
u1 y=U x T
U = T
51
Variances and Covariance
PCA: Find directions that maximises the variance of the transformed data.
Recall that:
Variance & Covariance - measure of the “spread” of a set of points
around their centre (mean).
Variance (scalar) - measure of the spread each dimension separately.
Covariance - measure of how much each of the dimensions vary from the
mean with respect to each other.
• Covariance is measured between two dimensions.
• Covariances sees if there is a relation between them.
• The covariance of a dimension with itself is the variance
52
PCA
Find directions that maximises the variance of the transformed data.
How do we nd these directions?
Eigenvectors of the sample covariance (scatter) matrix
N
1
∑
Cij = (xni − μi)(xnj − μj)
N n=1
Question: what is the covariance matrix in the projected space?
53
fi
Eigenvectors are directions of maximum variance
Find the rst direction u1 that maximises the variance in the projected space.
Optimisation criterion for 1st PCA including a unit-norm constraint via
Lagrange multipliers:
L(u1, λ1) = T
u1 Cu1 + λ1 (1 − u1 u1)
T
Variance of the Constraint to keep
data in direction u1 | u1 | = 1
We want to maximise this, so what can we do?
54
fi
Eigenvectors are directions of maximum variance
Find derivative w.r.t u1 and set to zero:
L(u1, λ1) = T
u1 Cu1 + λ1 (1 − u1 u1)
T
dL(u1, λ1)
= 2Cu1 − 2λ1u1 = 0
du1
Eigenvalue problem!
Cu1 = λ1u1 Multiple solutions, which do we pick?
Pick the largest eigenvalue.
55
Selecting other transformation vectors
Further directions: Orthogonal (uncorrelated) to the rst and each other
Use the remaining eigenvectors of C:
• Eigenvectors - basis vectors, principal components
• Eigenvalues - the variance of the data captured by that direction
For a D dimensional input, we will have D eigenvectors.
Create transformation matrix by forming these as columns.
U = [u1, …, uD]
For DR, we select the k eigenvectors with the highest
eigenvalues to keep, drop the rest.
56
fi
Reconstruction error vs maximum variance
We could minimise the error when transforming back (reconstruction).
1
( xn − x̃n)
2
2N ∑
E=
n
1
( xn − u1(u1 xn))
T 2
2N ∑
u1 =
T n
Transform yn1 = u1 xn 1
T 2
∑
= − u1 Cu1 + | xn |
N n
Inverse
Transform x̃n = u1yn1 So min reconstruction error = max variance
57
How many dimensions to keep?
Pick based on percentage of variance kept/lost.
The eigenvalues measure the amount of variance in each transformed
dimension.
The fraction of the total variance The total fraction of explained
described by the i-th PC is variance by a subset of PCs is
k
λi ∑i=1 λi
D D
∑j=1 λj ∑j=1 λj
58
How many dimensions to keep?
Look for an ‘elbow’ in a scree plot (plot of explained variance or eigenvalues).
59
Representation and Reconstruction
Example: Olivetti faces dataset.
y1
Representation:
Face x in ‘face space’
T
y = U (x − μ) = ⋮
coordinates. yk
Reconstruction: use representation to rebuild using eigenvectors as basis.
= +
x̃ = μ + y1u1 + y2u2 + y3u3 + …
60
PCA ingredients
• Data + pre-processing
• Model:
T
• Structure/architecture: Linear projection layer y = U x
• Parameters: The principal components (eigenvectors)
• Hyper-parameters: Number of components to keep, k
• Evaluation metric: Variance explained by the PCs
• Optimisation: Eigen-decomposition
61
Take Home Messages
• Unsupervised learning: no labels, learn from data only.
• Dimensionality reduction: useful for visualisation, feature discovery.
• Principal component analysis (PCA): use eigenvectors of the covariance
matrix to nd directions of maximum variance.
• Reconstruction error - mean squared di erence of our recovered data (after
transforming back) against the original data.
62
fi
ff
Further Reading
Chapter 7 (sections 7.1 and 7.2) in A First Course in Machine Learning
by Rogers and Girolami.
Chapter 14 of Deep Learning by Goodfellow.
Available at [Link]
63