Given linearly separable data (with real-valued attributes), we must find a linear discriminant function that separates the positives and negatives (i.e. the classes) and is as far as possible from any example in the data.
The line that achieves maximum margin is called the maximum margin hyperplane.
Computing the Equation for the Maximum Margin Hyperplane
Consider the data below (positive class: +1, negative class: -1)
The hyperplane equation is g(x) = 0.
For our data, we have the following linear constraints:
The solution gives the weights of the maximum margin hyperplane.
This is, however, the theoretical computation. SVM softwares compute slightly differently.
Let I be the indices of the support vectors. The SVM software outputs g(x) as a function of the support vectors:
So, we have two representtions of the maximum margin hyperplane:
SVM with Non-Linearly-Separable Data
The above works when the data is linearly-separable. What if the data is not linearly separable?
Then, the above technique can be used, since the data (in terms of z) is linearly separable.
However, this cannot always be done.
The idea is to map the data to a new space where it becomes linearly separable. This new space is an infinite-dimensional space.
Then, we have:
Some commonly-used kernel functions:
Polynomial Kernel (of degree d):
The hope is that the data becomes linearly separable by a d-degree polynomial in the attributes.
d is a tunable parameter.
Gaussian Kernel (Radial Basis Function RBF Kernel):
Using a Gaussian kernel is analogous to computing a distance-weighted sum (similar to KNN). It is the most suitable kernel when the data forms a checker-board pattern. To use a Polynomial kernel for the same data, we would need to use high degree d.
The Gaussian kernel is the most commonly-used kernel.
Note: If the number of support vectors returned by the SVM software is not much smaller than the size of the training set, it is a clear sign of overfitting.
Soft-Margin Hyperplanes
The previously discussed hyperplane refers to a hard-margin hyperplane. A soft-margin hyperplane allows examples to be in the margin region, as well as on the wrong side of the hyperplane. To accomodate for the examples that are on the wrong side of the hyperplane, we penalize by the distance of those examples.
For a soft-margin hyperplane, we do the following:
Therefore, SVMs aim to maximize the distance of the decision boundary to the closest point in the data set. This distance is called the margin of the hyperplane, and is denoted by ρ.
x1121323x2121/227/41r−1+1−1+1+1+1
Let g(x)=wTx+w0
The distance from point x to the hyperplane is ∣∣w∣∣2g(x)=w12+w22+...+wd2g(x) (note that there is no w0 in the denominator).
We need to determine w,w0 such that wTxt+w0>0 if rt=+1 and wTxt+w0≤0 if rt=−1.
w1+w2+w0≤0
2w1+2w2+w0>0
w1+21w2+w0≤0, and so on.
For the maximum margin hyperplane, we have ∣∣w∣∣2g(x)=ρ
Suppose we scale the coefficients of g, such that the new g(x)=1 (let's call it g∼(x)) for the points closest to the hyperplane. To do so, we must divide the coefficients of g by a certain quantity. Which quantity to use? Maybe the margin ρ?
Now, replace g(x) by g∼(x), we have new g(x) = −+1 for the points closest to the hyperplane. These points are called support vectors. Typically, we have at least 3 support vectors, some of which are on the + side and some are on the - side. The intuiton behind calling them support vectors is that they support the hyperplane in place, and the hyperplane will move if any of them move.
So, for the support vectors, g(xt)=+1ifrt=+1 and g(xt)=−1ifrt=−1. For other examples:
g(xt)>+1ifrt=+1
g(xt)<−1ifrt=−1
Maximum margin hyperplane on support vectors x satisfies the cannonical form of the maximum margin hyperplane i.e. g(x) = −+1. So, ρ=∣∣w∣∣2−+1.
Therefore, we must maximize w12+w22+...+wd2−+1 subject to the constraints:
wTx+w0≥+1forallxtwherert=+1
wTx+w0≤−1forallxtwherert=−1
(to simplify, we minimize w12+w22+...+wd2).
SVM softwares often don't directly output the weights. Instead, they output a dual representation of the hyperplane g(x)=0 where g(x)=wTx+w0:
g(x)=[∑t∈I(vt[xt])T.x]+v0
where x=[x1x2] i.e. the example to be classified.
Suppose the support vectors are [27/4],[31],[11]say x19,x5,x72 respectively, it will output coefficients for each support vector i.e. v19=3,v5=9,v72=−4 respectively, and v0=3(say).
The software will, therefore, output g(x). The coefficients of x1,x2 in g(x) give the weights w1,w2 and the constant term will be w0.
The Primal Representationg(x)=∑i=1dwixi+w0
The Dual Representationg(x)=[∑t∈I(vt[xt])T.x]+v0
(vt=0 for all t where xt is not a support vector).
Say the data follows x12+x22=1. We can make the data linearly separable using z1=x12,z2=x22.