Robust SVM

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

\[\begin{split}\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}\end{split}\]

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 \(X \in \mathbf{R}^{N\times n}\) has as its rows the training examples \(x_i^T\) and the vector \(d \in \{-1, 1\}^N\) 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{split}\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}\end{split}\]

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)