Implementation of Hard Margin SVM using Quadratic Programming , with Examples [CVXOPT Python]
At the end of the article “Step By Step Mathematical Formulation of Hard Margin SVM,” the formulation produced a compact cost function that was meant to be maximized. The gradient ascent method, whose implementation has been discussed in this article, can be used to solve this maximization problem. There exists a second solution that converts the maximization problem into a minimization one and solves it using quadratic programming.
Quadratic programming, roughly speaking, is a method to solve quadratic equations w.r.t. some conditions.
There is a software package in Python meant for solving convex optimization problems called “cvxopt”. One type is quadratic programming problems. “cvxopt” provides an interface called “cvxopt.solvers” for solving each of the included convex problems. The solver cvxopt.solvers.qp(*args) handles quadratic programming problems “as the name suggests”. This solver is implemented to handle quadratic minimization problems in the following format:
Therefore, before using cvxopt.solvers.qp(*args), minimization problems should be rearranged to conform with the standard format above.
The hard margin SVM can be formulated as a minimization problem by minimizing the negative of the cost function that originally intended to be maximized.
Hard margin SVM maximization form:
Multiplying J(α) by -1 and minimize it ⇒
So far, by comparing the minimization form of the hard margin SVM and the standard format of the quadratic programming solver from the cvxopt package:
We get the following equalities:
Before feeding the terms of the SVM’s minimization problem to the cvxopt.solvers.qp(*args), they should be converted into a special object called “matrix” that is provided by cvxopt too. Furthermore, the terms are passed as positional arguments (they must be passed in the following order):
cvxopt.solvers.qp(P, q, G, h, A, b)The output of the code above is a dictionary that contains the solution in the key “x” along with other key information about the solution. Last but not least, cvxopt never brings the values of the solution elements to zero; they get close but almost never exactly zero, as far as I know. As we know that only a few of the α’s are non-zero, a threshold should be used to zero out any value that is less than it.
Now that we have all of the elements required to construct the quadratic programming solution of the hard margin SVM, an OOP model could look like this:
Let’s try this solution on the same examples we have used in the implementation of the gradient ascent solution.
The code is identical to the previous article, with the exception that instances of the HardMarginSVMcvxopt class are used instead of HardMarginSVM. Then the visualization of the results will look like the following.
Synthetic data example
Customized Iris dataset example
