11.2 Primal Support-Vector Machine (SVM)

Machine-Learning (ML) has become a common widespread tool in many applications that affect our everyday life. In many cases, at the very core of these techniques there is an optimization problem. This case study focuses on the Support-Vector Machines (SVM).

The basic SVM model can be stated as:

We are given a set of $m$ points in ${\mathbb{R}}^n$, partitioned into two groups. Find, if any, the separating hyperplane of the two subsets with the largest margin, i.e. as far as possible from the points.

Mathematical Model

Let $x_1,\dots ,x_m\in {\mathbb{R}}^n$ be the given training set and let $y_i\in \{-1,+1\}$ be the labels indicating the group membership of the $i$-th training example. Then we want to determine an affine hyperplane $w^{T}x=b$ that separates the group in the strong sense that

(11.13)$$y_i(w^T{x}_i-b)\ge 1$$

for all $i$, the property referred to as large margin classification: the strip $\{x\in {\mathbb{R}}^n:-1<w^{T}x-b<1\}$ does not contain any training example. The width of this strip is $2\Vert w{\Vert }^{-1}$, and maximizing that quantity is equivalent to minimizing $\Vert w\Vert$. We get that the large margin classification is the solution of the following optimization problem:

$$\begin{array}{r}\begin{array}{lll}{\text{minimize}}_{b,w}& \frac{1}{2}\Vert w{\Vert }^2& \\ \text{subject to}& y_i(w^T{x}_i-b)\ge 1& i=1,\dots ,m.\end{array}\end{array}$$

If a solution exists, $w,b$ define the separating hyperplane and the sign of $w^{T}x-b$ can be used to decide the class in which a point $x$ falls.

To allow more flexibility the soft-margin SVM classifier is often used instead. It admits a violation of the large margin requirement (11.13) by a non-negative slack variable which is then penalized in the objective function.

$$\begin{array}{r}\begin{array}{lll}{\text{minimize}}_{b,w}& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m{\xi }_i& \\ \text{subject to}& y_i(w^T{x}_i-b)\ge 1-{\xi }_i& i=1,\dots ,m,\\ & {\xi }_i\ge 0& i=1,\dots ,m.\end{array}\end{array}$$

In matrix form we have

$$\begin{array}{r}\begin{array}{ll}{\text{minimize}}_{b,w,\xi }& \frac{1}{2}\Vert w{\Vert }^2+C{\mathbf{e}}^T\xi \\ \text{subject to}& y\star (Xw-b\mathbf{e})+\xi \ge \mathbf{e},\\ & \xi \ge 0.\end{array}\end{array}$$

where $\star$ denotes the component-wise product, and $\mathbf{e}$ a vector with all components equal to one. The constant $C\ge 0$ acts both as scaling factor and as weight. Varying $C$ yields different trade-offs between accuracy and robustness.

Implementing the matrix formulation of the soft-margin SVM in Fusion is very easy. We only need to cast the problem in conic form, which in this case involves converting the quadratic term of the objective function into a conic constraint:

(11.14)$$\begin{array}{r}\begin{array}{ll}{\text{minimize}}_{b,w,\xi ,t}& t+C{\mathbf{e}}^T\xi \\ \text{subject to}& \xi +y\star (Xw-b\mathbf{e})\ge \mathbf{e},\\ & (1,t,w)\in {\mathcal{Q}}_{\mathit{r}}^{n+2},\\ & \xi \ge 0.\end{array}\end{array}$$

where ${\mathcal{Q}}_{\mathit{r}}^{n+2}$ denotes a rotated cone of dimension $n+2$.

Fusion implementation

We now demonstrate how implement model (11.14). Let us assume that the training examples are stored in the rows of a matrix X, the labels in a vector y and that we have a set of weights C for which we want to train the model. The implementation in Fusion of our conic model starts declaring the model class:

    Model M = new Model("Primal SVM");

Then we proceed defining the variables :

      Variable w =  M.variable(n, Domain.unbounded());
      Variable t =  M.variable(1, Domain.unbounded());
      Variable b =  M.variable(1, Domain.unbounded());
      Variable xi = M.variable(m, Domain.greaterThan(0.));

The conic constraint is obtained by stacking the three values:

      M.constraint( Expr.vstack(1., t, w), Domain.inRotatedQCone());

Note how the dimension of the cone is deduced from the arguments. The relaxed classification constraints can be expressed using the built-in expressions available in Fusion. In particular:

1. element-wise multiplication $\star$ is performed with the Expr.mulElm function;

2. a vector whose entries are repetitions of $b$ is produced by Var.repeat.

The results is

      M.constraint(
        Expr.add( xi ,
                  Expr.mulElm( y,
                               Expr.sub( Expr.mul(X, w), Var.repeat(b, m) )
                             )
                ),
        Domain.greaterThan( 1. )
      );

Finally, the objective function is defined as

        M.objective( ObjectiveSense.Minimize, Expr.add( t, Expr.mul(c, Expr.sum(xi) ) ) );

To solve a sequence of problems with varying C we can simply iterate along those values changing the objective function:

      for (int i = 0; i < nc; i++) {
        double c = 500.0 * i;

        M.objective( ObjectiveSense.Minimize, Expr.add( t, Expr.mul(c, Expr.sum(xi) ) ) );
        M.solve();

        try {
          System.out.format("%4f | %8f", c, b.level()[0] );
          for (int j = 0; j < n; j++)
            System.out.format(" | %8f", w.level()[j] );

          System.out.print("\n");
        } catch (FusionException e) {}
      }
    }

Source code

Listing 11.8 The code implementing model (11.14) Click here to download.

    Model M = new Model("Primal SVM");
    try {
      System.out.format("Number of data    : %d\n", m);
      System.out.format("Number of features: %d\n", n);

      Variable w =  M.variable(n, Domain.unbounded());
      Variable t =  M.variable(1, Domain.unbounded());
      Variable b =  M.variable(1, Domain.unbounded());
      Variable xi = M.variable(m, Domain.greaterThan(0.));

      M.constraint(
        Expr.add( xi ,
                  Expr.mulElm( y,
                               Expr.sub( Expr.mul(X, w), Var.repeat(b, m) )
                             )
                ),
        Domain.greaterThan( 1. )
      );

      M.constraint( Expr.vstack(1., t, w), Domain.inRotatedQCone());

      System.out.println("   c   | b      | w");
      for (int i = 0; i < nc; i++) {
        double c = 500.0 * i;

        M.objective( ObjectiveSense.Minimize, Expr.add( t, Expr.mul(c, Expr.sum(xi) ) ) );
        M.solve();

        try {
          System.out.format("%4f | %8f", c, b.level()[0] );
          for (int j = 0; j < n; j++)
            System.out.format(" | %8f", w.level()[j] );

          System.out.print("\n");
        } catch (FusionException e) {}
      }
    }
    finally {
      M.dispose();
    }

Example

We generate a random dataset consisting of two groups of points, each from a Gaussian distribution in ${\mathbb{R}}^2$ with centres $(1.0,1.0)$ and $(-1.0,-1.0)$, respectively.

    Random gen = new Random(seed);

    int nump = gen.nextInt(m);
    int numm = m - nump;

    double [] y = new double[m];

    Arrays.fill(y, 0, nump, 1.);
    Arrays.fill(y, nump, m, -1.);

    double [][] X = new double[m][n];

    for (int i = 0; i < nump; i++)
      for (int j = 0; j < n; j++)
        X[i][j] = gen.nextGaussian() + 1.;

    for (int i = nump; i < m; i++)
      for (int j = 0; j < n; j++)
        X[i][j] = gen.nextGaussian() - 1.;

With standard deviation $\sigma =1/2$ we obtain a separable instance of the problem with a solution shown in Fig. 11.2.

Fig. 11.2 Separating hyperplane for two clusters of points.

For $\sigma =1$ the two groups are not linearly separable and the we obtain the optimal hyperplane as in Fig. 11.3.

Fig. 11.3 Soft separating hyperplane for two groups of points.