Classifiers, sequence models, CNNs
This page shows how a machine turns pixels into labels. It covers supervised classifiers (k-NN, SVM), probabilistic models for sequences and neural networks. It also covers the full convolutional network with each size and parameter calculation.
Supervised image classification
A supervised classifier learns from images with known class labels. Then it predicts labels for images it has not seen. It has four steps:
- Input images.
- Label the training data: give known class labels to representative images, pixels or regions.
- Train the classifier: the model learns the visual patterns of each class.
- Predict: apply the trained model to unseen images. The model gives class labels.
Major algorithms
| Algorithm | How it works | Typical application |
|---|---|---|
| Support Vector Machine (SVM) | Finds a decision boundary that separates the classes | Land-cover classification |
| Random Forest | Combines the predictions of many decision trees (voting) | Crop-type classification |
| k-Nearest Neighbours (KNN) | Class from nearby labelled samples | Small image datasets |
| Maximum Likelihood Classifier | Uses estimated class probability distributions (assign pixel to class with highest likelihood) | Traditional multispectral remote sensing |
| Convolutional Neural Network (CNN) | Learns spatial features directly from images | Object recognition, scene classification |
| Vision Transformer (ViT) | Learns relationships between image patches using attention | Complex image classification |
k-Nearest Neighbours (KNN)
KNN has no real training. It stores all labelled examples. To classify a new image, it finds the $K$ most similar stored examples and takes a majority vote. The idea: similar features mean the same class.
You move to a new city and want to know which cricket team the locals support. Ask the 3 nearest neighbours and use the majority answer.
$Q$ = query (unknown) point, $P_i$ = $i$-th training point, $n$ = number of features. Smaller $d$ means more similar. Steps: (1) compute the distance to every training sample, (2) sort and take the $K$ smallest, (3) take the majority vote.
Slide example 1 (satellite pixel). Features: $x_1$ = red reflectance, $x_2$ = near-infrared (NIR) reflectance. Classify $Q=(4,6)$ with $K=3$.
| Sample | x1 (red) | x2 (NIR) | Class |
|---|---|---|---|
| P1 | 2 | 8 | Vegetation |
| P2 | 3 | 7 | Vegetation |
| P3 | 2 | 6 | Vegetation |
| P4 | 8 | 2 | Water |
| P5 | 7 | 3 | Water |
| P6 | 9 | 1 | Water |
Step 1: distances.
$d(Q,P1)=\sqrt{(4-2)^2+(6-8)^2}=\sqrt{4+4}=\sqrt8=2.828$
$d(Q,P2)=\sqrt{1+1}=1.414$
$d(Q,P3)=\sqrt{4+0}=2.000$
$d(Q,P4)=\sqrt{16+16}=5.657$
$d(Q,P5)=\sqrt{9+9}=4.243$
$d(Q,P6)=\sqrt{25+25}=7.071$.
Step 2: rank.
| Sample | Class | Distance | Rank |
|---|---|---|---|
| P2 | Vegetation | 1.414 | 1 |
| P3 | Vegetation | 2.000 | 2 |
| P1 | Vegetation | 2.828 | 3 |
| P5 | Water | 4.243 | 4 |
| P4 | Water | 5.657 | 5 |
| P6 | Water | 7.071 | 6 |
Step 3: vote. $K=3$ nearest: P2, P3, P1, all Vegetation. Vegetation 3 votes, Water 0. Prediction: Vegetation.
Slide example 2 (2x2 grayscale images, K=3). To use KNN on an image, flatten the pixel matrix into a vector. A $2\times2$ image becomes 4 numbers.
| 10 | 20 |
| 30 | 40 |
Training set: $I_1=[10,20,30,40]$ Cat, $I_2=[12,18,28,42]$ Cat, $I_3=[80,90,70,60]$ Dog, $I_4=[85,95,65,55]$ Dog. New image $I_{new}=[11,19,31,39]$.
$d_1=\sqrt{1^2+(-1)^2+1^2+(-1)^2}=\sqrt4=2$
$d_2=\sqrt{(-1)^2+1^2+3^2+(-3)^2}=\sqrt{1+1+9+9}=\sqrt{20}\approx4.47$
$d_3=\sqrt{(-69)^2+(-71)^2+(-39)^2+(-21)^2}=\sqrt{4761+5041+1521+441}=\sqrt{11764}\approx108.46$
$d_4=\sqrt{(-74)^2+(-76)^2+(-34)^2+(-16)^2}=\sqrt{5476+5776+1156+256}=\sqrt{12664}\approx112.53$
Sorted: $I_1$ (2.00, Cat), $I_2$ (4.47, Cat), $I_3$ (108.46, Dog), $I_4$ (112.53, Dog). With $K=3$ the neighbours are $I_1,I_2,I_3$: Cat 2, Dog 1. New image = Cat.
Practice. Same data as example 1, but $Q=(5,5)$, $K=3$.
$d(P1)=\sqrt{9+9}=4.243$
$d(P2)=\sqrt{4+4}=2.828$
$d(P3)=\sqrt{9+1}=3.162$
$d(P4)=\sqrt{9+9}=4.243$
$d(P5)=\sqrt{4+4}=2.828$
$d(P6)=\sqrt{16+16}=5.657$.
Three smallest: P2 (2.828, Veg), P5 (2.828, Water), P3 (3.162, Veg). Vegetation 2, Water 1. Answer: Vegetation. The tie between P2 and P5 does not change the answer, because both are inside the top 3.
Points to state in answers: KNN is a lazy learner (no training phase, all work at prediction). It needs a distance metric. Scale the features to similar ranges. Pick an odd $K$ for two classes to avoid ties. A small $K$ is noisy (overfits). A large $K$ blurs the class boundaries (underfits). The cost per prediction grows with the size of the training set.
Support Vector Machine (SVM)
SVM draws the boundary that separates two classes. The boundary stays as far as possible from the closest training points of both classes. A wide gap gives safer predictions on new data. SVM works on numerical feature vectors. It is used for classification and regression.
- Hyperplane: the decision boundary (a line in 2D, a plane in 3D, a hyperplane in higher dimensions).
- Margin: the distance between the decision boundary and the closest training samples of the classes.
- Support vectors: the training samples closest to the hyperplane. They alone determine the optimal boundary. If you remove any other point, the boundary does not move.
$x_i$ = feature vector, $y_i$ = class label, $N$ = number of samples. $w$ = weight vector (normal to the hyperplane), $b$ = bias (offset). To maximise the margin $2/\lVert w\rVert$, minimise $\lVert w\rVert^2/2$ subject to $y_i(w^Tx_i+b)\ge1$.
Slide example: apples vs oranges (1D weight). Apples at $x=1,2$; oranges at $x=5,6$.
Closest apple $=2$, closest orange $=5$. Midpoint $=(2+5)/2=3.5$. So the boundary is $x=3.5$. Support vectors: Apple at 2 and Orange at 5.
One feature gives $wx+b=0$. Choose $w=1$. Then $3.5+b=0$, so $b=-3.5$. Boundary: $x-3.5=0$, $f(x)=x-3.5$.
New fruit $x=2.5$: $f=2.5-3.5=-1$, negative, so Apple. New fruit $x=5.5$: $f=5.5-3.5=2$, positive, so Orange.
(Sign convention: negative = Apple, positive = Orange.)
Margin for the same data. Each support vector is 1.5 from the boundary, so the margin width is $1.5+1.5=3$. In canonical form we need $|f|=1$ at the support vectors, so $w=2/3$, $b=-7/3$. Check: $f(5)=\tfrac{10}{3}-\tfrac73=1$, $f(2)=\tfrac43-\tfrac73=-1$. And $2/\lVert w\rVert=2/(2/3)=3$, matching. The slide uses $w=1$ only to show the sign test. The class does not change if you scale $w,b$.
Practice (2D). $w=(1,1)$, $b=-6$. Classify $(2,3)$ and $(5,4)$, and find the margin width and the distance of $(2,3)$ from the boundary.
$f(2,3)=2+3-6=-1$, so class $-1$. $f(5,4)=5+4-6=3$, so class $+1$.
$\lVert w\rVert=\sqrt{1+1}=\sqrt2$. Margin width $=2/\sqrt2=\sqrt2\approx1.414$. Distance of $(2,3)$: $|-1|/\sqrt2\approx0.707$.
Extras that examiners add: if the data is not linearly separable, use a soft margin (allow some errors, penalty $C$). Or use a kernel (RBF, polynomial) to map the data to a higher dimension where it becomes separable. Multi-class SVM uses one-vs-rest or one-vs-one. Only the support vectors matter for prediction. R-CNN uses class-specific SVMs on CNN features.
| Point | KNN | SVM |
|---|---|---|
| Type | Instance-based, lazy | Boundary-based, trained |
| Decision rule | Majority vote of $K$ nearest samples | Sign of $w^Tx+b$ |
| Training | None (store data) | Optimise maximum margin |
| Prediction cost | High (distance to all samples) | Low (one dot product, or kernel sum over support vectors) |
| Key hyperparameter | $K$, distance metric | $C$, kernel |
Generative vs discriminative (supporting idea)
A generative classifier (maximum likelihood classifier, Naive Bayes, HMM) models how the data of each class is produced, $p(x\mid c)$ and $p(c)$. Then it uses Bayes rule to get $p(c\mid x)$. A discriminative classifier (SVM, logistic regression, CNN) models the boundary or $p(c\mid x)$ directly.
| Generative | Discriminative |
|---|---|
| Learns $p(x,c)=p(x\mid c)p(c)$ | Learns $p(c\mid x)$ or the boundary directly |
| Can generate new samples, handles missing data | Usually higher accuracy with enough data |
| Examples: Maximum likelihood classifier, Naive Bayes, HMM | Examples: SVM, logistic regression, CNN |
Probabilistic models for sequence data
These models describe, analyse and predict data that changes over time or follows an ordered sequence. In vision, a sequence can be video frames, body poses, object movements, facial expressions or satellite images over time.
$x_t$ = the visual observation at time $t$ (what we can see). $T$ = number of observations. $s_t$ = the hidden state at time $t$ (activity, object state or scene condition). The goal is often to infer the hidden sequence $S$ from the observed sequence $X$.
The slide stops at this setup. The standard model for it is the Hidden Markov Model (HMM). Write the HMM in an answer. An HMM assumes two things. (1) The next state depends only on the current state (Markov property). (2) Each observation depends only on the current state. Three items define it:
- Initial probabilities $\pi_i=P(s_1=i)$.
- Transition matrix $A_{ij}=P(s_{t+1}=j\mid s_t=i)$.
- Emission probabilities $B_i(x)=P(x_t=x\mid s_t=i)$.
Forward algorithm (probability of the observations): $\alpha_1(i)=\pi_iB_i(x_1)$, $\alpha_{t+1}(j)=\big[\sum_i\alpha_t(i)A_{ij}\big]B_j(x_{t+1})$, $P(X)=\sum_i\alpha_T(i)$.
Viterbi (best state path): replace the sum by a max, $\delta_{t+1}(j)=\max_i[\delta_t(i)A_{ij}]\,B_j(x_{t+1})$, and keep back-pointers.
Worked HMM example (added practice). Hidden states: Walk (W), Run (R). Observations: Low motion (L), High motion (H).
$\pi=(W:0.6,\;R:0.4)$. Transitions: $W\to W=0.7,\;W\to R=0.3,\;R\to W=0.4,\;R\to R=0.6$. Emissions: $W$: $L=0.8,H=0.2$
$R$: $L=0.3,H=0.7$. Observed: $X=(L,H)$.
Forward. $\alpha_1(W)=0.6\times0.8=0.48$
$\alpha_1(R)=0.4\times0.3=0.12$.
$\alpha_2(W)=(0.48\times0.7+0.12\times0.4)\times0.2=(0.336+0.048)\times0.2=0.0768$.
$\alpha_2(R)=(0.48\times0.3+0.12\times0.6)\times0.7=(0.144+0.072)\times0.7=0.1512$.
$P(X)=0.0768+0.1512=0.228$.
Viterbi. $\delta_1=(0.48,0.12)$. $\delta_2(W)=\max(0.48\times0.7,\,0.12\times0.4)\times0.2=0.336\times0.2=0.0672$ (from W). $\delta_2(R)=\max(0.48\times0.3,\,0.12\times0.6)\times0.7=0.144\times0.7=0.1008$ (from W). The best end state is R with 0.1008, so the most likely hidden path is $W\to R$ (walking, then running).
Neural networks and deep learning
The artificial neuron
A neuron takes inputs and multiplies each input by a weight. It adds the products and a bias. It then passes the result through an activation function.
$x_j$ = inputs, $w_{ij}$ = synaptic weights, $b_i$ = bias (like an input $x_0=+1$ with weight $b_i$). $n_i$ = net input, $f$ = activation function, $a_i$ = output.
Practice. Inputs $x=(1,2)$, weights $w=(0.5,-1)$, bias $b=0.5$. Net input $n=0.5(1)+(-1)(2)+0.5=-1$. ReLU: $\max(0,-1)=0$. Sigmoid: $1/(1+e^{1})=0.269$. Tanh: $\tanh(-1)=-0.762$.
Activation functions
Without a non-linear activation, stacked layers become one linear map. Activations let the network learn curved decision boundaries.
| Name | $f(x)$ | Output range |
|---|---|---|
| Binary step | 1 if $x\ge0$, else 0 | {0, 1} |
| Bipolar step | 1 if $x\ge0$, else -1 | {-1, 1} |
| Linear / identity | $x$ | $(-\infty,\infty)$ |
| Sigmoid / logistic | $\dfrac{1}{1+e^{-x}}$ | (0, 1) |
| Tanh | $\tanh x$ | (-1, 1) |
| ReLU | $\max(0,x)$ | $[0,\infty)$ |
| Leaky ReLU | $x$ if $x\ge0$, else $\alpha x$ | $(-\infty,\infty)$, $\alpha\gt0$ |
| PReLU | $\max(x,\alpha x)$ ($\alpha$ learned) | $(-\infty,\infty)$ |
| ELU | $x$ if $x\gt0$, else $\alpha(e^x-1)$ | $(-\alpha,\infty)$ |
| SELU | $\lambda x$ if $x\gt0$, else $\lambda\alpha(e^x-1)$ | $(-\lambda\alpha,\infty)$ |
| Softplus | $\ln(1+e^x)$ | $(0,\infty)$ |
| Softsign | $\dfrac{x}{1+|x|}$ | (-1, 1) |
| Swish / SiLU | $\dfrac{x}{1+e^{-x}}$ | about $(-0.2785,\infty)$ |
| GELU | $x\Phi(x)$ ($\Phi$ = normal CDF) | about $(-0.17,\infty)$ |
| Mish | $x\tanh(\ln(1+e^x))$ | about $(-0.31,\infty)$ |
| Hard sigmoid | $\max(0,\min(1,0.2x+0.5))$ | [0, 1] |
| Hard tanh | $\max(-1,\min(1,x))$ | [-1, 1] |
| Gaussian / RBF | $e^{-x^2}$ | (0, 1] |
Learn at least these with formula and range: step, sigmoid, tanh, ReLU, Leaky ReLU. ReLU is the main choice in CNNs for three reasons. It is cheap to compute. It does not saturate for positive inputs (this reduces vanishing gradients). It gives sparse activations. Its weakness is "dying ReLU" (neurons stuck at 0). Leaky ReLU, PReLU and ELU fix this.
Network topologies
- Single-layer feed-forward: the input layer projects straight into the output layer.
- Multi-layer feed-forward: one or more hidden layers. Each layer receives input only from earlier layers, typically only the layer directly before it.
- Recurrent: has feedback. Some outputs connect back to inputs (discrete time). It is useful for sequences.
A traditional ANN usually means a shallow feed-forward network with one or a few hidden layers. Deep learning uses many layers.
What deep learning is
Deep learning is a branch of ML. It uses neural networks with multiple layers to learn complex patterns. In vision, it recognises objects, classifies images, detects abnormalities, segments regions and understands video. It learns hierarchical representations. Early layers detect edges, corners and textures. Middle layers detect shapes and parts (ears, eyes). Deep layers combine the parts into the whole object (cat).
| Feature | Traditional ML | Deep learning |
|---|---|---|
| Feature extraction | Often hand-designed | Learned automatically |
| Data requirement | Works with smaller datasets | Often needs large datasets |
| Computation | Usually lower | Often higher (GPUs) |
| Image representation | Handcrafted features such as HOG, SIFT | Features learned by the network |
| Examples | SVM, KNN, decision trees | CNN, ResNet, Vision Transformer |
How a network learns
- Collect training images and labels.
- Forward propagation: pass the input through the network to get a prediction.
- Loss: measure the gap between the prediction and the correct answer (e.g. $E=\sum\tfrac12(\text{target}-\text{output})^2$ on the CNN slide, or cross-entropy).
- Backpropagation and update: compute the gradients. Adjust the weights with an optimiser such as gradient descent or Adam: $w\leftarrow w-\eta\,\partial L/\partial w$ with learning rate $\eta$.
- Predict on new unseen images.
Advantages of deep learning: it extracts features automatically (pixels, edges, textures, shapes, objects). It handles complex data. A shallow ANN needs good features as input. A deep CNN learns spatial patterns from pixels. CNN-transformer hybrids add long-range relationships. It learns hierarchical representations. It uses large datasets better.
Why convolutional networks
An image is a tensor: grayscale $H\times W$, RGB $H\times W\times3$. A plain fully connected (FC) layer flattens the image. This loses the idea of "nearby pixels". It also needs too many weights.
RGB image $224\times224\times3=150{,}528$ inputs. Connect to an FC layer of 1,000 neurons: $150{,}528\times1000=150{,}528{,}000$ weights (over 150 million) for one layer, without biases. With biases: $150{,}529{,}000$ parameters.
Compare a conv layer of 64 filters of $3\times3$ on the same image: $64\times(3\times3\times3+1)=64\times28=1{,}792$ parameters.
CNNs solve this with three ideas:
- Spatial locality: useful patterns (edges, corners) are local. Each neuron looks only at a small window.
- Parameter sharing: the network uses the same filter at every position. Thus there are few parameters.
- Translation equivariance: if the input shifts, the feature map shifts with it. Pooling and later layers add translation tolerance (invariance).
CNN architecture
A basic CNN has three kinds of layers: convolutional, pooling and an output (fully connected) layer. The overall flow: input image (e.g. $224\times224\times3$), then convolution + ReLU (edges, textures), pooling (shrink), deeper conv layers (shapes, object parts), flatten or global pooling + classifier. The output is class scores (e.g. healthy leaf 0.08, diseased leaf 0.92). The first part does feature extraction. The last part does classification.
Convolution layer
A small $k\times k$ filter slides across the image. At each position, it multiplies element-wise with the patch under it and adds the products (a local dot product). The grid of results is a feature map (activation map). The layer uses the same filter weights at all positions. With stride 1 and no padding, the output is $(H-k+1)\times(W-k+1)$.
- Stride: how many pixels the filter moves at each step. Stride 1 = one pixel at a time. A larger stride gives a smaller output.
- Padding: add rings of zeros around the image. Then the output does not shrink too much and the border pixels are used. Use more rings for bigger filters (P=1 for $3\times3$ and P=2 for $5\times5$ keep the size at stride 1).
- Depth of the filter equals the depth (channels) of the input. A filter on an RGB image is $F\times F\times3$ and extends through all channels. One filter gives one feature map (depth 1).
- Multiple filters: all filters have the same size. The layer stacks their outputs along the depth. $K$ filters give output depth $K$. Slide example: a $32\times32\times3$ input and 10 filters of $5\times5\times3$ give $28\times28\times10$.
$O$ = output width/height, $N$ = input width/height, $F$ = kernel (filter) size, $P$ = padding on each side, $S$ = stride. The floor handles the case where the filter does not fit exactly. For a rectangular input, apply the formula to the width and the height separately. Output depth = number of filters.
Parameters in a conv layer: $(F\times F\times C_{in}+1)\times K$ ($+1$ is the bias per filter, $K$ is the number of filters). Pooling layers have no parameters.
"Same" padding at stride 1 needs $P=(F-1)/2$. "Valid" means $P=0$. Pooling uses the same size formula: $\lfloor(N-F)/S\rfloor+1$.
Slide example (size). $N=5$, $F=3$, $P=0$, $S=1$: $O=\frac{5+0-3}{1}+1=3$. Output $3\times3$.
Practice sizes. (a) $N=28,F=3,P=1,S=2$: $(28+2-3)/2=13.5\to13$, $+1=14$. (b) $N=224,F=7,P=3,S=2$: $(224+6-7)/2=111.5\to111$, $+1=112$. (c) $N=32,F=5,P=2,S=1$: $(32+4-5)/1+1=32$ (size preserved).
Pooling layer
Pooling shrinks the height and width. This reduces computation and gives a little translation tolerance. It works on each channel independently, so the depth does not change. Max pooling keeps the largest value in each window. It is the most popular type. Average pooling keeps the mean. Pooling has no learnable parameters.
Slide example. Max pooling, window $2\times2$, stride 2 on a $4\times4$ map:
| 429 | 505 | 686 | 856 |
| 261 | 792 | 412 | 640 |
| 633 | 653 | 851 | 751 |
| 608 | 913 | 713 | 657 |
Top-left block $\max(429,505,261,792)=792$; top-right $\max(686,856,412,640)=856$; bottom-left $\max(633,653,608,913)=913$; bottom-right $\max(851,751,713,657)=851$.
| 792 | 856 |
| 913 | 851 |
Size: $(4-2)/2+1=2$. RoI pooling does the same operation (see Object detection page).
ReLU in a CNN
ReLU, $f(x)=\max(0,x)$, is applied after each convolution. Positive values pass and negative values become 0. It adds non-linearity, so stacked convolutions do not become one big linear filter.
| Conv output x | -2 | 3 | 5 | -1 | 4 | -6 |
|---|---|---|---|---|---|---|
| ReLU f(x) | 0 | 3 | 5 | 0 | 4 | 0 |
Fully connected layer (output)
The last layer maps the features to one score per class. First flatten the final tensor, e.g. $7\times7\times64=3136$ values. Then connect it to the output units. For 10 classes: $3136\times10+10=31{,}370$ parameters. A softmax usually turns the scores into probabilities: $p_k=e^{z_k}/\sum_j e^{z_j}$.
Full CNN calculation (slide example)
Image $5\times5\times1$ (1 = white, 0 = black; the last 1 means one channel, grayscale):
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
Filter (looks for a horizontal intensity change): kernel $3\times3$, stride 1, padding 0, 1 filter.
| 1 | 1 | 1 |
| 0 | 0 | 0 |
| -1 | -1 | -1 |
Convolution. Size: $O=(5+0-3)/1+1=3$, so a $3\times3$ map. First position, upper-left patch $\begin{bmatrix}1&1&1\\1&1&1\\0&0&0\end{bmatrix}$: top row $1+1+1=3$, middle row $\times0$ gives 0, bottom row $0\times(-1)\times3=0$, total $3$. Every window in the first window-row (image rows 1-3) has the form [1 1 1; 1 1 1; 0 0 0] and gives 3. Every window in the second window-row (image rows 2-4) has the form [1 1 1; 0 0 0; 0 0 0]. The top row $\times1$ gives 3 and the rest give 0, so the result is 3. Every window in the third window-row (image rows 3-5) is all zeros, so 0. Feature map (slide):
| 3 | 3 | 3 |
| 3 | 3 | 3 |
| 0 | 0 | 0 |
ReLU. No negatives, so nothing changes.
Max pooling, $2\times2$ window, stride 1: output size $(3-2)/1+1=2$. First position $\max(3,3,3,3)=3$; last position $\begin{bmatrix}3&3\\0&0\end{bmatrix}\to3$. Pooled map $\begin{bmatrix}3&3\\3&3\end{bmatrix}$.
Flatten. $[3,3,3,3]$, so $2\times2=4$ inputs for the FC layer.
Fully connected with 2 neurons, each seeing all four values. Neuron 1: weights $[1,1,1,1]$, $b=0$: $3+3+3+3=12$. Neuron 2: weights $[1,0,-1,0]$, $b=0$: $3+0-3+0=0$. Output $\begin{bmatrix}12\\0\end{bmatrix}$. FC parameters $=4\times2+2=10$ (the slide set the biases to 0).
Practice problems from the slides, solved
Problem 1: complete flow. $X=\begin{bmatrix}1&1&1&1&1\\1&5&5&1&1\\1&5&5&1&1\\1&1&1&1&1\\1&1&1&1&1\end{bmatrix}$, $K=\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$ (stride 1, no padding, assume ReLU, then $2\times2$ max pool stride 1, then flatten).
Size: $(5-3)/1+1=3$. Each output is the sum of its $3\times3$ patch:
(0,0): $1+1+1+1+5+5+1+5+5=25$. (0,1): $1+1+1+5+5+1+5+5+1=25$. (0,2): $1+1+1+5+1+1+5+1+1=17$.
(1,0): $1+5+5+1+5+5+1+1+1=25$. (1,1): $5+5+1+5+5+1+1+1+1=25$. (1,2): $5+1+1+5+1+1+1+1+1=17$.
(2,0): $1+5+5+1+1+1+1+1+1=17$. (2,1): $5+5+1+1+1+1+1+1+1=17$. (2,2): $5+1+1+1+1+1+1+1+1=13$.
| 25 | 25 | 17 |
| 25 | 25 | 17 |
| 17 | 17 | 13 |
ReLU: unchanged (all positive). Max pool $2\times2$, stride 1 gives a $2\times2$ map: every window contains a 25, so all four outputs are 25: $\begin{bmatrix}25&25\\25&25\end{bmatrix}$. Flatten: $[25,25,25,25]$, 4 values.
Problem 2. Input $32\times32$, filter $5\times5$, $P=0$, $S=2$. $O=\lfloor(32-5)/2\rfloor+1=\lfloor13.5\rfloor+1=14$. Output $14\times14$ (per filter).
Problem 3. $X=\begin{bmatrix}1&3&2&4\\5&6&1&2\\7&2&8&3\\4&9&5&6\end{bmatrix}$, $2\times2$ average pooling, stride 2.
Top-left: $(1+3+5+6)/4=15/4=3.75$. Top-right: $(2+4+1+2)/4=9/4=2.25$. Bottom-left: $(7+2+4+9)/4=22/4=5.5$. Bottom-right: $(8+3+5+6)/4=22/4=5.5$.
| 3.75 | 2.25 |
| 5.5 | 5.5 |
For comparison, max pooling would give $\begin{bmatrix}6&4\\9&8\end{bmatrix}$.
Problem 4. Input $32\times32\times3$; Conv (16 filters, $3\times3$, s=1, p=1); MaxPool $2\times2$ s=2; Conv (32 filters, $3\times3$, s=1, p=1); MaxPool $2\times2$ s=2.
| Layer | Calculation | Output size |
|---|---|---|
| Input | $32\times32\times3$ | |
| Conv1 | $(32+2-3)/1+1=32$, depth 16 | $32\times32\times16$ |
| Pool1 | $(32-2)/2+1=16$, depth unchanged | $16\times16\times16$ |
| Conv2 | $(16+2-3)/1+1=16$, depth 32 | $16\times16\times32$ |
| Pool2 | $(16-2)/2+1=8$ | $8\times8\times32$ |
Extra: parameters. Conv1: $(3\times3\times3+1)\times16=448$. Conv2: $(3\times3\times16+1)\times32=4{,}640$. Pooling: 0. Flatten: $8\times8\times32=2{,}048$ values going to the FC layer.
Problem 5. Same $X$ as Problem 1. Filters $K_1=\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$ and $K_2=\begin{bmatrix}-1&-1&-1\\0&0&0\\1&1&1\end{bmatrix}$; stride 1, padding 0, bias 0.
1. Feature map from $K_1$ (from Problem 1): $\begin{bmatrix}25&25&17\\25&25&17\\17&17&13\end{bmatrix}$.
2. Feature map from $K_2$. Each output = (sum of bottom row of the patch) minus (sum of top row of the patch).
(0,0): top $1+1+1=3$, bottom $1+5+5=11$, so $8$. (0,1): top 3, bottom $5+5+1=11$, so 8. (0,2): top 3, bottom $5+1+1=7$, so 4.
(1,0): top $1+5+5=11$, bottom 3, so $-8$. (1,1): top $5+5+1=11$, bottom 3, so $-8$. (1,2): top 7, bottom 3, so $-4$.
(2,0): top 11, bottom 3, so $-8$. (2,1): $-8$. (2,2): top 7, bottom 3, so $-4$.
| 8 | 8 | 4 |
| -8 | -8 | -4 |
| -8 | -8 | -4 |
3. ReLU. Map 1 unchanged. Map 2: negatives become 0: $\begin{bmatrix}8&8&4\\0&0&0\\0&0&0\end{bmatrix}$.
4. Max pool $2\times2$, stride 1. Map 1: every window has a 25, so $\begin{bmatrix}25&25\\25&25\end{bmatrix}$. Map 2: windows: top-left $\max(8,8,0,0)=8$, top-right $\max(8,4,0,0)=8$, bottom row windows all zeros: $\begin{bmatrix}8&8\\0&0\end{bmatrix}$.
5. Final dimensions: $2\times2\times2$ (two channels).
6. Flatten: channel 1 then channel 2: $[25,25,25,25,8,8,0,0]$, 8 values.
Remember that deep learning "convolution" is cross-correlation: the kernel is not flipped. The slides (and the answers above) multiply the kernel as given with the patch. If the question means "convolution" in the signal-processing sense and the kernel is asymmetric, flip the kernel 180 degrees first. Also, padding $P$ is on every side, so it appears as $2P$ in the formula.
Quick self-test
List the four steps of supervised image classification.
Input images, label the training data, train the classifier, predict classes for unseen images.
Classify $Q=(4,6)$ using the 3-NN rule given points A(2,8) Veg, B(3,7) Veg, C(2,6) Veg, D(8,2) Water, E(7,3) Water. Show distances.
$d$: A 2.828, B 1.414, C 2.000, D 5.657, E 4.243. Three nearest: B, C, A, all Vegetation, so Vegetation (3 votes to 0).
Define hyperplane, margin and support vectors. For apples at x=1,2 and oranges at x=5,6, find the SVM boundary and classify x=4.
Hyperplane: the decision boundary. Margin: the distance from the boundary to the nearest training points of the classes. Support vectors: the nearest points that fix the boundary. Here the support vectors are 2 and 5, and the boundary is $x=3.5$ (so $f=x-3.5$). $f(4)=0.5>0$, so Orange.
For $w=(2,1)$, $b=-4$, find the class of $(3,1)$ and the margin width.
$f=2(3)+1-4=3>0$, so $+1$. $\lVert w\rVert=\sqrt5$; margin width $=2/\sqrt5\approx0.894$.
Why can't we feed a 224x224x3 image straight into a fully connected layer of 1000 neurons? How many weights?
$224\times224\times3=150{,}528$ inputs, so $150{,}528\times1000=150{,}528{,}000$ weights. This is too many weights, and the network can overfit easily. Flattening also destroys the spatial neighbourhood structure. CNNs use local filters with shared weights.
A $64\times64$ input goes through a $5\times5$ conv with P=2, S=1, then $2\times2$ max pooling with S=2. Give the output size.
Conv: $(64+4-5)/1+1=64$. Pool: $(64-2)/2+1=32$. Output $32\times32$ (times the number of filters in depth).
How many parameters in a conv layer with 20 filters of $5\times5$ on a 3-channel input? What about a max-pool layer?
$(5\times5\times3+1)\times20=76\times20=1{,}520$. Max pooling has 0 parameters.
Apply ReLU to $[-3,2,0,-1,7]$ and then $2\times2$ average pooling to $\begin{bmatrix}1&3\\5&7\end{bmatrix}$.
ReLU: $[0,2,0,0,7]$. Average pooling: $(1+3+5+7)/4=4$.
Difference between traditional ML and deep learning for image classification.
Traditional ML (SVM, KNN, trees) uses hand-crafted features (HOG, SIFT). It works on smaller data with less compute. Deep learning (CNN, ResNet, ViT) learns features automatically through layers (edges, then parts, then objects). It usually needs more data and compute.
Using the HMM in this page, compute $P(X)$ for $X=(H,H)$ (optional).
$\alpha_1(W)=0.6\times0.2=0.12$; $\alpha_1(R)=0.4\times0.7=0.28$. $\alpha_2(W)=(0.12\times0.7+0.28\times0.4)\times0.2=(0.084+0.112)\times0.2=0.0392$. $\alpha_2(R)=(0.12\times0.3+0.28\times0.6)\times0.7=(0.036+0.168)\times0.7=0.1428$. $P=0.182$.
- Supervised classification: label the data, train, predict. Algorithms: SVM, random forest, KNN, maximum likelihood, CNN, ViT.
- KNN: Euclidean distance to all training points, pick $K$ nearest, majority vote. Flatten images into vectors first.
- SVM: maximum-margin hyperplane $w^Tx+b=0$. Margin: $2/\lVert w\rVert$. The support vectors define the hyperplane. The sign of $f(x)$ gives the class.
- Sequence models: observations $X$, hidden states $S$; HMM uses $\pi$, $A$, $B$; forward gives $P(X)$, Viterbi gives the best path.
- Neuron: $a=f(\sum wx+b)$. Know ReLU, sigmoid, tanh, Leaky ReLU. Topologies: single-layer, multi-layer feed-forward, recurrent. Learning = forward, loss, backprop, update.
- CNN beats FC on images through locality, parameter sharing, translation equivariance. Layers: conv, ReLU, pooling, flatten, FC.
- Output size $\lfloor(N+2P-F)/S\rfloor+1$; conv params $(F^2C_{in}+1)K$; pooling has no parameters and keeps depth.