Module 3: Support

Vector Machine (SVM)

Dr. Amrita Sarkar
Support Vector Machine (SVM)
Algorithm
• Support Vector Machine (SVM) is a supervised machine learning
algorithm used for classification and regression tasks.
• It tries to find the best boundary known as hyperplane that separates different
classes in the data.
• It is useful when you want to do binary classification like spam vs. not spam or
cat vs. dog.
• The main goal of SVM is to maximize the margin between the two classes.
• The larger the margin the better the model performs on new and unseen data.
Support Vector Machine (SVM)
Support Vector Machine (SVM)
Support Vector Machine (SVM)
Key Concepts of Support Vector
Machine
• Hyperplane: A decision boundary separating different classes in feature
space and is represented by the equation wx + b = 0 in linear classification.
• Support Vectors: The closest data points to the hyperplane, crucial for
determining the hyperplane and margin in SVM.
• Margin: The distance between the hyperplane and the support vectors. SVM
aims to maximize this margin for better classification performance.
• Kernel: A function that maps data to a higher-dimensional space enabling
SVM to handle non-linearly separable data.
Key Concepts of Support Vector
Machine
• Hard Margin: A maximum-margin hyperplane that perfectly separates the
data without misclassifications.
• Soft Margin: Allows some misclassifications by introducing slack variables,
balancing margin maximization and misclassification penalties when data is
not perfectly separable.
• C: A regularization term balancing margin maximization and misclassification
penalties. A higher C value forces stricter penalty for misclassifications.
• Hinge Loss: A loss function penalizing misclassified points or margin
violations and is combined with regularization in SVM.
• Dual Problem: Involves solving for Lagrange multipliers associated with
support vectors, facilitating the kernel trick and efficient computation.
How does Support Vector Machine
Algorithm Work?
• The key idea behind the SVM algorithm is to find the hyperplane that best separates
two classes by maximizing the margin between them. This margin is the distance from
the hyperplane to the nearest data points (support vectors) on each side.
How does Support Vector Machine
Algorithm Work?
• The best hyperplane also known as the "hard margin" is the one that
maximizes the distance between the hyperplane and the nearest data points
from both classes.
• This ensures a clear separation between the classes.
• So from the above figure, we choose L2 as hard margin.
Let's consider a scenario like shown below:
• Here, we have one blue ball in the boundary of the red ball.
How does SVM classify the data?
• The blue ball in the boundary of red ones is an outlier of blue balls.

• The SVM algorithm has the characteristics to ignore the outlier and finds the best

hyperplane that maximizes the margin. SVM is robust to outliers.

How does SVM classify the data?
• A soft margin allows for some misclassifications or violations of the margin to
improve generalization.
• The SVM optimizes the following equation to balance margin maximization and
penalty minimization:

• The penalty used for violations is often hinge loss which has the following
behavior:

• If a data point is correctly classified and within the margin there is no

penalty (loss = 0).
• If a point is incorrectly classified or violates the margin the hinge loss
increases proportionally to the distance of the violation.
What if data is not linearly
separable?
• When data is not linearly separable i.e it can't be divided by a straight line,
SVM uses a technique called kernels to map the data into a higher-dimensional
space where it becomes separable.
• This transformation helps SVM find a decision boundary even for non-linear
data.
What if data is not linearly
separable?
• A kernel is a function that maps data points into a higher-dimensional space
without explicitly computing the coordinates in that space.
• This allows SVM to work efficiently with non-linear data by implicitly
performing the mapping. For example consider data points that are not
linearly separable.
• By applying a kernel function SVM transforms the data points into a higher-
dimensional space where they become linearly separable.
• Linear Kernel: For linear separability.
• Polynomial Kernel: Maps data into a polynomial space.
• Radial Basis Function (RBF) Kernel: Transforms data into a space based on
distances between data points.
What if data is not linearly
separable?
• In this case the new variable y is created as a function of distance from the
origin.
Mathematical Computation of SVM
• Consider a binary classification problem with two classes, labeled as +1 and -
1. We have a training dataset consisting of input feature vectors X and their
corresponding class labels Y. The equation for the linear hyperplane can be
written as:

• Where:
• is the normal vector to the hyperplane (the direction perpendicular to it).
• is the offset or bias term representing the distance of the hyperplane from the
origin along the normal vector .
Mathematical Computation of SVM
• Distance from a Data Point to the Hyperplane
The distance between a data point and the decision boundary can be calculated
as:

where ||w|| represents the Euclidean norm of the weight vector w.

Mathematical Computation of SVM
• Linear SVM Classifier
Distance from a Data Point to the Hyperplane:

Where is the predicted label of a data point.

Mathematical Computation of SVM
• Optimization Problem for SVM

For a linearly separable dataset the goal is to find the hyperplane that maximizes the

margin between the two classes while ensuring that all data points are correctly

classified. This leads to the following optimization problem:

Subject to the constraint:

Where:
• ​is the class label (+1 or -1) for each training instance.
• ​is the feature vector for the -th training instance.
• is the total number of training instances.
• The condition ensures that each data point is correctly classified and lies outside the
margin.
Types of Support Vector Machine
1. Linear SVM:
• Linear SVMs use a linear decision boundary to separate the data points of
different classes.
• When the data can be precisely linearly separated, linear SVMs are very
suitable.
• This means that a single straight line (in 2D) or a hyperplane (in higher
dimensions) can entirely divide the data points into their respective classes.
• A hyperplane that maximizes the margin between the classes is the decision
boundary.
Types of Support Vector Machine
2. Non-Linear SVM:
• Non-Linear SVM can be used to classify data when it cannot be separated into
two classes by a straight line (in the case of 2D).
• By using kernel functions, nonlinear SVMs can handle nonlinearly separable
data.
• The original input data is transformed by these kernel functions into a higher-
dimensional feature space where the data points can be linearly separated.
• A linear SVM is used to locate a nonlinear decision boundary in this modified
space.
Advantages of Support Vector
Machine (SVM)
• High-Dimensional Performance: SVM excels in high-dimensional spaces,
making it suitable for image classification and gene expression analysis.
• Nonlinear Capability: Utilizing kernel functions like RBF and polynomial SVM
effectively handles nonlinear relationships.
• Outlier Resilience: The soft margin feature allows SVM to ignore outliers,
enhancing robustness in spam detection and anomaly detection.
• Binary and Multiclass Support: SVM is effective for both binary
classification and multiclass classification suitable for applications in text
classification.
• Memory Efficiency: It focuses on support vectors making it memory efficient
compared to other algorithms.
Disadvantages of Support Vector Machine (SVM)

• Slow Training: SVM can be slow for large datasets, affecting performance in
SVM in data mining tasks.
• Parameter Tuning Difficulty: Selecting the right kernel and adjusting
parameters like C requires careful tuning, impacting SVM algorithms.
• Noise Sensitivity: SVM struggles with noisy datasets and overlapping
classes, limiting effectiveness in real-world scenarios.
• Limited Interpretability: The complexity of the hyperplane in higher
dimensions makes SVM less interpretable than other models.
• Feature Scaling Sensitivity: Proper feature scaling is essential, otherwise
SVM models may perform poorly.
Kernel Trick in Support Vector
Classification
• Support Vector Machines (SVMs) have proven to be a powerful and versatile
tool for classification tasks.
• A key component that significantly enhances the capabilities of SVMs,
particularly in dealing with non-linear data, is the Kernel Trick.
Linear vs Non-Linear Problems
• For linearly separable data, finding this hyperplane is straightforward.
• However, many real-world problems are non-linear, meaning that no linear
separation can perfectly divide the classes.
• This is where the kernel trick comes into play.
Concept of Feature Mapping
• To deal with non-linear data, one approach could be to map the input data into
a higher-dimensional space where it is linearly separable.
• This mapping involves transforming the data into a new space (feature space)
where the separation between the data points is clearer.
• For example, consider a set of data points that are not linearly separable in
two dimensions.
• By mapping these points into a three-dimensional space, we might find that they can be
separated by a plane in this higher-dimensional space.
What is the Kernel Trick?
• The kernel trick is a method used in SVMs to enable them to classify non-linear
data using a linear classifier.
• By applying a kernel function, SVMs can implicitly map input data into a
higher-dimensional space where a linear separator (hyperplane) can be used
to divide the classes.
• This mapping is computationally efficient because it avoids the direct
calculation of the coordinates in this higher space.
Types of Kernel Functions
Several kernel functions can be used, each suited to different types of data
distributions:

• Linear Kernel: No mapping is needed as the data is already assumed to be

linearly separable.
• Polynomial Kernel: Maps inputs into a polynomial feature space, enhancing the
classifier's ability to capture interactions between features.
• Radial Basis Function (RBF) Kernel: Also known as the Gaussian kernel, it is
useful for capturing complex regions by considering the distance between
points in the input space.
• Sigmoid Kernel: Mimics the behavior of neural networks by using a sigmoid
function as the kernel.
How Does the Kernel Trick Work?
• The kernel trick relies on the inner products of vectors.
• For SVMs, the decision function is based on the dot products of vectors within the input
space.
• Kernel functions replace these dot products with a non-linear function that computes a
dot product in a higher-dimensional space.
• Importantly, the computation of this dot product via the kernel function does not require
explicit knowledge of the coordinates in the higher space, thus saving computational
resources and time.
• The kernel trick is typically expressed as:

where,
• x and y are two vectors in the original input space
• is the mapping function to the higher-dimensional space.