Support Vector Machine
IIT Ropar
MA515: Foundations of Data Science
November 2023
A Hyperplane
A p-dimensional hyperplane is defined as
β0 + β1 X1 + β2 X2 + . . . + βp Xp = 0 (1)
● In a p-dimensional space, a hyperplane is a flat affine subspace of dimension
p − 1.
● In 2-d, a hyperplane is a line, while in 3-d, a hyperplane is a plane.
● Given a vector X = (X1 , X2 , . . . , Xp )T ,
▸ if Equation (1) holds, X is a point on the hyperplane.
▸ If Equation (1) holds, X doesn’t fall on the hyperplane: it must fall on one side
of the hyperplane or the other depending upon the sign of the left hand side of
the Equation (1)
1/16
Our Goal: Classification using hyperplane
Consider n training observations x1 , x2 , . . . , xn in p-dimensional space
(xi = (xi1 , xi2 , . . . , xip ) ∈ Rp ), where each of these observations fall into two classes,
or y1 , . . . , yn ∈ {−1, 1} where −1 represents one class and 1 represents the other.
● Assume we restrict ourselves to linear decision boundaries (hyperplane)
● Assume the data are linearly separable, i.e., a separating hyperplane exists
Properties of such a hyperplane
β0 + β1 xi1 + β2 xi2 + . . . + βp xip < 0 if yi = −1 (2)
and
β0 + β1 xi1 + β2 xi2 + . . . + βp xip > 0 if yi = 1. (3)
Idea
If there is a separating hyperplane, it can be employed to build a classifier that
categorizes a test observation into a class based on the side of the hyperplane
where the observation is situated. Specifically, given a test observation,
x∗ = (x1∗ , x2∗ , . . . , xp∗ ), we can assign it to class 1 if f (x∗ ) is positive and to class -1
if f (x∗ ) is negative, where
f (x∗ ) = β0 + β1 x1∗ + β2 x2∗ + . . . + βp xp∗ . (4)
2/16
Which separating hyperplane would you pick?
● If data can be perfectly separated with a hyperplane, there exists infinitely
many such hyperplanes.
● To create a classifier, we must choose one from the infinite options.
Feature 2
Feature 1
3/16
Maximal Margin Classifier
Key concept: Margin
The margin is the distance from the hyperplane to the closest point.
Idea Take the one with the largest margin
Why? If we slightly change the training set, the number of misclassifications will
stay low
The maximal margin classifier
The separating hyperplane for which the margin is largest—that is, it is the
hyperplane that has the farthest minimum distance to the training observations.
4/16
Maximal Margin Classifier: Example
Figure 1: The margin is the distance from the solid line to either of the dashed lines
indicated by arrows (Figure from the book “An Introduction to Statistical Learning with
Applications in R”)
5/16
How to construct the Maximal Margin Classifier
Key concept: Perpendicular distance of a point x from the hyperplane in Equation
(1) is given by
β0 + β1 xi1 + β2 xi2 + . . . + βp xip
p
∑j=1 βj2
The maximal margin hyperplane is the solution to the following optimization
problem
max M
β0 ,β1 ,...,βp
subject to
p
2
∑ βj = 1,
j=1
yi (β0 + β1 xi1 + β2 xi2 + . . . + βp xip ) ≥ M ∀i = 1, 2, . . . , n,
The two constraints actually ensure that each observation is on the correct side of
the hyperplane and at least a distance M (margin) from the hyperplane. The
optimization problem chooses β0 , β1 , . . . , βp that maximizes M.
6/16
Support Vector Classifier
Till now, we assumed that the data are linearly separable, i.e., a separating
hyperplane exists.
Question: What if that is not the case?
In such case, there is no maximal margin classifier, i.e., there is no solution to the
optimization problem in the previous slide with M > 0.
Figure 2: Data not separable by a hyperplane (Figure from the book “An Introduction to
7/16
Support Vector Classifier
Another limitation of the Maximal Margin Classifier is it’s sensitivity to individual
observations.
How to tackle such cases? Support Vector Classifier
Idea? Identify a hyperplane that almost separates the classes.
● We allow some observations to be on the incorrect side of the margin, or even
the incorrect side of the hyperplane (misclassification).
Figure 3: Left: observation on the wrong side of margin, Right: observation on the wrong
side of margin as well as the hyperplane (Figure from the book “An Introduction to
Statistical Learning with Applications in R”)
8/16
How to construct a Support Vector Classifier
Support Vector Classifier is the solution to the following optimization problem
max M
β0 ,β1 ,...,βp ,ϵ1 ,ϵ2 ,...,ϵn
subject to
p
2
∑ βj = 1,
j=1
yi (β0 + β1 xi1 + β2 xi2 + . . . + βp xip ) ≥ M(1 − ϵi ) ∀i = 1, 2, . . . , n,
n
ϵi ≥ 0, ∑ ϵi ≤ C
i=1
where C is a non-negative tuning parameter.
9/16
How to construct a Support Vector Classifier
Role of the slack variables ϵ1 , ϵ2 , . . . , ϵn Encode the location of the ith observation
relative to the hyperplane and relative to the margin.
The ith observation is
● on the correct side of the margin if ϵi = 0
● on the wrong side of the margin and is said to have violated the margin if ϵi > 0
● on the wrong side of the hyperplane if ϵi > 1
Role of the tuning parameter C defines the extent and seriousness of deviations
permitted within the margin and hyperplane. As C increases, the margin gets wider
and more tolerant of violation. As C decreases, the margin gets narrower.
● C = 0: no budget is available for violations (which means ϵi = 0, . . . , ϵn = 0, and
if solution exists, it is the same as the maximal margin classifier.
● C > 0, no more than C observations may be on the wrong side of the
hyperplane
How to choose C : Like other tuning parameters, C is generally selected using cross
validation.
10/16
Support Vector Classifier: Example
Figure 4: Support vector classifier for different values of C (Figure from the book “An
Introduction to Statistical Learning with Applications in R”) 11/16
Support Vector Classifier: Continued
● Figuring out the support vector classifier involves a bit of technicality.
● Surprisingly, the solution only depends on the inner-products of the
observations, not the actual observations.
The linear support vector classifier can be represented as
n
f (x) = β0 + ∑ αi ⟨x, xi ⟩
i=1
where there are n parameters, α1 , . . . , αn , one per training observation.
Estimation of the parameters α1 , . . . , αn and β0 requires the (n2) inner products
between all pairs of training observations.
12/16
Support Vector Classifier: Continued
It turns out that
● Only points on the margin or those violating it influence the hyperplane and,
consequently, the classifier.
● Points strictly on the correct side of the margin have no impact on the
classifier if their position remains unchanged.
● Observations directly on the margin or on the wrong side for their class are
termed “support vectors.”
Therefore, αi is zero for all observations except for the support vectors
Equivalently, the linear support vector classifier can be represented as
f (x) = β0 + ∑ αi ⟨x, xi ⟩
i∈S
where S is the collection of indices of these support vectors.
13/16
Non-Linear Decision Boundary: Support Vector Machine
Possible Way: Enlarge the feature space (map x to ϕ(x)) using functions of the
original features and obtain the support vector classifier.
Issue: Computations of inner products would become unmanageable if the enlarged
feature space has huge number of features
What next then? Kernels and Support Vector Machine
Idea: Replace the inner product ⟨xi , xj ⟩ every time it appears, by a generalization of
the inner product of the form K (xi , xj ) where K is some function, known as kernel.
The resulting classifier is known as a support vector machine,
f (x) = β0 + ∑ αi K (x, xi )
i∈S
14/16
Kernels
A kernel is a function that quantifies the similarity of two observations.
Examples
● Linear Kernel
p
K (xi , xj ) = ∑ xik xjk
k=1
(equivalent to the support vector classifier)
● Polynomial Kernel
p
K (xi , xj ) = (1 + ∑ xik xjk )d
k=1
where d is a positive integer. (Equivalent to fitting a support vector classifier
in a higher dimensional space involving polynomials of degree d, instead of the
original feature space.)
● Gaussian Kernel or Squared Exponential Kernel
p
K (xi , xj ) = exp (−γ ∑ (xik − xjk )2 )
k=1
where γ is a positive constant. (the corresponding feature space ϕ(x) is
infinite dimensional.)
15/16
Reference
16/16