Support Vector Machine

Classification and Regression

Support Vector Machine 1 / 40

Equation of Line, 2D Plane and
Hyperplane

Support Vector Machine 2 / 40

Equation of Line

Slope-Intercept Form y
m = slope
y = mx + c
where y = mx + c
m : Slope
c : Y-intercept
It can also be written as c

y = β0 + β1 x x
where

β1 = m, β0 = c

Support Vector Machine 3 / 40

General Form of a Line
The general equation of a line is

ax + by + c = 0
Because every straight line in a 2D plane can be written in the above form.
Rearranging,

by = −ax − c
Dividing by b,

a c
y =− x−
b b
Comparing with

y = mx + c,
we obtain

a c
m=− , c=−
b b
Support Vector Machine 4 / 40
Equation of a Plane (Decision Boundary)
For two input features x1 and x2 , the linear equation becomes
w1 x1 + w2 x2 + b = 0 where
w1 and w2 = weight corresponding to feature x1 and x2
b = bias (intercept)
This equation represents a straight line in a two-dimensional feature space.
w1 x1 + w2 x2 + b = 0 or equivalently, x2 = − w b
w2 x1 − w2 Hence,
1

w1
Slope = − w 2
, Intercept = − wb2 .
x2

x1

Support Vector Machine 5 / 40

Hyperplane Equation and Representation
General Hyperplane Equation
For an n-dimensional feature space,

w1 x1 + w2 x2 + · · · + wn xn + b = 0
or equivalently,

wT x + b = 0
where    
w1 x1
w2  x2 
w= .  x=.
   
 ..   .. 
wn xn
The dot product is
wT x = w1 x1 + w2 x2 + · · · + wn xn
Support Vector Machine 6 / 40
 x3
w
Hyperplane

x1

x2

wT x + b = 0
Interpretation
A hyperplane is a flat decision boundary that divides the feature space into
two regions or classes. The vector w is perpendicular (normal) to the
hyperplane, while b determines its position relative to the origin. The
hyperplane acts as the decision boundary in machine learning algorithms
such as Logistic Regression, Perceptron, and Support Vector Machines.
Support Vector Machine 7 / 40
Hyperplane Representation

Hyperplane in Different Dimensions

Dimension Equation Representation

1-D w1 x + b = 0 Point
2-D w1 x1 + w2 x2 + b = 0 Line
3-D w1 x1 + w2 x2 + w3 x3 + b = 0 Plane
n-D wT x + b = 0 Hyperplane

Key Points
w is called the weight (coefficient) vector.
x is the feature vector.
b is the bias (intercept).
A hyperplane is an (n − 1) dimensional flat surface that divides an
n-dimensional feature space into two regions.
Support Vector Machine 8 / 40
Geometric Representation of a Hyperplane
x2
w1 x1 + w2 x2 + b = 0

For two features,

w1 x1 + w2 x2 + b =
0 represents a Straight Line
x1
x3
For three features, Plane
w1 x1 + w2 x2 + w3 x3 + b =
0 represents a Plane
x1
x2
In Support Vector Machine, our objective is not just to find any
hyperplane, but to find the optimal hyperplane that best separates the two
classes by maximizing the margin
Support Vector Machine 9 / 40
Normal Vector of a Hyperplane

The hyperplane is

wT x + b = 0
The vector w

w
90◦
is called the Normal Vector
because it is perpendicular to the
hyperplane.
For any point x on the hyperplane, Hyperplane
wT x + b = 0.
The shortest distance from any point to
the hyperplane is measured along the
direction of the normal vector w.

Support Vector Machine 10 / 40

Distance Between a Point and a Hyperplane

Hyperplane wT x + b = 0
Point  w
x0
x01
x02  d
x0 =  . 
 
 .. 
x0n
The perpendicular distance is In SVM, the perpendicular
|wT x0 +b| distance is computed for every
d = ∥w∥
q training point from the decision
where ∥w∥ = w12 + w22 + · · · + wn2 . boundary. The nearest points are
If wT x0 + b > 0, the point lies on the called support vectors, and they
positive side. determine the position of the
If wT x0 + b < 0, the point lies on the optimal hyperplane.
negative side.

Support Vector Machine 11 / 40

Support Vector Machine (SVM)
Definition
A Support Vector Machine (SVM) is a supervised machine learning
algorithm used for both classification and regression.
Its primary objective is to find the optimal separating hyperplane that
maximizes the distance (margin) between different classes.

Mainly used for binary classification

Uses support vectors (critical data
points) to find the maximum
margin hyperplane.
Among all possible separating
hyperplanes, SVM selects the one
that leaves the largest possible
margin between the two classes,
Decision Boundary
leading to better generalization on
unseen data.
Support Vector Machine 12 / 40
Why Do We Need Support Vector Machines?
Suppose we have a binary classification problem.
A linearly separable dataset may have infinitely many separating
hyperplanes.
Although all hyperplanes correctly classify the training data, they do
not provide the same generalization performance.

Which hyperplane should we choose?

x2
× × ×
× × ×
×
H2
H1
H3

◦ ◦ ◦
◦ ◦ ◦
◦
x1
Support Vector Machine 13 / 40
Which Hyperplane is the Best?

All three hyperplanes correctly classify the training data.

However, their ability to classify unseen data differs.
Support Vector Machine (SVM) selects the hyperplane with the
maximum margin.
This principle is called the Maximum Margin Classifier.

Support Vector Machine 14 / 40

Maximum Margin Hyperplane

The maximum margin hyperplane is equidistant from the nearest training

samples of both classes.

Support Vector Machine 15 / 40

Linearly Separable Data

Blue circles belong to Class +1

Red squares belong to Class -1
Many separating lines are possible.
SVM chooses the one with the maximum margin.

Support Vector Machine 16 / 40

Equation of the Margin Hyperplanes

The two margin hyperplanes are

wT x + b = 1
and

wT x + b = −1
The decision boundary lies exactly midway between them.

wT x + b = 0
Hence,

Margin Width = Distance between the two margin hyperplanes.

Support Vector Machine 17 / 40

Hyperplane Equation
For an n-dimensional feature space,

wT x + b = 0

where    
w1 x1
w2   x2 
w =  . , x =.
   
 ..   .. 
wn xn

f (x) = w T x + b
Decision rule

f (x) > 0 ⇒ +1

f (x) < 0 ⇒ −1
Support Vector Machine 18 / 40
Functional Margin
Suppose the class labels are
yi ∈ {−1, +1}
For correct classification,
yi (w T xi + b) > 0
SVM scales the parameters since there are infinitely many values of w and
b that represent the same decision boundary. so
yi (w T xi + b) ≥ 1
Hence, Positive support hyperplane
wT x + b = 1
Negative support hyperplane
w T x + b = −1
Decision boundary
wT x + b = 0
Support Vector Machine 19 / 40
Derivation of Margin
Distance from a point to a hyperplane

|w T x + b|
d=
||w ||

Distance from the support hyperplane w T x + b = 1 to the decision

boundary w T x + b = 0 is
1
∥w ∥
1
Similarly, distance from w T x + b = −1 to w T x + b = 0 =
∥w ∥
Therefore,
2
Margin =
||w ||

Support Vector Machine 20 / 40

Optimization Problem
Maximum margin
2
max
||w ||
is equivalent to

min ||w ||
For mathematical convenience,

1
min ||w ||2
2
subject to

yi (w T xi + b) ≥ 1
This is called the Primal Optimization Problem.
Support Vector Machine 21 / 40
Need for Lagrange Multipliers

SVM is a constrained optimization problem. The objective is to

minimize
1
∥w ∥2
2
while satisfying the constraint

yi (w T xi + b) ≥ 1, i = 1, 2, . . . , n.

Since ordinary differentiation cannot handle constraints directly, the

Lagrange Multiplier Method combines the objective function and the
constraints into a single Lagrangian function, which can then be
optimized using differentiation.

Support Vector Machine 22 / 40

Using Lagrange Multipliers

Objective:
1
min ∥w ∥2
2
Constraint:
yi (w T xi + b) ≥ 1, i = 1, 2, . . . , n
Introduce a Lagrange multiplier αi ≥ 0 for each constraint and combine the
objective and constraints into the Lagrangian:
n
1 X 
∥w ∥2 − αi yi (w T xi + b) − 1

L(w , b, α) =
2
i=1

min max L(w , b, α)

w ,b α≥0

Result: Minimize with respect to w , b and maximize with respect to αi to obtain

the optimal maximum-margin hyperplane.

Support Vector Machine 23 / 40

Derivative with Respect to w

Take partial derivative

∂L
=0
∂w
Therefore,
X
w− αi y i x i = 0
i

Hence,
X
w= αi y i x i
i

The weight vector is a linear combination of training samples.

Support Vector Machine 24 / 40

Derivative with Respect to b

Take derivative

∂L
=0
∂b
X
− αi yi = 0
i

Hence,
X
αi y i = 0
i

This is another optimization constraint.

Support Vector Machine 25 / 40

Dual Optimization Problem (Step 1)

Substitute
X
w= αi y i x i
i

into the Lagrangian

1 X X
L = wT w − αi yi w T xi + αi
2
i i

Since
X
αi yi = 0,
i

the term containing b becomes zero.

Support Vector Machine 26 / 40

Dual Optimization Problem (Step 2)

Compute
!T  
X X
wT w = αi y i x i  αj yj xj 
i j
XX
= αi αj yi yj xiT xj
i j

Similarly,
X XX
αi yi w T xi = αi αj yi yj xiT xj .
i i j

Substitute these expressions into the Lagrangian.

Support Vector Machine 27 / 40

Dual Optimization Problem (Step 3)
The Lagrangian becomes
1 XX XX X
L= αi αj yi yj xiT xj − αi αj yi yj xiT xj + αi
2
i j i j i

Simplifying,
X 1 XX
L= αi − αi αj yi yj xiT xj
2
i i j

Hence, the dual optimization problem is

 
X 1 X X
max  αi − αi αj yi yj xiT xj 
α 2
i i j

subject to
X
αi ≥ 0, αi yi = 0.
i

Support Vector Machine 28 / 40

Constraints of the Dual Optimization Problem
The dual optimization problem is subject to constraints αi ≥ 0
m
X
αi y i = 0
i=1

Interpretation of the Constraints

αi ≥ 0:
Every Lagrange multiplier must be zero or positive.
If αi = 0, the corresponding training sample does not influence the
classifier.
If αi > 0, the corresponding training sample becomes a support
vector.
m
X
αi yi = 0:
i=1
Balances the contributions of the positive and negative classes.
Ensures that the resulting hyperplane correctly separates the two
classes.
Support Vector Machine 29 / 40
Dual Optimization Problem

After solving the dual optimization problem,

The primal optimization problem is transformed into the dual
optimization problem.
The optimization is performed only over the Lagrange multipliers αi .
Only training samples with
αi > 0
become the support vectors.
The support vectors determine the position of the optimal
separating hyperplane.
The dual formulation depends only on the inner products

xiT xj ,

which enables the use of kernel functions for non-linear classification.

Support Vector Machine 30 / 40

Decision Function
We know, X
w= αi y i x i
i
Only points with
αi > 0
are called Support Vectors. Classifier
X
f (x) = αi yi xiT x + b
i

Prediction
ŷ = signum(f (x))


 +1, if f (x) > 0,

signum(f (x)) = 0, if f (x) = 0,


−1, if f (x) < 0.


Support Vector Machine 31 / 40

Hard Margin Support Vector Machine
Hard Margin SVM assumes that the dataset is perfectly linearly separable.
x2
× × × × ×

◦ ◦ ◦ ◦
x1

Characteristics
No misclassification allowed.
Works only for perfectly separable datasets.
Very sensitive to noise and outliers.
Support Vector Machine 32 / 40
Limitation of Hard Margin SVM

Real-world datasets usually contain noisy observations.

× × × ×

◦ ◦ ◦ ◦

A single noisy point may make the data non-separable.

Hence, Hard Margin SVM fails.

Support Vector Machine 33 / 40

Soft Margin Support Vector Machine

Soft Margin SVM allows a few samples to violate the margin.

Instead of enforcing

yi (w T xi + b) ≥ 1,
it introduces a slack variable

ξi ≥ 0
which measures the degree of margin violation.
Soft Margin provides better generalization for noisy datasets.

Support Vector Machine 34 / 40

Slack Variables in Soft-Margin SVM

Soft-Margin SVM Constraint

 
yi w T xi + b ≥ 1 − ξ i , ξi ≥ 0

The slack variable measures how much a sample violates the margin.
Slack Variable (ξi )
ξi = 0 Correctly classified, on or outside the margin
0 < ξi < 1 Correctly classified, inside the margin.
ξi = 1 On the decision boundary.
A larger value of ξi indicates a greater violation of the margin.
Slack variables allow SVM to tolerate noisy or overlapping data while
still maximizing the margin.

Support Vector Machine 35 / 40

Soft Margin Optimization

The optimization problem becomes

n
!
1 X
min ||w ||2 + C ξi
2
i=1

Subject to

yi (w T xi + b) ≥ 1 − ξi
where

ξi ≥ 0.
The first term maximizes the margin.
The second term penalizes classification errors.

Support Vector Machine 36 / 40

Meaning of Parameter C

The parameter C controls the trade-off between Large margin and

Training accuracy
Large Margin: Better Generalization and allow few classification.
Small Margin: High training accuracy and more prone to overfitting.

Large C → Less misclassifications

Small C → Larger margin

Support Vector Machine 37 / 40

Hinge Loss Function

Unlike Logistic Regression, SVM uses the Hinge Loss.

L = max(0, 1 − yf (x))
where

f (x) = w T x + b.
Properties
Zero loss for correctly classified samples outside the margin.
Positive loss for samples inside the margin.
Linear penalty for misclassified samples.

Support Vector Machine 38 / 40

Hard Margin vs Soft Margin

Hard Margin Soft Margin

Perfectly separable data Noisy data
No misclassification Allows misclassification
Sensitive to outliers Robust to outliers
No slack variables Uses slack variables
Limited practical use Widely used in practice

Support Vector Machine 39 / 40

Summary

Hard Margin SVM assumes perfectly separable data.

Soft Margin SVM introduces slack variables.
Parameter C controls the trade-off between margin and classification
error.
Hinge Loss is the objective function used by SVM.
Soft Margin SVM is preferred in most practical applications.

Support Vector Machine 40 / 40