Support Vector
Machine
Contents
Support Vector Machine
Support Vectors
Hard Margin
Linear Separability
SVM for Linear Classification
SVM for Non-linear Classification
Kernel SVM
Support Vector Machine
Supervised ML algorithm
Mostly used for Classification
Used for linear classification
Can also be used for non-linear classification –Kernel SVM
Application: text classification, image classification, spam detection,
handwriting identification, face detection, anomaly detection, etc.
Linearly Separable Data
Linearly Separable Data
• SVM helps us choose the best line or in general the best hyperplane that
segregates the data points.
Support Vector Machine
𝒙𝟐
• Objective: Find the optimal line in a 2D
space that can separate the data points
• Best hyperplane or line maximizes the
separation margin between the data
points
𝒙𝟏
Best Separating Hyperplane
𝒙𝟐
𝐿1
𝐿2
𝐿3
: Maximum-margin hyperplane/hard margin
The hyperplane whose distance from the
nearest data points on each side is maximum.
𝒙𝟏
Best Separating Hyperplane
𝒙𝟐
Select the hyperplane so that the Hard margin/
margin is maximized. Decision surface
Margin: The separation between the data
points of both classes 𝑑1
𝑑2
𝑑1=𝑑 2=𝑑 ⇒ 𝑑 1+ 𝑑 2=2 𝑑
Margin
𝒙𝟏
Support Vectors
𝒙𝟐
Decision surface
• Data points that lie closest to the
decision surface or hyperplane.
• Most difficult to classify.
𝑑
𝒙𝟏
Support Vectors
𝒙𝟐
New Decision
surface
• Support vectors have direct influence on
the optimum location of the decision
surface
𝑑𝑛𝑒𝑤
𝑑𝑛𝑒𝑤
𝒙𝟏
Support Vectors
𝒙𝟐
New
Decision
• Support vectors have direct Decision surface surface
influence on the optimum
location of the decision surface
𝒙𝟏
Mathematical Formulation:
Classification
Input SVM Target
Feature Output
Class 1 or class 2
( 1) (𝟐 ) (𝒎 )
𝑋=[ 𝐱 , 𝐱 , … , 𝐱 ]
𝐱 (𝒊 )=[𝑥 1 , 𝑥 2 , … , 𝑥𝑛 ] ( 𝑖)
y ∈ {+ 1 ,−1 }
Parameters: Set of weights, and bias
𝒘 =[𝑤 1 , 𝑤2 , …, 𝑤𝑛 ]
Mathematical Formulation:
Classification
𝒙𝟐
( 1) (𝟐 ) ( 𝟏𝟑 )
𝑋=[ 𝐱 , 𝐱 , … , 𝐱 ]
𝐱 (𝒊 )=[ 𝐱 (1𝒊 ) , 𝐱 (2𝒊 ) ]
or
𝒘 ={𝑤 1 , 𝑤2 }
𝒘 𝑇 𝐱 +𝑏=0 𝒙𝟏
Mathematical Formulation:
Classification
The SVM classifier can be defined as 𝒙𝟐
Decision function for binary
classification
𝑇
𝒘 𝐱 +𝑏=0 𝒙𝟏
Mathematical Formulation:
Classification
𝒙𝟐
(𝐢 )
The distance between data pointand the 𝐱
decision boundary
|𝒘 𝑇 𝐱 ( 𝐢) +𝑏| |𝒘 𝑇 𝐱( 𝐢 )+ 𝑏|
𝑑𝑖 = =
𝒘 𝒘
𝑇
‖𝒘‖2
Decision boundary
𝑇
𝒘 𝐱 +𝑏=0 𝒙𝟏
Mathematical Formulation:
Classification
𝒙𝟐
distance between and (𝐢 )
𝐱
𝒘 𝐱
‖𝒘‖2
‖𝒘‖2 𝒘 𝑇 𝒙 𝒊+𝑏 𝒙𝟏
⟹ 𝛼=(𝒘 ¿¿𝑇 𝒙¿¿ 𝒊+𝑏) 𝑇 = ¿¿
𝒘 𝒘 ‖𝒘‖2
Mathematical Formulation:
Classification
𝒙𝟐
𝒘
𝐱 (𝐢 ) − 𝐱 =𝜶 (𝐢 )
‖𝒘‖2 𝐱
(𝐢 )
𝑑𝑖 =¿ 𝐱 − 𝐱 ∨¿ 𝜶
‖ 𝒘
‖
‖𝒘‖2 2
=‖𝜶‖2 𝒘
‖𝒘‖2
𝐱
|𝒘 𝑇 𝐱 (𝐢 ) +𝑏|
⟹ 𝑑𝑖=
‖𝒘‖2
𝒙𝟏
Mathematical Formulation:
Classification
The objective of SVM is to find a decision line so that 𝒙𝟐
the distance of each data point from the decision
boundary will be very high.
Optimization problem.
But instead of considering all data points, the SVM
considers only difficult data points that is the
support vectors.
𝒙𝟏
Mathematical Formulation :
Classification
𝒙𝟐
Assumption: All data points are at a
distance larger than 1 from the hyperplane.
𝒙𝟏
Mathematical Formulation :
Classification
𝒙𝟐
(Hard margin)
= Distance of from the support vector corresponding to the
class
= Distance of from the support vector corresponding to the 𝐻1
class
𝒙𝟏
𝐻0 𝐻2
Mathematical Formulation :
Classification
𝒙𝟐
𝑑+¿ 𝑑 −=𝑑
𝑑+¿ 𝑑
1
𝑑𝑖 = 𝑑 −=d
‖𝒘 ‖2
2
⟹ 𝑀𝑎𝑟𝑔𝑖𝑛= 𝐻1
‖𝒘‖2
𝒙𝟏
𝐻0 𝐻2
Mathematical Formulation :
Classification
𝒙𝟐
2
𝑀𝑎𝑟𝑔𝑖𝑛= 𝒘 𝑇 𝐱 +𝑏=1
‖𝒘‖2
𝑇
Objective: Maximize the margin 𝒘 𝐱 +𝑏=−1
Minimize
𝑑
Minimize
𝑑
Condition: There are no data points between and
when
when
𝑇
𝑦 (𝒘 𝐱 +𝑏) ≥1 𝒙𝟏
𝑦 ( 𝒘 𝑇 𝐱 + 𝑏 ) −1 ≥ 0 𝒘 𝑇 𝐱 +𝑏=0
Mathematical Formulation :
Classification
Optimization problem:
Constrained optimization problem
Can be solved by the Lagrangian multiplier method
Optimal Parameter Calculation
Langrangian
With respect to and .
slack variables
Optimal Parameter Calculation
Solution: Find partial derivative wrt and b and equate to
Optimal Parameter Calculation
We have the Primal problem as
,
We got
∑𝑎
𝑚 (𝑖) (𝑖)
𝒘 =∑ 𝑎 𝑦 𝐱(𝑖) (𝑖) (𝐢)
and 𝑦 =0
𝑖=1 𝑖=1
Optimal Parameter Calculation
Langrange dual problem: Instead of minimizing subject to constraints
involving ’s, we can maximize over ’s, subject to
𝑚
𝒘 =∑ 𝑎 𝑦 𝐱 ( 𝑖) (𝑖 ) ( 𝐢)
𝑖=1
∑𝑎 (𝑖 ) (𝑖 )
𝑦 =0
𝑖 =1
Optimal Parameter Calculation
𝒙𝟐
𝑇
𝒘 𝐱 +𝑏=−1
Karush-Kuhn-Tucker (KKT) condition
𝑇
𝒘 𝐱 +𝑏=1
𝑎
(𝑖 )
( 𝑦 (𝑖 ) ( 𝒘 𝑇 𝐱 ( 𝐢 ) ,+𝑏 ) −1 ) =0
𝒙𝟏
𝒘 𝑇 𝐱 +𝑏=0
Optimal Parameter Calculation
Langrange dual problem:
𝑚 𝑚 𝑚 𝑚
1
max 𝐿 𝐷=¿ ∑ 𝑎 −(𝑖 )
∑ ∑ 𝑎(𝑖 ) 𝑎( 𝑗 ) 𝑦 ( 𝑖 ) 𝑦 ( 𝑗 ) ( 𝐱 (𝐢 ) . 𝐱 ( 𝐣 ) ) +𝑏 ∑ 𝑎( 𝑖 ) 𝑦 (𝑖 ) ¿
𝑖 =1 2 𝑖=1 𝑗 =1 i=1
s uch that ∑ 𝑎 (𝑖 ) 𝑦 ( 𝑖 )=0
𝑗 =1
and ,
Optimal Parameter Calculation
Langrange dual problem:
𝑚 𝑚 𝑚
1
max 𝐿 𝐷 =¿ ∑ (𝑖 )
𝑎 − ∑ ∑ 𝑎(𝑖 ) 𝑎( 𝑗 ) 𝑦 ( 𝑖 ) 𝑦 ( 𝑗 ) ( 𝐱 (𝐢 ) . 𝐱 ( 𝐣 ) ) ¿
𝑖 =1 2 𝑖=1 𝑗 =1
s uch that ∑ 𝑎 (𝑖 ) 𝑦 ( 𝑖 )=0
𝑗 =1
and ,
Optimal Parameter Calculation
Findby taking the derivative of wrt and equate it to zero.
Find the values of’s for all and compute optimal as
𝑚
𝒘 ∗ =∑ 𝑎 (𝑖 ) 𝑦 ( 𝑖 ) 𝐱 (𝐢 )
𝑖=1
𝑚
𝒘 ∗= ∑ 𝑎(𝑖 ) 𝑦 (𝑖 ) 𝐱 ( 𝐢 )
𝑖=1
(𝑖 )
𝑎 >0
Optimal Parameter Calculation
To compute optimal bias:
Computefor each support vector as
Optimal bias: Average ’s over all support vectors
𝑏∗ = avg { 𝑏( 𝑖 ) }
𝑎 ( 𝑖) >0
Inference
For a new data point
𝑚
𝒘 ∗= ∑ 𝑎( 𝑖) 𝑦 (𝑖 ) 𝐱 (𝐢 )
^𝑦 =sign(𝒘 ∗𝑇 𝐳 +𝑏∗ ) ¿𝑖 =1
( 𝑖)
¿𝑎 >0
(∑ )
𝑚
⇒^
𝑦 =sign (𝑖 ) ( 𝑖)
𝑎 𝑦 𝐱 . 𝐳 +𝑏 (𝐢) ∗
𝑏∗ = avg { 𝑏( 𝑖 ) }
𝑖 =1 𝑎 ( 𝑖) >0
Intuition behind the slack
variables
The first optimization problem
The Primal problem
Intuition behind the slack
variables
𝑚 𝑚
1
𝐿𝑝 = ‖𝒘‖ − ∑ 𝑎(𝑖 ) 𝑦 (𝑖 ) ( 𝒘 𝑇 𝒙 𝒊+𝑏 ) + ∑ 𝑎(𝑖 )
2 2 𝑖=1 𝑖=1
𝑚
1
⇒ 𝐿𝑝 = ‖𝒘‖ − ∑ ¿ ¿
2 2 𝑖=1
Intuition behind the slack
variables
𝑚
1
𝐿𝑝 = ‖𝒘‖ − ∑ ¿ ¿
2 2 𝑖 =1
Consider
Intuition behind the slack
variables
Term 1 can be either or a positive value, i.e.,
Support Vector Machine for Not-
linearly Separable Data
𝒙𝟐
Modify the objective function to solve the problem
𝒙𝟏
Support Vector Machine for Not-
linearly Separable Data
Previously
𝑦 ( 𝒘 𝑇 𝐱 + 𝑏 ) −1 ≥ 0
𝑦 𝒘 𝐱 +𝑏 ) ≥1, ∀ 𝑖
( 𝑇 (𝐢 )
(𝑖 )
Maximize the margin and get as many data points classified correctly as
possible.
Modified constraint
𝑦 (𝑖 ) ( 𝒘 𝑇 𝐱 (𝐢 ) +𝑏 ) ≥1 − 𝜉 𝑖 , ∀ 𝑖
Support Vector Machine for Not-
linearly Separable Data
𝒙𝟐
Misclassified data points
𝜉3
𝜉4 𝜉2 𝜉5
Erroneous data points, within the margin
𝜉1
𝒙𝟏
Support Vector Machine for Not-
linearly Separable Data
𝑦 (𝑖 ) ( 𝒘 𝑇 𝐱 (𝐢 ) +𝑏 ) ≥1 − 𝜉 𝑖 , ∀ 𝑖
𝜉𝑖 ≥ 0 , ∀ 𝑖
𝑚
∑ 𝜉 𝑖 ≤ 𝐶𝑜𝑛𝑠𝑡𝑎𝑛𝑡
𝑖=1
Support Vector Machine for Not-
linearly Separable Data
Modified objective function
𝑚
𝒘 ∗= ∑ 𝑎( 𝑖) 𝑦 (𝑖 ) 𝐱 (𝐢 )
𝑏∗ = avg { 𝑏( 𝑖 ) }
¿𝑖 =1
( 𝑖)
¿𝑎 >0 𝑎 ( 𝑖) >0
Support Vector Machine for Not-
linearly Separable Data
Gain linearly separation by mapping the data to a higher dimensional space
Kernel SVM
Dual problem:
𝑚 𝑚 𝑚
1
max 𝐿 𝐷 =¿ ∑ 𝑎 (𝑖 )
− ∑∑ 𝑎(𝑖 ) 𝑎( 𝑗 ) 𝑦 ( 𝑖 ) 𝑦 ( 𝑗 ) ¿ ¿
𝑖 =1 2 𝑖=1 𝑗 =1
Kernel SVM
For a new data point
^
𝑦 = sign ¿
Kernel SVM
Polynomial Kernel
𝑑
1+ ⟨ 𝐱 , 𝐱 ⟩
(𝐢 ) (𝐣)
RBF Kernel
¿
ANN tanh Kernel
𝐾 1 ⟨ 𝐱 (𝐢 ) , 𝐱 ( 𝐣 ) ⟩ + 𝐾 2
Kernel SVM
Kernel SVM
References
1. NPTEL - Introduction to Machine Learning by Prof. Balaraman Ravindran, IIT
Madras [Link]
2. NPTEL - Machine Learning by Prof. Sudeshna Sarkar, IIT Kharagpur
[Link]
3. Machine Learning-McGraw-Hill Education (1997) BY Tom M. Mitchell
4. Burkov, Andriy. The hundred-page machine learning book. Vol. 1. Quebec
City, QC, Canada: Andriy Burkov, 2019.
5. Rogers, Simon, and Mark Girolami. A first course in machine learning.
Chapman and Hall/CRC, 2016.
Thank You