Supervised Learning

Support Vector Machine (SVM)

The SVM is a linear classifier that finds the max-margin separating hyperplane, giving a unique, optimal solution (unlike perceptron). Its dual form depends only on dot products, which enables the kernel trick.

Resources:

• https://www.quarkml.com/2022/09/primal-formulation-of-svm-simplified.html
• StatQuest: https://www.youtube.com/watch?v=efR1C6CvhmE&ab_channel=StatQuestwithJoshStarmer

Margins: Intuition

Given weight $w$, the distance from a point $x_i$ to the hyperplane $\{x:⟨w,x⟩+b=0\}$ is $\frac{|⟨w,x_i⟩+b|}{\Vert w{\Vert }_2}$. The margin of a dataset is the smallest such distance over all points (assuming all are correctly classified).

Perceptron finds any separator. SVM picks the one with the largest margin, which generalizes better.

Geometric picture

SVM finds the widest street separating the two classes. The decision hyperplane runs down the centerline; the margin is the curb-to-curb width. A wide street is robust: small perturbations in the data do not flip a point’s side. Without the margin requirement, the solution is not unique (infinitely many hyperplanes separate the same points), so SVM imposes a principled tiebreaker.

1. Hard-Margin SVM (Primal)

Assume the data is linearly separable. Maximize the margin:

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2\text{s.t.}{y}_i(⟨w,x_i⟩+b)\ge 1\forall i$$

Intuition

$\hat{y}=⟨w,x⟩+b$ is the equation of the hyperplane we want to learn. The sign tells us which side $x$ lies on: if $\hat{y}>0$, same side as $w$; if $\hat{y}<0$, opposite side. So correct classification means $y\hat{y}\ge 1$ (the ”$\ge 1$” is a scale convention).

Minimizing $\Vert w{\Vert }_2^2$ maximizes the margin $1/\Vert w{\Vert }_2$.

2. Soft-Margin SVM (Primal)

Real data is rarely linearly separable. Introduce slack variables ${\xi }_i\ge 0$ that measure how far each point violates the margin.

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }_2^2+C\sum _i{\xi }_i\text{s.t.}{y}_i(⟨w,x_i⟩+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

Equivalently, in unconstrained form using hinge loss:

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2+C\sum _i\max (0,1-y_i(⟨w,x_i⟩+b))$$

Interpreting the slack:

• ${\xi }_i=0$: on correct side of margin
• $0<{\xi }_i<1$: correctly classified but inside margin
• ${\xi }_i\ge 1$: misclassified

$C$ controls the tradeoff: $C\to 0$ ignores the data (only minimizes $\Vert w\Vert$); $C\to \infty$ recovers hard-margin SVM.

Read $C$ as “how much do I punish misclassifications versus margin violations?” Small $C$: a wide margin with many points inside it. Large $C$: a narrow margin that tries hard to get every point right, possibly overfitting noise.

Note the similarity to ridge regression: the $\Vert w{\Vert }_2^2$ term is L2 regularization, and the hinge-loss sum is the data loss.

3. Dual Formulation

Convert constrained optimization to unconstrained via Lagrange multipliers. For hard-margin:

$$\underset{\alpha \ge 0}{\min }\underset{w,b}{\max }\left[\frac{1}{2}\Vert w{\Vert }_2^2-\sum _i{\alpha }_i(y_i(⟨w,x_i⟩+b)-1)\right]$$

Strong duality lets us swap min and max. Setting ${\nabla }_w$ and ${\partial }_b$ to 0 inside gives $w={\sum }_i{\alpha }_i{y}_i{x}_i$ and ${\sum }_i{\alpha }_i{y}_i=0$. Substituting back:

$$\underset{\alpha \in {\mathbf{R}}^n,0\le \alpha \le C}{\min }\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨x_i,x_j⟩-\sum _i{\alpha }_i\text{s.t.}\sum _i{\alpha }_i{y}_i=0$$

(For hard-margin drop the upper bound $C$; for soft-margin keep it.)

Key observation

The dual depends on the data only through dot products $⟨x_i,x_j⟩$. Replace with a kernel $k(x_i,x_j)$ and you can operate in (infinite-dimensional) feature spaces for free.

Support Vectors

Complementary slackness (a KKT condition) implies ${\alpha }_i\cdot (1-y_i{\hat{y}}_i-{\xi }_i)=0$ for each $i$, so either:

• ${\alpha }_i=0$ (point is on correct side of margin, doesn’t contribute), or
• ${\alpha }_i>0$ (point lies on the margin or violates it, a support vector)

The solution is a sum over support vectors: $w={\sum }_{i:{\alpha }_i>0}{\alpha }_i{y}_i{x}_i$

Only support vectors define the hyperplane, a form of sparsity.

Intuition

Only the points right on the curb (support vectors) matter. Delete a point deep inside its class’s territory and the solution does not change. This is why SVMs are memory-efficient at inference (you only keep the support vectors) and why they are less sensitive to outliers that sit far from the boundary, though close-to-boundary outliers can still hijack the fit.

Optimization

• Primal: gradient descent on the hinge-loss form. Subgradient: $-y_i{x}_i$ if $y_i{\hat{y}}_i<1$, $0$ otherwise. Non-differentiable at the hinge
• Dual: projected gradient descent, or SMO (sequential minimal optimization, what LIBSVM uses). Often more practical, especially with kernels

CS231n: Multiclass SVM Loss

For example $i$ with correct class $y_i$: $L_i={\sum }_{j\ne y_i}\max (0,s_j-s_{y_i}+\Delta )$

where:

• $s_j=f(x_i,W{)}_j$ is the score for class $j$
• $\Delta$ (typically 1) is the minimum margin

Full loss: $L=\frac{1}{N}{\sum }_i{L}_i+\lambda R(W),R(W)={\sum }_{k,l}{W}_{k,l}^2$

def L_i_vectorized(x, y, W):
    delta = 1.0
    scores = W.dot(x)
    margins = np.maximum(0, scores - scores[y] + delta)
    margins[y] = 0
    return np.sum(margins)

From CS480 lec5.

Related

• Perceptron (finds any separator; SVM picks max-margin)
• Hinge Loss
• Kernel Method (key extension, enables nonlinear SVMs)
• Hyperplane
• Lagrange Multipliers
• Regularization
• CS480