Support Vector Machines

Support Vector Machine

• Supervised Machine Learning
• Classification and Regression
• Geometry based interpretation
• Default – Binary classification
 Perceptron Revisited: Linear Separators

• Binary classification can be viewed as the task of

separating classes in feature space:
wTx + b = 0
wTx + b > 0
wTx + b < 0

f(x) = σ (wTx + b)
 Linear Separators

• Which of the linear separators is optimal?

 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
𝝅𝟏 That separates two classes
𝝅𝟐
Q. Which one to select?
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
𝝅𝟏 That separates two classes
𝝅𝟏
Q. Which one to select?

𝝅𝟏
Slight change will result in misclassification of points
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
That separates two classes
𝝅𝟏
Q. Which one to select?

𝝅𝟏
Slight change will result in misclassification of points

Misclassified Points
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
𝝅𝟐 That separates two classes
𝝅𝟐
Q. Which one to select?

𝝅𝟐
Slight change will not affect much
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
𝝅𝟐 That separates two classes

Q. Which one to select?

𝝅𝟐
Slight change will not affect much

NO misclassified Points
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
That separates two classes

Q. Which one to select?

Select hyperplane that separates two class points

where points are as far away as possible to the
hyperplane
 Support Vector Machine

Geometric interpretation
For given data we can draw different hyperplanes
𝝅𝟏 That separates two classes
𝝅𝟐
Q. Which one to select?

Hence 𝝅𝟐 is better choice than 𝝅𝟏

For 𝝅𝟐 points are far away as compare to 𝝅𝟏

Support Vector Machine

𝝅 Margin Maximizing hyperplane

Take any plane 𝝅
Support Vector Machine

𝝅+𝝅 Margin Maximizing hyperplane

Take any plane 𝝅

Take another plane + parallel to 𝝅

Support Vector Machine

𝝅+𝝅 Margin Maximizing hyperplane

Take any plane 𝝅

Take another plane + parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅+ 𝝅
Margin Maximizing hyperplane
Take any plane 𝝅

Take another plane 𝝅+ parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine
𝝅+
𝝅 Margin Maximizing hyperplane
Take any plane 𝝅

Take another plane 𝝅+ parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

Take any plane 𝝅

Take another plane 𝝅+ parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

Take any plane 𝝅

Take another plane 𝝅+ parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

𝝅−
Take any plane 𝝅

Take another plane 𝝅− parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

𝝅−
Take any plane 𝝅

Take another plane 𝝅− parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

𝝅−
Take any plane 𝝅

Take another plane 𝝅− parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

𝝅− Take any plane 𝝅

Take another plane 𝝅− parallel to 𝝅

Move in the direction of points till it touches
at least one point
Support Vector Machine

𝝅 Margin Maximizing hyperplane

𝝅− Margin(𝒅 ) = distance between 𝝅+ and 𝝅−
Parallel lines/planes/hyperplanes have same
coefficients but intercept is different

Note: distance between 𝝅+ and 𝝅− is same

𝒅
Support Vector Machine
𝝅 𝝅−
𝝅+
Margin Maximizing hyperplane

Margin(𝒅 ) = distance between 𝝅+ and 𝝅−

Parallel lines/planes/hyperplanes have same
coefficients but intercept is different

Note: distance between 𝝅+ and 𝝅− is same

𝒅
Support Vector Machine
𝝅 𝝅−
𝝅+
If hyperplane 𝝅 is closer to the data points then
Case 1 marginal distance is small

𝒅
Support Vector Machine

Case 2 𝝅+
If hyperplane 𝝅 is farther to the data points then
𝝅 marginal distance is large
𝝅−

𝒅
Support Vector Machine
Case 2 𝝅+
𝝅 𝝅− 𝝅
𝝅+
Case 1 𝝅−

𝒅
Support Vector Machine

Case 2 𝝅+
Problem: Find a hyperplane 𝝅 such that marginal
𝝅 distance is maximum
𝝅− 𝝅 is margin maximizing separating plane

𝝅+ is +ve plane in direction of w

𝝅− is -ve plane in opposite direction of w

𝒅
Support Vector Machine
𝝅+
𝝅 𝝅+: 𝑾𝑻𝒙 + 𝒃 = +𝒌
𝝅− 𝝅 ∶ 𝑾𝑻𝒙 + 𝒃 = 𝟎
𝝅−: 𝑾𝑻𝒙 + 𝒃 = −𝒌

Note1: as all lines are parallel only intercept is varied

W vector (coefficients) remains same for all lines
Note2: W vector is perpendicular to all three planes
𝒅
 Support Vector Machine
𝝅+ Distance between two parallel lines?
𝝅 𝝅+: 𝑾𝑻𝒙 + 𝒃 = +𝒌
𝑷 𝝅 ∶ 𝑾𝑻𝒙 + 𝒃 = 𝟎
𝝅−
𝝅−: 𝑾𝑻𝒙 + 𝒃 = −𝒌
𝑨
𝑨𝑩 = 𝑷𝑩 − 𝑷𝑨

𝑾 𝑻𝑷 + 𝒃 + 𝒌 𝑾 𝑻𝑷 + 𝒃 − 𝒌
𝑨𝑩 = −
𝑩 𝑾 𝑾
𝒅
𝒌 − (−𝒌) 𝟐𝒌
𝑨𝑩 = =
𝑾 𝑾
 Support Vector Machine
𝝅+ Distance between two parallel lines?
𝝅 𝝅+: 𝑾𝑻𝒙 + 𝒃 = +𝟏
𝑷 𝝅 ∶ 𝑾𝑻𝒙 + 𝒃 = 𝟎
𝝅−
𝝅−: 𝑾𝑻𝒙 + 𝒃 = −𝟏
𝑨
𝑨𝑩 = 𝑷𝑩 − 𝑷𝑨
𝟏 − (−𝟏) 𝟐
𝑨𝑩 = =
𝑾 𝑾
𝑩
𝒅
For simplicity lets say k=1
 Support Vector Machine
𝝅+ Distance between two parallel lines?
𝝅 𝟐𝒌
𝑷 𝑨𝑩 = 𝒅 =
𝑾
𝝅−
𝐎𝐩𝐭𝐢𝐦𝐢𝐳𝐚𝐭𝐢𝐨𝐧 𝐏𝐫𝐨𝐛𝐥𝐞𝐦: Find w, b such that
𝑨 Marginal distance will be maximum

2𝑘 2
𝑊 ∗ , 𝑏∗ = max = 𝑘 × max
𝑤, 𝑾 𝑤, 𝑾
𝑩 𝑏 𝑏
𝒅
 Support Vectors

• Find the line that maximizes the

minimum margin.
• This maximum-margin separator is
determined by a subset of the data
points.
– called “support vectors”.
– we use the support vectors to
decide the separator line.
The support vectors are
indicated by the circles
around them.

33
 Classification Margin

• Distance from point xi to the separator is denoted by r.

• Data points closest to the hyperplane are support vectors.
• Margin d of the separator is the distance between support vectors
of two classes.
d
r
 Maximum Margin Classification
• Maximizing the margin is good for more confidence for
correct classification.
• Implies that only support vectors matter; other training
examples are ignorable.
 Non-linear Separators

• Datasets that are linearly separable with some noise work out great:

0 x

• But what are we going to do if the dataset is just too hard?

0 x

• How about… mapping data

2
to a higher-dimensional space:
x

0 x
 Non-linear Separator: Feature spaces
• General idea: the original feature space can always be mapped to
some higher-dimensional feature space where the training set is
separable:

Φ: x → φ(x)
 SVM Main Idea

1. Start with data in a relatively low dimension.

2. Move the data into higher dimension.
3. Find support vector classifier that separates the
higher dimensional data into two groups.
 Introduction

• SVM is a powerful supervised algorithm that works best on

smaller and complex datasets.
• An efficient learning algorithms for non-linear functions based
on computational learning theory developed
• Basic idea of support vector machines: just like 1- layer or
multi-layer neural nets
–Optimal hyperplane for linearly separable patterns
–Extend to patterns that are not linearly separable by
transformations of original data to map into new space – the
Kernel function
What is a Support Vector Machine?
• It is a supervised machine learning problem where
we try to find a hyperplane that best separates the
two classes.
• Does SVM and logistic regression are same??
– Both the algorithms try to find the best hyperplane
– Logistic regression is a probabilistic approach
– Whereas, SVM is based on statistical approaches.
 Linear Separators
• Now the question is which hyperplane does it select?

• There can be an infinite number of hyperplanes passing through a point

and classifying the two classes perfectly. So, which one is the best?
• SVM does this by finding the maximum margin between the
hyperplanes that means maximum distances between the two classes.
 Types of Support Vector Machine
Linear SVM
• When the data is perfectly linearly separable .
• Perfectly linearly separable means data points can be
classified into 2 classes by using a single straight line(if
2D).

Non-Linear SVM
• When the data is not linearly separable.
• Which means when the data points cannot be separated
into 2 classes by using a straight line (if 2D).
• We use kernel tricks to classify them.
 Few Definitions

Support Vectors
• These are the points that are closest to the hyperplane.
• A separating line will be defined with the help of these data
points.

Margin
• it is the distance between the hyperplane and the observations
closest to the hyperplane (support vectors).
• In SVM large margin is considered a good margin.
• There are two types of margins hard margin and soft
margin.
 SVM Working?

• SVM is defined in terms of the support vectors only.

• No need to worry about other observations since the margin is
made using the points which are closest to the hyperplane
(support vectors).
 SVM Working?
Example:
• Suppose we have a dataset that has two classes (green and blue). We
want to classify that the new data point as either blue or green.
• To classify these points, we can have many decision boundaries,
but the question is which is the best and how do we find it?
 SVM Working?
Example:
• The best hyperplane is that plane that has the maximum distance
from both the classes.
• This is done by finding different hyperplanes which classify the
labels in the best way then it will choose the one which is farthest
from the data points or the one which has a maximum margin.
 Mathematical Intuition behind Support
Vector Machine
Dot-Product
• vector is a quantity that has magnitude as well as direction
• multiplication of vectors which can be done in two ways, dot
product, and cross product.
• dot product is used to get a scalar value as a resultant whereas
cross-product is used to obtain a vector again.
 Mathematical Intuition behind Support
Vector Machine
Dot-Product
• The dot product can be defined as the projection of one vector
along with another.

A . B = |A| cosθ * |B|

Where |A| cosθ is the projection of A on B

And |B| is the magnitude of vector B

In SVM, we need the projection of A not the magnitude of B.

To get the projection we can simply take the unit vector of B;
because it will be in the direction of B but its magnitude will be 1.
Hence the equation becomes: A.B = |A| cosθ * unit vector of B
 Mathematical Intuition behind Support
Vector Machine
Use of Dot Product in SVM:
Consider a random point X and we want to know whether it lies on the right
side of the plane or the left side of the plane (positive or negative).
 Mathematical Intuition behind Support
Vector Machine
Use of Dot Product in SVM:
To find it, first we assume this point is a vector (X) and then we make a vector
(w) which is perpendicular to the hyperplane. Let’s say the distance of vector
w from origin to decision boundary is ‘c’. Now we take the projection of X
vector on w.
 Mathematical Intuition behind Support
Vector Machine
Use of Dot Product in SVM:
We already know that projection of any vector or another vector is called dot-
product. Hence, we take the dot product of x and w vectors to make the
decision.

There can be infinite points on the boundary to measure the distance from X,
therefore the perpendicular vector w to the hyperplane is considered to
measure the distance.
 Margin in Support Vector Machine

• The equation of a hyperplane is w.x+b=0

where w is a vector normal to hyperplane and
b is an offset.
 Margin in Support Vector Machine-Definitions
To classify a point as negative or positive we need to define a decision
rule. We can define decision rule as:
Define the hyperplanes H such that:
w•xi+b >= +1 when yi =+1
H1
w•xi+b <= -1 when yi = –1
H0
H1 and H2 are the planes: H2 d+
H1: w•xi+b = +1 d-
H
H2: w•xi+b = –1
• The points on the planes H1 and H2
are the tips of the Support Vectors
• The plane H0 is the median in
between, where w•xi+b =0
d+ = the shortest distance to the closest positive point
d- = the shortest distance to the closest negative point
The margin of a separating hyperplane is [(d+) + (d–)].
 Margin in Support Vector Machine-Definitions
Now we need (w,b) such that the margin has a maximum distance d.

• To calculate ‘d’ we need the equation of L1 and L2.

• For this, we will take few assumptions that the equation of
L1 is w.x+b=1 and for L2 it is w.x+b=-1.
 Margin in Support Vector Machine-Definitions

We have L1 is w.x+b=1 and for L2 it is w.x+b=-1.

1. Why the magnitude is equal, why didn’t we take 1 and -2?

2. Why did we take 1 and -1, why not any other value like 24 and -100?
 Margin in Support Vector Machine-Definitions
1. We want our plane to have equal distance from both the classes that
means L should pass through the center of L1 and L2 that’s why we take
magnitude equal.

2. Let’s say the equation of our hyperplane is 2x+y=2, we observe that

even if we multiply the whole equation with some other number, the line
doesn’t change (try plotting on a graph). Hence for mathematical
convenience, we take it as 1.
 Moving a support vector
moves the decision
boundary

Moving the other vectors

has no effect

The optimization algorithm to generate the weights proceeds in such a

way that only the support vectors determine the weights and thus the
boundary.
 Optimization function and its constraints

In order to get optimization function, there are few constraints to

consider-
• The constraint is- “We’ll calculate the distance (d) in such
a way that no positive or negative point can cross the
margin line”.
Let’s write these constraints mathematically:

Now, try to simplify these two constraints into 1

• We assume that negative classes have y=-1 and positive
classes have y=1
Optimization function and its constraints cont..
• We can say that for every point to be correctly classified this
condition should always be true:

• we need to maximize (d) such that this constraint holds true.

Optimization function and its constraints cont..
• Lets take 2 support vectors, 1 from the negative class and
2nd from the positive class.
• The distance between these two vectors x1 and x2 will be (x2-
x1) vector.
• We need to find out the shortest distance between these two
points using dot product.
• We take a vector ‘w’ perpendicular to the hyperplane and then
find the projection of (x2-x1) vector on ‘w’.

Note: this perpendicular vector should be a unit vector then only

this will work. To make this ‘w’ a unit vector we divide this with
the norm of ‘w’.
Optimization function and its constraints cont..
Optimization function and its constraints cont..
• We know how to find the projection of a vector on another vector
using the dot-product.

• Since x2 and x1 are support vectors and they lie on the hyperplane,
hence they will follow yi* (w.x+b)=1 so we can write it as:
 Optimization function and its constraints
• Putting equations (2) and (3) in equation (1) we get:

• Hence the equation which we have to maximize is:

• This is the optimization function for perfectly linearly separable

data, which is unrealistic.

• This is called as Hard Margin SVM.

Soft Margin SVM
 Support Vector Machine
𝝅+ Lets allow our model to make few mistakes
𝝅 Find plane/hyperplane such that all positive points
Are above 𝝅+and all negative points are below𝝅−
𝝅−
Here 4 points (1, 2, 3, 4) are not in appropriate position

Signed distance
4 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓
3
2
2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓

1 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = 𝟎. 𝟓
𝟐
4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓
 Support Vector Machine
𝝅+ Lets allow our model to make few mistakes
𝝅 Find plane/hyperplane such that all positive points
Are above 𝝅+and all negative points are below𝝅−
𝝅−
Here 4 points (1, 2, 3, 4) are not in appropriate position

Signed distance
4 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓
3
2
2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓

1 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = 𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓
𝟐
4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓
 Support Vector Machine
𝝅+ Lets allow our model to make few mistakes
𝝅 Find plane/hyperplane such that all positive points
Are above 𝝅+and all negative points are below𝝅−
𝝅−
Here 4 points (1, 2, 3, 4) are not in appropriate position

Signed distance
4 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
3
2
2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊

1 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = 𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
𝟐
4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
 Support Vector Machine
𝝅+ Signed distance
𝝅 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
𝝅− 2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = 𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊

4
3 Lets focus one point at a time
2

𝟐 1
Support Vector Machine
𝝅+ Signed distance
𝝅 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = − 0.5 as it is in opposite direction of w

Point 1 is supposed to be above 𝝅+

1
Support Vector Machine
𝝅+ Signed distance
𝝅 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = − 0.5 as it is in opposite direction of w

Point 1 is supposed to be above 𝝅+

But it is 1.5 distance away from 𝝅+ in wrong direction

1
Support Vector Machine
𝝅+ Signed distance
𝝅 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = − 0.5 as it is in opposite direction of w

Point 1 is supposed to be above 𝝅+

But it is 1.5 distance away from 𝝅+in wrong direction
This is what 𝜻𝒊 telling us 
1
Support Vector Machine
𝝅+ Signed distance
𝝅 1 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟎. 𝟓 = 𝟏 − 𝟏. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = − 0.5 as it is in opposite direction of w

𝜻𝒊 
How far point is from correct plane in incorrect direction

1 Is 1.5 distance away from correct plane 𝝅+in opposite direction

1
𝝅+ Signed distance
𝝅 2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = −1.5 as it is in opposite direction of w

Point 1 is supposed to be above 𝝅+

2
Support Vector Machine
𝝅+ Signed distance
𝝅 2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = −1.5 as it is in opposite direction of w

Point 2 is supposed to be above 𝝅+

2 But it is 2.5 distance away from 𝝅+ in wrong direction
Support Vector Machine
𝝅+ Signed distance
𝝅 2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = −1.5 as it is in opposite direction of w

Point 2 is supposed to be above 𝝅+

2 But it is 2.5 distance away from 𝝅+in wrong direction
This is what 𝜻𝒊 telling us 
Support Vector Machine
𝝅+ Signed distance
𝝅 2 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = −1.5 as it is in opposite direction of w

𝜻𝒊 
How far point is from correct plane in incorrect direction
2
2 Is 2.5 distance away from correct plane 𝝅+in opposite direction
Support Vector Machine
𝝅+ Signed distance
𝝅 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = +𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +0.5 as it is in opposite direction of w

Point 1 is supposed to be above 𝝅+

3
Support Vector Machine
𝝅+ Signed distance
𝝅 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = +𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +0.5 as it is in opposite direction of w

Point 3 is supposed to be above 𝝅+

3
But it is 0.5 distance away from 𝝅+ in wrong direction
Support Vector Machine
𝝅+ Signed distance
𝝅 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = +𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +0.5 as it is in opposite direction of w

Point 3 is supposed to be above 𝝅+

3 But it is 0.5 distance away from 𝝅+in wrong direction
This is what 𝜻𝒊 telling us 
Support Vector Machine
𝝅+ Signed distance
𝝅 3 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = +𝟎. 𝟓 = 𝟏 − 𝟎. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = +1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +0.5 as it is in opposite direction of w

𝜻𝒊 
3 How far point is from correct plane in incorrect direction

3 Is 0.5 distance away from correct plane 𝝅+in opposite direction

 Support Vector Machine
𝝅+ Signed distance
𝝅 4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = −1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +1.5 as it is in opposite direction of w

Point 4 is supposed to be below 𝝅−

4
 Support Vector Machine
𝝅+ Signed distance
𝝅 4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = −1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +1.5 as it is in opposite direction of w

Point 4 is supposed to be below 𝝅−

4
But it is 2.5 distance away from 𝝅+ in wrong direction
 Support Vector Machine
𝝅+ Signed distance
𝝅 4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = −1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +1.5 as it is in opposite direction of w

Point 4 is supposed to be above 𝝅−

4
But it is 2.5 distance away from 𝝅−in wrong direction
This is what 𝜻𝒊 telling us 
 Support Vector Machine
𝝅+ Signed distance
𝝅 4 𝒚𝒊 𝑾𝑻𝒙𝒊 + 𝒃 = −𝟏. 𝟓 = 𝟏 − 𝟐. 𝟓 = 𝟏 − 𝜻𝒊
𝝅−
Positive point 𝑦𝑖 = −1
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑑𝑖 = +1.5 as it is in opposite direction of w

𝜻𝒊 
4
How far point is from correct plane in incorrect direction

4 Is 2.5 distance away from correct plane 𝝅−in opposite direction

 Support Vector Machine

𝜻𝒊 = 𝟎 𝝅+
𝜻𝒊 = 𝟎 If points are in appropriate region then 𝜻𝒊 = 𝟎
𝝅
If point is correctly classified then 𝜻𝒊 = 𝟎
𝝅−

𝜻𝒊 = 𝟎

𝜻𝒊 = 𝟎

𝜻𝒊 = 𝟎

𝜻𝒊 = 𝟎
 Support Vector Machine
𝝅+
If points are Not in appropriate region then 𝜻𝒊 ≠ 𝟎
𝝅
If point is misclassified then 𝜻𝒊 ≠ 𝟎
𝝅−

As 𝜻𝒊 increases point moves farther away from

𝜻𝒊 = 𝟎. 𝟓 Correct hyperplane in incorrect direction
𝜻𝒊 = 𝟐. 𝟓

As we want to allow our model to make some mistake

𝜻𝒊 = 𝟐. 𝟓
Lets modify our original formulation!

𝜻𝒊 = 𝟏. 𝟓
 Support Vector Machine
𝝅+ 𝜁𝑖 = 0 𝑖𝑓 𝑦𝑖 (𝑊𝑇 𝑥𝑖 + 𝑏) ≥ 1
𝝅
Point is correctly classified
𝝅−
𝜻𝒊 = 𝟎

𝜁𝑖 > 0 𝑖𝑓 𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 < 1

𝜻𝒊 = 𝟐. 𝟓 Point is misclassified

𝜻𝒊 = 𝟎
 Support Vector Machine
𝝅+ Original Formulation: Convert from maximization
𝝅 to minimization
2
𝝅− 𝑤 ∗ , 𝑏∗ = max
𝜻𝒊 = 𝟎 𝑤, 𝑊
𝑏

𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡, 𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 ≥ 1
𝜻𝒊 = 𝟐. 𝟓
𝑊
𝑤 ∗ , 𝑏∗ = min
𝑤, 2
𝑏

𝜻𝒊 = 𝟎 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡, 𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 ≥ 1
 Support Vector Machine
𝝅+ New optimization Problem
𝝅
𝑛
𝑊 1
𝝅− 𝑤 ∗ , 𝑏∗ = min + 𝐶 ∑ 𝜁𝑖
𝜻𝒊 = 𝟎 𝑤, 2 𝑛
𝑏 𝑖
=1
𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡,
𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 ≥ 1 − 𝜁𝑖 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖′𝑠
𝜻𝒊 = 𝟐. 𝟓
𝜁𝑖 ≥ 0

𝜻𝒊 = 𝟎
 Support Vector Machine
𝝅+ New optimization Problem Marginal distance
𝝅
𝑛
𝑊 1
𝝅− 𝑤 ∗ , 𝑏∗ = min + 𝐶 ∑ 𝜁𝑖
𝜻𝒊 = 𝟎 𝑤, 2 𝑛
𝑏 𝑖
=1
𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡,
𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 ≥ 1 − 𝜁𝑖 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖′𝑠
𝜻𝒊 = 𝟐. 𝟓
𝜁𝑖 ≥ 0

𝜻𝒊 = 𝟎
 Support Vector Machine
𝝅+ New optimization Problem Allowed Error
𝝅
𝑛
𝑊 1
𝝅− 𝑤 ∗ , 𝑏∗ = min + 𝐶 ∑ 𝜁𝑖
𝜻𝒊 = 𝟎 𝑤, 2 𝑛
𝑏 𝑖
=1
𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡,
𝑦𝑖 𝑊 𝑇 𝑥 𝑖 + 𝑏 ≥ 1 − 𝜁𝑖 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖′𝑠
𝜻𝒊 = 𝟐. 𝟓
𝜁𝑖 ≥ 0

𝜻𝒊 = 𝟎 Here C is a hyperparameter
 Soft Margin SVM
• In real-life applications we don’t find any dataset which is linearly
separable, what we’ll find is either an almost linearly separable
dataset or a non-linearly separable dataset.

• In this scenario, we can not use the above equation.

• Lets modify the above equation in such a way that it allows few
misclassifications that means it allows few points to be wrongly
classified.

• We know that max[f(x)] can also be written as min[1/f(x)], it is

common practice to minimize a cost function for optimization
problems; therefore, we can invert the function.
 Soft Margin SVM
• To make a soft margin equation we add 2 more terms to this equation
which is zeta and multiply that by a hyperparameter ‘c’

• For all the correctly classified points, zeta will be equal to 0 and for
all the incorrectly classified points the zeta is the distance of that
particular point from its correct hyperplane.

• So we can say that SVM Error = Margin Error + Classification

Error. The higher the margin, the lower would-be margin error, and
vice versa.
 Soft Margin SVM
Example:-
• Let’s say you take a high value of ‘c’ =1000, this would mean that
you don’t want to focus on margin error and just want a model which
doesn’t misclassify any data point.

• which is a better model, the one where the margin is maximum and
has 2 misclassified points or the one where the margin is very less,
and all the points are correctly classified?
 Soft Margin SVM

• There’s no correct answer to this question, rather we can use

SVM Error = Margin Error + Classification Error to justify this.
• If you don’t want any misclassification in the model then you can
choose figure 2. That means we’ll increase ‘c’ to decrease
Classification Error.
• If you want your margin should be maximized then the value of ‘c’
should be minimized.
• That’s why ‘c’ is a hyperparameter and we find the optimal value of
‘c’ using GridsearchCV and cross-validation.
Kernel Tricks in SVM
 Non-linear Separators

• Datasets that are linearly separable with some noise works out great:

0 x

• What if data-points are too hard to linearly separate?

0 x

• How about… mapping data

2
to a higher-dimensional space:
x

0 x
 Non-linear Separator: Feature spaces
• General idea: the original feature space can always be mapped to
some higher-dimensional feature space where the training set is
separable:

Φ: x → φ(x)
 How to make a plane curved
• Fitting hyperplanes as a
separators is mathematically easy.
It requires a linear operation.

• By replacing the raw input

variables with larger set of
features, we get a property:
– A planar separator in the high-
dimensional space of feature
vectors is a curved separator
in the low dimensional space A planar separator in a
of the raw input variables. 20-D feature space
projected back to the
original 2-D space
 A potential problem and a magic solution
• If we map the input vectors into a very high-dimensional feature
space, surely the task of finding the maximum-margin separator
becomes computationally difficult.
– Linear operations will be required, but the vectors have
large number of components.
– So taking the scalar product of two vectors is very
expensive.
• The way to keep things tractable is to use
“the kernel trick”
 What the kernel trick achieves
• All of the computations that we need to do to find the maximum-
margin separator can be expressed in terms of scalar products
between pairs of data-points (in the high-dimensional feature
space).

• These scalar products are the only part of the computation that
depends on the dimensionality of the high-dimensional space.

• The kernel trick is just a magic way of doing scalar products faster
than is usually possible.
– It relies on choosing a way of mapping to the high-dimensional
feature space that allows fast scalar products.
 The kernel trick
• For many mappings from a
low-D space to a high-D Low-D
space, there is a simple b
x
operation on two vectors in xa
the low-D space that can be
used to compute the scalar
product of their two images

in the high-D space.
High-D

K ( x a , x b )   ( x a ) . ( x b )
 ( xa )
Letting the doing the scalar  ( xb )
kernel do product in the
the work obvious way
 The kernel trick
• Suppose we have a dataset as below:

• we cannot draw a single line or say hyperplane which can classify the points
correctly.
• So, converting this lower dimension space to a higher dimension space
using some quadratic functions, allow us to find a decision boundary that
clearly divides the data points.
• These functions which help us do this are called Kernels and which kernel
to use is purely determined by hyper-parameter tuning.
The kernel trick
 Different Kernel functions
1. Polynomial kernel
Following is the formula for the polynomial kernel:

Here d is the degree of the polynomial, which can be manually

specified.
• Suppose we have two features X1 and X2 and output variable
as Y, so using polynomial kernel we can write it as:

We need to find X12 , X22 and X1.X2.

2 dimensions got converted into 5 dimensions.
 Different Kernel functions
1. Polynomial kernel
Example:
 Different Kernel functions
2. Sigmoid kernel
We can use it as the proxy for neural networks.
Equation is as below:

It simply takes input data points and map them to a value of 0 and 1,
so that they can be separated by a simple straight line.
 Different Kernel functions
3. Radial Basis Function (RBF) kernel
• It creates the non-linear combinations of features to lift samples
points into a higher-dimensional feature space.
• Now, a linear decision boundary can be used to separate these
points.
• It is the most used kernel in SVM classifications, the following
formula explains it mathematically:

where,
1. ‘σ’ is the variance, a hyperparameter in this case
2. ||X₁ – X₂|| is the Euclidean Distance between two points X₁
and X₂
 Different Kernel functions
3. RBF kernel
• Example
 Different Kernel functions
4. Bessel function kernel
5. Anova Kernel

How to choose the right Kernel?

- Depends on the kind of dataset.
- For linearly separable dataset one should use linear kernel function.
Suggest the Kernel Function
Suggest the Kernel Function
RBF
Suggest the Kernel Function
Suggest the Kernel Function
RBF
 Performance
• Support Vector Machines work very well in practice.
– The user must choose the kernel function and its parameters,
but the rest is automatic.
– The test performance is very good.

• They can be expensive in time and space for big datasets

– We need to store all the support vectors.

• SVM’s are very good if you have no idea about what structure to
impose on the task.

• The kernel trick can also be used to do PCA in a much higher-

dimensional space, thus giving a non-linear version of PCA in the
original space.
Advantages of SVM
1. SVM works better when the data is Linear.
2. It is more effective in high dimensions.
3. With the help of the kernel trick, we can solve any complex problem.
4. SVM is not sensitive to outliers.
5. Can help us with Image classification.

Disadvantages of SVM
1. Choosing a good kernel is not easy.
2. It doesn’t show good results on a big dataset.
3. Hyper-parameter tuning is difficult.