In this article, couple of implementations of the support vector machine binary classifier with quadratic programming libraries (in R and python respectively) and application on a few datasets are going to be discussed.
The next figure describes the basics of SoftMargin SVM (without kernels).
SVM in a nutshell
The following figure describes the softmargin SVM in a more formal way.
The following figures show how the SVM dual quadratic programming problem can be formulated using the R quadprog QP solver (following the QP formulation in the R package quadprog).
The following figures show how the SVM dual quadratic programming problem can be formulated using the Python CVXOPT QP solver (following the QP formulation in the python library CVXOPT).
The following R code snippet shows how a kernelized (soft/hardmargin) SVM model can be fitted by solving the dual quadratic optimization problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

library (quadprog) library (Matrix) svm_fit < function (X, y, FUN=linear_kernel, C= NULL ) { n_samples < nrow (X) n_features < ncol (X) # Gram matrix K < matrix ( rep (0, n_samples*n_samples), nrow=n_samples) for (i in 1:n_samples){ for (j in 1:n_samples){ K[i,j] < FUN (X[i,], X[j,]) } } Dmat < outer (y,y) * K # convert Dmat to the nearest positive definite matrix Dmat < as.matrix ( nearPD (Dmat)$mat) dvec < rep (1, n_samples) if (! is.null (C)) { # softmargin Amat < rbind (y, diag (n_samples), 1* diag (n_samples)) bvec < c (0, rep (0, n_samples), rep (C, n_samples)) } else { # hardmargin Amat < rbind (y, diag (n_samples)) bvec < c (0, rep (0, n_samples)) } res < solve.QP (Dmat,dvec, t (Amat),bvec=bvec, meq=1) # Lagrange multipliers a < res$solution # Support vectors have non zero lagrange multipliers ind_sv 1e5) # some small threshold # ... } 
The following python code from Mathieu Blondel’s Blog, shows how a kernelized (soft/hardmargin) SVM model can be fitted by solving the dual quadratic optimization problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import numpy as np import cvxopt def fit(X, y, kernel, C): n_samples, n_features = X.shape # Compute the Gram matrix K = np.zeros((n_samples, n_samples)) for i in range (n_samples): for j in range (n_samples): K[i,j] = kernel(X[i], X[j]) # construct P, q, A, b, G, h matrices for CVXOPT P = cvxopt.matrix(np.outer(y,y) * K) q = cvxopt.matrix(np.ones(n_samples) *  1 ) A = cvxopt.matrix(y, ( 1 ,n_samples)) b = cvxopt.matrix( 0.0 ) if self .C is None : # hardmargin SVM G = cvxopt.matrix(np.diag(np.ones(n_samples) *  1 )) h = cvxopt.matrix(np.zeros(n_samples)) else : # softmargin SVM G = cvxopt.matrix(np.vstack((np.diag(np.ones(n_samples) *  1 ), np.identity(n_samples)))) h = cvxopt.matrix(np.hstack((np.zeros(n_samples), np.ones(n_samples) * C))) # solve QP problem solution = cvxopt.solvers.qp(P, q, G, h, A, b) # Lagrange multipliers a = np.ravel(solution[ 'x' ]) # Support vectors have non zero lagrange multipliers sv = a > 1e  5 # some small threshold # ... 
For each dataset, the 8020 Validation on the dataset is used to
As can be seen from the results below,
© 2020 Data Science Central ® Powered by
Badges  Report an Issue  Privacy Policy  Terms of Service
Most Popular Content on DSC
To not miss this type of content in the future, subscribe to our newsletter.
Other popular resources
Archives: 20082014  20152016  20172019  Book 1  Book 2  More
Most popular articles
You need to be a member of Data Science Central to add comments!
Join Data Science Central