SVM Margins and Kernels

Let the training set be $(x_i,y_i)_{i=1}^n$, where $x_i\in\mathbb R^d$ and $y_i\in\{-1,+1\}$. A linear classifier uses

$$f(x)=w^\top x+b, \qquad \hat y=\operatorname{sign}(f(x)).$$

The signed functional margin of point $i$ is

$$m_i = y_i(w^\top x_i+b).$$

The geometric distance from $x_i$ to the boundary is the signed margin divided by the normal length:

$$\gamma_i=\frac{y_i(w^\top x_i+b)}{\|w\|_2}.$$

Because multiplying $(w,b)$ by a positive constant leaves the sign of $f(x)$ unchanged, the hard-margin SVM fixes the functional margin scale at $m_i\ge 1$ and then maximizes geometric margin by minimizing $\|w\|_2$:

$$\min_{w,b}\frac12\|w\|_2^2 \quad \text{subject to}\quad y_i(w^\top x_i+b)\ge 1,\ i=1,\ldots,n.$$

The distance from the decision boundary to each margin rail is

$$\frac{1}{\|w\|_2},$$

so the full margin width between the two rails is

$$\frac{2}{\|w\|_2}.$$

Write the constraints as $1-y_i(w^\top x_i+b)\le 0$ and attach multipliers $\alpha_i\ge 0$. The hard-margin dual is

$$\max_\alpha \sum_i \alpha_i -\frac12\sum_i\sum_j \alpha_i\alpha_j y_i y_j x_i^\top x_j$$

subject to

$$\alpha_i\ge 0, \qquad \sum_i \alpha_i y_i=0.$$

At the optimum,

$$w^\star=\sum_i \alpha_i^\star y_i x_i.$$

Complementary slackness gives the support-vector rule:

$$\alpha_i^\star\left(1-y_i((w^\star)^\top x_i+b^\star)\right)=0.$$

If $y_i f(x_i)>1$, the point is outside the margin and $\alpha_i=0$. If $\alpha_i>0$, the point is active: it lies on the margin in the hard-margin case, or it is on/inside the soft-margin tube in the soft-margin case.

For nonseparable data, introduce slack variables $\xi_i\ge 0$:

$$\min_{w,b,\xi} \frac12\|w\|_2^2+C\sum_i \xi_i$$

subject to

$$y_i(w^\top x_i+b)\ge 1-\xi_i, \qquad \xi_i\ge 0.$$

Equivalently, the slack term is the hinge loss:

$$\max(0,1-y_i f(x_i)).$$

The parameter $C$ controls how much the optimizer pays for margin violations relative to a wider margin.

Now the kernel step. If the dual and prediction only need inner products, replace

$$x_i^\top x_j$$

with a valid kernel

$$K(x_i,x_j)=\langle \phi(x_i),\phi(x_j)\rangle.$$

The dual becomes

$$\max_\alpha \sum_i \alpha_i -\frac12\sum_i\sum_j \alpha_i\alpha_j y_i y_j K(x_i,x_j),$$

and prediction becomes

$$f(x)=\sum_i \alpha_i y_iK(x_i,x)+b.$$

For example, the RBF kernel

$$K_\gamma(x,z)=\exp(-\gamma\|x-z\|_2^2)$$

makes nearby points highly similar and far-away points weakly similar. It can produce nonlinear boundaries in the original input plane because it is linear in a different, implicit feature space.