Support Vector Machine - Linear SVM

Linear SVM

Given some training data, a set of n points of the form

where the y_i is either 1 or −1, indicating the class to which the point belongs. Each is a p-dimensional real vector. We want to find the maximum-margin hyperplane that divides the points having from those having . Any hyperplane can be written as the set of points satisfying

where denotes the dot product and the normal vector to the hyperplane. The parameter determines the offset of the hyperplane from the origin along the normal vector .

If the training data are linearly separable, we can select two hyperplanes in a way that they separate the data and there are no points between them, and then try to maximize their distance. The region bounded by them is called "the margin". These hyperplanes can be described by the equations

and

By using geometry, we find the distance between these two hyperplanes is, so we want to minimize . As we also have to prevent data points from falling into the margin, we add the following constraint: for each either

of the first class

or

of the second.

This can be rewritten as:

We can put this together to get the optimization problem:

Minimize (in )

subject to (for any )