09 SUPPORT VECTOR MACHINES

Fall 2023 CS54118 Machine Learning

Credits
1. B1: Machine learning: an algorithmic perspective. 2nd Edition,
Marsland, Stephen. CRC press, 2015
2. [Link]
part-1/
3. [Link]
4. [Link]
5. Introduction to Data Mining, 1st Edition, Pang-Ning Tan, Michael
Steinbach, Anuj Karpatne, Vipin Kumar, Pearson 2005
Assignment
Read:
B1: Chapter 8.1, 8.2

Problems:
B1:8.1, 8.2, 8.3, 8.4
 Possible to transform any set of data so that the classes become
linearly separable.
 Recall XOR example
XOR Function – Linearly Inseparable
 XOR – separable in 3D

Added Dimension

In1 In2 In3 Output

0 0 1 0
0 1 0 1
1 0 0 1
1 1 0 0
Support Vector Machine (SVM)
 Introduced by Vapnik in 1992
 Work well on reasonably sized datasets
 Do not work well on large sized datasets
 Becomes computationally expensive
 Based on kernel functions
 Reformulates classification problem in such a way that we can tell a
good classifier from a bad one
Which classifier is a better one?

 A perceptron would stop training if it reaches any of the lines

 But, we like the middle one most
 Why? What is the separation criteria that we are trying to optimize?
 Support Vectors

 We define a cylindrical region around the line of separation

 𝑀: margin is the largest radius of such a hyper-cylinder
 Lets give a name: “Maximum margin (linear) classifier”
 Support Vectors

 Two things
𝑀 should be as large as possible
 Only support vectors need to be retained for classification (remaining data
points can be dropped)
 Recall, for a perceptron we classified a point
 As ‘+’ if 𝑤 𝑇 𝑥 + 𝑏 > 0 (𝑏 is the contribution from bias weight)
𝑇
 As ‘o’ if 𝑤 𝑥 + 𝑏 < 0

 We change this to (𝑘 > 0))

 As ‘+’ if 𝑤 𝑇 𝑥 + 𝑏 ≥ 𝑘
𝑇
 As ‘o’ if 𝑤 𝑥 + 𝑏 ≤ −𝑘
𝑇
 The actual separating hyperplane is still 𝑤 𝑥 + 𝑏 = 0

 The above can be simplified to:

 As ‘+’ if 𝑤 𝑇 𝑥 + 𝑏 ≥ 1
𝑇
 As ‘o’ if 𝑤 𝑥 + 𝑏 ≤ −1
 A support vector for ‘o’ class is a point 𝑥 𝑜 that lies on the boundary line s.t.
𝑇 𝑜
𝑤 𝑥 + 𝑏 = −1
 From 𝑥 𝑜 , if we travel perpendicular to the decision boundary for distance
𝑀, we will get separating hyperplane
 And further 𝑀, we will hit the decision boundary for class ‘+’ at point 𝑥 +

𝑥+

𝑥𝑜
 For expression 𝑤 𝑇 𝑥 + 𝑏 defining the decision boundaries, 𝑤 𝑇 is
perpendicular to all three decision boundaries. Hence,
𝑇
𝑤
𝑥 𝑜 + 2𝑀 𝑇 = 𝑥 +
𝑤
 But, 𝑤 𝑇 𝑥 + + 𝑏 = 1
 Hence,
𝑇
𝑤
𝑤 𝑇 𝑥 𝑜 + 2𝑀 𝑇 + 𝑏 = 1
𝑤
𝑇 𝑇
𝑥+ 𝑇 𝑜
𝑤 𝑤
𝑤 𝑥 + 𝑏 + 2𝑀 𝑇
=1
𝑤
−1 + 2𝑀 𝑤 𝑇 = 1
1
𝑥𝑜 𝑀= 𝑇
𝑤
 1 1 𝑇
 Making 𝑀 = as large as possible is the same as making 𝑤 𝑤
𝑤𝑇 2
1
as small as possible ( is added for convenience)
2
 If the goal is to maximize 𝑀, we can set 𝑤 = 0
 Will that be good enough?
 No, we also want the classification line to separate ‘+’ classes from ‘o’
classes.
 So, there are two problems to be solved simultaneously
 Finda decision boundary that classifies well
𝑇
 Minimize 𝑤 𝑤
 Constrained Optimization Problem
 Let 𝑦𝑖 ∈ {−1, +1} be the computed output and 𝑡𝑖 ∈ {−1, +1} be the target
output, then for correct classification:
𝑡𝑖 𝑦𝑖 = 𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1
 Hence, the full problem that we wish to solve is:
1 𝑇
Minimize 𝑤 𝑤 s.t. 𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1 for all 𝑖 = 1, … , 𝑛
2
Using gradient descent would require a lot of effort in enforcing the constraint
and would be slow
We use Quadratic Programming because the above equation is objective function
is quadratic and hence convex, and the constraints are linear
Maths Behind SVM
 Lagrange Multipliers
 Dual Form
 Karush-Kuhn-Tucker Conditions
 Quadratic Programming
Lagrange Multipliers
 Lagrange noticed that when we try to solve an optimization problem
of the form

the local minima of 𝑓 is found when its gradient point in the same
direction as the gradient of 𝑔. In other words, when:
𝛻𝑓 𝑥 = 𝜆𝛻𝑔(𝑥)
For some value 𝜆 called Lagrange multiplier
 Consider the following
example

 Minimum is obtained when

𝛻𝑓 and 𝛻𝑔 point in the
same direction, i.e.,
𝛻𝑓 𝑥 = 𝜆𝛻𝑔(𝑥)

For some 𝜆 called Lagrange

Multiplier
 How do we find 𝜆 in 𝛻𝑓 𝑥 = 𝜆𝛻𝑔(𝑥)
 We define Lagrange function

And solve for 𝛻𝐿 𝑥, 𝑦, 𝜆 = 0

To get value of 𝑥, 𝑦, 𝜆
Step 1: Introduce the Lagrangian function
𝐿(𝑥, 𝑦, 𝜆) = 𝑓(𝑥, 𝑦) − 𝜆𝑔(𝑥, 𝑦)
And its gradient is:
𝛻𝐿(𝑥, 𝑦, 𝜆) = 𝛻𝑓(𝑥, 𝑦) − 𝜆𝛻𝑔(𝑥, 𝑦)
Step 2: Solve for its gradient

𝛻𝐿(𝑥, 𝑦, 𝜆) = 0

1
𝑥 = 𝑦 = ,𝜆 = 1
2
 The Lagrange multiplier method can be summarized by these three
steps:
1. Construct the Lagrangian function ℒ by introducing one multiplier per
constraint
2. Get the gradient 𝛻ℒ of the Lagrangian function
3. Solve for 𝛻ℒ 𝑥, 𝜆 = 0
 The SVM Lagrangian problem
 Let target answers be ±1 (for classes ‘+’ and ‘o’)
 Let 𝑦𝑖 be the computed output and 𝑡𝑖 be the target output, then
for correct classification:
𝑡𝑖 𝑦𝑖 = 𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1
 Hence, the full problem that we wish to solve is:
1 𝑇
Minimize 𝑤 𝑤 s.t. 𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1 for all 𝑖 = 1, … , 𝑛
2
 Even though the linear constraints are inequality constraints, we
can still formulate it as Lagrangian problem if certain KKT
conditions are met
 Further, our problem is quadratic, and hence convex. Thus, global
minimum is guaranteed.
Karush-Kuhn-Tucker (KKT) Conditions
 KKT Conditions are first-order necessary conditions for a solution in
nonlinear programming to be optimal, provided that some regularity
conditions are satisfied.
 Allowing inequality constraints, the KKT approach to nonlinear programming
generalizes the method of Lagrange multipliers, which allows only equality
constraints.
 KKT Conditions are
 Stationarity condition
 Primal feasibility condition
 Dual feasibility condition
 Complementary slackness condition
 The KKT Conditions are:
∗𝑇
𝜆∗𝑖 (1 − 𝑡𝑖
𝑤 𝑥𝑖 + 𝑏 ∗ ) = 0
1 − 𝑡𝑖 𝑤 ∗ 𝑇 𝑥𝑖 + 𝑏 ∗ ≤ 0
𝜆∗𝑖 ≥ 0
Where 𝜆𝑖 s are positive values and are Lagrange multipliers.

∗ ∗𝑇 ∗𝑇
In 𝜆𝑖 (1 − 𝑡𝑖 𝑤 𝑥𝑖 ∗
+ 𝑏 ) = 0, if 𝜆∗𝑖 ≠ 0, then 1 − 𝑡𝑖 𝑤 𝑥𝑖 + 𝑏 ∗ =0
∗𝑇
1 − 𝑡𝑖 𝑤 𝑥𝑖 + 𝑏 ∗ =0 is true only for support vectors, i.e., support
vectors are those with corresponding non-zero Lagrange multiplier
Also, for non-support vectors, 𝜆𝑖 = 0
That is, parameters 𝑤 ∗ and 𝑏 ∗ only depend upon support vectors
 1 𝑇
 Minimize 𝑤 𝑤 s.t. 𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1 for all 𝑖 = 1, … , 𝑛
2
The Lagrangian function can be written as:
𝑛
1 𝑇
min max ℒ 𝑤, 𝑏, 𝜆 = 𝑤 𝑤 − ෍ 𝜆𝑖 (𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 − 1)
𝑤,𝑏 𝜆 2
𝑖=1
Where 𝜆𝑖 s are positive values known as Lagrange multipliers.

When we differentiate the above function to find minima w.r.t. 𝑤 and 𝑏

and set the derivatives to 0, we get
𝑛 𝑛

𝑤 ∗ = ෍ 𝜆𝑖 𝑡𝑖 𝑥𝑖 , ෍ 𝜆𝑖 𝑡𝑖 = 0
𝑖=1 𝑖=1
 Substituting
𝑛 𝑛

𝑤 ∗ = ෍ 𝜆𝑖 𝑡𝑖 𝑥𝑖 , ෍ 𝜆𝑖 𝑡𝑖 = 0
𝑖=1 𝑖=1
into Lagrangian Function
𝑛
1 𝑇
ℒ 𝑤, 𝑏, 𝜆 = 𝑤 𝑤 − ෍ 𝜆𝑖 (𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 − 1)
2
𝑖=1
We get,
𝑛 𝑛 𝑛 𝑛
1
ℒ 𝑤, 𝑏, 𝜆 = ෍ 𝜆𝑖 − 𝑏 ෍ 𝜆𝑖 𝑡𝑖 − ෍ ෍ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑥𝑖𝑇 𝑥𝑗
2
𝑖=1 𝑖=1 𝑖=1 𝑗=1
𝑛 𝑛 𝑛 𝑛
1
⇒ ℒ 𝑤, 𝑏, 𝜆 = ෍ 𝜆𝑖 − ෍ ෍ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑥𝑖𝑇 𝑥𝑗 ∵ ෍ 𝜆𝑖 𝑡𝑖 = 0
2
𝑖=1 𝑖=1 𝑗=1 𝑖=1
 𝑛 𝑛 𝑛
1
ℒ 𝑤, 𝑏, 𝜆 = ෍ 𝜆𝑖 − ෍ ෍ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑥𝑖𝑇 𝑥𝑗
2
𝑖=1 𝑖=1 𝑗=1
 The above is called the Wolfe dual Lagrangian function, the
corresponding optimization problem is Wolfe dual problem involves
maximization of the above function w.r.t. 𝜆 subject to
𝑛

𝜆𝑖 ≥ 0 for all 𝑖 and ෍ 𝜆𝑖 𝑡𝑖 = 0

𝑖=1
 We solve the above problem (using Quadratic Programming) to get all
𝜆𝑖 s
 Suppose, we have calculated 𝑤 ∗ and 𝜆𝑖 s, we still need 𝑏 ∗ .
 We find it using: for a support vector, the following holds
𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 = 1
 We can substitute the value of 𝑤 ∗ , to get
𝑏 = 𝑡𝑖 − 𝑤 ∙ 𝑥𝑖 (recall 𝑡𝑖2 = 1)
 To make the above value more stable, we average over all support
vectors
𝑆
1
𝑏 = ෍(𝑡𝑖 − 𝑤 ∙ 𝑥𝑖 )
𝑆
𝑖=1
Where, 𝑆= #support vectors
Making Predictions using SVM
 We calculate the following for a new data point 𝑧
𝑤 ∗ 𝑇 𝑧 + 𝑏∗
Using

The above becomes:

However, only the support vectors are used while computing the value of 𝑤 ∗ .
 Hence, to classify a new point, we just need to compute the inner product
between the new datapoint and the support vectors
 ∗𝑇
Instead of taking, 𝑤 𝑧 + 𝑏 ∗ , we can use sigmoid function to get the
output prediction as:

𝑡 𝑥 = sig(𝑤 ∗ 𝑇 𝑧 + 𝑏 ∗ )
The Lagrangian multipliers have been obtained solving through quadratic programming.
Compute the decision boundary and the margin

Decision boundary is 𝑤 𝑇 𝑥 + 𝑏. We need to compute 𝑤 and 𝑏

𝑛

𝑤 = ෍ 𝜆𝑖 𝑡𝑖 𝑥𝑖
𝑖=1
For each support vector, we get a 𝑏
𝑏 = 𝑡𝑖 − 𝑤 ∙ 𝑥𝑖
Then we average all 𝑏s
 𝑛

𝑤 ∗ = ෍ 𝜆𝑖 𝑡𝑖 𝑥𝑖
𝑖=1
For each support vector, we get a 𝑏
𝑏 = 𝑡𝑖 − 𝑤 ∙ 𝑥𝑖
Then we average all 𝑏s

𝑏avg = 7.93 + 7.9289 ÷ 2 = 7.93

 𝑤1 = −6.64,
𝑤2 = −9.32,
𝑏avg = 7.93

Margin ?
1
Margin: 𝑀 =
𝑤𝑇
1
=
−6.64 2 + −9.32 2

=~.09
 Dealing with Noisy Data
 The input data can have outlier points
that
 Closer to the other examples than most
of the examples of its class, thus
reducing the margin
 The input data can have outlier points
that
 Can be among the other examples and
break linear separability
 Slack Variables for Noisy Data
 We introduce slack variables 𝜂𝑖 ≥ 0 s.t. the constraints become
𝑡𝑖 𝑤 𝑇 𝑥𝑖 + 𝑏 ≥ 1 − 𝜂𝑖
 We want to introduce the following into our minimization criteria
 A classifier just putting a point on the wrong side of the line is better than a classifier putting
a point a long way onto the wrong side of the line.
 Now our minimization criteria looks like:
𝑤 𝑇 𝑤 + 𝐶(෍ distance of misclassified points form the correct boundary line)

𝐶: tradeoff parameter
 Small 𝐶: prize large margin over distance of misclassified points
 Large 𝐶: less value to margin vs. more weight on keeping distance of misclassified points low
 So, function that we want to minimize is
𝑛

𝐿 𝑤, 𝜖 = 𝑤 𝑇 𝑤 + 𝐶 ෍ 𝜖𝑖
𝑖=1
Where 𝜖𝑖 is the distance of 𝑖 th misclassified point from the correct boundary line.
The Lagrangian derivation of the dual form still holds, except
0 ≤ 𝜆𝑖 ≤ 𝐶 and the support vectors are those vectors with 𝜆𝑖 > 0
KKT conditions become
Previous Now
𝜆∗𝑖 (1 − 𝑡𝑖 𝑤 ∗ 𝑇 𝑥𝑖 + 𝑏 ∗ ) = 0 𝜆∗𝑖 (1 − 𝑡𝑖 𝑤 ∗ 𝑇 𝑥𝑖 + 𝑏 ∗ − 𝜂𝑖 ) = 0
1 − 𝑡𝑖 𝑤 ∗ 𝑇 𝑥𝑖 + 𝑏 ∗ ≤ 0 𝐶 − 𝜆∗𝑖 𝜂𝑖 = 0
𝑛
𝜆∗𝑖 ≥ 0
෍ 𝜆∗𝑖 𝑡𝑖 = 0
𝑖=1
 This is called soft margin SVM
 The problem with soft margin formulation is that it is not as clear how
to choose a limited set of vectors, and so most of our training set will
be support vectors
Kernels – Dealing with Non-linearly Separable Data
 In the current form, the discussed solution does not work well if the
solution boundary is not a straight line.

 Solution: transform the data by adding new features (as we did in XOR case)
Basis Functions
 Several ML algorithms can be written as

Where, Φ𝑖 (𝑥) is some function of input 𝑥, and 𝛼𝑖 are the parameters we

can solve for in order to make the model fit the data.
 Φ𝑖 (𝑥) are known as basis functions.

 They are the basis in terms of which 𝑓(𝑥) is expressed.

 Consider a basis that consists of polynomials of everything up to
degree 2.
 For a 𝑑-dimensional input, the basis Φ(𝑥) consists of:
 Constant value 1
 Each of the individual scalar input elements 𝑥1 , 𝑥2 , … , 𝑥𝑑
2 2 2
 Squares of each input elements 𝑥1 , 𝑥2 , … , 𝑥𝑑

 Product of each pair of elements 𝑥1 𝑥2 , 𝑥1 𝑥3 , … , 𝑥𝑑−1 𝑥𝑑

 E.g., 𝑥, 𝑦 ⇒ (1, 𝑥, 𝑦, 𝑥 2 , 𝑦 2 , 𝑥𝑦)

𝑑2
 Contains around terms.
2
Using 𝑥1 2 as well as 𝑥1 allows these two classes to be separated.
 For 𝑑 = 3, the basis looks like

Additional 2s have been added for convenience.

𝑑2
 Problem: basis Φ 𝑥𝑖 has terms
2
 SVM solution involves frequent multiplication of input vectors Φ 𝑥 𝑇 Φ 𝑦 ,
which can be computationally expensive.
 Trick:

Can actually be factorized as

1 + 𝑥𝑇𝑦 2
This dot product only requires 𝑂(𝑑) multiplications vs. 𝑂(𝑑 2 )
multiplications of the original algorithm.
 The same holds true for the polynomials of any degree 𝑠, where the
naïve multiplication will cost 𝑂(𝑑 𝑠 )
 We form a kernel matrix (also known as Gram matrix) 𝐾 that is made
(cheaply at linear cost) from the dot products of the original vectors.
 Kernel trick!
𝑡ℎ
 The kernel matrix is an 𝑛 × 𝑛 matrix, where 𝑖, 𝑗 entry gives the dot
product of inputs 𝑥𝑖 and 𝑥𝑗
Choosing Kernels
 Any symmetric function that is positive definite (meaning that it
enforces positivity on the integral of arbitrary functions) can be used
as a kernel
 Mercer’s Theorem
 Let the input vector be 𝑥 = 𝑥1 , … 𝑥𝑘 , … 𝑥𝑑
 There are three different types of basis functions that are commonly
used, and they have nice kernels that correspond to them
 Polynomials

 Sigmoid

 Radial basis
Polynomials
 Polynomials up to some degree 𝑠 in the elements 𝑥𝑘 of the input vector
have kernel:
𝐾 𝑥, 𝑦 = 1 + 𝑥 𝑇 𝑦 𝑠

For 𝑠 = 1 this gives a linear kernel

Sigmoid functions
 Sigmoid functions of the 𝑥𝑘 s with parameter 𝜅 and 𝛿, have the kernel:
𝐾 𝑥, 𝑦 = tanh(𝜅𝑥 𝑇 𝑦 − 𝛿)
Radial Basis Functions
 Radial basis function expansions of the 𝑥𝑘 s with parameter 𝜎 have
the kernel
 Choosing which kernel to use and the parameters in these kernels is a
tricky problem.
 While there is some theory based on something known as the Vapnik–
Chernik dimension that can be applied, most people just experiment
with different values and find one that works using a validation set as
we did for the MLP.
Quadratic Programming
 Quadratic programming (QP) is the process of solving a special type
of mathematical optimization problem of optimizing (minimizing or
maximizing) a quadratic function of several variables subject to linear
constraints on these variables.
 We will not go into the maths and implementation as there are ready-
to-use quadratic solvers
 Find 𝜆 that minimizes the following quadratic functions
1 𝑇
min 𝜆 𝑃𝜆 + 𝑞𝑇 𝜆
𝜆 2
with linear constraints:
𝐺𝜆 ≤ ℎ
𝐴𝜆 = 𝑏
 Where

𝜆 ∈ ℝ𝑛
𝑛 𝑛
 𝑃 ∈ ℝ × ℝ and is symmetric
𝑛
𝑞 ∈ ℝ

𝐺 ∈ ℝ
𝑘×𝑛
𝑘
ℎ ∈ ℝ

𝐴 ∈ ℝ
𝑙×𝑛
𝑙
𝑏 ∈ ℝ
  Quadratic solver requires
1 𝑇
min 𝜆 𝑃𝜆 + 𝑞𝑇 𝜆
𝜆 2
Subject to:
𝐺𝜆 ≤ ℎ
𝐴𝜆 = 𝑏
Dual Lagrangian Function For Quadratic Solver
𝑛 𝑛 𝑛 1 𝑇 𝑇
1 min 𝜆 𝑡𝑡 𝐾𝜆 − 𝜆
max ℒ 𝑤, 𝑏, 𝜆 = ෍ 𝜆𝑖 − ෍ ෍ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑥𝑖𝑇 𝑥𝑗 𝜆 2
𝜆 2
𝑖=1 𝑖=1 𝑗=1 𝐾 is 𝑛 × 𝑛 kernel matrix

Subject to: Subject to:

𝑛 𝑇
𝜆 ≤ 𝐶, 𝐶 … 𝐶
0 ≤ 𝜆𝑖 ≤ 𝐶 for all i, and ෍ 𝜆𝑖 𝑡𝑖 = 0 −𝜆 ≤ 0
𝑖=1 𝑡𝑇𝜆 = 0
 Quadratic solver requires For Quadratic Solver
1 𝑇 1 𝑇 𝑇
min 𝜆 𝑃𝜆 + 𝑞𝑇 𝜆 min 𝜆 𝑡𝑡 𝐾𝜆 − 𝜆
𝜆 2 𝜆 2
Subject to: 𝐾 is 𝑛 × 𝑛 kernel matrix
𝐺𝜆 ≤ ℎ
Subject to:
𝐴𝜆 = 𝑏 𝑇
𝜆 ≤ 𝐶, 𝐶 … 𝐶
While mapping: −𝜆 ≤ 0
𝑃 = 𝑡𝑡 𝑇 𝐾 𝑡𝑇𝜆 = 0
𝑞𝑇 : identity vector of − 1s
𝐴 = 𝑡𝑇
1 0 … 0 𝐶
0 1 … 0 𝐶
⋮ ⋮ ⋮ ⋮ ⋮
0 0 … 1 𝐶
𝐺2𝑛×𝑛 𝜆 ≡ −1 0 … 0 𝜆 ≤ ℎ2𝑛×1 ≡
0
0 −1 … 0 0
⋮ ⋮ ⋮ ⋮ ⋮
0 0 0 −1 0
Multi-Class Classification
 SVM only works for two class classification
 For multi-class classification
 One vs. rest
 One SVM for each class

 The SVM that gives the strongest prediction is prediction of the combined
model
Using SVM for Regression
 The goal is totally opposite: to find a line such that all existing points
lie “within” the cylinder of radius 𝑀
 The motivation behind the error function is:

2
Were 𝑤 is the regularization term and 𝜆 is a constant that controls
its importance
 It is transformed further using 𝜖-insensitive error function 𝐸𝜖
 Returns 0 if 𝑡𝑖 − 𝑦 < 𝜖
 Returns (𝑡𝑖 − 𝑦 − 𝜖) otherwise

Reason: we are only interested in

points that are not well predicted
 Again, we introduce slack variables for each datapoint along with the
constraints
 Introduce Lagrange multipliers
 Transfer to Dual problem
 User Kernel trick and Solve with a quadratic solver