Support Vector Machine (SVM)

Classification technique. Supervised learning technique. Watch this 2 min video on SVM.

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

• It's all about decision boundaries.

We have positive and negative examples. How to separate these points?

Vapnik Theory: Try to put the lines which separates the negative points from the positive points as wide as possible.

MLP 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.

1D example to show why MLP finds any separator

Suppose we have three data points:

$$\begin{array}{rl}x=-3,& y=-1\\ x=-1,& y=-1\\ x=2,& y=1\end{array}$$

And many separating perceptrons, $T[wx+b]$, the equation to solve will become $wx+b=0$. The solutions will gve:

$$\begin{array}{rl}b& <3w-1\\ b& <w-1\\ b& >-2w+1\end{array}$$

which satisfy for whatever $x\in [-1,2]$

Separating Hyperplanes

• Let’s consider a vector perpendicular on the median line $\vec{w}$
• Then we also have some unknown $\vec{u}$

We are interested if this unknown is on the left part of the street or if it is on the right part of the street.

• We project $\vec{u}$ on the perpendicular direction.
  • Thus, $\vec{w}\cdot \vec{u}\ge c$ (constant)

(1) Decision rule:

If $\vec{w}\cdot \vec{u}+b\ge 0$ then "$+$"

• where $c=-b$

Page 21. See the notes from Claude as well to continue the idea.