Support Vector Machine

Our main focus in this course is to study deep learning techniques. However, we take a slight deviation in this chapter to briefly discuss the core idea behind another similar ML method called the Support Vector Machines (SVMs). In particular, we highlight the geometric foundations of SVMs, which provide a useful perspective for comparing the learning methodologies of SVMs and artificial neural networks.

We demonstrate the SVM method for linearly separable datasets in the first Section «Click Here», where we derive primal optimization problems whose solution is the weight vector for the optimal separating hyperplane. We also derive the dual optimization problem and discuss its advantages when compared to primal problem. As we did in the previous chapter, we then go beyond linearly separable datasets in the last Section «Click Here», where we discuss kernel tricks to construct SVM for a dataset which is nonlinearly separable.

Linearly Separable Dataset

In the preceding section, we studied a perceptron, which is a basic model in deep learning architectures. Recall that the perceptron algorithm updates its weight vector based on misclassified examples, and the algorithm converges if and only if the dataset is linearly separable. However, when multiple separating hyperplanes exist, the perceptron may converge to any one (see Figure-(a) below) of them without regard to its generalization ability.

On the other hand, SVMs are classification methods in the broader field of machine learning that also seek a linear decision boundary (possibly in a transformed feature space) but are based on a different learning principle from the perceptron. Rather than updating the weight vector based on individual misclassifications, an SVM selects the one that maximizes the margin between the two classes among all possible separating hyperplanes (see Figure-(b) below). This margin-based criterion leads to an optimal separating hyperplane, called the SVM solution, with a relatively strong generalization ability.

In this subsection, we briefly discuss the learning procedure of SVMs for linearly separable dataset, while postponing the treatment of the nonlinearly separable case to the next subsection.

Hard and Soft Margins

Let us start with the definition of the margin between two class of examples in a given linearly separable dataset.

An illustration of a linearly separable dataset where red dots represents labels with value \(-1\) and green dots corresponds to labels with value +1. (a) Each dotted line represents a separating lines (b) Solid line represents the optimal separating line (the SVM solution), and the dotted lines indicate lower and upper margins.

Clearly the margin of a given hyperplane is the distance between the hyperplane and the nearest example in \(\mathcal{D}\). The SVM solution is the separating hyperplane that maximizes the margin as illustrated in the above Figure-(b).

A separating hyperplane (also referred to as decision boundary) classifies all the examples of \(\mathcal{D}\) correctly. This is equivalent to the condition that

The above conditions can be combined to obtain the following lemma.

The following lemma is a consequence of the Definition «Click Here» on margin, and the condition given in the above lemma.

In view of the above lemma, the SVM solution of a linearly separable dataset can be obtained as the optimal separating hyperplane of the dataset.

The optimization problem (3.2) can be expressed equivalently as a convex optimization problem in the weight vector \(\boldsymbol{w}\), which is strictly convex and therefore admits a unique global solution for \(\boldsymbol{w}.\)

Loss-function form

We now present the equivalence between the quadratic optimization problem (3.6) and an unconstrained optimization problem that involves a loss function based on the hinge loss.

We can eliminate the slack variables \(\boldsymbol{\xi}\)​ and write the constraints in (3.6) directly in terms of a hinge loss as

where \(h(\boldsymbol{x}) = \langle \boldsymbol{w}, \boldsymbol{x} \rangle - b\) and \(y\in \{-1, 1\}\). Then the soft margin SVM objective (3.6) can be written as

where

is the empirical risk based on the hinge loss. The first term in (3.7) is called the regularizer.

Subgradient Descent Algorithm

In this subsection, we outline an algorithm based on the subgradient descent method for the soft margin problem with hinge loss given by (3.7)-(3.8).

Let us define the cost function as

where \(\lambda\) is the regularization parameter, and the hinge loss \(\ell_{\text{hinge}}\) is given by

The aim is to compute the minimizer of the cost function. That is, to find

Since both the regularizer and the empirical risk are convex with respect to \((b,\boldsymbol{w})\), the cost function is convex. Moreover, since the regularizer is strictly convex in \(\boldsymbol{w}\), for \(\lambda>0\), the optimal weight vector \(\boldsymbol{w}^*\) is unique.

We use the gradient descent method to compute the global minimizer of the cost function. Since the hinge loss function is not differentiable, we use subgradients and the resulting version of the gradient descent method is called the subgradient descent method. The subgradient of the hinge loss function with respect to \(\boldsymbol{w}\) is given by

and the subgradient with respect to \(b\) is given by

Therefore, the subgradient of the cost function with respect to \(\boldsymbol{w}\) and \(b\) are given, respectively, by

The subgradient descent update rule for minimizing the primal soft margin SVM with hinge-loss objective is defined as

where \(0<\eta<1\) is the learning rate.

Dual Optimazation Problem

The SVM problems (3.3) and (3.6) are referred to as the primal optimization problems. These are convex optimization problems with quadratic objective functions and linear constraints. An alternative formulation is derived from the primal problem which is referred to as the dual optimization problem which are equivalent to the original problem.

A convex dual problem can be derived by forming the Lagrangian of the primal problem as

where the first two terms correspond to the objective function in (3.6), and the expressions inside the brackets correspond to the inequality constraints enforced using the parameter vectors \(\boldsymbol{\alpha}\ge \boldsymbol{0}\) and \(\boldsymbol{\beta}\ge \boldsymbol{0}\), called the Lagrange multipliers.

The gradient of \(\mathcal{L}\) with respect to \(\boldsymbol{w}\) is given by

Also, differentiating \(\mathcal{L}\) with respect to the bias \(b\) and \(\xi_k\), for \(k=1,2,\ldots, N\), gives

In order to obtain the extremum of the Lagrangian, we equate the above three expressions to zero. First, equating gradient vector in (3.14) to zero, we obtain

which shows that the optimal weight vector of the primal problem (3.6) can be obtained as a linear combination of the input vectors where the coefficients are such that

from stationarity of the Lagrangian with respect to \(b\). Note that only those vectors \(\boldsymbol{x}_k\) for which \(\alpha_k>0\), for \(k=1,2,\ldots, N\) contribute to the weight \(\boldsymbol{w}\) and they are called support vectors.

Substituting (3.17) and (3.18) into (3.6), we get

Equating (3.16) to zero, we obtain

Thus, we have proved

Further, since \(\boldsymbol{\beta}\ge \boldsymbol{0}\), we see that \(\alpha_k\le C\) for each \(k=1,2,\ldots, N\).

The following constrained optimization problem is called the Lagrange dual problem associated to the primal problem (3.6):

Using (3.19), the Lagrange dual problem can also be written as

The above dual problem gives \(\boldsymbol{\alpha}^*\) which can be substituted in (3.17) to obtain the weight vector \(\boldsymbol{w}^*\). To obtain an approximation to \(b^*\), compute \(|y_k - \boldsymbol{w}^*\cdot \boldsymbol{x}_k|\) for all support vectors \(\boldsymbol{x}_k\) from the dataset and take the median value as the value of \(b^*\).

These problems have been extensively studied in the optimization literature, and various computational algorithms are available. We omit further discussion of this topic, as our primary focus is on deep learning techniques. SVM is introduced here mainly for comparison, to highlight an alternative classical approach to classification problems within the broader field of machine learning.

Nonlinearly Separable Datasets

So far, we have formulated the SVM problems to classify a given dataset. If the dataset is linearly separable, then hard margin SVM can be efficiently used. On the other hand, the soft margin SVM allows some violations of the margin constraints by introducing slack variables. In this way, the soft margin SVM can handle nonlinearly separable dataset in the given input space. However, this method finally obtains a hyperplane as the decision boundary, and hence is a linear classifier in the input space with a better tolerance to noise or overlap.

In the previous chapter, we discussed how mapping data into a higher-dimensional feature space can make a dataset linearly separable. In this section, we extend our discussion from the previous chapter on feature mapping and introduce the kernel method, which enables SVM to be a nonlinear classifier.

Kernel Method: Implicit Feature Mapping

At the end of previous chapter, we have seen that through a suitable feature map, one can transform the dataset from the input space to the feature space where the dataset is linearly separable. However, explicitly constructing such a map is often impossible, especially when the dataset is large or when the separation requires a highly nonlinear decision boundary.

Kernel methods overcome this difficulty by introducing a kernel function that compute inner products in a higher dimensional feature space implicitly. This approach is known as the kernel trick. In this subsection, we outline the idea of kernel trick without getting into technical details.

First, let us give the definition of a kernel function in the context of machine learning.

The following results gather some important properties of kernel functions.

Observe that the dual problem (3.20) depends on the input vectors only through the inner products appearing in the objective function. Thus, one can implicitly work in a feature space by replacing the inner product of two input vectors with a kernel function based on a feature map \(\phi\). This procedure is often referred to as the kernel trick. Let us make the idea of kernel trick more precise.

Kernel Trick

Thus, the hyperplane as the decision boundary in the input space is now transformed into a nonlinear function in the feature space given by

where \(\alpha_k\), for \(k=1,2,\ldots, N\), are obtained by solving the dual problem (3.20), but the objective function is now posed in the feature space as

The kernel trick is to replace the inner product in the above objective function with a kernel function \(\text{𝕜}(\boldsymbol{x_j}, \boldsymbol{x}_k)\). Hence, the dual problem under consideration is

The kernel trick enables us to use certain kernels without explicitly defining the corresponding feature map.

Let us illustrate the kernel trick by use the quadratic polynomial kernel to train a hard margin SVM for the XOR function.