Maximum Separability

How does SVM separate two or more classes? Consider the set of points in Figure 8.2. Before you look at the next figure, visually think of a straight line dividing the points into two groups.

Now look at Figure 8.3, which shows two possible lines separating the two groups of points. Is this what you had in mind?

Though both lines separate the points into two distinct groups, which one is the right one? For SVM, the right line is the one that has the widest margins (with each margin touching at least a point in each class), as shown in Figure 8.4. In that figure, d1 and d2 are the width of the margins. The goal is to find the largest possible width for the margin that can separate the two groups. Hence, in this case d2 is the largest. Thus the line chosen is the one on the right.

Each of the two margins touches the closest point(s) to each group of points, and the center of the two margins is known as the hyperplane. The hyperplane is the line separating the two groups of points. We use the term “hyperplane” instead of “line” because in SVM we typically deal with more than two dimensions, and using the word “hyperplane” more accurately conveys the idea of a plane in a multidimensional space.

Support Vectors

A key term in SVM is support vectors. Support vectors are the points that lie on the two margins. Using the example from the previous section, Figure 8.5 shows the two support vectors lying on the two margins.

In this case, we say that there are two support vectors—one for each class.

Formula for the Hyperplane

With the series of points, the next question would be to find the formula for the hyperplane, together with the two margins. Without delving too much into the math behind this, Figure 8.6 shows the formula for getting the hyperplane.

As you can see from Figure 8.6, the formula for hyperplane (g) is given as:

where x₁ and x₂ are the inputs, and are the weight vectors, and b is the bias.

If the value of g is , then the point specified is in Class 1, and if the value of g is , then the point specified is in Class 2. As mentioned, the goal of SVM is to find the widest margins that divide the classes, and the total margin (2d) is defined by:

where is the normalized weight vectors ( and ). Using the training set, the goal is to minimize the value of so that you can get the maximum separability between the classes. Once this is done, you will be able to get the values of , , and b.

Finding the margin is a Constrained Optimization problem, which can be solved using the Larange Multipliers technique. It is beyond the scope of this book to discuss how to find the margin based on the dataset, but suffice it to say that we will make use of the Scikit‐learn library to find them.

Using Scikit‐learn for SVM

Now let's work on an example to see how SVM works and how to implement it using Scikit‐learn. For this example, we have a file named svm.csv containing the following data:

x1,x2,r
0,0,A
1,1,A
2,3,B
2,0,A
3,4,B 

The first thing that we will do is to plot the points using Seaborn:

%matplotlib inline
import pandas as pd
import numpy as np
import seaborn as sns; sns.set(font_scale=1.2)
import matplotlib.pyplot as plt
 
data = pd.read_csv('svm.csv')
sns.lmplot('x1', 'x2',
           data=data,
           hue='r',
           palette='Set1',
           fit_reg=False,
           scatter_kws={"s": 50}); 

Figure 8.7 shows the points plotted using Seaborn.

Using the data points that we have previously loaded, now let's use Scikit‐learn's svm module's SVC class to help us derive the value for the various variables that we need to compute otherwise. The following code snippet uses the linear kernel to solve the problem. The linear kernel assumes that the dataset can be separated linearly.

from sklearn import svm
#---Converting the Columns as Matrices---
points = data[['x1','x2']].values
result = data['r']
 
clf = svm.SVC(kernel = 'linear')
clf.fit(points, result)
 
print('Vector of weights (w) = ',clf.coef_[0])
print('b = ',clf.intercept_[0])
print('Indices of support vectors = ', clf.support_)
print('Support vectors = ', clf.support_vectors_)
print('Number of support vectors for each class = ', clf.n_support_)
print('Coefficients of the support vector in the decision function = ',
       np.abs(clf.dual_coef_)) 

The SVC stands for Support Vector Classification. The svm module contains a series of classes that implement SVM for different purposes:

• svm.LinearSVC: Linear Support Vector Classification
• svm.LinearSVR: Linear Support Vector Regression
• svm.NuSVC: Nu‐Support Vector Classification
• svm.NuSVR: Nu‐Support Vector Regression
• svm.OneClassSVM: Unsupervised Outlier Detection
• svm.SVC: C‐Support Vector Classification
• svm.SVR: Epsilon‐Support Vector Regression

The preceding code snippet yields the following output:

Vector of weights (w) =  [0.4 0.8]
b =  -2.2
Indices of support vectors =  [1 2]
Support vectors =  [[1. 1.]
 [2. 3.]]
Number of support vectors for each class =  [1 1]
Coefficients of the support vector in the decision function =  [[0.4 0.4]] 

As you can see, the vector of weights has been found to be [0.4 0.8], meaning that is now 0.4 and is now 0.8. The value of b is –2.2, and there are two support vectors. The index of the support vectors is 1 and 2, meaning that the points are the ones in bold:

x1  x2  r
0   0   0  A
1   1   1  A
2   2   3  B
3   2   0  A
4   3   4  B 

Figure 8.8 shows the relationship between the various variables in the formula and the variables in the code snippet.

Plotting the Hyperplane and the Margins

With the values of the variables all obtained, it is now time to plot the hyperplane and its two accompanying margins. Do you remember the formula for the hyperplane? It is as follows:

To plot the hyperplane, set to 0, like this:

In order to plot the hyperplane (which is a straight line in this case), we need two points: one on the x‐axis and one on the y‐axis.

Using the preceding formula, when , we can solve for x₂ as follows:

(0) +  + b = 0
 = -b
x2= -b/ 

When x₂ = 0, we can solve for x₁ as follows:

 + (0) + b = 0
 = -b
x1 = -b/ 

The point (0,‐b/ ) is the y‐intercept of the straight line. Figure 8.9 shows the two points on the two axes.

Once the points on each axis are found, you can now calculate the slope as follows:

Slope = (-b/) / (b/)
Slope = -(/) 

With the slope and y‐intercept of the line found, you can now go ahead and plot the hyperplane. The following code snippet does just that:

#---w is the vector of weights---
w = clf.coef_[0]
 
#---find the slope of the hyperplane---
slope = -w[0] / w[1]
 
b = clf.intercept_[0]
 
#---find the coordinates for the hyperplane---
xx = np.linspace(0, 4)
yy = slope * xx - (b / w[1])
 
#---plot the margins---
s = clf.support_vectors_[0]    #---first support vector---
yy_down = slope * xx + (s[1] - slope * s[0])
 
s = clf.support_vectors_[-1]   #---last support vector---
yy_up   = slope * xx + (s[1] - slope * s[0])
 
#---plot the points---
sns.lmplot('x1', 'x2', data=data, hue='r', palette='Set1',
fit_reg=False, scatter_kws={"s": 70})
 
#---plot the hyperplane---
plt.plot(xx, yy, linewidth=2, color='green');
 
#---plot the 2 margins---
plt.plot(xx, yy_down, 'k--')
plt.plot(xx, yy_up, 'k--') 

Figure 8.10 shows the hyperplane and the two margins.

Making Predictions

Remember, the goal of SVM is to separate the points into two or more classes, so that you can use it to predict the classes of future points. Having trained your model using SVM, you can now perform some predictions using the model.

The following code snippet uses the model that you have trained to perform some predictions:

print(clf.predict([[3,3]])[0])  # 'B'
print(clf.predict([[4,0]])[0])  # 'A'
print(clf.predict([[2,2]])[0])  # 'B'
print(clf.predict([[1,2]])[0])  # 'A' 

Check the points against the chart shown in Figure 8.10 and see if it makes sense to you.

Adding a Third Dimension

To do so, we can add a third dimension, say the z‐axis, and define z to be:

Once we plot the points using a 3D chart, the points are now linearly separable. It is difficult to visualize this unless you plot the points out. The following code snippet does just that:

%matplotlib inline
 
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_circles
 
#---X is features and c is the class labels---
X, c = make_circles(n_samples=500, noise=0.09)
 
rgb = np.array(['r', 'g'])
plt.scatter(X[:, 0], X[:, 1], color=rgb[c])
plt.show()
 
fig = plt.figure(figsize=(18,15))
ax = fig.add_subplot(111, projection='3d')
z = X[:,0]**2 + X[:,1]**2
ax.scatter(X[:, 0], X[:, 1], z, color=rgb[c])
plt.xlabel("x-axis")
plt.ylabel("y-axis")
plt.show() 

We first create two sets of random points (a total of 500 points) distributed in circular fashion using the make_circles() function. We then plot them out on a 2D chart (as what was shown in Figure 8.11). We then add the third axis, the z‐axis, and plot the chart in 3D (see Figure 8.12).

Plotting the 3D Hyperplane

With the points plotted in a 3D chart, let's now train the model using the third dimension:

#---combine X (x-axis,y-axis) and z into single ndarray---
features = np.concatenate((X,z.reshape(-1,1)), axis=1)
 
#---use SVM for training---
from sklearn import svm
 
clf = svm.SVC(kernel = 'linear')
clf.fit(features, c) 

First, we combined the three axes into a single ndarray using the np.concatenate() function. We then trained the model as usual. For a linearly‐separable set of points in two dimensions, the formula for the hyperplane is as follows:

g(x) =  +  + b 

For the set of points now in three dimensions, the formula now becomes the following:

g(x) =  +  +  + b 

In particular, is now represented by clf.coef_[0][2], as shown in Figure 8.14.

The next step is to draw the hyperplane in 3D. In order to do that, you need to find the value of x3, which can be derived, as shown in Figure 8.15.

This can be expressed in code as follows:

x3 = lambda x,y: (-clf.intercept_[0] - clf.coef_[0][0] * x-clf.coef_[0][1] * y) / 
                   clf.coef_[0][2] 

To plot the hyperplane in 3D, use the plot_surface() function:

tmp = np.linspace(-1.5,1.5,100)
x,y = np.meshgrid(tmp,tmp)
 
ax.plot_surface(x, y, x3(x,y))
plt.show() 

The entire code snippet is as follows:

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_circles
 
#---X is features and c is the class labels---
X, c = make_circles(n_samples=500, noise=0.09)
z = X[:,0]**2 + X[:,1]**2
 
rgb = np.array(['r', 'g'])
 
fig = plt.figure(figsize=(18,15))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(X[:, 0], X[:, 1], z, color=rgb[c])
plt.xlabel("x-axis")
plt.ylabel("y-axis")
# plt.show()
 
#‐‐‐combine X (x‐axis,y‐axis) and z into single ndarray‐‐‐
features = np.concatenate((X,z.reshape(‐1,1)), axis=1)
 
#‐‐‐use SVM for training‐‐‐
from sklearn import svm
 
clf = svm.SVC(kernel = 'linear')
clf.fit(features, c)
x3 = lambda x,y: (‐clf.intercept_[0] ‐ clf.coef_[0][0] * x‐clf.coef_[0][1]
                   * y) / clf.coef_[0][2]
 
tmp = np.linspace(‐1.5,1.5,100)
x,y = np.meshgrid(tmp,tmp)
 
ax.plot_surface(x, y, x3(x,y))
plt.show() 

Figure 8.16 shows the hyperplane, as well as the points, plotted in 3D.

C

In the previous section, you saw the use of the C parameter:

C = 1
clf = svm.SVC(kernel='linear', C=C).fit(X, y) 

C is known as the penalty parameter of the error term. It controls the tradeoff between the smooth decision boundary and classifying the training points correctly. For example, if the value of C is high, then the SVM algorithm will seek to ensure that all points are classified correctly. The downside to this is that it may result in a narrower margin, as shown in Figure 8.20.

In contrast, a lower C will aim for the widest margin possible, but it will result in some points being classified incorrectly (see Figure 8.21).

Figure 8.22 shows the effects of varying the value of C when applying the SVM linear kernel algorithm. The result of the classification appears at the bottom of each chart.

Note that when C is 1 or 10¹⁰, there isn't too much difference among the classification results. However, when C is small (10^–10), you can see that a number of points (belonging to “versicolor” and “virginica”) are now misclassified as “setosa.”

Radial Basis Function (RBF) Kernel

Besides the linear kernel that we have seen so far, there are some commonly used nonlinear kernels:

• Radial Basis function (RBF), also known as Gaussian Kernel
• Polynomial

The first, RBF, gives value to each point based on its distance from the origin or a fixed center, commonly on a Euclidean space. Let's use the same example that we used in the previous section, but this time modify the kernel to use rbf:

C = 1
clf = svm.SVC(kernel='rbf', gamma='auto', C=C).fit(X, y)
title = 'SVC with RBF kernel' 

Figure 8.23 shows the same sample trained using the RBF kernel.

Gamma

If you look at the code snippet carefully, you will discover a new parameter—gamma. Gamma defines how far the influence of a single training example reaches. Consider the set of points shown in Figure 8.24. There are two classes of points—x's and o's.

A low Gamma value indicates that every point has a far reach (see Figure 8.25).

On the other hand, a high Gamma means that the points closest to the decision boundary have a close reach. The higher the value of Gamma, the more it will try to fit the training dataset exactly, resulting in overfitting (see Figure 8.26).

Figure 8.27 shows the classification of the points using RBF, with varying values of C and Gamma.

Note that if Gamma is high (10), overfitting occurs. You can also see from this figure that the value of C controls the smoothness of the curve.

Polynomial Kernel

Another type of kernel is called the polynomial kernel. A polynomial kernel of degree 1 is similar to that of the linear kernel. Higher‐degree polynomial kernels afford a more flexible decision boundary. The following code snippet shows the Iris dataset trained using the polynomial kernel with degree 4:

C = 1  # SVM regularization parameter
clf = svm.SVC(kernel='poly', degree=4, C=C, gamma='auto').fit(X, y)
title = 'SVC with polynomial (degree 4) kernel' 

Figure 8.28 shows the dataset separated with polynomial kernels of degree 1 to 4.