Support vector machines

Given a collection of \(m\) labeled vectors, each of the form \((a_i,\delta_i) \subset \mathbb{R}^n \times \{-1,1\}\), a soft-margin Support Vector Machine seeks the “best” hyperplane for approximately separating the labeled vectors in the sense that it balances maximizing the separation distance (“margin”) associated with the hyperplane with the possibility that some of the vectors might not fit the model.

More specifically, a solution is sought for

\[\begin{split}& \min_{w,\beta,z} \frac{1}{2} \| w \|_2^2 + \lambda \sum_i \xi_i \\ & \text{s.t. } \delta_i ( w^T a_i + \beta ) \le 1 - \xi_i, \; \xi_i \ge 0, \; \forall\; i,\end{split}\]

where \(w\) is the unnormalized normal vector for the separating hyperplane, \(2/\|w\|_2\) is the margin, \(\beta/\|w\|_2\) is the distance between the hyperplane and the origin, and the \(i\)’th entry of \(z\), \(\xi_i\), is the misfit for the \(i\)’th vector.

The problem can be placed in affine quadratic form by building an \(m \times n\) matrix \(A\) with its \(i\)’th row set to \(a_i\) and a vector \(d\) with its \(i\)’th entry set to \(\delta_i\), yielding

\[\begin{split}& \min_{w,\beta,z} \frac{1}{2} \| w \|_2^2 + \lambda 1^T z \\ & \text{s.t. } \begin{pmatrix} -\text{diag}(d) A & -d & -I \\ 0 & 0 & -I \end{pmatrix} \begin{pmatrix} w \\ \beta \\ z \end{pmatrix} \le \begin{pmatrix} -1 \\ 0 \end{pmatrix},\end{split}\]

which Elemental then defaults to solving with a Mehrotra Predictor-Corrector primal-dual Interior Point Method.

Python API

SVM(A, d, lambd[, ctrl=None])

C++ API

void SVM(const Matrix<Real> &A, const Matrix<Real> &d, Real lambda, Matrix<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

void SVM(const ElementalMatrix<Real> &A, const ElementalMatrix<Real> &d, Real lambda, ElementalMatrix<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

void SVM(const SparseMatrix<Real> &A, const Matrix<Real> &d, Real lambda, Matrix<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

void SVM(const DistSparseMatrix<Real> &A, const DistMultiVec<Real> &d, Real lambda, DistMultiVec<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

C API

Single-precision

ElError ElSVM_s(ElConstMatrix_s A, ElConstMatrix_s d, float lambda, ElMatrix_s x)

ElError ElSVMDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s d, float lambda, ElDistMatrix_s x)

ElError ElSVMSparse_s(ElConstSparseMatrix_s A, ElConstMatrix_s d, float lambda, ElMatrix_s x)

ElError ElSVMDistSparse_s(ElConstDistSparseMatrix_s A, ElConstDistMultiVec_s d, float lambda, ElDistMultiVec_s x)

Double-precision

ElError ElSVM_d(ElConstMatrix_d A, ElConstMatrix_d d, double lambda, ElMatrix_d x)

ElError ElSVMDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d d, double lambda, ElDistMatrix_d x)

ElError ElSVMSparse_d(ElConstSparseMatrix_d A, ElConstMatrix_d d, double lambda, ElMatrix_d x)

ElError ElSVMDistSparse_d(ElConstDistSparseMatrix_d A, ElConstDistMultiVec_d d, double lambda, ElDistMultiVec_d x)

Expert interface

Single-precision

ElError ElSVMX_s(ElConstMatrix_s A, ElConstMatrix_s d, float lambda, ElMatrix_s x, ElQPAffine_s ctrl)

ElError ElSVMXDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s d, float lambda, ElDistMatrix_s x, ElQPAffineCtrl_s ctrl)

ElError ElSVMXSparse_s(ElConstSparseMatrix_s A, ElConstMatrix_s d, float lambda, ElMatrix_s x, ElQPAffineCtrl_s ctrl)

ElError ElSVMXDistSparse_s(ElConstDistSparseMatrix_s A, ElConstDistMultiVec_s d, float lambda, ElDistMultiVec_s x, ElQPAffineCtrl_s ctrl)

Double-precision

ElError ElSVMX_d(ElConstMatrix_d A, ElConstMatrix_d d, double lambda, ElMatrix_d x, ElQPAffine_d ctrl)

ElError ElSVMXDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d d, double lambda, ElDistMatrix_d x, ElQPAffineCtrl_d ctrl)

ElError ElSVMXSparse_d(ElConstSparseMatrix_d A, ElConstMatrix_d d, double lambda, ElMatrix_d x, ElQPAffineCtrl_d ctrl)

ElError ElSVMXDistSparse_d(ElConstDistSparseMatrix_d A, ElConstDistMultiVec_d d, double lambda, ElDistMultiVec_d x, ElQPAffineCtrl_d ctrl)