Support Vector Machines (SVM) are a method that uses points in a transformed problem space that best separate classes into two groups. Classification for multiple classes is then supported by a one-vs-all method (just like we previously did for Logistic Regression for Multi Class Classification).
This lecture section will be broken up by the following sections:
Part 1: Introduction to Support Vector Machines
Part 2: SVM General Explanation
Part 3: Computing the Hyperplane
Part 4: Additional Math Resources
Part 5: SVM with Sci Kit Learn
Part 6: Additional Resources
Formal Explanation:
In machine learning, support vector machines (SVMs) are supervised learning models with associated learning algorithms that analyze data and recognize patterns, used for classification and regression analysis. Given a set of training examples, each marked for belonging to one of two categories, an SVM training algorithm builds a model that assigns new examples into one category or the other, making it a non-probabilistic binary linear classifier. An SVM model is a representation of the examples as points in space, mapped so that the examples of the separate categories are divided by a clear gap that is as wide as possible. New examples are then mapped into that same space and predicted to belong to a category based on which side of the gap they fall on.
The advantages of support vector machines are:
The disadvantages of support vector machines include:
Let's go ahead and break down the main idea of SVMs!
We'll start by imagining a situation in which we want to seperate a training set with two classes. We have two classes in our set, blue and red. We plot them out in the feature space and we try to place a green line that seperates both classes.
from IPython.display import Image
url = 'http://docs.opencv.org/_images/separating-lines.png'
Image(url)
From the image above we see that we have multiple ways of drawing this line (which we will call a hyperplane) that can seperate the classes completely. So which is the optimal line?
We decide that the optimal hyperplane that seperates these two classes is the one with the maximum margin between the two classes as seen in the image below:
url= 'http://docs.opencv.org/_images/optimal-hyperplane.png'
Image(url)
So how do we actually mathematically compute that optimal hyperplane? I'll explain with a very brief overview below in Part 3, but I highly suggest you check out the full explanation on Wikipedia or in the lecture videos following Part 3.
Let's go ahead and start by defining the Hyperplane in this case with the equation of a line, where Beta tranposed is the known weight vector of the features we've seen before and Beta nought is the bias.
$$ f(x) = \beta_{0} + \beta^{T} x $$There are an infinite number of ways we could scale the weight vector and the bias, but remember we want to maximize the margin between the two classes. So we realize through some math (explained in detail the videos below) can set this as:
$$ |\beta_{0} + \beta^{T} x| = 1 $$where x symbolizes the training examples closest to the hyperplane. In general, the training examples that are closest to the hyperplane are called support vectors. These support vectors are filled in with color in the image above. This representation is known as the canonical hyperplane.
From geometry we know that the distance betweeen a point x and the hyperplane (Beta,Beta0)is:
$$\mathrm{distance} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||}.$$In particular, for the canonical hyperplane, the numerator is equal to one and the distance to the support vectors is
$$\mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}$$Recall that the margin introduced in the previous section, here denoted as M, is twice the distance to the closest examples:
$$M = \frac{2}{||\beta||}$$Finally, the problem of maximizing M is equivalent to the problem of minimizing a function L(Beta) subject to some constraints. The constraints model the requirement for the hyperplane to classify correctly all the training examples xi.
Formally,
$$\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i$$where yi represents each of the labels of the training examples.
This is a problem of Lagrangian optimization that can be solved using Lagrange multipliers to obtain the weight vector Beta and the bias Beta0 of the optimal hyperplane.
If we want to do non-linear classification we can employ the kernel trick. Using the kernel trick we can "slice" the feature space with a Hyperplane. For a quick illustraion of what this looks like, check out both the image and the video below!
# Kernel Trick for the Feature Space
url='http://i.imgur.com/WuxyO.png'
Image(url)
# Kernel Trick Visualization
from IPython.display import YouTubeVideo
YouTubeVideo('3liCbRZPrZA')
Below are video links to free resources for a deeper dive into the mathematics of Support Vector Machines. First a lecture by Andrew Ng and then a lecture from MIT Open CourseWare
# Andrew Ng Lecture
YouTubeVideo('qdnT_jGTg2s')
# MIT Lecture
YouTubeVideo('_PwhiWxHK8o')
Now we are ready to jump into some Python code and Sci Kit Learn, we'll start with some basic imports and we will import Sci Kit Learn along the way while we use it.
#Imports
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
#Note, we won't use seaborn due to a plot at the end.
First we'll start by importing the Data set we are already very familiar with, the Iris Data Set
from sklearn import datasets
# load the iris datasets
iris = datasets.load_iris()
# Grab features (X) and the Target (Y)
X = iris.data
Y = iris.target
# Show the Built-in Data Description
print iris.DESCR
Iris Plants Database Notes ----- Data Set Characteristics: :Number of Instances: 150 (50 in each of three classes) :Number of Attributes: 4 numeric, predictive attributes and the class :Attribute Information: - sepal length in cm - sepal width in cm - petal length in cm - petal width in cm - class: - Iris-Setosa - Iris-Versicolour - Iris-Virginica :Summary Statistics: ============== ==== ==== ======= ===== ==================== Min Max Mean SD Class Correlation ============== ==== ==== ======= ===== ==================== sepal length: 4.3 7.9 5.84 0.83 0.7826 sepal width: 2.0 4.4 3.05 0.43 -0.4194 petal length: 1.0 6.9 3.76 1.76 0.9490 (high!) petal width: 0.1 2.5 1.20 0.76 0.9565 (high!) ============== ==== ==== ======= ===== ==================== :Missing Attribute Values: None :Class Distribution: 33.3% for each of 3 classes. :Creator: R.A. Fisher :Donor: Michael Marshall (MARSHALL%PLU@io.arc.nasa.gov) :Date: July, 1988 This is a copy of UCI ML iris datasets. http://archive.ics.uci.edu/ml/datasets/Iris The famous Iris database, first used by Sir R.A Fisher This is perhaps the best known database to be found in the pattern recognition literature. Fisher's paper is a classic in the field and is referenced frequently to this day. (See Duda & Hart, for example.) The data set contains 3 classes of 50 instances each, where each class refers to a type of iris plant. One class is linearly separable from the other 2; the latter are NOT linearly separable from each other. References ---------- - Fisher,R.A. "The use of multiple measurements in taxonomic problems" Annual Eugenics, 7, Part II, 179-188 (1936); also in "Contributions to Mathematical Statistics" (John Wiley, NY, 1950). - Duda,R.O., & Hart,P.E. (1973) Pattern Classification and Scene Analysis. (Q327.D83) John Wiley & Sons. ISBN 0-471-22361-1. See page 218. - Dasarathy, B.V. (1980) "Nosing Around the Neighborhood: A New System Structure and Classification Rule for Recognition in Partially Exposed Environments". IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-2, No. 1, 67-71. - Gates, G.W. (1972) "The Reduced Nearest Neighbor Rule". IEEE Transactions on Information Theory, May 1972, 431-433. - See also: 1988 MLC Proceedings, 54-64. Cheeseman et al"s AUTOCLASS II conceptual clustering system finds 3 classes in the data. - Many, many more ...
Now we will import the SVC (Support Vector Classification) from the SVM library of Sci Kit Learn, I encourage you to check out the other types of SVM options in the Sci Kit Learn Documentation!
# Support Vector Machine Imports
from sklearn.svm import SVC
Now we create a Support Vector Classification model for the data.
# Fit a SVM model to the data
model = SVC()
Now we will split the data into a training set and a testing set and then train our model.
from sklearn.cross_validation import train_test_split
# Split the data into Trainging and Testing sets
X_train, X_test, Y_train, Y_test = train_test_split(X, Y)
# Fit the model
model.fit(X_train,Y_train)
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0, degree=3, gamma=0.0, kernel='rbf', max_iter=-1, probability=False, random_state=None, shrinking=True, tol=0.001, verbose=False)
Now we'll go ahead and see how well our model did!
from sklearn import metrics
# Get predictions
predicted = model.predict(X_test)
expected = Y_test
# Compare results
print metrics.accuracy_score(expected,predicted)
1.0
Looks like we have achieved a 97.4 % accuracy with Support Vector Classification!
Now that we've gone through a basic implementation of SVM lets go ahead and quickly explore the various kernel types we can use for classification. We can do this by plotting out the boundaries created by each kernel type! We'll start with some imports and by setting up the data.
The four methods we will explore are two linear models, a Gaussian Radial Basis Function,and a SVC with a polynomial (3rd Degree) kernel.
The linear models LinearSVC() and SVC(kernel='linear') yield slightly different decision boundaries. This can be a consequence of the following differences:
# Import all SVM
from sklearn import svm
# We'll use all the data and not bother with a split between training and testing. We'll also only use two features.
X = iris.data[:,:2]
Y = iris.target
# SVM regularization parameter
C = 1.0
# SVC with a Linear Kernel (our original example)
svc = svm.SVC(kernel='linear', C=C).fit(X, Y)
# Gaussian Radial Bassis Function
rbf_svc = svm.SVC(kernel='rbf', gamma=0.7, C=C).fit(X, Y)
# SVC with 3rd degree poynomial
poly_svc = svm.SVC(kernel='poly', degree=3, C=C).fit(X, Y)
# SVC Linear
lin_svc = svm.LinearSVC(C=C).fit(X,Y)
Now that we have fitted the four models, we will go ahead and begin the process of setting up the visual plots. Note: This example is taken from the Sci Kit Learn Documentation.
First we define a mesh to plot in. We define the max and min of the plot for the y and x axis by the smallest and larget features in the data set. We can use numpy's built in mesh grid method to construct our plot.
# Set the step size
h = 0.02
# X axis min and max
x_min=X[:, 0].min() - 1
x_max =X[:, 0].max() + 1
# Y axis min and max
y_min = X[:, 1].min() - 1
y_max = X[:, 1].max() + 1
# Finally, numpy can create a meshgrid
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),np.arange(y_min, y_max, h))
Now the plot titles
# title for the plots
titles = ['SVC with linear kernel',
'LinearSVC (linear kernel)',
'SVC with RBF kernel',
'SVC with polynomial (degree 3) kernel']
Finally we will go through each model, set its position as a subplot, then scatter the data points and draw a countour of the decision boundaries.
# Use enumerate for a count
for i, clf in enumerate((svc, lin_svc, rbf_svc, poly_svc)):
# Plot the decision boundary. For that, we will assign a color to each
# point in the mesh [x_min, m_max]x[y_min, y_max].
plt.figure(figsize=(15,15))
# Set the subplot position (Size = 2 by 2, position deifined by i count
plt.subplot(2, 2, i + 1)
# SUbplot spacing
plt.subplots_adjust(wspace=0.4, hspace=0.4)
# Define Z as the prediction, not the use of ravel to format the arrays
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# Put the result into a color plot
Z = Z.reshape(xx.shape)
# Contour plot (filled with contourf)
plt.contourf(xx, yy, Z, cmap=plt.cm.terrain, alpha=0.5,linewidths=0)
# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=plt.cm.Dark2)
# Labels and Titles
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.xticks(())
plt.yticks(())
plt.title(titles[i])
plt.show()
1.) Microsoft Research Paper SVM Tutorial
3.) Sci Kit Learn Documentation
4.) Wikipedia