Support Vector Machine

Kritanta Saha
Assistant Professor
Dept. of Computer Science & Engineering
Sister Nivedita University
For Classification problem

Which line is better?

For Classification problem

Which line is better?

How to split data while separating line
How to split data while separating line
How to split data while separating line
How to split data while separating line
How to separate lines
How to separate lines
How to separate lines
How to separate lines
How to separate lines
How to separate lines
Expanding rate
Expanding rate
Expanding rate
Definition

● A Support Vector Machine (SVM) is a classifier defined by a

separating hyperplane.

● In other words, given labeled training data (supervised learning), the

algorithm outputs an optimal hyperplane which categorizes new
examples.

● In two dimensional space this hyperplane is a line dividing a plane in

two parts where in each class lay in either side.

● Our objective is to find a plane that has the maximum margin, i.e the
maximum distance between data points of both classes.
SVM: properties

● Data points falling on either side of the hyperplane can be attributed to different classes.

● Also, the dimension of the hyperplane depends upon the number of features.

● If the number of input features is 2, then the hyperplane is just a line.

● If the number of input features is 3, then the hyperplane becomes a two-dimensional plane.
Support Vectors
● Support vectors are data points that are closer to the hyperplane and influence the position and
orientation of the hyperplane.

● Using these support vectors, we maximize the margin of the classifier.

Large margin intuition

● In SVM, we take the output of the linear function and if that output is greater than
1, we identify it with one class and if the output is less than -1, we identify is with
another class.

● Since the threshold values are changed to 1 and -1 in SVM, we obtain this
reinforcement range of values([-1,1]) which acts as margin.
Previous Cost Function for logistic regression
For each example of Logistic regression
Modified Cost Function for SVM
For each example of Logistic regression
Modified Cost Function for SVM
For each example of Logistic regression
Cost Function
Cost Function
Now, if C is very large
then minimizing this
optimization
objective will make
first term equal to
zero.
SVM decision boundary
Objective becomes minimizing the norm of the square length of the parameter
vector theta.
SVM decision boundary
Objective becomes minimizing the norm of the square length of the
parameter vector theta.
Why SVM will maximize margin?
Why SVM will maximize margin?
Why SVM will maximize margin?
Why SVM will maximize margin?
Why SVM will maximize margin?

But should be small

Why SVM will maximize margin?

But should be small

Why SVM will maximize margin?

But should be small, so summation of p(i) should be large, i.e. the margin.
Lagrange duality
● Consider a constrained optimization problem:
● In this method, we define the Lagrangian to be:
● Here, the βi ’s are called the Lagrange multipliers.
We would then find and set L’s partial derivatives
to zero: and solve for w and β.
● We will generalize this to constrained optimization
problems in which we may have inequality as well
as equality constraints.
Lagrange duality
● Consider the following, which weʼll call
the primal optimization problem:
● To solve it, we start by defining the
generalized Lagrangian Here, the αi ʼs
and βi ʼs are the Lagrange multipliers.
● Consider the quantity: Here, the “P”
subscript stands for “primal.”
Lagrange duality
● Conversely, if the constraints are indeed satisfied for a particular value of
w, then θP(w) = f(w). Hence:
● Thus, θP takes the same value as the objective in our problem for all values
of w that satisfies the primal constraints, and is positive infinity if the
constraints are violated.
● Hence, if we consider the minimization problem we see that it is the same
problem
● We also define the optimal value of the objective to be
p∗ = minw θP(w); we call this the value of the primal problem.
Lagrange duality
● Now, letʼs look at a slightly different
problem. We define:
● Here, the “D” subscript stands for
“dual.” Note also that whereas in the
definition of θP we were optimizing
(maximizing) with respect to α, β, here
we are minimizing with respect to w.
● We can now pose the dual
optimization problem
● We also define the optimal value of the
dual problemʼs objective to be
KKT Conditions
However, under certain conditions, we will have d∗ = p∗ , so that we can solve
the dual problem in lieu of the primal problem.

We assume there are w∗ , α∗ , β∗ so that w∗ is the solution to the primal

problem, α∗ , β∗ are the solution to the dual problem, and moreover p ∗ = d ∗ =
L(w∗ , α∗ , β∗ ). Moreover, w∗ , α∗ , β∗ satisfy the Karush-Kuhn-Tucker (KKT)
conditions, which are as follows, then it is also a solution to the primal and
dual problems.

=> KKT dual complementarity condition.

KKT Conditions
● The KKT dual complementarity condition, specifically, it implies that if α∗i > 0, then
gi(w∗) = 0. (I.e., the “gi(w) ≤ 0” constraint is active, meaning it holds with equality
rather than with inequality.)
● Later on, this will be key for showing that the SVM has only a small number of
“support vectors”
● The KKT dual complementarity condition will also give us our convergence test
when we talk about the SMO algorithm.
Optimal margin classifiers
● The (primal) optimization problem for
finding the optimal margin classifier:

● We can write the constraints as

● From the KKT dual complementarity
condition, we will have αi > 0 only for the
training examples that have functional
margin exactly equal to one
Optimal margin classifiers
● Consider the figure below, in which a maximum margin
separating hyperplane is shown by the solid line.
● The points with the smallest margins are exactly the ones
closest to the decision boundary
● Here, three points (one negative and two positive examples)
that lie on the dashed lines parallel to the decision
boundary.

● Thus, only three of the αi ’s will be non-zero at the optimal solution to our optimization
problem.

● These three points are called the support vectors in this problem.

● The fact that the number of support vectors can be much smaller than the size the
training set will be useful later
 What is Hinge Loss?
● Hinge loss is used in SVM to ensure correct classification.
○ It penalizes misclassified points and those within the margin.

● Loss function:
L(y, f(x)) = max(0, 1 - y * f(x))
○ If correctly classified and outside margin → loss = 0.
○ Otherwise, the loss increases linearly.
 Mathematical Formulation of SVM
● Decision function: f(x) = w^T x + b
● Hinge loss function: L(y, f(x)) = max(0, 1 - y f(x))
● Total objective function:
J(w, b) = (1/N) Σ max(0, 1 - y_i (w^T x_i + b)) + (λ/2) ||w||^2
○ The first term is the hinge loss.
○ The second term is the regularization to prevent
overfitting.
 Visualization of SVM and Hinge Loss
● SVM aims to maximize the margin between two classes.
● Support vectors define the optimal hyperplane.
● Points within the margin or misclassified contribute to the loss.
● The hinge loss increases when a point is incorrectly classified.
● SVM is a powerful classification algorithm.
● Hinge loss ensures correct classification and large margin.
● The objective function balances hinge loss and regularization.
● Useful in high-dimensional spaces and robust to overfitting.
Reference
● Machine Learning, Stanford University by Prof. Andrew NG (Coursera)

● Support Vector Machines (SVMs): A friendly introduction by Luis Serrano