Robust SVM¶

The robust SVM training problem can be expressed as a cone QP with second-order cone constraints:

$\begin{array}{ll} \mbox{minimize} & (1/2) w^Tw + \gamma \mathbf{1}^Tv \\ \mbox{subject to} & \mathbf{diag}(d)(Xw + b \mathbf{1} ) \succeq 1 - v + Eu \\ & v \succeq 0 \\ & \| S_j w\|_2 \leq u_j, \quad j =1,\ldots,t. \end{array}$

The variables are $w \in \mathbf{R}^n$ , $b \in \mathbf{R}$ , $v \in \mathbf{R}^N$ , and $u \in \mathbf{R}^t$ . The matrix

System Message: WARNING/2 (X \in \mathbf{R}^{N×n})

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.20 (TeX Live 2019) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2018-12-01> (/usr/local/texlive/2019/texmf-dist/tex/latex/base/article.cls Document Class: article 2018/09/03 v1.4i Standard LaTeX document class (/usr/local/texlive/2019/texmf-dist/tex/latex/base/size12.clo)) (/usr/local/texlive/2019/texmf-dist/tex/latex/base/inputenc.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?' option. (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/umsb.fd) ! Package inputenc Error: Unicode character × (U+00D7) (inputenc) not set up for use with LaTeX. See the inputenc package documentation for explanation. Type H <return> for immediate help. ... l.13 ...{12}{14}\selectfont $X \in \mathbf{R}^{N× n}$ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 360 bytes). Transcript written on math.log.

has as its rows the training examples $x_i^T$ and the vector

System Message: WARNING/2 (d \in \{−1, 1\}^N)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.20 (TeX Live 2019) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2018-12-01> (/usr/local/texlive/2019/texmf-dist/tex/latex/base/article.cls Document Class: article 2018/09/03 v1.4i Standard LaTeX document class (/usr/local/texlive/2019/texmf-dist/tex/latex/base/size12.clo)) (/usr/local/texlive/2019/texmf-dist/tex/latex/base/inputenc.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?' option. (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/local/texlive/2019/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/local/texlive/2019/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/local/texlive/2019/texmf-dist/tex/latex/amsfonts/umsb.fd) ! Package inputenc Error: Unicode character − (U+2212) (inputenc) not set up for use with LaTeX. See the inputenc package documentation for explanation. Type H <return> for immediate help. ... l.14 \{− 1, 1\}^N$ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 360 bytes). Transcript written on math.log.

contains the training labels. The matrices $S_j$ define the shape and the size of the uncertainty ellipsoids, and the matrix $E$ is a selector matrix with zeros and one ‘1’ per row. $E_{ij} = 1$ means that the i’th training vector is associated with the j’th uncertainty ellipsoid. For $t = 0$ , the term $Eu$ and the norm constraints are absent, and the problem reduces to the standard linear SVM

$\begin{array}{ll} \mbox{minimize} & (1/2) w^Tw + \gamma \mathbf{1}^Tv \\ \mbox{subject to} & \mathbf{diag}(d)(Xw + b \mathbf{1} ) \succeq 1 - v \\ & v \succeq 0. \end{array}$

Documentation

A custom solver for the robust SVM problem is available as a Python module robsvm.py. The module implements the following function:

robsvm(X, labels, gamma, P, e)¶

Solves the ‘soft-margin’ robust SVM problem.

The first three input arguments are the data matrix $X$ (with the $N$ training examples $x_i^T$ as rows), the label vector $d$ , and the positive parameter $\gamma$ . The fourth input argument P must be a Python list of $t$ matrices $S_1,\ldots,S_t$ . The last argument e is an $N$ -vector where the i’th element $e_i \in \{0,..,t-1\}$ is the index of the uncertainty ellipsoid associated with the i’th training vector.

The function returns $w$ , $b$ , $u$ , $v$ , and the number of iterations (an integer).

Example

from robsvm import robsvm
from cvxopt import matrix, normal, uniform

# parameters
m, n = 60, 2
gamma = 10.0

# generate random problem data
X = 2.0*uniform(m,n)-1.0
d = matrix(1,(m,1))

# generate noisy labels
w0 = matrix([2.0,1.0])+normal(2,1); b0 = 0.4
z = 0.2*normal(m,1)
for i in range(m):
    if (X[i,:]*w0)[0] + b0 < z[i]: d[i] = -1

# generate uncertainty ellipsoids
k = 2
P = [0.1*normal(4*n,n) for i in range(k)]
P = [ p.T*p for p in P]
e = matrix(0,(m,1))
for i in xrange(m):
    if d[i] == -1: e[i] = 1

# solve SVM training problem
w, b, u, v, iterations = robsvm(X, d, gamma, P, e)