3
$\begingroup$

I am trying to get a better understanding of SVMs and their optimization process. I understand that we have a constrained optimization problem that we have to solve with Lagrange multipliers.

The formula that we need to maximize is

lagrange

where the alphas are the Lagrange multipliers, the x-vectors the vectors of the training data and the scalar y is the label for the positive/negative class {-1, 1}. N is the total number of training vectors.

In my mind, the alphas are optimized in such a way that non-relevant vectors (non-support vectors) are equal to zero and the real support vectors get a value greater than zero. In most tutorials, however, the lecturer stops and leaves the optimization to an algorithm of sorts. I want to understand how the machine calculates these parameters with only a few, say four or five vectors.

Is it correct that the first thing that I have to do is to take the derivative of L w.r.t. every alpha, so that I get a system of linear equations that I can solve for every alpha?

To make my thoughts clear, consider the case with only 2 support vectors, where the first vector has class 1 and the second vector class -1. The system would look like this:

deriv1

deriv2

I set all equations equal to zero because I want to find the maximum. This leaves me with a system of linear equations, when reordering the alphas:

enter link description here

enter link description here

I would be grateful for some advice, if this is correct or not. I have stumbled across calculations similar to this (e.g. https://axon.cs.byu.edu/Dan/478/misc/SVM.example.pdf), but I cannot reproduce the equations there with my approach.

Also, I would be interested in how I am going to continue from here. I know that I can calculate the normal vector of the plane with all the alphas, but I do not know how to calculate the offset b of the plane.

Thanks for your help!

$\endgroup$

1 Answer 1

1
$\begingroup$

$\def\o{{\tt1}}\def\D{{\rm Diag}}\def\p#1#2{\frac{\partial #1}{\partial #2}}$Let $X$ be the matrix whose colums are the $x_k$ vectors. Let's also define the vectors $(a,y)$ whose components are $(\alpha_k,y_k)$, and their corresponding diagonal matrices $$\eqalign{ A = \D(a) \quad\quad Y=\D(y) \\ }$$ It will also be convenient to define the symmetric matrix $$S=YX^TXY$$ Write the Lagrangian in terms of these new variables and the all-ones vector $\o$.
Then calculate the differential and the gradient. $$\eqalign{ L &= \o:a - \tfrac 12S:aa^T \\ dL &= \o:da - \tfrac 12S:\left(da\,a^T+a\,da^T\right) \\ &= \o:da - \tfrac 12\left(S+S^T\right):da\,a^T \\ &= \o:da - S:da\,a^T \\ &= \left(\o - Sa\right):da \\ \p{L}{a} &= \left(\o - Sa\right) \\ }$$ Set the gradient to zero and solve for the vector of Lagrange multipliers $$\eqalign{ Sa = \o \quad\implies\quad a = S^{-1}\o \\\\ }$$


In the above, a colon is used as a convenient product notation for the trace function, i.e. $$A:B = {\rm Tr}(A^TB)$$ Note that when $(A,B)$ are vectors, this reduces to the ordinary dot product.

The transpose and cyclic properties of the trace allow the terms in such a product to be rearranged in many equivalent ways, e.g. $$\eqalign{ A:B &= B:A = B^T:A^T \\ BC:A &= B:AC^T = C:B^TA \\ }$$
The important thing to remember is that the matrix (or vector) on each side of the colon must have the same dimensions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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