# 10.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 \(\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,\ldots,x_m\in \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

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

If a solution exists, \(w,b\) define the separating hyperplane and the sign of \(w^Tx -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 (1) by a non-negative slack variable which is then penalized in the objective function.

In matrix form we have

where \(\star\) denotes the component-wise product, and \(\mathbf{e}\) a vector with all components equal to one. The constant \(C\geq 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:

where \(\Qr^{n+2}\) denotes a rotated cone of dimension \(n+2\).

*Fusion* implementation

We now demonstrate how implement model (2). 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.0) );
```

The conic constraint is obtained by stacking the three values:

```
M.Constraint( Expr.Vstack(1.0, 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:

- element-wise multiplication \(\star\) is performed with the
`Expr.MulElm`

function; - a vector whose entries are repetitions of \(b\) is produced by
`Var.Repeat`

.

The results is

```
M.Constraint( Expr.Add(Expr.MulElm( y, Expr.Sub( Expr.Mul(X, w), Var.Repeat(b, m) ) ), xi ),
Domain.GreaterThan( 1.0 ) );
```

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:

```
Console.WriteLine(" 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();
Console.Write("{0} | {1} |", c, b.Level()[0] );
for (int j = 0; j < n; j++)
Console.Write(" {0}", w.Level()[j] );
Console.WriteLine();
}
```

Source code

```
Model M = new Model("Primal SVM");
try {
Console.WriteLine("Number of data : {0}\n", m);
Console.WriteLine("Number of features: {0}\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.0) );
M.Constraint( Expr.Add(Expr.MulElm( y, Expr.Sub( Expr.Mul(X, w), Var.Repeat(b, m) ) ), xi ),
Domain.GreaterThan( 1.0 ) );
M.Constraint( Expr.Vstack(1.0, t, w) , Domain.InRotatedQCone());
M.AcceptedSolutionStatus(AccSolutionStatus.NearOptimal);
Console.WriteLine(" 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();
Console.Write("{0} | {1} |", c, b.Level()[0] );
for (int j = 0; j < n; j++)
Console.Write(" {0}", w.Level()[j] );
Console.WriteLine();
}
}
finally {
M.Dispose();
}
```

Example

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

```
int nc = 10;
int m = 50;
int n = 3;
int seed = 1;
double variance = 1.0;
double mean = 1.0;
Random gen = new Random(seed);
int nump = gen.Next(m);
double [] y = new double[m];
for (int i = 0; i < nump; i++) y[i] = 1.0;
for (int i = nump; i < m; i++) y[i] = -1.0;
double [,] X = new double[m, n];
for (int i = 0; i < nump; i++)
for (int j = 0; j < n; j++) {
double xx = Math.Sqrt( -2.0 * Math.Log(gen.NextDouble()) );
double yy = Math.Sin( 2.0 * Math.PI * gen.NextDouble() );
X[i, j] = (xx * yy) * variance + mean;
}
```

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

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