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 Soft-Margin SVM (without kernels).
SVM in a nutshell
The following figure describes the soft-margin 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/hard-margin) 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)) { # soft-margin Amat <- rbind (y, diag (n_samples), -1* diag (n_samples)) bvec <- c (0, rep (0, n_samples), rep (-C, n_samples)) } else { # hard-margin 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 1e-5) # some small threshold # ... } |
The following python code from Mathieu Blondel’s Blog, shows how a kernelized (soft/hard-margin) 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 : # hard-margin SVM G = cvxopt.matrix(np.diag(np.ones(n_samples) * - 1 )) h = cvxopt.matrix(np.zeros(n_samples)) else : # soft-margin 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 80-20 Validation on the dataset is used to
As can be seen from the results below,
© 2021 TechTarget, Inc.
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: 2008-2014 | 2015-2016 | 2017-2019 | 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