TransWikia.com

Support Vector Machines with soft margin: solving the dual form

Data Science Asked by Miistogun on April 4, 2021

I am currently struggling with finding an analytical solution for the $alpha_k$.
I have derived the following constrained optimization problem:

$$
L = sum_{i=1}^{N} alpha_i – frac{1}{2} sum_{i=1}^{N}sum_{j=1}^{N}alpha_i alpha_j y_i y_j (textbf{x}_j^T textbf{x})
$$

$$
s.t. quad 0 leq alpha_i leq C quad forall i, quad sum_{i=1}^{N} alpha_i y_i = 0
$$

I had, at first, not taken the constraints into account which, after taking the derivative w.r.t. $alpha_k$, gave me:
$$
y_k sum_{i=1}^{N} alpha_i y_i (textbf{x}_j^T textbf{x}) = 1
$$

This system of linear equations I could easily solve in Python using numpy.
But as the alpha values were way too high (as could have been expected), I went back and found that I had forgotten about the constraints.

Now, I don’t know how to find an analytical solution to that.
I have tried writing down the problem using Lagrange Multipliers but that doesn’t seem to get me anywhere.
I have also looked around the Internet a lot and couldn’t find a single lecture/slides/etc. that actually went on from that point.

Now is my question, is there a way to find an analytical solution to that constrained optimization problem or do I have to just put all of that into a solver?
And if there is a solution, I would appreciate some hints on how to get there.

Thank you for your Time!

One Answer

if you want to find an analytical solution for the problem I think that it doesn't exist.

At this point you should apply decomposition (don't try to work on all your variables, but iteratively considers only a subset of them called working set), if (and only if) you use a working set W, |W|=2, then your subproblem has an analytical solution.

Due to the large number of alpha variables, decomposition is the basis of svm implementations, in particular the svm light algorithm uses a working set W of cardinality 2.

Answered by fabianod on April 4, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP