Extensive Guide to Support Vector Machines

What are support vector machines?

Support vector machines (SVMs) are supervised machine learning models. They are the most prominent member of the class of kernel methods. SVMs can be used both for classification and regression. The original SVM proposed in 1963 is a simple binary linear classifier. What does this mean?

Assume we are given a dataset \(D = \big \{ \mathbf{x}_n, y_n \big \}_{n=1}^N\), where \(\pmb{x}_n \in \mathbb{R}^D\) and labels \(y_n \in \{-1, +1 \}\). A linear (hard-margin) SVM separates the two classes using a (\(D-1\) dimensional) hyperplane.

Special to SVMs is that they use not any hyperplane but the one that maximizes the distance between itself and the two sets of datapoints. Such a hyperplane is called maximum-margin hyperplane:

In case you have never heard the term margin: the margin describes the distance between the hyperplane and the closest examples in the dataset.

Two types of SVMs exist: primals SVMs and dual SVMs. Although most research in the past looked into dual SVMs both can be used to perform non-linear classification. Therefore, we will look at both approaches and compare them in the end.

Primal approach – Hard-margin SVM

When training an SVM our goal is to find the hyperplane that maximizes the margin between the two sets of points. This hyperplane is fully defined by the points closest to the margin, which are also called support vectors.

The equation of a hyperplane is given by \(\langle \pmb{w}, \pmb{x} \rangle + b = 0\) , where \(\langle \cdot, \cdot \rangle\) denotes the inner product and \(\mathbf {w}\) is the normal vector to the hyperplane. If an example \(\pmb{x}_i\) lies on the right side of the hyperplane (that is, it has a positive label) we have \(\langle \pmb{w}, \pmb{x}_i \rangle + b \gt 0\). If instead \(\pmb{x}_i\) lies on the left side (= negative label) we have \(\langle \pmb{w}, \pmb{x}_i \rangle + b \lt 0\).

The support vectors lie exactly on the margin and the optimal separating hyperplane should have the same distance from all support vectors. In this sense the maximum margin hyperplane lies between two separating hyperplanes that are determined by the support vectors:

Goal 1

When deriving a formal equation for the maximum margin hyperplane we assume that the two delimiting hyperplanes are given by:
$$\langle \pmb{w}, \pmb{x}_{+} \rangle + b = +1$$
$$\langle \pmb{w}, \pmb{x}_{-} \rangle + b = -1$$

In other words: we want our datapoints to lie at least a distance of 1 away from the decision hyperplane into both directions. To be more precise: for our positive examples (those with label \(y_n = +1\)) we want the following to hold: \(\langle \pmb{w}, \pmb{x}_n \rangle + b \ge +1\).

For our negative examples (those with label \(y_n = -1\)) we want the opposite: \(\langle \pmb{w}, \pmb{x}_n \rangle + b \le -1\). This can be combined into a single equation: \(y_n(\langle \pmb{w}, \pmb{x}_n \rangle + b) \ge 1\). This is our first goal: we want a decision boundary that classifies our training examples correctly.

Goal 2

Our second goal is to maximize the margin of this decision boundary. The margin is given by \(\frac{1}{\pmb{w}}\). If you would like to understand where this value is coming from take a look at the section „(Optional) Deriving the margin equation“ below.

Our goal to maximize the margin can be expressed as follows:
$$ \max_{\pmb{w}, b} \frac{1}{\Vert \pmb{w} \Vert}$$

Instead of maximizing \(\frac{1}{\Vert \pmb{w} \Vert}\) we can instead minimize \(\frac{1}{2} \Vert \pmb{w} \Vert^2\). This simplifies the computation of the gradient.

Combined goal

Combining goal one and two yields the following objective function:
$$
\min_{\pmb{w}, b} \frac{1}{2} \Vert \pmb{w} \Vert^2 \\
\text{subject to: } y_n(\langle \pmb{w}, \pmb{x}_n \rangle + b) \ge 1 \text{ for all } n = 1, …, N
$$

In words: we want to find the values for \(\pmb{w}\) and \(b\) that maximize the margin while classifying all training examples correctly. This approach is called the hard-margin support vector machine. „Hard“ because it does not allow for violations of the margin requirement (= no points are allowed to be within the margin).

(Optional) Deriving the margin equation

We can derive the width of the margin in several ways (see sections 12.2.1-12.2.2 of the Mathematics for Machine Learning book). Personally, I found the explanation of this MIT lecture on SVMs easiest to understand.

The derivation of the margin is based on the assumptions that we have already noted above:
$$\langle \pmb{w}, \pmb{x}_{+} \rangle + b = +1$$
$$\langle \pmb{w}, \pmb{x}_{-} \rangle + b = -1$$

Including the label of each example we can rewrite this as
$$y_i (\langle \pmb{w}, \pmb{x}_{i} \rangle + b) -1 = 0$$

Let’s say we have a positive example \(\pmb{x}_{+}\) that lies on the right delimiting hyperplane and a negative example \(\pmb{x}_{-}\) that lies on the left delimiting hyperplane. The distance between these two vectors is given by (\(\pmb{x}_{+} – \pmb{x}_{-})\). We want to compute the orthogonal projection of the vector onto the line that is perpendicular to the decision hyperplane. This would give us the width between the two delimiting hyperplanes. We can compute this by multiplying the vector (\(\pmb{x}_{+} – \pmb{x}_{-})\) with a vector that is perpendicular to the hyperplane. We know that the vector \(\pmb{w}\) is perpendicular to the decision hyperplane. So we can compute the margin by multiplying \((\pmb{x}_{+} – \pmb{x}_{-})\) with the vector \(\pmb{w}\) where the latter is divided by the scale \(||\pmb{w}||\) to make it a unit vector.

$$
\begin{align}
\text{width} &= (\pmb{x}_{+} – \pmb{x}_{-}) \cdot \frac{\pmb{w}}{||\pmb{w}||} \\
&= \frac{\pmb{x}_{+} \cdot \pmb{w}}{||\pmb{w}||} – \frac{\pmb{x}_{-} \cdot \pmb{w}}{||\pmb{w}||}
\end{align}
$$

For the positive example \(\pmb{x}_{+}\) we have \(y_+ = +1\) and therefore \((\langle \pmb{w}, \pmb{x}_{+} \rangle = 1 – b\). For the negative example \(\pmb{x}_{-}\) we have \(y_- = -1\) and therefore \(– (\langle \pmb{w}, \pmb{x}_{-} \rangle) = 1 + b\):

$$
\begin{align}
\text{width} &= (\pmb{x}_{+} – \pmb{x}_{-}) \cdot \frac{\pmb{w}}{||\pmb{w}||} \\
&= \frac{\pmb{x}_{+} \cdot \pmb{w}}{||\pmb{w}||} – \frac{\pmb{x}_{-} \cdot \pmb{w}}{||\pmb{w}||} \\
&= \frac{(1 – b) + (1 + b)}{||\pmb{w}||}\\
&= \frac{2}{||\pmb{w}||}\\
\end{align}
$$

We conclude that the width between the two delimiting hyperplanes equals \(\frac{2}{\pmb{w}}\). And therefore, that the distance between the decision hyperplane and each delimiting hyperplane is \(\frac{1}{\pmb{w}}\).

Primal approach – Soft-margin SVM

In most real-world situations the available data is not linearly separable. Even if it is, we might prefer a solution which separates the data well while ignoring some noisy examples and outliers. This motivated an extension of the original hard-margin SVM called soft-margin SVM.

A soft-margin SVM allows for violations of the margin requirement (= classification errors). In other words: not all training examples need to be perfectly classified. They might fall within the margin or even lie on the wrong side of the decision hyperplane. However, such violations are not for free. We pay a cost for each violation, where the value of the cost depends on how far the example is from meeting the margin requirement.

To implement this, we introduce so called slack variables \(\xi_n\). Each training example \((\pmb{x}_n, y_n)\) is assigned a slack variable \(\xi_n \ge 0\). The slack variable allows this example to be within the margin or even on the wrong side of the decision hyperplane:

• If \(\xi_n = 0\) the training example \((\pmb{x}_n, y_n)\) lies exactly on the margin
• \(0 \lt \xi_n \lt 1\) the training example lies within the margin but on the correct side of the decision hyperplane
• \(\xi_n \ge 1\) the training example lies on the wrong side of the decision hyperplane

We extend our objective function to include the slack variables as follows:
$$ \min_{\pmb{w}, b, \pmb{\xi}} \frac{1}{2} \Vert \pmb{w} \Vert^2 + C \sum_{n=1}^N \xi_n $$

$$ \text{subject to:} $$

$$ y_n(\langle \pmb{w}, \pmb{x}_n \rangle + b) \ge 1 – \xi_n $$$$ \xi_i \ge 0 \text{ for all } n = 1, …, N $$

The parameter \(C\) is a regularization term that controls the trade-off between maximizing the margin and minimizing the training error (which in turn means classifying all training examples correctly). If the value of \(C\) is small, we care more about maximizing the margin than classifying all points correctly. If the value of \(C\) is large, we care more about classifying all points correctly than maximizing the margin.

Solving the primal optimization problem

Theoretically, the primal SVM can be solved in multiple ways. The most well known way is to use the hinge loss function together with subgradient descent.

Hinge loss function

The hinge loss function, given the true target \(y \in \{-1, +1\}\) and the prediction \(f(\pmb{x}) = \langle\pmb{w}, \pmb{x}\rangle+b\), is computed as follows:

$$\ell(t)=\max \{0,1-t\} \quad \text{where} \quad t=y \cdot f(\pmb{x})= y \cdot \big(\langle\pmb{w}, \pmb{x}\rangle+b\big)$$

Let’s understand the output of this loss function with a few examples:

• If a training example has label \(y = -1\) and the prediction is on the correct side of the marghin (that is, \(f(\pmb{x}) \le -1\)), the value of \(t\) is larger or equal to \(+1\). Therefore, the hinge loss will be zero (\(\ell(t) = 0\))
• The same holds if a training example has label \(y = 1\) and the prediction is on the correct side of the margin (that is, \(f(\pmb{x}) \ge 1\))
• If a training example (\(y = 1\)) is on the correct side of the decision hyperplane but lies within the margin (that is, \(0 \lt f(\pmb{x}) \lt 1\)) the hinge loss will output a positive value.
• If a training example (\(y = 1\)) is on the wrong side of the decision hyperplane (that is, \(f(\pmb{x}) \lt 0\)), the hinge loss returns an even larger value. This value increases linearly with the distance from the decision hyperplane

Updated objective function

Using the hinge loss, we can reformulate the optimization problem of the primal soft-margin SVM. Given a dataset \(D = \big \{ \mathbf{x}_n, y_n \big \}_{n=1}^N\) we would like to minimize the total loss which is now given by:

$$
\min _{\pmb{w}, b} \frac{1}{2}\|\pmb{w}\|^{2} + C \sum_{n=1}^{N} \max \left\{0,1-y_{n}\left(\left\langle\pmb{w}, \pmb{x}_{n}\right\rangle+b\right)\right\}
$$

If you would like to understand why this is equivalent to our previous formulation of the soft-margin SVM, please take a look at chapter 12.2.5 of the Mathematics for Machine Learning book.

[Optional] Three parts of the objective function

Our objective function can be divided into three distinct parts:

Part 1: \(\frac{1}{2}\|\pmb{w}\|^{2}\)

This part is also called the regularization term. It expresses a preference for solutions that separate the datapoints well, thereby maximizing the margin. In theory, we could replace this term by a different regularization term that expresses a different preference.

Part 2: \(\sum_{n=1}^{N} \max \left\{0,1-y_{n}\left(\left\langle\pmb{w}, \pmb{x}_{n}\right\rangle+b\right)\right\}\)

This part is also called the empirical loss. In our case it is the hinge loss which penalizes solutions that make mistakes when classifying the training examples. In theory, this term could be replaced with another loss function that expresses a different preference.

Part 3: The hyperparameter \(C\) that controls the tradeoff between a large margin and a small hinge loss.

Sub-gradient descent

The hinge loss function is not differentiable (namely at the point \(t=1\)). Therefore, we cannot compute the gradient right away. However, we can use a method called subgradient descent to solve our optimization problem. To simplify the derivation we will adapt two things:

1. We assume that the bias \(b\) is contained in our weight vector as the first entry \(w_0\), that is \(\pmb{w} = [b, w_1, …, w_D]\)
2. We divide the hinge loss by the number of samples

Our cost function is then given by:
$$
J(\pmb{w}) = \frac{1}{2}\|\pmb{w}\|^{2} + C \frac{1}{N} \sum_{n=1}^{N} \max \left\{0,1-y_{n}\left(\left\langle\pmb{w}, \pmb{x}_{n}\right\rangle\right)\right\}
$$

We will reformulate this to simplify computing the gradient:
$$
J(\pmb{w}) = \frac{1}{N} \sum_{n=1}^{N} \Big[ \frac{1}{2}\|\pmb{w}\|^{2} + C \max \left\{0,1-y_{n}\left(\left\langle\pmb{w}, \pmb{x}_{n}\right\rangle\right)\right\}\Big]
$$

The gradient is given by:
$$
\nabla_{w} J(\pmb{w}) = \frac{1}{N} \sum_{n=1}^N \left\{\begin{array}{ll}
\mathbf{w} & \text{if} \max \left(0,1-y_{n} \left(\langle \pmb{w}, \pmb{x}_{n} \rangle \right)\right)=0 \\
\mathbf{w}-C y_{n} \pmb{x}_{n} & \text { otherwise }
\end{array}\right.
$$

With this formula we can apply stochastic gradient descent to solve the optimization problem.

[Optional] Difference subgradient descent and gradient descent

The subgradient method allows us to minimize a non-differentiable convex function. Although looking similar to gradient descent the method has several important differences.

What is a subgradient?¶

A subgradient can be described as a generalization of gradients to non-differentiable functions. Informally, a sub-tangent at a point is any line that lies below the function at the point. The subgradient is the slope of this line. Formally, the subgradient of a convex function \(f\) at \(w_0\) is defined as all vectors \(g\) such that for any other point \(w\)

$$ f(w) – f(w_0) \ge g \cdot (w – w_0) $$

If \(f\) is differentiable at \(w_0\), the subgradient contains only one vector which equals the gradient \(\nabla f(w_0)\). If, however, \(f\) is not differentiable, there may be several values for \(g\) that satisfy this inequality. This is illustrated in the figure below.

Subgradient method

To minimize the objective function \(f\), the subgradient method uses the following update formula for iteration \(k+1\):

$$ w^{(k+1)} = w^{(k)} – \alpha_k g^{(k)}$$

Where \(g^{(k)}\) is any subgradient of \(f\) at \(w^{(k)}\) and \(\alpha_k\) is the \(k\)-th step size. Thus, at each iteration, we make a step into the direction of the negative subgradient. When \(f\) is differentiable, \(g^{(k)}\) equals the gradient \(\nabla f(x^{(k)})\) and the method reduces to the standard gradient descent method.

More details on the subgradient method can be found here.

Implementation primal approach

Toy dataset

To implement what we have learned about primal SVMs, we first have to generate a dataset. In the cell below we create a simple dataset with two features and labels +1 and -1. We further split the dataset into a test and train set.

SVM class definition

Next, we would like to implement an SVM class. We will use the knowledge we already acquired:

1. Our objective function using the hinge loss function is given by:
   $$
   J(\pmb{w}) = \frac{1}{2}\|\pmb{w}\|^{2} + C \frac{1}{N} \sum_{n=1}^{N} \max \left\{0,1-y_{n}\left(\left\langle\pmb{w}, \pmb{x}_{n}\right\rangle\right)\right\}
   $$
2. We can minimize this function by computing the gradient:
   $$
   \nabla_{w} J(\pmb{w}) = \frac{1}{N} \sum_{n=1}^N \left\{\begin{array}{ll}
   \mathbf{w} & \text{if} \max \left(0,1-y_{n} \left(\langle \pmb{w}, \pmb{x}_{n} \rangle \right)\right)=0 \\
   \mathbf{w}-C y_{n} \pmb{x}_{n} & \text { otherwise }
   \end{array}\right.
   $$
3. Given the gradient we use stochastic gradient descent to train our model
4. After training our model we can make predictions using the sign function

As mentioned previously, we will assume that the bias \(b\) is contained in our weight vector as the first entry \(w_0\), that is \(\pmb{w} = [b, w_1, …, w_D] = \pmb{w} = [w_0, w_1, …, w_D]\).

Training and testing an SVM

After defining our SVM class, we can train a model and test it on unseen examples.

5Visualizing the decision boundary

Given our trained model, we can visualize the decision boundary, as done below.