COMP4318 · Machine Learning and Data Mining
Support Vector Machines & Dimensionality Reduction
Week 6 covers support vector machines — the maximum-margin hyperplane, soft margins and the kernel trick — then dimensionality reduction with PCA and SVD. Expect an SVM question (classify a point by sign(w·z+b), compute the margin, name the support vectors) and a PCA/SVD question (true/false on principal components, or a compression-ratio calculation). The homework quiz (h6) drills the margin and kernel ideas.
What this chapter covers
- 01Linear decision boundary w·x + b = 0; classify a new point z by sign(w·z + b)
- 02Support vectors = the closest points, on H1: w·x+b=1 and H2: w·x+b=−1; SVM picks the maximum-margin hyperplane
- 03Margin size d = 2/‖w‖; maximising the margin ⇔ minimising ½‖w‖² subject to yᵢ(w·xᵢ+b) ≥ 1
- 04Soft margin: the parameter C trades margin width against training error (large C → fit the training data harder)
- 05Kernel trick: K(u,v) = Φ(u)·Φ(v) computes high-dimensional dot products without ever forming Φ
- 06Common kernels (Mercer's theorem): polynomial (x·y+1)^p, RBF e^(−‖x−y‖²/(2σ²)), tanh
- 07PCA: unsupervised orthogonal axes ordered by variance; keep the first k (e.g. 95% variance, or the elbow)
- 08SVD X = U·Λ·Vᵀ; a low-rank reconstruction keeps the k largest singular values; compression ratio r = k(1+n+m)/(n·m)
Classifying with an SVM boundary and finding the margin
- +1Classify z by the sign of w·z + b: 3·2 + 4·2 − 5 = 6 + 8 − 5 = 9.
- +1Since 9 > 0, z lies on the positive side of the boundary → class +1.
- +1Norm of the weight vector: ‖w‖ = √(3² + 4²) = √25 = 5.
- +1Margin width d = 2/‖w‖ = 2/5 = 0.4 (in feature units).
Key terms
- Maximum-margin hyperplane
- The linear boundary w·x + b = 0 that maximises the gap to the nearest points; SVMs choose it for best generalisation.
- Support vector
- A training point lying on a supporting hyperplane (w·x+b = ±1); only these points determine the boundary, and w = Σ αᵢ yᵢ xᵢ over them.
- Soft margin (C)
- A relaxation allowing some training points inside the margin; the hyperparameter C trades margin width against training error (large C fits the training data harder).
- Kernel trick
- Computing dot products in a high-dimensional feature space via a kernel K(u,v) = Φ(u)·Φ(v) without ever constructing Φ; enables non-linear boundaries.
- PCA
- Principal component analysis: an unsupervised projection onto orthogonal axes ordered by variance; keep the first k to reduce dimensions while retaining most variance.
- SVD
- Singular value decomposition X = U·Λ·Vᵀ; V holds the principal-component axes, U the projected data, Λ the singular values, and keeping the top k compresses the data.
Support Vector Machines & Dimensionality Reduction FAQ
What exactly is the 'kernel trick'?
It lets an SVM draw a non-linear boundary without paying the cost of an explicit high-dimensional mapping. The optimisation only ever needs dot products between points, so you replace each dot product with a kernel K(u,v) = Φ(u)·Φ(v) that computes the mapped dot product directly — for example K(u,v) = (u·v)² corresponds to a quadratic feature map. You never form Φ, which may be huge or infinite-dimensional.
Is PCA supervised or unsupervised?
Unsupervised — it ignores the labels entirely and finds orthogonal directions (principal components) ordered by the variance they capture, keeping the first k. It is used for compression and visualisation and to fight the curse of dimensionality, not directly for classification.
How do I compute the SVM margin in the exam?
Two facts do most of the work: classify a point by the sign of w·z + b, and the margin width is d = 2/‖w‖. So compute ‖w‖ = √(Σwᵢ²) and divide 2 by it. Remember the objective is to minimise ½‖w‖² subject to yᵢ(w·xᵢ+b) ≥ 1, and that removing a non-support-vector point does not change the boundary.
How many principal components should I keep?
Keep enough to retain a chosen fraction of the total variance (95% is common) or use the elbow of the variance-versus-dimensions curve. Because components are ordered by variance, the first few often capture most of it — in the iris example the first component alone captures about 92.5%.
Exam move
For SVMs, drill the two workhorse facts — classify by sign(w·z+b) and margin d = 2/‖w‖ — and be able to state the primal objective (minimise ½‖w‖² subject to yᵢ(w·xᵢ+b) ≥ 1) and explain support vectors and the role of C. Know the kernel trick in one sentence and the three standard kernels. For dimensionality reduction, rehearse the PCA true/false points (components are orthogonal; PCA is for compression) and one SVD compression-ratio calculation r = k(1+n+m)/(nm). When the margin algebra slips, ask Sia to recompute it with a fresh w and check ‖w‖.
Working through Support Vector Machines & Dimensionality Reduction in COMP4318? Sia is AskSia’s AI Machine Learning tutor — ask any COMP4318 Support Vector Machines & Dimensionality Reduction question and get a clear, step-by-step explanation grounded in how COMP4318 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
