How does a Support Vector Machine (SVM) work, and what differentiates it from other linear classifiers, such as the Linear Perceptron, Linear Discriminant Analysis, or Logistic Regression? *

(* I'm thinking in terms of the underlying motivations for the algorithm, optimisation strategies, generalisation capabilities, and run-time complexity)

up vote 111 down vote accepted

Support vector machines focus only on the points that are the most difficult to tell apart, whereas other classifiers pay attention to all of the points.

The intuition behind the support vector machine approach is that if a classifier is good at the most challenging comparisons (the points in B and A that are closest to each other in Figure 2), then the classifier will be even better at the easy comparisons (comparing points in B and A that are far away from each other).

Perceptrons and other classifiers:

Perceptrons are built by taking one point at a time and adjusting the dividing line accordingly. As soon as all of the points are separated, the perceptron algorithm stops. But it could stop anywhere. Figure 1 shows that there are a bunch of different dividing lines that separate the data. The perceptron's stopping criteria is simple: "separate the points and stop improving the line when you get 100% separation". The perceptron is not explicitly told to find the best separating line. Logistic regression and linear discriminant models are built similarly to perceptrons.

The best dividing line maximizes the distance between the B points closest to A and the A points closest to B. It's not necessary to look at all of the points to do this. In fact, incorporating feedback from points that are far away can bump the line a little too far, as seen below.

enter image description here

Support Vector Machines:

Unlike other classifiers, the support vector machine is explicitly told to find the best separating line. How? The support vector machine searches for the closest points (Figure 2), which it calls the "support vectors" (the name "support vector machine" is due to the fact that points are like vectors and that the best line "depends on" or is "supported by" the closest points).

Once it has found the closest points, the SVM draws a line connecting them (see the line labeled 'w' in Figure 2). It draws this connecting line by doing vector subtraction (point A - point B). The support vector machine then declares the best separating line to be the line that bisects -- and is perpendicular to -- the connecting line.

The support vector machine is better because when you get a new sample (new points), you will have already made a line that keeps B and A as far away from each other as possible, and so it is less likely that one will spillover across the line into the other's territory.

enter image description here

I consider myself a visual learner, and I struggled with the intuition behind support vector machines for a long time. The paper called Duality and Geometry in SVM Classifiers finally helped me see the light; that's where I got the images from.

  • 3
    +1 from another visual learner ! For the reader, I would like to note that these boundaries evident in the figure above is based on a data set that has been transformed already. Not the raw data set. – Kingz Jul 29 '16 at 21:13
  • Reading svm for more then two years, today understood how seperation line is identified and few more things. Thanks for clean answer. – user123 Sep 22 '16 at 9:19

Ryan Zotti's answer explains the motivation behind the maximization of the decision boundaries, carlosdc's answer gives some similarities and differences with respect to other classifiers. I'll give in this answer a brief mathematical overview of how SVMs are trained and used.

Notations

In the following, scalars are denoted with italic lowercases (e.g., $y,\, b$), vectors with bold lowercases (e.g., $\mathbf{w},\, \mathbf{x}$), and matrices with italic uppercases (e.g., $W$). $\mathbf{w^T}$ is the transpose of $\mathbf{w}$, and $\|\mathbf{w}\| = \mathbf{w}^T\mathbf{w}$.

Let:

  • $\mathbf{x}$ be a feature vector (i.e., the input of the SVM). $\mathbf{x} \in \mathbb{R}^n$, where $n$ is the dimension of the feature vector.
  • $y$ be the class (i.e., the output of the SVM). $y \in \{ -1,1\}$, i.e. the classification task is binary.
  • $\mathbf{w}$ and $b$ be the parameters of the SVM: we need to learn them using the training set.
  • $(\mathbf{x}^{(i)}, y^{(i)})$ be the $i^ {\text {th}}$ sample in the dataset. Let's assume we have $N$ samples in the training set.

With $n=2$, one can represent the SVM's decision boundaries as follows:

enter image description here

The class $y$ is determined as follows:

$$ y^{(i)}=\left\{ \begin{array}{ll} -1 &\text{ if } \mathbf{w^T}\mathbf{x}^{(i)}+b \leq -1 \\ 1 &\text{ if } \mathbf{w^T}\mathbf{x}^{(i)}+b \ge 1 \\ \end{array} \right. $$

which can be more concisely written as $y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1$.

Goal

The SVM aims at satisfying two requirements:

  1. The SVM should maximize the distance between the two decision boundaries. Mathematically, this means we want to maximize the distance between the hyperplane defined by $\mathbf{w^T}\mathbf{x}+b = -1$ and the hyperplane defined by $\mathbf{w^T}\mathbf{x}+b = 1$. This distance is equal to $\frac{2}{\|\mathbf{w}\|}$. This means we want to solve $\underset{\mathbf{w}}{\operatorname{max}} \frac{2}{\|\mathbf{w}\|}$. Equivalently we want $\underset{\mathbf{w}}{\operatorname{min}} \frac{\|\mathbf{w}\|}{2}$.

  2. The SVM should also correctly classify all $\mathbf{x}^{(i)}$, which means $y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1, \forall i \in \{1,\dots,N\}$

Which leads us to the following quadratic optimization problem:

$$\begin{align} \min_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1 &\forall i \in \{1,\dots,N\} \end{align}$$

This is the hard-margin SVM, as this quadratic optimization problem admits a solution iff the data is linearly separable.

One can relax the constraints by introducing so-called slack variables $\xi^{(i)}$. Note that each sample of the training set has its own slack variable. This gives us the following quadratic optimization problem:

$$\begin{align} \min_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \xi^{(i)}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1 - \xi^{(i)},&\forall i \in \{1,\dots,N\} \\ \quad&\xi^{(i)}\ge0, &\forall i \in \{1,\dots,N\} \end{align}$$

This is the soft-margin SVM. $C$ is a hyperparameter called penalty of the error term. (What is the influence of C in SVMs with linear kernel? and Which search range for determining SVM optimal parameters?).

One can add even more flexibility by introducing a function $\phi$ that maps the original feature space to a higher dimensional feature space. This allows non-linear decision boundaries. The quadratic optimization problem becomes:

$$\begin{align} \min_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \xi^{(i)}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\phi \left(\mathbf{x}^{(i)}\right)+b) \ge 1 - \xi^{(i)},&\forall i \in \{1,\dots,N\} \\ \quad&\xi^{(i)}\ge0, &\forall i \in \{1,\dots,N\} \end{align}$$

Optimization

The quadratic optimization problem can be transformed into another optimization problem named the Lagrangian dual problem (the previous problem is called the primal):

$$\begin{align} \max_{\mathbf{\alpha}} \quad &\min_{\mathbf{w},b} \frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \alpha^{(i)} \left(1-\mathbf{w^T}\phi \left(\mathbf{x}^{(i)}\right)+b)\right), \\ s.t. \quad&0 \leq \alpha^{(i)} \leq C, &\forall i \in \{1,\dots,N\} \end{align}$$

This optimization problem can be simplified (by setting some gradients to $0$) to:

$$\begin{align} \max_{\mathbf{\alpha}} \quad & \sum_{i=1}^{N} \alpha^{(i)} - \sum_{i=1}^{N}\sum_{j=1}^{N} \left( y^{(i)}\alpha^{(i)}\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right) y^{(j)}\alpha^{(j)} \right), \\ s.t. \quad&0 \leq \alpha^{(i)} \leq C, &\forall i \in \{1,\dots,N\} \end{align}$$

$\mathbf{w}$ doesn't appear as $\mathbf{w}=\sum_{i =1}^{N}\alpha^{(i)}y^{(i)}\phi\left(x^{(i)}\right)$ (as stated by the representer theorem).

We therefore learn the $\alpha^{(i)}$ using the $(\mathbf{x}^{(i)}, y^{(i)})$ of the training set.

(FYI: Why bother with the dual problem when fitting SVM? short answer: faster computation + allows to use the kernel trick, though there exist some good methods to train SVM in the primal e.g. see {1})

Making a prediction

Once the $\alpha^{(i)}$ are learned, one can predict the class of a new sample with the feature vector $\mathbf{x}^{\text {test}}$ as follows:

\begin{align*} y^{\text {test}}&=\text {sign}\left(\mathbf{w^T}\phi\left(\mathbf{x}^{\text {test}}\right)+b\right) \\ &= \text {sign}\left(\sum_{i =1}^{N}\alpha^{(i)}y^{(i)}\phi\left(x^{(i)}\right)^T\phi\left(\mathbf{x}^{\text {test}}\right)+b \right) \end{align*}

The summation $\sum_{i =1}^{N}$ could seem overwhelming, since it means one has to sum over all the training samples, but the vast majority of $\alpha^{(i)}$ are $0$ (see Why are the Lagrange multipliers sparse for SVMs?) so in practice it isn't an issue. (note that one can construct special cases where all $\alpha^{{(i)}} > 0$.) $\alpha^{{(i)}}=0$ iff $x^{{(i)}}$ is a support vector. The illustration above has 3 support vectors.

Kernel trick

One can observe that the optimization problem uses the $\phi\left(\mathbf{x}^{(i)}\right)$ only in the inner product $\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right)$. The function that maps $\left(\mathbf{x}^{(i)},\mathbf{x}^{(j)}\right)$ to the inner product $\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right)$ is called a kernel, a.k.a. kernel function, often denoted by $k$.

One can choose $k$ so that the inner product is efficient to compute. This allows to use a potentially high feature space at a low computational cost. That is called the kernel trick. For a kernel function to be valid, i.e. usable with the kernel trick, it should satisfy two key properties. There exist many kernel functions to choose from. As a side note, the kernel trick may be applied to other machine learning models, in which case they are referred as kernelized.

Going further

Some interesting QAs on SVMs:

Other links:


References:

  • 2
    Hi Franck, many thanks for your answer. Would you mind to explain why vector $w$ is orthogonal to the hyperplane that SVM generates? And how did you calculate the distance between two decision boundaries to be equal to $\frac{2}{\lVert w \rVert}$ – tosik Jan 13 '17 at 13:17
  • 3
    In addition to this great answer, I want to recommend this video which walks through the mathematics behind SVM and especially clarifies the question @tosik commented youtube.com/watch?v=_PwhiWxHK8o – Nikolas Rieble Jan 16 '17 at 16:34
  • Very nice answer. Just one remark as to this part: $\alpha^{{(i)}}=0$ iff $x^{{(i)}}$ is a support vector. For classification, the summation is effectively over support vectors (i.e., $\alpha^{{(i)}} \ge 0$). – 989 Jul 26 at 15:15

I'm going to focus on the the similarities and differences it from other classifiers:

  • From a perceptron: SVM uses hinge loss and L2 regularization, the perceptron uses the perceptron loss and could use early stopping (or among other techniques) for regularization, there is really no regularization term in the perceptron. As it doesn't have an regularization term, the perceptron is bound to be overtrained, therefore the generalization capabilities can be arbitrarily bad. The optimization is done using stochastic gradient descent and is therefore very fast. On the positive side this paper shows that by doing early stopping with a slightly modified loss function the performance could be on par with an SVM.

  • From logistic regression: logistic regression uses logistic loss term and could use L1 or L2 regularization. You can think of logistic regression as the discriminative brother of the generative naive-Bayes.

  • From LDA: LDA can also be seen as a generative algorithm, it assumes that the probability density functions (p(x|y=0) and p(x|y=1) are normally distributed. This is ideal when the data is in fact normally distributed. It has however, the downside that "training" requires the inversion of a matrix that can be large (when you have many features). Under homocedasticity LDA becomes QDA which is Bayes optimal for normally distributed data. Meaning that if the assumptions are satisfied you really cannot do better than this.

At runtime (test time), once the model has been trained, the complexity of all these methods is the same, it is just a dot product between the hyperplane the training procedure found and the datapoint.

  • 1
    Since you seem very competent in SVM, let me ask you to clarify my doubt: once we found the best separating hyperplane, what do we use it for? We can define SVM as a method that, firstly, chooses the best hyperplane to correctly classify data points, and, secondly, it uses this hyperplane to sever new data points in the two classes. Right? (I've some doubts on the second part) – DavideChicco.it Apr 27 '12 at 16:16
  • 1
    @DavideChicco.it Yes, we can use the indicator function to classify new data, which is often the main purpose of the classifier. (Don't take my word for any of this though, I'm new to all of it). – keyser Sep 29 '14 at 14:05

The technique is predicated upon drawing a decision boundary line leaving as ample a margin to the first positive and negative examples as possible:

enter image description here

As in the illustration above, if we select an orthogonal vector such that $ \lVert w \rVert=1$ we can establish a decision criterion for any unknown example $\mathbf u$ to be catalogued as positive of the form:

$$ \color{blue}{\mathbf w} \cdot {\mathbf u} \geq C$$

corresponding to a value that would place the projection beyond the decision line in the middle of the street. Notice that $\color{blue}{\mathbf w} \cdot {\mathbf u} = {\mathbf u} \cdot \color{blue}{\mathbf w}$.

An equivalent condition for a positive sample would be:

$$\color{blue}{\mathbf w}\cdot \mathbf u + b \geq 0 \tag 1$$

with $C = - b.$

We need $b$ and $\color{blue}{\mathbf w}$ to have a decision rule, and to get there we need constraints.

First constraint we are going to impose is that for any positive sample $\mathbf x_+,$, $\color{blue}{\mathbf w}\cdot \mathbf x_+ + b \geq 1$; and for negative samples, $\color{blue}{\mathbf w}\cdot \mathbf x_- + b \leq -1$. In the division boundary or hyperplane (median) the value would be $0$, while the values at the gutters will be $1$ and $-1$:

enter image description here

The vector $\bf w$ is the weights vector, whereas $b$ is the bias.


To bring these two inequalities together, we can introduce the variable $y_i$ so that $y_i=+1$ for positive examples, and $y_i=-1$ if the examples are negative, and conclude

$$ y_i (x_i\cdot \color{blue}{\mathbf w} + b) -1\geq 0.$$

So we establish that this has to be greater than zero, but if the example is on the hyperplanes (the "gutters") that maximize the margin of separation between the decision hyperplane and the tips of the support vectors, in this case lines), then:

$$ y_i \,(x_i\cdot \color{blue}{\mathbf w} + b) -1 = 0\tag 2$$

Notice that this is equivalent to requiring that $y_i \,(x_i\cdot \color{blue}{\mathbf w} + b) = 1.$

enter image description here


Second constraint: the distance of the decision hyperplane to the tips of the support vectors will be maximized. In other words the margin of separation ("street") will be maximized:

enter image description here

Assuming a unit vector perpendicular to the decision boundary, $\mathbf w$, the dot product with the difference between two "bordering" plus and minus examples is the width of "the street":

$$ \text{width}= (x_+ \,{\bf -}\, x_-) \cdot \frac{w}{\lVert w \rVert}$$

On the equation above $x_+$ and $x_-$ are in the gutter (on hyperplanes maximizing the separation). Therefore, for the positive example: $ ({\mathbf x_i}\cdot \color{blue}{\mathbf w} + b) -1 = 0$, or $ {\mathbf x_+}\cdot \color{blue}{\mathbf w} = 1 - b$; and for the negative example: $ {\mathbf x_-}\cdot \color{blue}{\mathbf w} = -1 - b$. So, reformulating the width of the street:

$$\begin{align}\text{width}&=(x_+ \,{\bf -}\, x_-) \cdot \frac{w}{\lVert w \rVert}\\[1.5ex] &= \frac{x_+\cdot w \,{\bf -}\, x_-\cdot w}{\lVert w \rVert}\\[1.5ex] &=\frac{1-b-(-1-b)}{\lVert w \rVert}\\[1.5ex] &= \frac{2}{\lVert w \rVert}\tag 3 \end{align}$$

So now we just have to maximize the width of the street - i.e. maximize $ \frac{2}{\lVert w \rVert},$ minimize $\lVert w \rVert$, or minimize:

$$\frac{1}{2}\;\lVert w \rVert^2 \tag 4$$

which is mathematically convenient.


So we want to:

  1. Minimize $\lVert x\rVert^2$ with the constraint:

  2. $y_i(\mathbf w \cdot \mathbf x_i + b )-1=0$


Since we want to minimize this expression based on some constraints, we need a Lagrange multiplier (going back to equations 2 and 4):

$$ \mathscr{L} = \frac{1}{2} \lVert \mathbf w \rVert^2 - \sum \lambda_i \Big[y_i \, \left( \mathbf x_i\cdot \color{blue}{\mathbf w} + b \right) -1\Big]\tag 5$$

Differentiating,

$$ \frac{\partial \mathscr{L}}{\partial \color{blue}{\mathbf w} }= \color{blue}{\mathbf w} - \sum \lambda_i \; y_i \; \mathbf x_i = 0$$.

Therefore,

$$\color{blue}{\mathbf w} = \sum \lambda_i \; y_i \; \mathbf x_i\tag 6$$

And differentiating with respect to $b:$

$$ \frac{\partial \mathscr{L}}{\partial b}=-\sum \lambda_i y_i = 0,$$

which means that we have a zero sum product of multipliers and labels:

$$ \sum \lambda_i \, y_i = 0\tag 7$$

Pluging equation Eq (6) back into Eq (5),

$$ \mathscr{L} = \frac{1}{2} \color{purple}{\left(\sum \lambda_i y_i \mathbf x_i \right) \,\left(\sum \lambda_j y_j \mathbf x_j \right)}- \color{green}{\left(\sum \lambda_i y_i \mathbf x_i\right)\cdot \left(\sum \lambda_j y_j \mathbf x_j \right)} - \sum \lambda_i y_i b +\sum \lambda_i$$

The penultimate term is zero as per equation Eq (7).

Therefore,

$$ \mathscr{L} = \sum \lambda_i - \frac{1}{2}\displaystyle \sum_i \sum_j \lambda_i \lambda_j\,\, y_i y_j \,\, \mathbf x_i \cdot \mathbf x_j\tag 8$$

Eq (8) being the final Lagrangian.

Hence, the optimization depends on the dot product of pairs of examples.

Going back to the "decision rule" in Eq (1) above, and using Eq (6):

$$ \sum\; \lambda_i \; y_i \; \mathbf x_i\cdot \mathbf u + b \geq 0\tag 9$$

will be the final decision rule for a new vector $\mathbf u.$

  • Nothing original... Just my own notes at a more entry level. Basically from this video from MIT with my own illustrations. For errors, please let me know. For insightful answers, and further details go to the expert level (Franck's post and others). – Antoni Parellada Feb 5 '17 at 16:41
  • And how do I compute b? – mike Nov 30 '17 at 9:32
  • 1
    @mike $b= y_s -\displaystyle \sum_{m\in S} \alpha_m y_m \mathbf{x}_m\cdot \mathbf {x}_s$ with $S$ being the set of indices of the support vectors $(\alpha_i > 0).$ You can find it here. – Antoni Parellada Dec 1 '17 at 12:47
  • @AntoniParellada amazing answer Antoni thanks a lot - but aren't you missing a part on the Dual problem and KTT conditions ? – Xavier Bourret Sicotte Jun 28 at 13:20
  • @XavierBourretSicotte I won't be able to work on it for a while. Please consider writing an alternative answer touching on these issues, and if you do, please let me know so I am aware of it, and can upvote it. – Antoni Parellada Jun 28 at 13:27

Some comments on Duality and KTT conditions

Primal problem

Picking up from @Antoni's post in between equations $(4)$ and $(5)$, recall that our original, or primal, optimization problem is of the form:

\begin{aligned} \min_{w, b} f(w,b) & = \min_{w, b} \ \frac{1}{2} ||w||^2 \\ s.t. \ \ g_i(w,b) &= - y^{(i)} (w^T x^{(i)} + b) + 1 = 0 \end{aligned}

Lagrange method

The method of Lagrange multipliers allows us to turn a constrained optimization problem into an unconstrained one of the form:

$$\mathcal{L}(w, b, \alpha) = \frac{1}{2} ||w||^2 - \sum_i^m \alpha_i [y^{(i)} (w^T x^{(i)} + b) - 1]$$

Where $\mathcal{L}(w, b, \alpha)$ is called the Lagrangian and $\alpha_i$ are called the Lagrangian multipliers.

Our primal optimization problem with the Lagrangian becomes the following: (note that the use of $min$, $max$ is not the most rigorous as we should also be using $\inf$ and $\sup$ here...)

$$ \min_{w,b} \left( \max_\alpha \mathcal{L}(w, b, \alpha)\right)$$

Dual problem

What @Antoni and Prof. Patrick Winston have done in their derivation is assume that the optimization function and the constraints meet some technical conditions such that we can do the following:

$$ \min_{w,b} \left( \max_\alpha \mathcal{L}(w, b, \alpha)\right) = \max_\alpha \left( \min_{w,b} \mathcal{L}(w, b, \alpha)\right)$$

This allows us to take the partial derivatives of $\mathcal{L}(w, b, \alpha)$ with respect to $w$ and $b$, equate to zero and then plug the results back into the original equation of the Lagrangian, hence generating an equivalent dual optimization problem of the form

\begin{aligned} &\max_{\alpha} \min_{w,b} \mathcal{L}(w,b,\alpha) \\ & \max_{\alpha} \sum_i^m \alpha_i - \frac{1}{2} \sum_{i,j}^m y^{(i)}y^{(j)} \alpha_i \alpha_j <x^{(i)} x^{(j)}> \\ & s.t. \ \alpha_i \geq 0 \\ & s.t. \ \sum_i^m \alpha_i y^{(i)} = 0 \end{aligned}

Duality and KTT

Without going into excessive mathematical technicalities, these conditions are a combination of the Duality and the Karush Kuhn Tucker (KTT) conditions and allow us to solve the dual problem instead of the primal one, while ensuring that the optimal solution is the same. In our case the conditions are the following:

  • The primal objective and inequality constraint functions must be convex
  • The equality constraint function must be affine
  • The constraints must be strictly feasible

Then there exists $w^*, \alpha^*$ which are solutions to the primal and dual problems. Moreover, the parameters $w^*, \alpha^*$ satisfy the KTT conditions below:

\begin{aligned} &\frac{\partial}{\partial w_i} \mathcal{L}(w^*, \alpha^*, \beta^*) = 0 &(A) \\ &\frac{\partial}{\partial \beta_i} \mathcal{L}(w^*, \alpha^*, \beta^*) = 0 &(B) \\ &\alpha_i^* g_i(w^*) = 0 &(C) \\ &g_i(w^*) \leq 0 &(D) \\ &\alpha_i^* \geq 0 &(E) \end{aligned}

Moreover, if some $w^*, \alpha^*$ satisfy the KTT solutions then they are also solution to the primal and dual problem.

Equation $(C)$ above is of particular importance and is called the dual complementarity condition. It implies that if $\alpha_i^* > 0$ then $g_i(w^*) = 0$ which means that the constraint $g_i(w) \leq 0$ is active, i.e. it holds with equality rather than inequality. This is the explanation behind equation $(2)$ in Antoni's derivation where the inequality constraint is turned into an equality constraint.

A intuitive but informal diagram

enter image description here

Sources

  • 2
    Thank you very much. I read it quickly, and get back to it later with more time, but it sounds great, and touches on missing points in my answer. – Antoni Parellada Jun 28 at 15:55

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.