0
$\begingroup$

So I need to code an SVM from bottom up in Python, and I cannot use stuff like libSVM or scikit-learn, for reasons of my own.

Referring to Andrew Ng's excellent notes on Support Vector Machines, I need to specifically implement the second equation on page 20,

$$\max_\alpha W(\alpha) = \sum_{i=1}^m\alpha_i - \frac 1 2 \sum_{i,j=1}^m(y^{(i)} \times y^{(j)} \times \alpha_i \times \alpha_j \times \langle x_i, x_j\rangle)$$

Subject to the given constraints, $\sum_{i=1}^m\alpha_i y_i = 0$, and $0 \le \alpha_i \le C$.

Does someone have the code for this in any language, or can explain the intuition behind coding this? Most SVM implementations I could find either stick to scikit-learn or neglect kernel functions altogether. While I am working in Python, I would try to understand code in any language.

$\endgroup$
2
$\begingroup$

The SVM problem is a quadratic programming problem. It depends on whether you are willing to call a quadratic programming packages to solve your problem, if you are willing to do so, you just have to reformat the question in the input format of a programming language. Here is a resource for how to call quadratic programing solver in Python and here is how to do it in matlab.

Note that

$$\sum_{i=1}^m \alpha_i-\frac12\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_jK( x_i, x_j)=e^T\alpha-\frac12\alpha^TA\alpha$$

where $A_{ij}=y^{(i)}y^{(j)}K(x_i,x_j)$ , $K$ is the kernel function, and $e$ is the all one vector.

Now, suppose you are not willing to call a quadratic programming solver. If you read on the document that you attached, you will reach a section called sequential minimal optimization. Here is the wikipedia page of the algorithm.

The idea of the algorithm is that we can't update a single $\alpha_i$ at a time due to the linearity constraint, hence we do the update in pairs of $\alpha_i$ and $\alpha_j$. You might want to refer to Platt's paper for details including heuristic on how to choose the pair for update.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Hi, so I am actually using an alternative to SMO, and was planning to use an optimization algorithm to say, maximize a single function. While you can, say, control the first constraint using a clipping function on the boundaries, it is tougher to implement the second condition in a single function. Could you think about it like that? Thanks for your help though! $\endgroup$ – VSA Dec 4 '17 at 2:55
  • $\begingroup$ SMO code online. $\endgroup$ – Siong Thye Goh Dec 4 '17 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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