[Supervised Learning] SVM – Support Vector Machine explained with examples

This post is the first part of a double post about SVMs. This part tries to help to clarify how SVMs work in theory (with 2 full developed examples). The second part (not published yet) will explain the algorithm to solve this problem using a computer: Quadratic Programming and SMO.

Index

Basic definition

Support vector machines (SVMs from now on) are supervised learning models used for classification and regression. The basic idea of SVMs in binary classification is to find the farthest boundary from each class.

basicsvm

Therefore, solving a basic mathematical function given the coordinates (features) of each sample will tell whether the sample belongs to one region (class) or other. Input features determine the dimension of the problem. To keep it simple, the explanation will include examples in 2 dimensions.

Mathematical explanation

expl1

The vector \overrightarrow{w} is a perpendicular vector to the boundary, but since boundary’s coefficients are unknown, \overrightarrow{w} vector’s coefficients are unknown as well. What we want to do is to calculate the boundary’s coefficients with respect to \overrightarrow{u} because we have its coordinates (sample’s coordinates).

expl3

If both vectors are multiplied, the result will be the purple vector.
\overrightarrow{w} \cdot \overrightarrow{u} \geq c \quad \text{or generally} \quad \overrightarrow{w} \cdot \overrightarrow{u} + b \geq 0

Let us say that:
\overrightarrow{w} \cdot \overrightarrow{x_+} + b \geq 1 \quad \text{and} \quad \overrightarrow{w} \cdot \overrightarrow{x_-} + b \leq -1
Where \overrightarrow{x_+} is a positive sample (class A) and \overrightarrow{x_-} is a negative sample (class B).
A new variable is now introduced:
y_i \quad \text{such that } y_i = +1 \quad \text{for + samples} \\ \text{ } \hspace{70pt} y_i = -1 \quad \text{for - samples}

Multiply each of them by the previous equations:
y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) \geq 1 \\ +1 * (\overrightarrow{x_i} \cdot \overrightarrow{w}+b) \geq 1 \\ -1 * (\overrightarrow{x_i} \cdot \overrightarrow{w}+b) \geq 1

The result is the same equation. Therefore, we only need the previous formula:
y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) \geq 1 \quad \to \quad y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) -1 \geq 0

expl4

Finally, we add an additional constrain y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) -1 = 0 so that the values that fulfill this, fall in between the two regions as depicted (green zone).

expl5

The next step is to maximize the projection of \overrightarrow{x_+}-\overrightarrow{x_-} on \overrightarrow{w} (the black perpendicular vector to the boundary) to keep samples from each class as far as possible. I assume that you know about scalar projection, but if you don’t, you can check out the Appendix A.

The length of the projection is given by the following formula:
(x_+ - x_-)  \cdot  \frac{\overrightarrow{w}}{\| w \|}

From the previous formula y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) -1 = 0 now let us substitute both positive and negative samples x_+ and x_- so that:
y_i = +1 \quad \to \quad 1(\overrightarrow{x_+} \cdot \overrightarrow{w} + b) -1 = 0 \quad \to \quad \overrightarrow{x_+} \cdot \overrightarrow{w} = 1-b \\ y_i = -1 \quad \to \quad -1(\overrightarrow{x_-} \cdot \overrightarrow{w} + b) -1 = 0 \quad \to \quad \overrightarrow{x_-} \cdot \overrightarrow{w} = -1-b

Therefore:
(x_+ - x_-)  \cdot  \frac{\overrightarrow{w}}{\| w \|} = \frac{\overrightarrow{x_+} \cdot \overrightarrow{w}-\overrightarrow{x_-} \cdot \overrightarrow{w}}{\| w \|} = \frac{1-b+1+b}{\| w \|} = \frac{2}{\| w \|}

The goal is to maximize \frac{2}{\| w \|} which is the same as minimizing \| w \| or, to make it more mathematically convenient, \frac{1}{2}\| w \|^2

Thus, we have a function to minimize with a constraint (y_i(\overrightarrow{x_i} \cdot \overrightarrow{w} + b) -1 = 0 ), so Lagrange is applied. In case you want to know more about Lagrange multipliers, you can check Appendix B.

L = \frac{1}{2}\| w \|^2 - \sum \alpha_i [ y_i (\overrightarrow{w} \cdot \overrightarrow{x_i} +b)-1]
First we have the function we want to minimize, and later the constraints.

\frac{\partial L}{\partial w} = \overrightarrow{w} - \sum \alpha_i y_i x_i = 0 \to \overrightarrow{w} = \sum \alpha_i y_i x_i \\ \frac{\partial L}{\partial b} = - \sum \alpha_i y_i = 0 \to \sum \alpha_i y_i = 0

Plug these two functions to L.

L = \frac{1}{2}(\sum \alpha_i y_i \overrightarrow{x_i}) \cdot (\sum \alpha_j y_j \overrightarrow{x_j}) - (\sum \alpha_i y_i \overrightarrow{x_i}) \cdot (\sum \alpha_j y_j \overrightarrow{x_j}) - \sum \alpha_i y_i b + \sum \alpha_i = \sum \alpha_i - \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j \overrightarrow{x_j} \cdot \overrightarrow{x_j}

Hence, we aim to minimize \sum \alpha_i - \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j \overrightarrow{x_j} \cdot \overrightarrow{x_j}
The optimization depends on \overrightarrow{x_j} \cdot \overrightarrow{x_j}

Kernel trick

One of the most interesting properties of SVMs is that we can transform problems from a certain number of dimensions to another dimensional space. This flexibility, as known as kernel trick, allows SVMs to classify nonlinear problems.

kernel1

kernel2

\text{from } \quad f(x) \quad \text{ to } \quad f(x,x^2)

The following example shows how to graphically solve the XOR problem using 3 dimensions.

xorprob

Now it is not difficult to imagine a plane that can separate between blue and red samples.

Example 1: 2 points in a plane

problem1
Points and class (coordinate x (x1), coordinate y (x2), class/output (y)):

Point 1:

Coordinates: x = [-1,1]
Class (output): y = 1

Point 2:

Coordinates: x = [1,-1]
Class (output): y = -1

We want to minimize: \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{i=1}^N \alpha_i \alpha_j y_i y_j x_i^T \cdot x_j
We know that: w = \sum_{i=1}^N \alpha_i y_i x_i
and \sum_{i=1}^N \alpha_i y_i = 0

Let us calculate the second part of the function we want to minimize first to keep it simple:
 L_1 = \begin{cases} \alpha_1 * \alpha_1 * 1 * 1 * (-1 * -1 + 1*1) = 2 \alpha_1^2\\  \alpha_1 * \alpha_2 * 1 * -1 * (-1 * 1 + 1*-1) = 2 \alpha_1 \alpha_2 \\  \alpha_2 * \alpha_1 * -1 * 1 * (1 * -1 + -1*1) = 2 \alpha_1 \alpha_2 \\  \alpha_2 * \alpha_2 * -1 * -1 * (1 * 1 + -1*-1) = 2 \alpha_2^2 \end{cases} = 2 \alpha_1^2 + 2 \alpha_1 \alpha_2 + 2 \alpha_1 \alpha_2 + 2 \alpha_2 \\

L = \alpha_1 + \alpha_2 - \frac{1}{2} (2 \alpha_1^2 + 2 \alpha_1 \alpha_2 + 2 \alpha_1 \alpha_2 + 2 \alpha_2) = \alpha_1 + \alpha_2 - 2 \alpha_1 \alpha_2 - \alpha_1^2 - \alpha_2^2

 \vspace{2 em} \frac{\partial L}{\partial \alpha_1} = 0 \quad \to \quad -2 \alpha_1 - 2 \alpha_2 +1 = 0 \quad \to \quad \alpha_1 + \alpha_2 = \frac{1}{2} \\ \frac{\partial L}{\partial \alpha_2} = 0 \quad \to \quad -2 \alpha_2 - 2 \alpha_1 +1 = 0 \quad \to \quad \alpha_1 + \alpha_2 = \frac{1}{2}

 \vspace{2 em} \sum_{i=1}^N \alpha_i y_i = 0 \quad \to \quad 1 \alpha_1 - 1 \alpha_2 = 0 \quad \to \quad \alpha_1 = \alpha_2

Ergo:

\alpha_1 = \alpha_2 = \frac{1}{4}

Now let us calculate \overrightarrow{w}:

\overrightarrow{w} = \sum_{i=1}^N \alpha_i y_i x_i = \frac{1}{4} * 1 * [-1,1] + \frac{1}{4} * -1 * [1,-1] = [\frac{-1}{4} , \frac{1}{4}] + [\frac{-1}{4} , \frac{1}{4}] = [\frac{-2}{4} , \frac{2}{4}] = [\frac{-1}{2} , \frac{1}{2}]

Now we have to figure out the bias
\alpha [y_i (\overrightarrow{w}^T\overrightarrow{x_i} +b) -1] = 0 \quad \to \quad \alpha_i y_i \overrightarrow{w}^T\overrightarrow{x_i} + \alpha_i b y_i - \alpha_i = 0 \\ b = \frac{1-y_i \overrightarrow{w}^T\overrightarrow{x_i}}{y_i} \quad \to \quad b = \frac{1}{y_i} - \overrightarrow{w}^T\overrightarrow{x_i}

 \text{for i=1} \\ \text{ } \hspace{3em} b = 1 -[(-1,1) \cdot (\frac{-1}{2},\frac{1}{2})] = 0 \\ \text{for i=2} \\ \text{ } \hspace{3em} b = - 1 -[(1,-1) \cdot (\frac{-1}{2},\frac{1}{2})] = 0 \vspace{3em} \text{ }

Solution = \frac{-1}{2}x+\frac{1}{2}y=0 \quad \to \quad x-y=0

Example 2: 3 points in a plane

problem2
Points and class (coordinate x (x1), coordinate y (x2), class/output (y)):

Point 1:

Coordinates: x = [-1,-1]
Class (output): y = -1

Point 2:

Coordinates: x = [2,0]
Class (output): y = 1

Point 3:

Coordinates: x = [3,1]
Class (output): y = 1

First let us calculate the second part of the function we want to minimize. You can see both alphas being multiplied by two numbers. The first number is the product of y_i and y_j. The second number is the dot product between the two coordinates \overrightarrow{x_i} \cdot \overrightarrow{x_j}.
 L_1 = \begin{cases} \alpha_1 * \alpha_1 * 1 * 2\\  \alpha_1 * \alpha_2 * -1 * -2 \\  \alpha_2 * \alpha_1 * -1 * -4 \\  \alpha_2 * \alpha_2 * -1 * -2 \\  \alpha_1 * \alpha_2 * 1 * 4 \\  \alpha_2 * \alpha_1 * 1 * 6 \\  \alpha_2 * \alpha_2 * -1 * -4 \\  \alpha_1 * \alpha_2 * 1 * 6 \\  \alpha_2 * \alpha_1 * 1 * 10 \end{cases} = 2 \alpha_1^2 + 4 \alpha_1 \alpha_2 + 8 \alpha_1 \alpha_3 + 4 \alpha_2^2 + 12 \alpha_2 \alpha_3 + 10 \alpha_3^2 = 0 \\ \text{Apply } \alpha_1 = \alpha_2 + \alpha_3 \text{ and } \frac{-1}{2} \\ 2 \alpha_2 + 2 \alpha_3 - 5 \alpha_2^2 - 10 \alpha_3^2 - 14 \alpha_2 \alpha_3 = 0 \vspace{1em} \text{  }

 \frac{\partial L}{\partial \alpha_2} = 2 - 10 \alpha_2 - 14 \alpha_3 = 0 \\ \frac{\partial L}{\partial \alpha_3} = 2 - 14 \alpha_2 - 20 \alpha_3 = 0 \\ \alpha_2 = 3, \alpha_3 = -2, \alpha_1 = 1

w = 1*-1*[-1,-1] + 3*1*[2,0] - 2*1*[3,1] = [1,-1] \\ b_1 = b_2 = b_3 = -1

Result: x - y -1 = 0

Appendix A: Scalar Projection of Vectors

vecpro

We have two points and its vector:
R = [2,10] \quad \text{(red)} \\ B = [9,7] \quad \text{(blue)} \\ \overrightarrow{RB} = (7,-3)

And we want to calculate the length of the vector’s projection (purple) on the orange vector \overrightarrow{O} (which by the way, is the perpendicular of both green lines). The result is the blue vector which is over the orange one within the green region.

For this, we have to solve the formula:
\overrightarrow{RB} \cdot \frac{\overrightarrow{O}}{\| O \|} \\ (7,-3) \cdot \frac{(3,3)}{\sqrt{3^2 + 3^2}} \\ \frac{7*3-3*3}{\sqrt{18}} = 2\sqrt{2}

Now with the length and the angle, we can calculate the coordinates using sine and cosine functions.
x_{relative} = 2\sqrt{2} * \cos{(180 + 45)} = -2 \\ x_{relative} = 2\sqrt{2} * \sin{(180 +45)} = -2

B was in [9,7], so the point on the other side of the projection is [9-2,7-2] \to [7,5]

Appendix B: Lagrange Multipliers

Lagrange is a strategy to find local maxima and minima of a function subject to equality constraints, i.e. max of f(x,y) subject to g(x,y)=c. f(\cdot) and g(\cdot) need to have continuous first partial derivatives.

\text{ } \quad \wedge (x,y,\lambda) = f(x,y) + \lambda(g(x,y)-c) \quad \lambda \text{ may be positive or negative}

If f(x_0,y_0) is a maximum of f(x,y) for the original constrained problem, then there exists \lambda such that (x_0,y_0,\lambda_0) is a stationary point for Lagrange function (so \partial \wedge is 0).

localmaxmin

In mathematics, a stationary point of a differentiable function of one variable is a point of the function domain where the derivative is zero. For a function of several variables, the stationary point is an input whose all partial derivatives are zero (gradient zero). They correspond to local maxima or minima.

surface

To make it clear, let us say that we have a surface g(x,y,z) whose gradient is \Delta g and it is perpendicular to the whole surface. We try to find its maxima whose gradient should theoretically be perpendicular as well. Let us not forget the relationship between the first derivative and the gradient. Hence we can say that the gradient of g and the gradient of f are pointing in the same direction so: \overrightarrow{\Delta f} = \lambda \overrightarrow{\Delta g} (proportional). \lambda is called Lagrange multiplier.

Example 1: 1 constraint, 2 dimensions

Maximize f(x,y) = 3x+3y on unit circle x^2+y^2=1 \to g(x,y) = x^2+y^2-1

\frac{\partial f}{\partial x} = \lambda \frac{\partial g}{\partial x}  \to 3 = 2x \lambda \to x = \frac{3}{2 \lambda}\\ \frac{\partial f}{\partial y} = \lambda \frac{\partial g}{\partial y} \to 3 = 2y \lambda \to y = \frac{3}{2 \lambda}

Now we plug these results into the original equation.

x^2 + y^2 = 1 \to \frac{9+9}{4 \lambda^2} = \frac{18}{4 \lambda^2} = 1 \to \lambda = \pm \frac{\sqrt{18}}{2} = 2.12

Therefore we have two points:
(x,y) = (0.707,0.707) \quad \text{or} \quad (x,y) = (-0.707,-0.707) \quad \text{so} \quad f(x,y) = 2.12 \quad \text{or} \quad -2.12

exampl1

Example 2: 1 constraint, 2 dimensions

Find the rectangle of maximal perimeter that can be inscribed in the ellipse x^2+4y^2=4. We want to maximize the perimeter which is f(x,y) = 4x+4y subject to g(x,y) = x^2 +4y^2 -4

exampl2

\frac{\partial f}{\partial x} = \lambda \frac{\partial g}{\partial x}  \to 4 = 2x \lambda \\ \frac{\partial f}{\partial y} = \lambda \frac{\partial g}{\partial y} \to 4 = 8y \lambda \\ x = 4y

Now plug it into the original equation.

x^2+4y^2 = 4 \quad \to \quad 20y^2=4 \quad \to \quad y = \pm \sqrt{\frac{1}{5}}, \quad x=\frac{4}{\sqrt{5}} \quad (we take the positive because it is a maximum),

Then, P = (\frac{4}{\sqrt{5}},\frac{1}{\sqrt{5}})
So the maximum permieter is: f(x,y) = 4x+4y = 4* \frac{4}{\sqrt{5}}+4* \frac{1}{\sqrt{5}} = 4 \sqrt{5}

Example 3: 2 constraints, 3 dimensions

f(x,y,z) = x^2 + y^2 + z^2 \quad \text{subject to} \quad x+y+z=1 \to g_1(x,y,z) = x+y+z-1 \\ \text{ } \hspace{140pt} \text{and } x+2y+3z = 6 \to g_2(x,y,z) = x+2y+3z-6 \\ \vspace{15pt} \\
 \frac{\partial f}{\partial x} = \lambda_1 \frac{\partial g_1}{\partial x} + \lambda_2 \frac{\partial g_2}{\partial x} \quad \to \quad 2x = \lambda_1 + \lambda_2 \quad \to \quad x = \frac{\lambda_1 + \lambda_2}{2}\\ \frac{\partial f}{\partial y} = \lambda_1 \frac{\partial g_1}{\partial y} + \lambda_2 \frac{\partial g_2}{\partial y} \quad \to \quad 2y = \lambda_1 + 2 \lambda_2 \quad \to \quad y = \frac{\lambda_1 + 2 \lambda_2}{2}\\ \frac{\partial f}{\partial z} = \lambda_1 \frac{\partial g_1}{\partial z} + \lambda_2 \frac{\partial g_2}{\partial z} \quad \to \quad 2z = \lambda_1 + 3 \lambda_2 \quad \to \quad z = \frac{\lambda_1 + 3 \lambda_2}{2}\\

Now plug it into g_1(x,y,z) and g_2(x,y,z):

\frac{\lambda_1 + \lambda_2}{2} + \frac{\lambda_1 + 2 \lambda_2}{2} + \frac{\lambda_1 + 3 \lambda_2}{2} = 1 \quad \to \quad 3 \lambda_1 + 6 \lambda_2 = 2 \\ \frac{\lambda_1 + \lambda_2}{2} + \lambda_1 + 2 \lambda_2 + \frac{3}{2} (\lambda_1 + 3 \lambda_2) = 6 \quad \to \quad 6 \lambda_1 + 14 \lambda_2 = 12 \\ \lambda_2 = -4, \quad \lambda_1 = \frac{-22}{3} \\ x = \frac{-5}{3}, \quad y = \frac{1}{3}, \quad z = \frac{7}{3} \\ f(x,y,z) = x^2 + y^2 + z^2 \quad f(\frac{-5}{3}, \frac{1}{3}, \frac{7}{3}) = \frac{25}{3}

Since this is a parabola in 3 dimensions, this has no maximum, so it is a minimum.

lipman

"The only way to proof that you understand something is by programming it"

7 thoughts on “[Supervised Learning] SVM – Support Vector Machine explained with examples

  1. In example 1, the last line says
    (x,y) = (3/5, 4/5) Then f(x,y) = 3(x + y) = 21/5 = 4.2. Hos is the answer shown as 5? Am i missing something?

    1. That would be absolutely true, but there was a typo in that part of the text and I updated it:

      I wrote:
      3 = 2xλ
      4 = 2yλ
      And it is suppose to be:
      3 = 2xλ
      3 = 2yλ

      Thank you for noticing the error!

  2. Very useful and nice explanation.
    In mathematical explanation section after “(From the previous formula y_i(\overrightarrow{x_i} \cdot \overrightarrow{w}+b) -1 = 0 now let us substitute both positive and negative samples x_+ and x_- so that:)” in second equation I guess there is a typo I guess. It should be “x_-” instead of and “x_+”.
    am I right ?

Leave a Reply

Your email address will not be published. Required fields are marked *