How to code an SVM's equation including kernels?

Question

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.

Answer 1

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.