Support Vector Machines

Abstract

Recall that algorithms like the perceptron look for a separating hyperplane. However, there are many separating hyperplanes and none of them are unique. Intuitively, for an optimal answer, you want an algorithm that finds a hyperplane that maximizes the margin between different classes so that it can perform better on new data. Support Vector Machines (SVM) accomplishes this and finds a unique hyperplane by solving the *primal* and *dual* problem. SVMs can also be extended to classify non-linearly separable data by using *soft margin* classification and implicitly mapping inputs into high-dimensional feature spaces to classify them easier using the *kernel trick*.

Once Upon A Time

You’re Naruto Uzumaki (a ninja). It’s you and your team’s job to get an important person to other side of the land, *safely* and as *comfortably* as possible. There is an army of Hidden Mist ninjas on the right and an army of Sand ninjas on the left trying to kill the important person. In addition to making it to the other side of the land, the important person also has a personal goal of predicting whether a ninja is a Hidden Mist ninja or a Sand ninja.

In order for you to protect him, you use your jutsu (magic powers) to set up 2 straight rock barriers on your left and right, between the important person and the 2 armies. There are many ways to do this, as you can see:

But you want the important person to be safe, *and* comfortable. In order to do this, you must give him the most space possible to walk. This is accomplished by *maximizing the margin* between the the Hidden Mist ninjas and the Sand ninjas, allowing the important person to walk exactly in the middle of the 2 barriers.

So, naruto uses his jutsu to build two parallel rock barriers, making the margin as big as possible. The first wall will be placed on the left, stopping the Hidden Mist, and the and the second wall will be placed on the right, stopping the Sand. The Hidden Mist and Sand ninjas that the respective walls made contact with are known as *support vectors*.

The important person now walks safely to his destination, dead in the center of the two walls. His path of walking is known as the *hyperplane*. Any *new* ninja to the right of his walking path, he predicts will be a Hidden Mist ninja, whether they are within the walls or not. And the same goes for the left and the Sand ninja. However, you are extremely confident with your prediction if a new ninja appears on the other side of the walls (support vectors).

There are also cases where a few ninjas are ruthless and are closer in together, attacking more aggressively. If you were to build the walls using your justsu to block *all* ninjas like before, you run the risk of forcing yourself to make narrow walls, and making the important person extremely uncomfortable, walking through a tight space. Narrow walls will also make the important person less confident in his predicted answers.

So, what you could do, is allow a few of those outlier ninjas in the area, while still making a large margin. The tradeoff is that now the important person is caught of guard, and isn’t able to predict which ninja is which. There will be some damage taken, there is no free lunch. This is called *soft margin* classification.

In the final case, all the ninjas are grouped together, attacking from all angles. The important person must still make it to the other side of the village, and still wants to predict accurately where each ninja is. The issue is, the threats are not linearly separable. At least not in 3 dimensions.

So, Naruto uses his special Sage Genjustu skills to project everyone into 5 dimensions. In 5 dimensions, the ninjas are placed in different spots. The world looks different.

He is able to make linear walls in 5 dimensions to separate them.

In 3 dimensions it seems non-linear, but in 5 it is linear. The special Sage Genjustu he used to implicitly move everyone into 5 dimensions is known as the *kernel trick*.

Support Vector Machines

Recall that most algorithms model situations by creating a *feature space*, which is a finite-dimensional vector space, where each dimension represents a *feature* of your training examples.

For example, if you wanted to classify whether someone was an *adult* or *child* (labels), and you were given 2 features (*height* and *weight*), you would model it with a 2 dimensional graph. In order to classify, you want to find a a hyperplane that will separate the data. So, when you get new data you want to classify, you just simply see what side of the hyperplane that new piece of data falls on.

Support Vector Machines (SVM), unlike the perceptron, finds the most optimal separating plane with the largest margin between classes. We want to look for a hyperplane that maximizes the space between both classes, because if we select a hyperplane which is close to the data points of one class, then it might not generalize well to new, unseen data. When we get more data points, if the margin was maximized, there is a smaller chance that the new data point will be placed on the wrong side of the hyperplane. So we want a hyperplane that is as far as possible from data points from each category.

SVMs have the most math out of any of the other algorithms that you have seen thus far. So, I will first walk you though what we will be doing:

- First we will formalize/define what we mean by a margin.
- We will then proceed to maximize the margin which is called the
*primal*problem. - We see that we can solve the primal problem, but it would be far easier to turn it into a
*Lagrangian*and solve the*dual*problem. - To combat
*overfitting*and* non-linearly separable*data, we introduce the *soft margin *hyperplane*.* Soft margin uses *slack variables, *which is a variable that allows SVM to make some error, allowing for some overlap in the classes, so that it can generalize better (performance on unseen data). - We then extend SVM to solve non-linear decision boundaries. In order to do that, we introduce
*kernels*which is a method to impliclity move data to a higher dimension so that we can classify them.

Margin

Given a particular hyperplane, we can compute the distance between the hyperplane and the closest data point. Once we have this value, if we double it, we will get what is called the *margin*.

To compute the margin, we have to have a working knowledge of how to find the sum/difference, magnitude, unit vector, and dot product of vectors (click the links to learn/refresh).

Recall that an equation of a line is usually written as . However, in machine learning literature, you usually see the equation of a hyperplane defined as:

where .

These two equations are the same thing. is simply the *bias* which means that this value determines the intersection of the line with the vertical axis.

We use because it is easier to work in two dimensions with this notation and the vector will always be orthogonal to the hyperplane (because two vectors are orthogonal if their dot product is zero).

Let’s show an example. We set , so it will pass through the origin:

As you can see, the equation of the hyperplane is:

with and

We would like to compute the distance between the closest point and the hyperplane. You can find this by finding the magnitude of the projection of on the weight vector . We can view the point as a vector from the origin to . If we project it onto the normal vector we get vector .

Recall that the orthogonal projection formula of onto is given by:

We start with two vectors, which is normal to the hyperplane, and which is the vector between the origin and .

Our projection vector is given as:

So, , and it’s distance/magnitude is given by:

Now that we have the distance between and the hyperplane, the margin is defined by:

We have computed the margin of the hyperplane. But how do we find the *optimal* hyperplane? We form the *primal* problem.

Primal Form

After selecting two hyperplanes which separate the data with no points between them, you maximize their distance (margin) and the region bounded by the two hyperplanes will be the biggest possible margin.

Given a hyperplane separating the dataset and satisfying:

We can select two other hyperplanes and which also separate the data and have the following equations:

and

so that is equidistant from and .

Note that from the Point-Plane Distance formula, we get that is the perpendicular distance from the hyperplane to the origin.

When tuning parameters, we just need to alternate one. So we can simplify the problem by setting , so now we have:

- with normal vector and perpendicular distance from the origin
- with normal vector and perpendicular distance form the origin

We want to make sure (try) to have no points between them. We won’t select just *any *hyperplane, we will only select those who meet the two following constraints:

For each training example vector for all either:

- for having the class 1
- for having the class -1

To express this more compactly, we can put them together into a single constraint:

This is true because the output is a discrete answer i.e. for a positive example or negative example.

Earlier, for uniqueness, recall that we set for any example closest to the boundary. So, the distance from the closest sample to is:

We then double it and have the margin is . As you can see, if we want to make the margin bigger, we must minimize . The smaller is, the bigger the margin.

Therefore, we will try to minimize such that for all . We added the and squared it to make it more mathematically easy. We do this a lot in mathematics.

This results in the following constraint optimization problem known as the *primal* problem:

*Don't forget what the purpose of doing this is. We want to minimize \(w\) to increase the margin. However, the margin must respect the constraints we set, so we can find the largest margin that separates all classes.*

Solving this equation is no different than solving a homework assignment in Calc 3 class. Once this is solved, we have found the parameters for which is the smallest possible and the constraints we fixed are met. Which we means we will have the equation of the optimal hyperplane!

The primal form, which is an optimization problem with a *convex quadratic objective* and linear constraints, can be solved using commercial quadratic programming (QP) code.

Although it seems that we have solved the problem, we will make a digression to talk about *Lagrange duality*. This will lead us to our optimization problem’s *dual* form. In the primal problem, in order to classify a new point, we must explicitly compute the scalar product which may be expensive if there are a lot of features (high dimensions). The dual form, however, will be easier to compute and play a key role in allowing us to work efficiently in very high dimensional spaces.

In order to move on, you must be comfortable with partial derivatives, gradient, hessian, and convex functions.

Dual Form

In mathematical optimization theory, *duality* means that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem (*duality principle*). The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. It turns out that most times, solving the dual problem is simpler than solving the primal problem.

In the schema above, imagine that in our primal problem, we are trying to minimize the function at the top of the graph. Its minimum is the black dot at the bottom of the primal. If we search for a dual function, we could end up with the one at the bottom of the graph, whose maximum is the black dot at the top of the dual. In this case, we clearly see that dual black dot is a lower bound. We call the value the *duality gap*. In this example, and we say that *weak duality holds*.

For *strong duality* to hold, there must be no duality gap, i.e. . This is when the solution to both primal and dual will be the same. It is shown below:

*Dual and primal could give us the same answer. The reason we'd rather solve the dual is because we will be able to use kernels. Keep reading below.*

Recall from above that in constraint problems, an optimization problem is typically written as:

where there are functions which define inequality constraints and functions which define equality constraints.

For instance, if I said:

The red star would be our optimal point in, which is within the constraints.

So what’s one way we can find a solution to the optimization problem? We use can use Lagrange Mulitipliers! In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality/inequality constraints. More on Lagngrangian here.

So our Generalized Lagrangian has the form:

where , are the constraints our function is subject to and , are our Langrange multipliers. We would then find and set ’s partial derivatives to zero to solve for the parameters we are looking for.

Solution is the optimal in the primal, and are the optimal and in the dual.

For a solution to exist (and hence the primal and dual problems are equivalent), the *Krush-Kuhn-Tucker Conditions* (KKT) must be fulfilled.

KKT Conditions

Moreover, if some , , and satisfy the KKT conditions, then it is also a solution to the primal and dual problems, i.e. Primal Dual .

So, going back to our original (primal) problem:

where we can write the constraints as:

If we try to set it up as a Lagrangian, we get:

with

Note that there are no Lagrange multipliers, since the problem only has inequality constraints.

Setting the derivatives of w.r.t and to zero, we have:

and

By plugging in these 2 quantities back into Lagrangian , we get:

But recall that from partial derivatives of , the last term must be zero, so after simplifying, we obtain:

Recall that we got to the equation above by minimizing with respect to and . Putting this together with the constraints (that we always had) and the constraint from taking the partial derivative of , we obtain the following dual optimization problem:

such that and

The objective function of the dual problem needs to be maximized and can be done with QP solvers. Solve the dual problem to find the . Once we find the , we can find the optimal ’s with:

Having found , by considering the primal problem, it is also straightforward to find the optimal value for the intercept term :

Then, for a new data , we can make a prediction simply by computing:

and classify as class 1 if sum is positive and class 2 otherwise.

You will see that all of the ’s besides the support vectors will be zero. There are only a small number of support vectors and the decision boundary is determined only by them. As a result, many of the terms in the sum above will be zero, so we will only need to find the inner products between and the support vectors in order to calculate and make our prediction.

By examining the dual form of the optimization problem, we were able to write the entire algorithm in term of only inner products between input feature vectors. We will later exploit this property to apply kernels to be able to efficiently learn in very high dimensional spaces.

Non-Linearly Seperable

What about for non-linearly separable data? We use a *soft-margin hyperplane*. We allow some small *error* in classification so that we can still maximize the margin and generalize better for ‘unseen’ data. are *slack variables* in optimization and they approximate the number of misclassified samples:

Once we account for slack variable , we get:

As you can see, we want to minimize where is tradeoff parameter between error and margin. A large corresponds to assigning a higher penalty to errors. Note that if there is no error in . You can think of as an upper bound of the number of errors.

The optimization problem then becomes:

The dual of this new constrained optimization problem is:

subject to for all and

is recovered as . Notice that this is similar to the linear separable case, except that there is an upper bound on now. Once again, a QP solver can be used to find .

Extend To Non-Linear Decision Boundary

SVM also works for non-linear decision boundaries. Something that is non-linear in 2 dimensions might be linear in 3 dimensions. For example, in the figure below on the right, in 2 dimensions, there is no linear boundary to separate the examples. However, if we project those same features to *3* dimensions, we can find a linear separating hyperplane. So it would be linear in 3 dimensions and non-linear in 2.

Notice above that the two data sets are the same, one is just projected to a different dimension. Another example would be one below. We use our feature mapping function to project the data to a different dimension. For example, from below, at once it gets put through our feature mapping function, we get which corresponds to the blue point on the right. As you can see, with our feature mapping, we are able to find a linear boundary in which corresponds to a non-linear boundary in . Our new function becomes

Just to recap, the key idea is to transform to a higher dimensional space to *make life easier*. You go from the input space: the space the points are located and map it to the feature space, the space of after transformation. You transform because linear operations in the features space is equivalent to non-linear operation in the input space. Also, classification can become easier with proper transformation. For example, in the XOR problem, adding a new feature of makes the problem linearly separable.

However, computation in the feature space can be costly because it is high dimensional as the feature space is typically infinite-dimensional. What can we do about this? We use the *kernel trick*! Recall that in our new SVM optimization problem, the data points only appear as inner product . As long as we can calculate the inner product in the feature space, we do not need the mapping explicitly.

We define the kernel function K by

Suppose our feature mapping is given as follows:

An inner product in the feature space is given by:

So, if we define the kernel function as follows, there is no need to carry out the feature mapping explicitly:

The use of kernel function to avoid carrying out is known as the kernel trick.

Kernelling can be a confusing concept to understand, so I will illustrate one more example.

Say we are in 3-dimensional space and want to project to 9-dimensional space to classify the new data. The two data points we have are:

and our feature mapping to get to 9 dimensions is

So in order to calculate the inner product in the feature space *without *kernelling, we must first calculate and

We then calculate :

The issue with this is, there were a lot of computational steps because of the mapping from 3 dimensions to 9. As we get to higher dimensions, the runtime increases causing some programs to crash.

Instead, we can just use the kernelling function :

which gives you the same result without going to higher dimensions, saving TONS of computation!

*Kernelling can be quite confusing. Make sure you walk through the math to see why the kernel trick saves us a bunch of computation.*

Now, how exactly do we come up with kernelling functions that happen to produce the same output as the the dot product in the feature space? Unfortunately, there is no systematic way for that. It’s an art and takes practice.

Another view is that the kernel function, being an inner product, is really a similarity measure between the objects. So, we simply change all the inner products to kernel functions. For training, we get

After finding the , we can find the ’s with:

To classify a new piece of data , we have:

Some observations:

- Not all similarity measures can be used as a kernel.
- A kernel needs to satisfy the
*Mercer conditions*, meaning it’s a valid kernel*if and only if*for all examples it produces a*Gram*matrix: .- The Gram matrix must be
*symmetric*: . - The Gram matrix must be
*positive semi-definite*: for all .

- The Gram matrix must be
- This also means that the QP is convex (having one global optima) and can be solved in polynomial time.
- Since training data of SVM only requires the value of , there is no restriction of the form and .

Algorithm

Given a training set , the SVM algorithm works like this:

- Use cross validation to find the best value for our hyperparameters like .
- Find what kernel function would be best for the given problem, i.e. .
- Solve the dual problem by using a QP solver package. It will return the optimal ’s.
- With those , we can plug them, the kernel function, and the label into .
- We can then solve for .
- When we have a new example, we can simply plug it into and return it’s prediction.

Example

A group of your friends have been infected by an alien parasite. You have a radiation beam that could kill the parasite, but it’s so strong that it could also kill your friends if its on them for too many seconds. If it’s too few seconds, then the parasite will not be exterminated.

Your job is to use SVM to build a model and classify whether or not your radiation beam was successful. You have already deployed the beam on 5 of your friends. One was successfully treated, the other 4 were not. The features given are how many seconds the beam was on your friend:

As you can see, thus far, your only friend that survived is the one that had the radiation beam on him for 3 seconds (survived=-1).

is set to 1000 and we use the polynomial kernel of degree 2, given by:

We first find for all :

By using a QP solver, we get:

Note that the constraints are indeed satisfied.

Recall, that support vectors correspond to the non-zero , so the support vectors are

The discriminant function we get from above is:

is then recovered by solving , , or , as and lie on the line and lies on the line

All three give so our discriminant function is now:

So, on our 6th friend who’s been under the radiation for 3.3 seconds, we want to see if his treatment was successful.

We simply plug him into our discriminant function:

By our model, we see that 3.3 seconds was enough time for the radiation beam to remove the parasite but not long enough to harm our friend. He is classified as safe!

Summary/Discussion

Support Vector Machines are a powerful supervised learning method that build on the intuition that a hyperplane that maximizes the margin between classes provides the most optimal model. The purpose of SVM is to train a model to assign new, unseen data into a certain class. It achieves this by creating a linear partition of the feature space into two classes. Based on the features of the new data, it places it on once side of the linear separator, leading to a categorization.

We have discussed and formalized what we mean by margin and introduced the primal problem to maximize the margin. We then took a digression to discuss Langragian multipliers so that we could introduce the dual problem, a problem that would bring the same solution, but easier to compute. We then extended the problem to non-linearly separable data by introducing soft margin classification with slack variables. We finally introduced kernels which would allow us to implicilty project the data to higher dimensions to find non-linear decision boundaries in the original dimension.

Other observations:

- Can be used for regression or classification.
- We can treat the QP solver as a
*black box*without bothering how it works. - A classifier in high-dimensional space has many parameters and may suffer from the curse of dimensionality. But SVM does not suffer because it is flexible (high capacity). This is formalized by the VC-dimension, which is the max number of points that the classifier can perfectly classify irrespective of the labels.
- It also doesn’t suffer from curse of dimensionality, meaning it is an effective tool in high-dimensional spaces. This is because it enforces largest margin, which permits good generalization. It can also be shown that generalization in SVM is a function of the margin,
*independent*of the dimensionality. So complexity relies on number of support vectors, not the dimensionality of the transformed space. - SVM can viewed as implementing Structural Risk Minimization (SRM) because approximates the training error and is related to the VC-dimension of the resulting classifier.
- SRM is an inductive principle that says we should try to find a classier that minimizes the sum of training error (empirical risk) and a term that is a function of the flexibility of the classifier (model complexity).

- Training SVMs are relatively easy. There is no local optima and it is memory efficient because only a subset of the training points are used in the actual decision process of assigning new members (support vectors).
- Tradeoff between classifier complexity and error can be controlled explicitly with regularization parameter .
- SVM has a strong theoretical foundation but is non-probabilistic. The classifier predicts by placing new data above or below a classifying hyperplane, so there is no direct probabilistic interpretation for class membership. The features fully determine its location in feature space, so there is no stochastic element involved.
- When the number of features for each object exceeds the number of training examples, SVMs can perform poorly. Intuitively, this is because if the high-dimensional feature space is much larger than the samples, then there are less effective support vectors on which to support the optimal hyperplanes.