COMP5318 — Week 6 Supplement
Mathematical Foundations
Hyperplanes, geometric margin, kernels, covariance/eigenvectors, and the projection math behind principal component analysis.
Linear SVM: score, boundary, and margin
The lecture starts from the geometric question: among all separating hyperplanes, which one gives the widest safety buffer between the two classes? SVM answers: choose the maximum-margin hyperplane.
Core SVM formulas
Decision boundary: \[ w^\top x+b=0 \]
Classification rule: \[ \hat{y}=\operatorname{sign}(w^\top x+b) \]
Distance from point \(x\) to the hyperplane: \[ \frac{|w^\top x+b|}{\lVert w\rVert} \]
For the canonical support-vector planes \(w^\top x+b=\pm 1\), the full margin width is \[ \frac{2}{\lVert w\rVert} \]
A kernel computes \(K(x,x')=\langle \phi(x),\phi(x')\rangle\). The classic RBF kernel is \[ K(x,x')=\exp(-\gamma \lVert x-x' \rVert^2) \] and lets SVM form nonlinear boundaries while still using inner products.
Worked Example 1: classify with a linear boundary and compute margin distance
Take the line shown in the lecture style notation:
\[ x_1 + 0.5x_2 - 1 = 0 \]
This means \(w=(1,0.5)\) and \(b=-1\).
Point \(x=(2,1)\)
\[ w^\top x+b=1\cdot 2 + 0.5\cdot 1 -1 = 1.5 \]
The score is positive, so the point is classified into the \(+1\) side.
Norm of \(w\): \[ \lVert w\rVert=\sqrt{1^2+0.5^2}=\sqrt{1.25}\approx 1.118 \]
Distance to the boundary: \[ \frac{|1.5|}{1.118}\approx1.34 \]
Point \(x=(0,1)\) and margin width
\[ w^\top x+b=1\cdot 0 + 0.5\cdot 1 -1 = -0.5 \]
This point is on the negative side of the boundary.
Its distance to the boundary is \[ \frac{0.5}{1.118}\approx0.45 \]
The canonical margin width for this \(w\) would be \[ \frac{2}{1.118}\approx1.79 \]
PCA: variance, covariance, eigenvectors, and SVD
PCA is a dimensionality-reduction method that looks only at the geometry of the input data, not the class labels. It rotates the coordinate system to align with directions of highest variance, then keeps only the first few directions.
PCA pipeline
1. Centre the data matrix \(X\) by subtracting the column means.
2. Compute the covariance matrix of the centred data.
3. Find eigenvalues and eigenvectors of the covariance matrix.
4. Sort eigenvectors by descending eigenvalue.
5. Project onto the first \(k\) eigenvectors.
The lecture also states that any matrix can be factored as \(X=U\Sigma V^\top\). In PCA, the columns of \(V\) give the principal directions, and the singular values in \(\Sigma\) encode how much variance each direction captures.
Explained variance
If eigenvalues are \(\lambda_1,\dots,\lambda_m\), then the explained-variance ratio of principal component \(j\) is \(\lambda_j / \sum_k \lambda_k\). This is what drives the “keep 95% of the variance” rule from the lecture and notebook.
Worked Example 2: a 2D PCA projection
Consider the 2D points \((-2,-1),(-1,0),(0,1),(1,2),(2,3)\). They lie almost perfectly on a line, so PCA should discover one dominant direction.
Mean and covariance
The feature means are \((0,1)\). After centring, the covariance matrix is
\[ \Sigma= \begin{bmatrix} 2.5 & 2.5\\ 2.5 & 2.5 \end{bmatrix} \]
Its eigenvalues are \(5\) and \(0\). That means all variance lies in one direction, with none left in the orthogonal direction.
Principal component and projection
The first principal component can be taken as
\[ v_1=\frac{1}{\sqrt{2}}(1,1) \]
Projecting the centred points onto \(v_1\) gives approximately
\[ -2.83,\ -1.41,\ 0,\ 1.41,\ 2.83 \]
So 2D data have been compressed to one coordinate per point without losing meaningful variance. This is exactly the geometric objective of PCA.
How to think about kernels and dimensionality choice
SVM tuning intuition
- Linear kernel first if the data may already be close to linearly separable.
- For RBF SVM, larger \(\gamma\) makes each point’s influence more local and can create very wiggly boundaries.
- Smaller \(C\) means stronger regularisation and a wider tolerance for margin violations.
PCA interpretation traps
- PCA is unsupervised: class labels do not enter the covariance calculation.
- High explained variance does not automatically mean best classification accuracy.
- Always fit PCA on the training data only, then transform the test data with the same fitted projection.