Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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)
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.
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.
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.
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.
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:
With $n=2$, one can represent the SVM's decision boundaries as follows:
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$.
The SVM aims at satisfying two requirements:
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}$.
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}$$
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})
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.
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.
Some interesting QAs on SVMs:
Other links:
References:
The technique is predicated upon drawing a decision boundary line leaving as ample a margin to the first positive and negative examples as possible:
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$:
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.$
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:
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:
Minimise $\lVert w\rVert^2$ with the constraint:
$y_i(\mathbf w \cdot \mathbf x_i + b )-1=0$
Since we want to minimise 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.$
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.
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}
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)$$
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}
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:
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.
