Multiclass SVM¶

Crammer and Singer (2001) have extended the binary SVM classifier to classification problems with more than two classes. The training problem of the Crammer-Singer multiclass SVM can be expressed as a QP

(1)¶ $\begin{array}{ll} \mbox{maximize} & -(1/2) \mathbf{Tr}(U^TQU) + \mathbf{Tr}(E^TU) \\ \mbox{subject to} & U \preceq \gamma E \\ & U \mathbf{1}_m = 0 \end{array}$

with variable $U \in \mathbf{R}^{N \times m}$ where $N$ is the number of training examples and $m$ the number of classes. The $N \times N$ kernel matrix $Q$ is given by $Q_{ij} = K(x_i, x_j)$ where $K$ is a kernel function and $x_i^T$ is the i’th row of the $N \times n$ data matrix $X$ , and $d$ is an $N$ -vector with labels (i.e. $d_i \in \{ 0,1,\ldots,m-1 \}$ ).

Documentation

A custom solver for the multiclass support vector machine training problem is available as a Python module mcsvm. The module implements the following function:

mcsvm(X, labels, gamma, kernel = 'linear', sigma = 1.0, degree = 1)¶

Solves the problem (1) using a custom KKT solver.

The 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$ .

Valid kernel functions are:

'linear'
the linear kernel: $K(x_i,x_j) = x_i^Tx_j$

'poly'
the polynomial kernel: $K(x_i,x_j) = (x_i^Tx_j/\sigma)^d$

The kernel parameters $\sigma$ and $d$ are specified using the input arguments sigma and degree, respectively.

Returns the function classifier(). If $Y$ is $M \times n$ then classifier(Y) returns a list with as its k’th element

$\operatorname*{arg\,max}_{j=0,\ldots,m-1} \sum_{i=1}^N U_{ij} K(x_i, y_k)$

where $y_k^T$ is row $k$ of $Y$ , $x_i^T$ is row $k$ of $X$ , and $U$ is the optimal solution of the QP (1).