Classification Algorithms:

Support Vector Machine (SVM)

Prof. A. G. Patil
TKIET, Warananagar
 Conceptual Overview
• A Support Vector Machine (SVM) is a supervised learning algorithm used for
classification and regression tasks.
• It constructs an optimal hyperplane in a high-dimensional feature space that
maximally separates data points of different classes.
• The goal is to find a decision boundary with the maximum margin.
• The margin is the perpendicular distance between the Decision Boundary (the hyperplane)
and the closest data points from either class. These closest points are known as Support
Vectors.
• The SVM algorithm's primary goal is to maximize this margin.
• A wider margin generally leads to better "generalization," meaning the model
will perform more accurately on new, unseen data because it isn't "crowding"
the training points.
• Only a subset of training points, called support vectors, influence the decision
boundary.
 Hyperplane and Optimal Hyperplane
• A hyperplane is simply a decision boundary that separates data
into different classes.
• In 2D → it is a line
• In 3D → it is a plane
• In higher dimensions → called a hyperplane
• For a linearly separable dataset with features 𝒙 and labels 𝒚 in
{−𝟏, 𝟏}, the hyperplane is defined by the equation:
• 𝒘⋅𝒙+𝒃=𝟎
• The classifier follows the decision rule:
• 𝑓 𝑥 = 𝑠𝑖𝑔𝑛 (𝒘 ⋅ 𝒙 + 𝒃 = 𝟎)
• Example:
• Imagine:
• Students classified as Pass (+1) and Fail (-1)
• Based on marks & attendance
• Feature 1 → Marks
• Feature 2 → Attendance
• Each student = one point on the graph
• In R2, a hyperplane = a line
• Feature 1 → Marks
• Feature 2 → Attendance
• Feature 3 → Study Hours
• In R3, a hyperplane = a plane
 Hyperplane and Optimal Hyperplane
• The optimal hyperplane is: • Small margin
• The line (or plane) that maximizes the • Sensitive to noise
distance from nearest points of both classes • Optimal Hyperplane:
• Why Optimal Hyperplane? • Equal distance from both classes
• Better generalization • Large margin
• Less chance of error on new data • More robust
• Example: Think => • Mathematical Meaning: max
2
• You draw multiple lines between two groups ∥𝑤∥
• The widest gap line is best → optimal
hyperplane • SVM chooses the hyperplane that
• The middle line = Optimal Hyperplane maximizes margin
1
• Parallel lines = Margins • Equivalent to: min | 𝑤 |2
2
• Distance between them = Maximum
Margin
• Bad Hyperplane:
• Too close to one class
R2 and R3 Optimized Hyperplane
 Mathematical Formulation
• Hyperplane Equation: For a dataset 𝐷 = 𝑥𝑖, 𝑦𝑖 𝑖 = 1 𝑡𝑜 𝑛
• where: 𝑥𝑖 ∈ ℝ: 𝐹𝑒𝑎𝑡𝑢𝑟𝑒 𝑣𝑒𝑐𝑡𝑜𝑟
• 𝑦𝑖 ∈ {−1, +1}: 𝐶𝑙𝑎𝑠𝑠 𝑙𝑎𝑏𝑒𝑙
• The hyperplane is defined as: 𝒘 ⋅ 𝒙 + 𝒃 = 𝟎
• Where:
• 𝑤: 𝑊𝑒𝑖𝑔ℎ𝑡 𝑣𝑒𝑐𝑡𝑜𝑟
• 𝑏: 𝐵𝑖𝑎𝑠 𝑡𝑒𝑟𝑚
2
• Margin Maximization: max𝑤, 𝑏
∥𝑤∥
• Maximizing margin is equivalent to minimizing
1
• SVM solves: Find 𝑤, 𝑏 such that :: min𝑤, 𝑏 | 𝑤 |2
2
• Subject to constraints: 𝑦𝑖(𝑤 ⋅ 𝑥𝑖 + 𝑏) ≥ 1
• This is the optimization objective of SVM. i.e. 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑖𝑛𝑔 𝑚𝑎𝑟𝑔𝑖𝑛 =
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑖𝑛𝑔 ∥ 𝑤 ∥
 Hard Margin vs. Soft Margin
• Hard Margin: Assumes the data is perfectly linearly separable. It strictly
enforces that no data points fall within the margin.
• Soft Margin: Introduced by Cortes and Vapnik (1995) to handle noisy
data.
• It uses a slack variable 𝝃 to allow some misclassifications or margin
violations, governed by a regularization parameter 𝐶
• min𝑤 , 𝑏 1 𝑤 2 + 𝐶 σ𝑛𝑖=1 𝝃𝑖 Subject to : 𝑦𝑖 𝑤 ⋅ 𝑥𝑖 + 𝑏 ≥ 1 − 𝝃𝑖 , 𝝃𝑖 > 0
2
• Where 𝝃𝑖 : error (slack) and ∁: penalty control
• High 𝐶: Prioritizes correct classification of all training points (narrow margin).
• Low 𝐶 : Prioritizes a larger margin, even if some points are misclassified (better
generalization).
 Kernel Trick (Non-Linear Classification)
• In the simplest terms, the Kernel Function is a mathematical "shortcut" that
allows the SVM to solve complex, non-linear problems as if they were simple,
linear ones.
• When data is not linearly separable, SVM uses kernel functions to map data
into higher dimensions: 𝐾(𝑥𝑖​, 𝑥𝑗) = 𝜙(𝑥𝑖) ⋅ 𝜙(𝑥𝑗)
• Kernel Function is a clever trick because it calculates the dot product (the
relationship) between two points in that high-dimensional space without ever
actually moving them there.
• Common Kernels:
• Linear: 𝐾(𝑥𝑖, 𝑥𝑗) = 𝑥𝑖 ⋅ 𝑥𝑗 When data is already separable by a straight line.
• Polynomial: (𝑥𝑖 ⋅ 𝑥𝑗 + 1)𝑑 For curved boundaries (like parabolas).
• RBF (Gaussian): 𝐾(𝑥𝑖, 𝑥𝑗) = exp(−𝛾 ∥ 𝑥𝑖 − 𝑥𝑗 ∥ 2)
• Sigmoid: 𝐾 𝑥𝑖 , 𝑥𝑗 = tanh(𝛼𝑥 ⋅ 𝑦 + 𝐶) Often used in neural networks.
 Decision Function
• The final classifier:
• 𝑓(𝑥) = 𝑠𝑖𝑔𝑛(σ𝑛𝑖=1 𝛼𝑖𝑦𝑖𝐾(𝑥𝑖, 𝑥) + 𝑏)
• 𝛼𝑖: Lagrange multipliers
• Only support vectors have 𝛼𝑖 > 0
• Computes which side of boundary point lies
• Output:
• +1 → Class A
• -1 → Class B
• For a New student:
• Input marks + attendance
• Model predicts → Pass or Fail
 Algorithm Steps
1. Input training data (𝑥𝑖, 𝑦𝑖)
2. Choose kernel function
3. Solve optimization problem (quadratic programming)
4. Identify support vectors
5. Construct decision boundary
6. Predict new data using decision function
Algorithm Steps: Visuals
 Simple Example Point (x1) (x2) Class (y)

A 2 2 +1
• Given Dataset:
B 4 4 +1
• Step 1: Plot the Data C 2 4 -1
• (+1 class): A, B D 4 2 -1
• (-1 class): C, D
• Step 2: Find a Separating Line
• We assume a linear hyperplane:
𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = 0
• From observation, a separating line is: 𝑥1 − 𝑥2 = 0
• So: 𝑤 = (1, −1) and 𝑏 = 0
• Step 3: Check Constraints
• Condition: 𝑦𝑖 (𝑤 ⋅ 𝑥𝑖 + 𝑏) ≥ 1
• Let’s verify:
• For 𝑨 (𝟐, 𝟐), 𝒚 = +𝟏 (1 ∗ 2 + (−1) ∗ 2) = 0
• Not ≥ 1 → needs scaling
• Step 4: Scale the Equation
• We scale to satisfy margin condition:
• Let: 𝑤 = (0.5, −0.5), 𝑏 = 0
• Now check: 𝑭𝒐𝒓 𝑨: 0.5(2) − 0.5(2) = 0
• Still not enough → adjust further
• Step 5: Correct Optimal Hyperplane
• A better separating boundary is: x1−x2=1
• Now test:
• 𝑭𝒐𝒓 𝑨 (𝟐, 𝟐), 𝒚 = +𝟏: 2 − 2 − 1 = −1 → 𝑦(−1) = +1 ✔
• 𝑭𝒐𝒓 𝑪 (𝟐, 𝟒), 𝒚 = −𝟏: 2 − 4 − 1 = −3 → 𝑦 −3 = +3 ✔
• Step 6: Identify Support Vectors
• Closest points:
• A (2,2)
• C (2,4)
• These are support vectors
• Step 7: Final Decision Function
𝑓(𝑥) = 𝑠𝑖𝑔𝑛(𝑥1 − 𝑥2 − 1)
• Step 8: Prediction Example
• For new point (3,2):
• 3 − 2 − 1 = 0 : On boundary
The sign() function (short for signum function)
• For (5,2):
is a simple mathematical operator that
• 5 − 2 − 1 = 2 > 0 Class = +1
extracts the "sign" or the direction of a real
• Final Answer (Exam Format) number.
• Hyperplane: 𝑥1 − 𝑥2 − 1 = 0 • If 𝑓(𝑥) = 0, the point lies exactly on the
line.
• Support Vectors: (2,2), (2,4) • If 𝑓(𝑥) > 0, the point lies on one side of
• Decision Function: the line (the "positive" side)
𝑓(𝑥) = 𝑠𝑖𝑔𝑛(𝑥1 − 𝑥2 − 1) • If 𝑓(𝑥) < 0, the point lies on the opposite
side (the "negative" side)
 SVM vs Random Forest
Feature SVM Random Forest

Type Margin-based classifier Ensemble learning

Idea Best separating line Voting of many trees

Data handling Works well in high dimension Works well with large data

Overfitting Low (controlled by margin) Very low (due to averaging)

Interpretability Low Medium

Speed Slow for large datasets Faster

Noise handling Sensitive Robust

Non-linearity Kernel trick Naturally handles

 Advantages & Disadvantages
• Advantages Effective in high-dimensional spaces
• Works well with clear margin separation
• Uses only support vectors → memory efficient
• Flexible via kernels
• Disadvantages
• Computationally expensive for large datasets
• Choice of kernel is critical
• Sensitive to noise (especially hard margin)
Applications
Thank You