Support vector machines are large-margin linear classifiers. They pick the boundary that

maximizes the distance to the nearest points, control overfitting with the hinge loss and a

penalty $C$, and use kernels to fit nonlinear boundaries without ever forming the feature map.

Throughout, labels are $y \in \{-1,+1\}$ and the decision uses a raw score $z = w^T x - b$.

- Define the SVM hypothesis, its separating hyperplane, and the geometric margin.

- State the hard-margin primal and the soft-margin primal with hinge loss and penalty $C$.

- Define kernels, the kernel trick, and the Mercer condition.

- Form the Lagrangian, derive the dual and KKT conditions, and define support vectors.

Labels are $y \in \{-1,+1\}$, with weight vector $w \in \mathbb{R}^{n}$ and bias $b$.

The hypothesis is defined as the sign of the raw score $z = w^T x - b$:

$$\boxed{ h(x) = \operatorname{sign}(w^T x - b) }$$

The decision boundary is the set of points with zero score:

$$\boxed{ w^T x - b = 0 }$$

*Remark:* $w$ is orthogonal to the boundary, so it sets the orientation, and $b$ sets the offset.

The geometric margin of example $i$ is defined as its signed distance to the boundary, made

positive by the label:

$$\boxed{ \gamma^{(i)} = y^{(i)} \, \frac{w^T x^{(i)} - b}{\lVert w \rVert} }$$

A correctly classified point has $\gamma^{(i)} > 0$. The margin of the dataset is the smallest

$\gamma^{(i)}$ over all examples.

*Remark:* dividing by $\lVert w \rVert$ makes the margin invariant to rescaling $(w,b)$, unlike

the raw score $z$.

Fixing the scale so the closest points satisfy $y^{(i)}(w^T x^{(i)} - b) = 1$, maximizing the

margin is equivalent to minimizing $\lVert w \rVert^2$ subject to a unit functional margin:

$$\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 \ \ \forall i }$$

This is a convex quadratic program with linear constraints, so it has a unique optimum.

*Remark:* it requires the data to be linearly separable. The next lesson relaxes that with slack

variables.

The raw score is $z = w^T x - b$ and labels are $y \in \{-1,+1\}$.

The hinge loss is defined as the amount by which the margin $yz$ falls short of $1$, clipped at zero:

$$\boxed{ L(z,y) = \max(0,\, 1 - yz), \quad z = w^T x - b }$$

It is zero once $yz \ge 1$ (the point is correct and beyond the margin) and grows linearly inside

or past the margin.

*Remark:* the hinge loss is convex but not differentiable at $yz = 1$, so it is optimized with

subgradients.

Introduce a slack $\xi_i \ge 0$ per example to allow margin violations, penalized by $C > 0$:

$$\boxed{ \min_{w,b,\xi} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\xi_i \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 - \xi_i, \ \ \xi_i \ge 0 }$$

At the optimum $\xi_i = \max(0,\, 1 - y^{(i)}(w^T x^{(i)} - b))$, so eliminating the slacks gives

the unconstrained regularized form:

$$\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\max\!\big(0,\, 1 - y^{(i)}(w^T x^{(i)} - b)\big) }$$

This is regularization plus hinge loss: the $\tfrac{1}{2}\lVert w \rVert^2$ term widens the margin

and the sum penalizes violations.

| $C$ | Penalty on violations | Margin | Behaviour |

| --- | --- | --- | --- |

| small | weak | wide | more violations tolerated, lower variance |

| large | strong | narrow | fewer violations, fits training data harder |

*Remark:* as $C \to \infty$ no violation is tolerated, which recovers the hard-margin classifier.

A kernel is defined as the inner product of a feature map $\phi$ applied to two inputs:

$$\boxed{ K(x,z) = \phi(x)^T \phi(z) }$$

A valid kernel computes this inner product directly, so $\phi$ never has to be formed (it may even

be infinite-dimensional).

The SVM dual depends on the data only through inner products $\langle x^{(i)}, x^{(j)} \rangle$.

The kernel trick replaces each inner product with a kernel:

$$\boxed{ \langle x^{(i)}, x^{(j)} \rangle \ \longrightarrow \ K(x^{(i)}, x^{(j)}) }$$

This fits a linear boundary in the feature space, which is nonlinear in the original space, at the

cost of evaluating $K$ instead of $\phi$.

A widely used choice is the Gaussian (RBF) kernel:

$$\boxed{ K(x,z) = \exp\!\left( -\frac{\lVert x - z \rVert^2}{2\sigma^2} \right) }$$

A function $K$ is a valid kernel if and only if, for every finite sample, its Gram matrix is

symmetric positive semidefinite:

$$\boxed{ K = K^T, \qquad K \succeq 0 }$$

*Remark:* this is the Mercer condition. It guarantees a feature map $\phi$ exists, so the dual stays

convex.

| Kernel | $K(x,z)$ | Note |

| --- | --- | --- |

| Linear | $x^T z$ | no mapping, recovers the linear SVM |

| Polynomial | $(x^T z + c)^d$ | degree $d$, offset $c$ |

| Gaussian (RBF) | $\exp\!\big(-\tfrac{\lVert x - z \rVert^2}{2\sigma^2}\big)$ | infinite-dimensional, local |

*Remark:* a small $\sigma$ makes the RBF kernel very local, which can overfit. It trades off against

$C$.

For a primal objective $f(w)$ with inequality constraints $g_i(w) \le 0$ and multipliers

$\beta_i \ge 0$, the Lagrangian is defined as:

$$\boxed{ \mathcal{L}(w,\beta) = f(w) + \sum_{i=1}^{m} \beta_i \, g_i(w) }$$

Applied to the SVM primal $\tfrac{1}{2}\lVert w \rVert^2$ with constraints

$1 - y^{(i)}(w^T x^{(i)} - b) \le 0$, the stationarity conditions $\nabla_w \mathcal{L} = 0$ and

$\partial_b \mathcal{L} = 0$ give:

$$\boxed{ w = \sum_{i=1}^{m} \beta_i\, y^{(i)} x^{(i)}, \qquad \sum_{i=1}^{m} \beta_i\, y^{(i)} = 0 }$$

So the optimal $w$ is a linear combination of the training inputs weighted by $\beta_i y^{(i)}$.

Substituting these back eliminates $w$ and $b$, leaving a problem in $\beta$ that depends on the

data only through inner products:

$$\boxed{ \max_{\beta} \ \sum_{i=1}^{m}\beta_i - \tfrac{1}{2}\sum_{i,j}\beta_i \beta_j\, y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle \quad \text{s.t.} \quad \beta_i \ge 0, \ \ \sum_{i}\beta_i y^{(i)} = 0 }$$

At the optimum, complementary slackness ties each multiplier to its constraint:

$$\boxed{ \beta_i \big[\, y^{(i)}(w^T x^{(i)} - b) - 1 \,\big] = 0 }$$

Support vectors are defined as the examples with a nonzero multiplier:

$$\boxed{ \text{support vectors} = \{\, i : \beta_i > 0 \,\} }$$

These are the points exactly on the margin. All others have $\beta_i = 0$ and do not affect $w$.

Replacing the inner product by a kernel gives a decision rule expressed only through support vectors:

$$\boxed{ h(x) = \operatorname{sign}\!\left( \sum_{i=1}^{m} \beta_i\, y^{(i)}\, K(x^{(i)}, x) - b \right) }$$

*Remark:* only support vectors ($\beta_i > 0$) contribute, so prediction cost scales with their

count, not with $m$.

---