SVM

SSU | [Metoda podpůrných vektorů]

Reformulation of the Maximum margin classifier problem into a quadratic program solving

$$(w^{\ast },b^{\ast })=\text{arg}\underset{w\in {\mathbb{R}}^d,b\in \mathbb{R}}{\min }\frac{1}{2}||w|{|}^2$$

subject to

$$\begin{array}{r}⟨x_i,w⟩+b\ge +1i\in {\mathcal{I}}_{+}\\ ⟨x_i,w⟩+b\le -1i\in {\mathcal{I}}_{-}\end{array}$$

Support vectors are the training examples that are closest to the decision hyperplane. These are the only training data we need to keep after training is finished.

Question

Draw a line and a point. Draw a triangle with a right angle and write what the distances are equal to between the line and the point. What is the distance from the margin to other points?

Answer

Question

Why does minimizing the weight vector maximizes the margin? What is left to minimize when the closest point has distance of 1?

Answer

When the distance $⟨x_i,w⟩+b=1$, the distance from the decision bound to the support vector is just $1/||w||$.

Soft-margin SVM

When data are not linearly separable, we can introduce slack-variables and reformulate the quadratic program to

$$(w^{\ast },b^{\ast },{\xi }^{\ast })=\text{arg}\underset{w\in {\mathbb{R}}^d,b\in \mathbb{R},\xi \in {\mathbb{R}}^m}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i$$

subject to

$$\begin{array}{rlr}⟨x_i,w⟩+b& \ge +1-{\xi }_i& i\in {\mathcal{I}}_{+}\\ ⟨x_i,w⟩+b& \le -1+{\xi }_i& i\in {\mathcal{I}}_{-}\\ {\xi }_i& \ge 0& i\in \hat{m}\end{array}$$

Slack variable ${\xi }_i$ is equal to 0, when point with index $i$ is classified correctly and is positive when misclassified. It “pushes” the point further away from the decision bound, so the point ends up correctly classified.

Regularization constant $C$ is a hyperparameter. Setting it high pushes slack variables close to zero and tends to overfitting. Setting it low allows greater margin, smoother bound and better generalization.

Implicit structured risk minimization

Structural risk minimization is implemented directly inside the algorithm. We can re-define the objective function with Hinge loss as

$$(w^{\ast },b^{\ast })=\text{arg}\underset{w\in {\mathbb{R}}^d,b\in \mathbb{R}}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m\max \{0,1-⟨x_i,w⟩+b\}$$

• Hinge loss is exactly equal to the slack variables.
• It also implicitly satisfies the conditions that margin is at least 1.

Parameter $C$ becomes the complexity term.

Implementation

TODO