CHAPTER:05

Support Vector Machines

Instructor:
Dr. Furqan Shoukat
Support Vector Machine
• A Support Vector Machine (SVM) is a very
powerful and versatile Machine Learning
model, capable of performing
- linear or nonlinear classification,
- regression,
- outlier detection
• SVMs are particularly well suited for the
classification of complex but small- or
medium-sized datasets.
 Classification
• Regression and Classification algorithms are Supervised
Learning algorithms.
• Both algorithms are used for prediction in Machine learning and
work with the labeled datasets.
• Regression algorithms predict continuous values such as price,
salary, age, etc.
• Classification algorithms are used to predict/Classify discrete
values such as Male or Female, True or False, Spam or Not
Spam, etc.
Outlier/Anomaly Detection
Anomaly detection, also called outlier detection, is the identification of
unexpected events, observations, or items that differ significantly from
the norm.
Uses of SVM
• SVMs can be used for a variety of tasks, such
as
- text classification,
- image classification,
- spam detection,
- handwriting identification,
- gene expression analysis,
- face detection, and
- anomaly detection.
SVM
• SVM algorithm is to find the optimal hyperplane in an N-dimensional
space that can separate the data points in different classes in the feature
space.
• The hyperplane tries that the margin between the closest points of
different classes should be as maximum as possible.
• The dimension of the hyperplane depends upon the number of features.
• If the number of input features is two, then the hyperplane is just a line.
• If the number of input features is three, then the hyperplane becomes a
2-D plane.
• It becomes difficult to imagine when the number of features exceeds
three.
SVM
• Let’s consider two independent variables x1, x2, and one dependent
variable which is either a blue circle or a red circle.

From the figure, it’s very clear that

there are multiple lines (our
hyperplane here is a line because we
are considering only two input features
x1, x2) that segregate our data points or
do a classification between red and
blue circles. So how do we choose the
best line or the best hyperplane that
segregates our data points?
Linear SVM Classifier
Figure 5-1 shows part of the iris dataset.
The two classes can clearly be separated easily with a straight
line (they are linearly separable).
The left plot shows the decision boundaries of three possible
linear classifiers.
Linear SVM Classifier
The model whose decision boundary is represented by the dashed line is so
bad that it does not separate the classes properly. The other two models
work perfectly on this training set, but their decision boundaries come so
close to the instances that these models will probably not perform as well
on new instances.
Linear SVM Classifier
The solid line in the plot on the right represents the decision boundary of an
SVM classifier; this line not only separates the two classes but also stays as
far away from the closest training instances as possible. You can think of an
SVM classifier as fitting the widest possible street (represented by the
parallel dashed lines) between the classes. This is called large margin
classification.
 the distance between the
hyperplane and the
Linear SVM Classifier closest data points, called
support vectors

Notice that adding more training instances “off the street” will not affect the
decision boundary at all: it is fully determined (or “supported”) by the
instances located on the edge of the street. These instances are called the
support vectors (they are circled in Figure 5-1).
Soft Margin Classification
If we strictly impose that all instances be off the street and on the right side,
this is called hard margin classification. There are two main issues with
hard margin classification. First, it only works if the data is linearly
separable, and second, it is quite sensitive to outliers.
Soft Margin Classification
Figure 5-3 shows the iris dataset with just one additional outlier: on the left,
it is impossible to find a hard margin, and on the right, the decision
boundary ends up very different from the one we saw in Figure 5-1 without
the outlier, and it will probably not generalize as well.
Soft Margin Classification
To avoid these issues, it is preferable to use a more flexible model. The
objective is to find a good balance between keeping the street as large as
possible and limiting the margin violations (i.e., instances that end up in the
middle of the street or even on the wrong side). This is called soft margin
classification.
Soft Margin Classification
In Scikit-Learn’s SVM classes, you can control this balance using the C hyperparameter: a
smaller C value leads to a wider street but more margin violations. Figure 5-4 shows the
decision boundaries and margins of two soft margin SVM classifiers on a nonlinearly
separable dataset. On the left, using a low C value the margin is quite large, but many
instances end up on the street.
 Margin violations occur when a data
point is either on the wrong side of the
margin or not far enough from the
Soft Margin Classification decision boundary.
On the right, using a high C value the classifier makes fewer margin
violations but ends up with a smaller margin. However, it seems likely that
the first classifier will generalize better: even on this training set it makes
fewer prediction errors since most of the margin violations are on the
correct side of the decision boundary.
Example Code
Equations
In these equations, β
(beta) represents the
coefficients or weights
of the respective
features X1, X2,…, Xp
 Non-linear SVM Classifier
• Although linear SVM classifiers are
efficient and work surprisingly well in many
cases, many datasets are not even close
to being linearly separable.
• One approach to handling nonlinear
datasets is to add more features, such as
polynomial features (as you did in Chapter
4); in some cases, this can result in a
linearly separable dataset.
Polynomial Features
• Polynomial features are features created by raising existing features to
an exponent.
• For example, if a dataset had one input feature X, then a polynomial
feature would be the addition of a new feature (column) where values
were calculated by squaring the values in X, e.g. X^2.
• This process can be repeated for each input variable in the dataset,
creating a transformed version of each.
• The “degree” of the polynomial is used to control the number of features
added, e.g. a degree of 3 will add two new variables for each input
variable. Typically a small degree is used such as 2 or 3.
Non-linear SVM Classifier
Consider the left plot in Figure 5-5: it represents a simple dataset with just
one feature x1. This dataset is not linearly separable. But if you add a
second feature x2 = (x1)^2, the resulting 2D dataset is perfectly linearly
separable.
Polynomial Kernel
• Adding polynomial features is simple to implement and can work great.
• At a low polynomial degree, it cannot deal with very complex datasets.
• At high polynomial degrees, it creates a huge number of features, making
the model too slow.
• When using SVMs you can apply an almost miraculous mathematical
technique called the kernel trick.
• It makes it possible to get the same result as if you added many
polynomial features, even with very high degree polynomials, without So,
to add them.
• So, there is no combinatorial explosion of the number of features since
you don’t add any features.
Equation
ϕ(x) is the transformation
function
Polynomial Kernel
Adding Similarity Features
• Another technique to tackle nonlinear problems is to add features computed using a
similarity function that measures how much each instance resembles a particular
landmark.
• For example, let’s take the one-dimensional dataset discussed earlier and add two
landmarks to it at x1 = –2 and x1 = 1 (see the left plot in Figure 5-8).
Adding Similarity Features
• Next, let’s define the similarity function to be the Gaussian Radial Basis
Function (RBF) with γ = 0.3 (see Equation 5-1).
Adding Similarity Features
• It is a bell-shaped function varying from 0 (very far away from the
landmark) to 1 (at the landmark). Now we are ready to compute the new
features.
• For example, let’s look at the instance x1 = –1: it is located at Therefore,
from the first landmark and 2 from the second landmark.
Adding Similarity Features
• Therefore, its new features are x2 = exp (–0.3 × 1^2 ) ≈ 0.74 and x3 =
exp (–0.3 × 2^2 ) ≈ 0.30. The plot on the right of Figure 5-8 shows the
trans‐ formed dataset (dropping the original features). As you can see, it
is now linearly separable.
Step by step example
Step by step example
Step by step example
How to select a landmark
• You may wonder how to select the landmarks.
• The simplest approach is to create a landmark at the location of each and
every instance in the dataset.
• This creates many dimensions and thus increases the chances that the
transformed training set will be linearly separable.
• The downside is that a training set with m instances and n features gets
transformed into a training set with m instances and m features
(assuming you drop the original features).
• If your training set is very large, you end up with an equally large number
of features.
Gaussian RBF kernel
Computational Complexity
• The LinearSVC class is based on the liblinear library, which implements
an optimized algorithm for linear SVMs.
• It does not support the kernel trick, but it scales almost linearly with the
number of training instances and the number of features.
• Its training time complexity is roughly O(m × n).
• The algorithm takes longer if you require a very high precision. This is
controlled by the tolerance hyperparameter ϵ (called tol in Scikit-Learn).
• In most classification tasks, the default tolerance is fine.
Computational Complexity
• The SVC class is based on the libsvm library, which implements an
algorithm that supports the kernel trick.
• The training time complexity is usually between O(m^2 × n) and O(m^3 ×
n).
• Unfortunately, this means that it gets dreadfully slow when the number of
training instances gets large (e.g., hundreds of thousands of instances).
• This algorithm is perfect for complex but small or medium training sets.
• However, it scales well with the number of features, especially with
sparse features (i.e., when each instance has few nonzero features).
• In this case, the algorithm scales roughly with the average number of
nonzero features per instance.
Computational Complexity
SVM Regression
• As we mentioned earlier, the SVM algorithm is quite versatile: not only
does it support linear and nonlinear classification, but it also supports
linear and nonlinear regression.
• The trick is to reverse the objective: instead of trying to fit the largest
possible street between two classes while limiting margin violations, SVM
Regression tries to fit as many instances as possible on the street while
limiting margin violations (i.e., instances on‰
the street).
• The width of the street is controlled by a hyperparameter ϵ (epsilon).
SVM Regression
• Figure 5-10 shows two linear SVM Regression models trained on some
random linear data, one with a large margin (ϵ = 1.5) and the other with a
small margin (ϵ = 0.5).
SVM Regression
Decision Function and Predictions
• The linear SVM classifier model predicts the class of a new instance x by
simply computing the decision function w^Tx + b = w1x1 + ⋯ + wnxn + b:
if the result is positive, the predicted class ŷ is the positive class (1), or
else it is the negative class (0);
The dashed lines represent
the points where the
decision function is equal
to 1 or –1: they are parallel
and at equal distances to
the decision boundary,
forming a margin around
it. Training a linear SVM
classifier means finding the
value of w and b that make
this margin as wide as
possible while avoiding
margin violations (hard
margin) or limiting them
(soft margin).
Training Objective
• Consider the slope of the decision function: it is equal to the norm of the
weight vector, ∥w∥. If we divide this slope by 2, the points where the
decision function is equal to ±1 are going to be twice as far away from the
decision boundary. In other words, dividing the slope by 2 will multiply the
margin by 2. Perhaps this is easier to visualize in 2D in Figure 5-13. The
smaller the weight vector w, the larger the margin.
Training Objective
• So we want to minimize ∥w∥ to get a large margin. However, if we want to
avoid any margin violation (hard margin), we need the decision function
to be greater than 1 for all positive training instances, and lower than –1
for negative training instances. If we define t(i)= –1 for negative instances
(if y(i)=0) and t(i)=1 for positive instances (if y(i) =1), then we can express
this constraint as t(i)(w^Tx(i)+ b) ≥ 1 for all instances. We can therefore
express the hard margin linear SVM classifier objective as the
constrained optimization problem in Equation 5-3.
Training Objective
• To get the soft margin objective, we need to introduce a slack variable
ζ(i)≥0 for each instance: ζ(i) measures how much the ith instance is
allowed to violate the margin. We now have two conflicting objectives:
making the slack variables as small as possible to reduce the margin
violations and making ½w^T(w) as small as possible to increase the
margin. This is where the C hyperparameter comes in: it allows us to
define the trade‐off between these two objectives. This gives us the
constrained optimization problem in Equation 5-4.
Quadratic Programming
• The hard margin and soft margin problems are both convex quadratic
optimization problems with linear constraints. Such problems are known
as Quadratic Programming (QP) problems.
Convex functions
have a unique global
minimum, making
optimization easier
and more reliable.

Linear constraints ensure

that the data points are
correctly classified, and the
margin requirements are
met.
The Dual problem
• Given a constrained optimization problem, known as the primal problem,
it is possible to express a different but closely related problem, called its
dual problem. The solution to the dual problem typically gives a lower
bound to the solution of the primal problem, but under some conditions it
can even have the same solutions as the primal problem. Luckily, the
SVM problem happens to meet these conditions,6 so you can choose to
solve the primal problem or the dual problem; both will have the same
solution. The αi are
Lagrange
multipliers, which t(i)​ and t(j) are the class
appear in the labels (either +1 or -1).
dual problem. x(i)T ​xj​ is the dot
product between two
feature vectors xi and xj
The Dual Problem

• The dual problem is faster to solve than the primal when the number of
training instances is smaller than the number of features. More
importantly, it makes the kernel trick possible, while the primal does not.
Kernel Trick
• The kernel trick allows us to compute the inner product of two vectors
in the higher-dimensional space without ever actually computing the
transformation of the data points into that space.
• Instead of applying a feature transformation ϕ(x) to a data point x, we use
a kernel function K(x,x′) that directly computes the inner product between
two points x and x′ as if they were mapped to the higher-dimensional
space:
Kernelized SVM
• Suppose you want to apply a 2nd-degree polynomial transformation to a
two dimensional training set (such as the moons training set), then train a
linear SVM classifier on the transformed training set.
Kernelized SVM
Kernelized SVM
Kernelized SVM
Kernelized SVM
Online SVMs
• Online learning method for Support Vector Machines (SVMs), which
uses Gradient Descent (specifically Stochastic Gradient Descent or
SGD) to update the model incrementally as new data comes in.

• The first sum in the cost function will push the model to have a small
weight vector w, leading to a larger margin.
Online SVMs
• Online learning method for Support Vector Machines (SVMs), which
uses Gradient Descent (specifically Stochastic Gradient Descent or
SGD) to update the model incrementally as new data comes in.
Margin violations
occur when a data
point is either on
the wrong side of
the margin or not far
enough from the
decision boundary.
• The second sum computes the total of all margin violations. An instance’s
margin violation is equal to 0 if it is located off the street and on the
correct side, or else it is proportional to the distance to the correct side of
the street. Minimizing this term ensures that the model makes the margin
violations as small and as few as possible.