16
$\begingroup$

I am working on a trivial example of SVM to gain some intuition behind the way it works. In the case of 6 data points, would it be possible to calculate the value of $w$ and $b$ by hand ? Intuitively I am able to get the correct values up to a scaling factor only.

Using Sklearn with a linear kernel the correct values are

  • $w = (\frac{1}{4}, - \frac{1}{4})^T$
  • $b = - \frac{3}{4}$

Intuitively I tried different values:

  • $w = (1, - 1)^T$ and $b = - 3$ which comes from the straightforward equation of the line $x_2 = x_1 - 3$. This gives the correct decision boundary and geometric margin $2\sqrt{2}$
  • $w = (\frac{1}{\sqrt{2}}, - \frac{1}{\sqrt{2}})^T$ and $b = - \frac{3}{\sqrt{2}}$ which ensures that $||w|| = 1$ but doesn't get me much further

Example

SVM simple

Dataset and Sklearn result

import numpy as np
from sklearn.svm import SVC

X = np.array([[3,4],[1,4],[2,3],[6,-1],[7,-1],[5,-3]] )
y = np.array([-1,-1, -1, 1, 1 , 1 ])

clf = SVC(C = 1e5, kernel = 'linear')
clf.fit(X, y) 
$\endgroup$

3 Answers 3

11
$\begingroup$

Solving the SVM problem by inspection

By inspection we can see that the boundary decision line is the function $x_2 = x_1 - 3$. Using the formula $w^T x + b = 0$ we can obtain a first guess of the parameters as

$$ w = [1,-1] \ \ b = -3$$

Using these values we would obtain the following width between the support vectors: $\frac{2}{\sqrt{2}} = \sqrt{2}$. Again by inspection we see that the width between the support vectors is in fact of length $4 \sqrt{2}$ meaning that these values are incorrect.

Recall that scaling the boundary by a factor of $c$ does not change the boundary line, hence we can generalize the equation as

$$ cx_1 - xc_2 - 3c = 0$$ $$ w = [c,-c] \ \ b = -3c$$

Plugging back into the equation for the width we get

\begin{aligned} \frac{2}{||w||} & = 4 \sqrt{2} \\ \frac{2}{\sqrt{2}c} & = 4 \sqrt{2} \\ c = \frac{1}{4} \end{aligned}

Hence the parameters are in fact $$ w = [\frac{1}{4},-\frac{1}{4}] \ \ b = -\frac{3}{4}$$

To find the values of $\alpha_i$ we can use the following two constraints which come from the dual problem:

$$ w = \sum_i^m \alpha_i y^{(i)} x^{(i)} $$ $$\sum_i^m \alpha_i y^{(i)} = 0 $$

And using the fact that $\alpha_i \geq 0$ for support vectors only (i.e. 3 vectors in this case) we obtain the system of simultaneous linear equations: \begin{aligned} \begin{bmatrix} 6 \alpha_1 - 2 \alpha_2 - 3 \alpha_3 \\ -1 \alpha_1 - 3 \alpha_2 - 4 \alpha_3 \\ 1 \alpha_1 - 2 \alpha_2 - 1 \alpha_3 \end{bmatrix} & = \begin{bmatrix} 1/4 \\ -1/4 \\ 0 \end{bmatrix} \\ \alpha & = \begin{bmatrix} 1/16 \\ 1/16 \\ 0 \end{bmatrix} \end{aligned}

Source

$\endgroup$
6
  • $\begingroup$ Why is there alpha3 here? There are only two support vectors. $\endgroup$
    – Vol Ume
    Jun 6, 2020 at 14:34
  • $\begingroup$ there are three data points $\endgroup$ Jun 6, 2020 at 16:29
  • $\begingroup$ Thanks @Xavier. Got it, [6,-1], [2,3] and [3,4] are support vectors. Clarifies the need for alpha3. The code you had shared in the 'full post' shows only two support vectors. Ignores [3,4] also it shows [1,1] as number of vectors for each class. Pasting the cell output from your notebook. Is that convention of sklearn or I am missing something? > w = [[ 0.25 -0.25]] b = [-0.75] Indices of support vectors = [2 3] > Support vectors = [[ 2. 3.] [ 6. -1.]] Number of support vectors > for each class = [1 1] Coefficients of the support vector in the > decision function = [[0.0625 0.0625]] $\endgroup$
    – Vol Ume
    Jun 6, 2020 at 17:14
  • 1
    $\begingroup$ i see 3 support vectors. the -2alpha2 in the position (3,2) of the matrix is wrong, shouldnt there be a -1alpha? i mean ... the graph says y = -1 for support vector 2,3 $\endgroup$ Sep 3, 2020 at 20:52
  • $\begingroup$ @redestructa, yes you are right, it should be -1α2 $\endgroup$ Jul 24, 2021 at 8:38
1
$\begingroup$

Instead of computing the width between the support vectors (which in this case was easy because two of them happened to be directly across from each other over the decision line), it might be more convenient to use that the support vectors should have value $\pm1$ under the decision function:

$$ cx_1 - cx_2 -3c =0 $$

represents the line, but using the point $B=(2,3)$ with target $-1$ in the diagram, we should have

$$ c(2) - c(3) -3c =-1$$

and hence (again) $c=1/4$.

$\endgroup$
1
$\begingroup$

Yet another solution:

First let's note the support vectors (SV) output by sklearn implementation:

import numpy as np
from sklearn.svm import SVC

X = np.array([[3,4],[1,4],[2,3],[6,-1],[7,-1],[5,-3]] )
y = np.array([-1,-1, -1, 1, 1 , 1 ])

clf = SVC(C = 1e5, kernel = 'linear')
clf.fit(X, y) 
clf.support_vectors_
# array([[ 2.,  3.],
#        [ 6., -1.]])

By observing that out of the $n=6$ training data-points, two of the data-points $A=(6,-1)$ and $B=(2,3)$ suffice to construct the set of support vectors (and define the max-margin decision boundary), and the dual maximization objective $L$ being

$L(\alpha)=\sum\limits_{i=1}^6 \alpha_i - \frac{1}{2}\sum\limits_{i=1}^6\sum\limits_{j=1}^6 \alpha_i\alpha_j y_i y_j \langle x_i, x_j \rangle$,

s. t. $\quad\quad\quad\quad\sum\limits_{i=1}^6 \alpha_i y_i = 0$ and $\alpha_i \geq 0 \quad \forall{i}$.

Noting that $\alpha_i=0, \quad \forall{i}$ except the points $A, B$ (due to KKT complimentary slackness condition),

the dual Lagrangian reduces to the following:

$L(\alpha_A, \alpha_B, \lambda)$

$= (\alpha_A + \alpha_B) - \frac{1}{2}\left(\alpha_A^2 (y_A)^2 \langle A, A \rangle + \alpha_B^2 (y_B)^2 \langle B, B \rangle + 2\alpha_A \alpha_B (y_A y_B) \langle A, B \rangle\right) + \lambda (\alpha_A y_A + \alpha_B y_B)$,

$=(\alpha_A + \alpha_B) - \frac{1}{2}\left(37\alpha_A^2 + 13\alpha_B^2 - 18\alpha_A \alpha_B\right) + \lambda (\alpha_A - \alpha_B)$,

where $\lambda$ is the lagrange multiplier. Also, $y_A$ and $y_B$ have opposite signs (let $y_A=+1 \implies y_B=-1$).

At a critical point, we shall have,

$\frac{\partial L}{\partial \alpha_A} = 0 \implies 37\alpha_A-9\alpha_B-\lambda=1$ and

$\frac{\partial L}{\partial \alpha_B} = 0 \implies 13\alpha_B-9\alpha_A+\lambda=1$

$\frac{\partial L}{\partial \lambda} = 0 \implies \alpha_A=\alpha_B$

Putting $\alpha_A=\alpha_B$ in first two equations yields

$28\alpha_A-\lambda=1$

$4\alpha_A+\lambda=1$

$\implies \alpha_A=\alpha_B=\frac{1}{16}$

Hence, $w=\sum_\limits{i=1}^6 \alpha_i y_i x_i = (\alpha_A y_A) A + (\alpha_B y_B) B = \frac{1}{16}(6, -1) - \frac{1}{16} (2, 3) = \left(\frac{4}{16},-\frac{4}{16}\right)$

$\implies w = \left(\frac{1}{4},-\frac{1}{4}\right)$

Also, from $y_i (w^T x_i + b) = 1$, we have $b = y_i - w^T x_i$.

$\implies b = 1 - \left\langle \left(\frac{1}{4}, -\frac{1}{4}\right), (6, -1) \right\rangle = 1 - \frac{7}{4} = -\frac{3}{4}$.

We can follow the above calculations with SV set containing $3$ data-points $A=(6,-1),\; B=(2,3), \; C=(3,4)$, there will be $3$ dual decision variables and the equations will be more complex, but we shall end with the same $w$ and $b$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.