0 · Exam Mapcourse data · L13
| Assessment | Wt | Format |
|---|---|---|
| Weekly Homework Quizzes ×10 | 5% | Canvas, W2–11 |
| Assignment 1 | 15% | group program + report |
| Assignment 2 | 20% | group program + report |
| Final Exam | 60% | paper, 2 h; calculator |
Permitted materials during the exam: One sheet of your own notes - double-sided, A4 size, handwritten or typed (COMP5318 lecture 13 slides)
Hurdle: score ≥40% in the final or the final course mark is capped at 45; ≥50% overall is required to pass. (course data)
Use this as a selection plan: copy only what you can explain, prioritising procedures, assumptions, denominators and traps.
1 · Scale, Distance, kNNCh 1–2
scaling + similaritymin–max: x′=(x−min)/(max−min)
z=(x−x̄)/s
D₂(A,B)=√Σ(aᵢ−bᵢ)² · D₁=Σ|aᵢ−bᵢ|
cos(A,B)=A·B/(‖A‖‖B‖)
Scale before distance: otherwise the largest-range feature dominates. Euclidean = straight-line; Manhattan = axis steps; cosine compares direction rather than magnitude.
kNN: distance → sort → take k → majority vote (classification) or mean (regression). Compare squared Euclidean distances to rank. Choose k by validation error; small k = low bias/high variance, large k = high bias/low variance; k=n predicts the majority.
Exam bite → Lazy learning stores all rows; one query over m rows × n features costs about m×n distance operations. Prefer an eager model for real-time prediction.
1b · Risk + Rule BaselinesCh 1–2
| Item | Decision cue |
|---|---|
| empirical risk | average loss on training data |
| true risk | expected unseen-data loss; estimate on held-out data |
2 · Linear RegressionCh 3
least squaresŷ=b₀+b₁x
b₁=[Σxy−ΣxΣy/n]/[Σx²−(Σx)²/n]
b₀=ȳ−b₁x̄ · eᵢ=yᵢ−ŷᵢ · SSE=Σeᵢ²
fit scoreSST=Σ(yᵢ−ȳ)² = SSR+SSE
R²=SSR/SST=1−SSE/SST · r=sign(b₁)√R²
Where it bites: show Σx, Σy, Σxy, Σx², then substitute; predict only after fitting. Least squares minimises squared vertical residuals, not their raw sum. Test-set R² can be negative when predictions are worse than using ȳ.
3 · Logistic + PenaltiesCh 3
classification probabilityz=w·x+b · p(y=1|x)=σ(z)=1/(1+e⁻ᶻ)
p≥0.5 ⇔ z≥0 → class 1
| Method | Objective/effect | Use |
|---|---|---|
| Linear | least-squares SSE | numeric target |
| Logistic | maximum likelihood | binary target |
| Ridge L2 | +αΣwⱼ²; shrink | retain all features |
| Lasso L1 | +αΣ|wⱼ|; zeros | feature selection |
Larger α → heavier penalty → simpler model. Never claim logistic regression minimises SSE.
9 · PCACh 6
Procedure: centre → covariance → eigenvectors/eigenvalues (or SVD X=UΣVᵀ) → order λ descending → project onto first k components.
variance retainedfirst k PCs = Σᵢ₌₁ᵏλᵢ / Σⱼλⱼ
PCA is unsupervised, ignores labels and yields orthogonal PCs. Kernel SVM maps upward to separate; PCA projects downward to retain variance.
9b · Regression ChecksCh 3
Two fast traps → R² is a fraction of variation explained, not the slope. Logistic p is nonlinear in x, but log-odds are linear; z=0 is the default boundary.
4 · Naïve BayesCh 4
factor, score, argmaxP(H|E)=P(E|H)P(H)/P(E)
score(c)=P(c)∏ⱼP(xⱼ|c) · choose argmax c
Nominal feature: likelihood = class-conditional count/class count. Zero frequency: Laplace add-one smoothing stops one unseen value making the whole product zero. Numeric: use the Gaussian density with each class’s mean and sample SD.
Gaussian likelihoodp(x|c)=1/(√(2π)σc) · exp[−(x−μc)²/(2σc²)]
Assumption: features are conditionally independent given the class. Compare unnormalised class scores; P(E) is common.
5 · Honest EvaluationCh 4
| Choice | Rule |
|---|---|
| Holdout | fast; train/test once |
| k-fold CV | each row tested once; average k scores |
| Stratified | preserve class proportions |
| LOOCV | k=n; costly, low bias |
Train weights; validation/CV tunes k, α, depth; test estimates final generalisation. Never tune on test.
metricsaccuracy=(TP+TN)/N
precision=TP/(TP+FP) · recall=TP/(TP+FN)
F1=2PR/(P+R)=2TP/(2TP+FP+FN)
Exam bite → Imbalanced classes: accuracy can hide failure. Precision answers “flagged: how many right?” Recall answers “actual positives: how many caught?”
11 · Deep Architecture ChooserCh 8
| Problem | Pick | Reason |
|---|---|---|
| image | CNN | local + shared weights |
| short sequence | RNN | hidden state |
| long dependency | LSTM | cell + 3 gates |
| whole sequence | Transformer | self-attention |
GRU is the lighter two-gate alternative. Pooling: max keeps the strongest response; average keeps the mean.
6 · Trees: Split + StopCh 5
impurityH(S)=−Σᵢpᵢlog₂pᵢ · 0log₂0:=0
Gini(S)=1−Σᵢpᵢ²
information gainGain(S,A)=H(S)−Σₖ(|Sₖ|/|S|)H(Sₖ)
choose the largest gain
Entropy: pure=0; binary 50/50=1 bit. Numeric feature: sort values, try midpoint thresholds where labels change, score each. Weight every child by its row share.
High-cardinality trap: an ID-like attribute makes singleton pure leaves and memorises training data. Drop it or use gain ratio. Pre-pruning stops early; post-pruning grows then cuts using validation performance.
7 · EnsemblesCh 5
| Bagging / RF | Boosting | |
|---|---|---|
| Train | parallel, independent | sequential |
| Data | bootstrap rows | reweight mistakes |
| Combine | equal vote | weighted vote |
| Main gain | ↓ variance | ↓ bias |
| Noise | more robust | more sensitive |
Random forest = bagging + random feature subset at each split, decorrelating trees. Bootstrap means sample with replacement.
7b · Tree Decision ChecksCh 5
| Situation | Response |
|---|---|
| numeric feature | try midpoints where class changes |
| deep tree overfits | pre-stop or post-prune using validation |
| unstable high variance | bag independent bootstrap trees |
| correlated trees | random feature subset per RF split |
| persistent bias | sequential boosting |
Extra checks: Gini is 0 at a pure node and 0.5 at binary 50/50. Gain ratio counters information gain’s bias toward many-valued splits. Bagging combines by majority vote or averaging; boosting combines weighted learners and is more noise-sensitive.
8 · SVM + KernelsCh 6
hard-margin geometryboundary: w·x+b=0
supports: w·x+b=±1
constraint: yᵢ(w·xᵢ+b)≥1
margin=2/‖w‖ ⇔ minimise ½‖w‖²
Support vector iff yᵢ(w·xᵢ+b)=1; a point strictly beyond the margin is not one. Solve the ±1 support equations: direction alone does not fix ‖w‖ or margin.
C: larger C penalises training errors more; smaller C tolerates errors for a wider/softer margin. Kernel trick: K(x,y)=Φ(x)·Φ(y) computes a feature-space inner product without constructing Φ.
common kernelspolynomial: K(x,y)=(x·y+1)ᵈ
RBF: γ controls boundary smoothness
10 · Neurons + BackpropCh 7
forwardn=Σwᵢxᵢ+b · o=σ(n)=1/(1+e⁻ⁿ)
σ′(n)=o(1−o)
backward + updateδout=(t−o)o(1−o)
δh=oh(1−oh)Σout(δout·who)
Δw=η·δreceiver·osource · Δb=ηδ
Perceptron: step output; e=t−a; w←w+ex, b←b+e. It converges only for linearly separable data; one unit cannot learn XOR.
Dense parameter count: nᵢₙnₒᵤₜ+nₒᵤₜ (one bias per receiving neuron). Sigmoid saturation gives tiny derivatives → vanishing gradients; course fixes include ReLU, better initialisation and dropout.
10b · Boundary / Update ChecksCh 6–7
| Claim | Check |
|---|---|
| SVM support | yᵢ(w·xᵢ+b)=1 exactly |
| outside margin | strictly >1; not a support vector |
| perceptron correct | e=0 ⇒ no weight moves |
| input xᵢ=0 | its perceptron weight does not move |
| backprop edge | δ belongs to receiving unit |
Show direction and scale: solving the support equations fixes w and b; guessing only the boundary direction can give the wrong margin.
12 · ClusteringCh 9
K-means: choose k centroids → assign nearest → replace each centroid by member mean → repeat until unchanged. Minimises within-cluster SSE; sensitive to start, scale and outliers; prefers compact spherical clusters.
GMM/EM: soft probabilistic generalisation: E-step assigns responsibilities; M-step updates parameters. Agglomerative: start singleton, merge closest clusters; single=min pair distance, complete=max, average=mean.
DBSCAN: with Eps and MinPts, core has enough neighbours, border is reachable from a core but not core, noise is neither. Finds arbitrary shapes/noise; varying densities are hard.
qualitySSE=ΣclustersΣx∈C‖x−μC‖²
silhouette s=(b−a)/max(a,b)
13 · HMM + Reinforcement LearningCh 10–11
Markov / HMMP(π₁…πK)=P(π₁)∏ᵢP(πᵢ₊₁|πᵢ)
fₖ(1)=A₀(k)eₖ(x₁)
fₖ(t)=eₖ(xₜ)Σⱼ[fⱼ(t−1)aⱼₖ]
P(X)=Σₖfₖ(T)
Viterbi: same trellis but replace Σ with max, store back-pointers, trace argmax. Rows of A are from, columns to; each row sums to 1.
return + Bellman/QGₜ=Σₖ≥0γᵏrₜ₊ₖ₊₁
V*(s)=maxₐΣs′P(s′|s,a)[r+γV*(s′)]
Q←Q+α[r+γmaxₐ′Q(s′,a′)−Q]
ε-greedy: explore with ε; otherwise exploit argmax Q. Terminal next state: max term=0. Experience replay stores (s,a,r,s′), samples random minibatches, breaks sequential correlation and reuses experience.
Exam split: Forward evaluates P(observations) by summing every hidden path; Viterbi decodes one most likely path by max plus back-pointers; Baum–Welch/EM learns A, E and A₀. In an MDP, (S,A,R,P,γ) names states, actions, reward, transitions and discount.