Module 3

CST413 Machine Learning

SUPPORT VECTOR MACHINES

Syllabus

TRACE KTU

2
Support vector machines

▷ A Support Vector Machine (SVM) is a supervised

machine learning algorithm that can be employed
for both classification and regression purposes.
TRACE KTU
▷ SVMs are based on the idea of finding a
hyperplane that best divides a dataset into two
classes.

3
TRACE KTU

4
 Problem Statement
▷ steps that lead to a solution of the problem using
the ideas of support vector machines.

TRACE KTU

5
[Link]-Class data set

▷ the data are classified based on the values of the

variable “play”.
▷ This variable has only two values or labels ,namely
TRACE KTU
“ yes” and ”no”.
▷ When there are only two class labels the data is said
to be a “two-class data set.

6
[Link] plot of the data

TRACE KTU

7
A separating line

▷ It is possible to draw a straight line in the plane

separating the two types of points in the sense
that
○ all points plotted as filled squares are on one side of
TRACE KTU
the line.
○ all points marked as hollow circles are on the other
side of the line.
▷ Such a line is called a “separating line” for the
data.

8
 Support Vector Machines

TRACE KTU

▷ Find a linear hyperplane (decision boundary) that will separate the data
 Support
B
Vector Machines
1

TRACE KTU

▷ One Possible Solution

 Support Vector Machines

B2

TRACE KTU

▷ Another possible solution

 Support Vector Machines

B2

TRACE KTU

▷ Other possible solutions

 Support
B
Vector Machines
1

B2

TRACE KTU

▷ Which one is better? B1 or B2?

▷ How do you define better?
 Support
B
Vector Machines
1

B2

TRACE KTU b21

b22

margin
b11

b12

▷ Find hyperplane maximizes the margin => B1 is better than B2

 Support
B
Vector Machines
1

 
w• x + b = 0
 
 
w • x + b = −1 w • x + b = +1
TRACE KTU
b11

  b12
 1 if w • x + b  1 2
f ( x) =    Margin = 
− 1 if w • x + b  −1 || w ||
Support Vectors

TRACE KTU

16
Margin of a separating line

▷ To choose the “best” separating line

○ Use the concept of the margin of a separating line.
■ Given a separating line for the data,
we consider the perpendicular distances of
TRACE KTU
●
the data points from the separating line.
● The double of the shortest perpendicular
distance is called the “margin of the
separating line”.

17
Maximal margin separating line T

▷ The “best” separating line is the one with the

maximum margin.
▷ The separating line with the maximum margin is
TRACE KTU
called the “maximum margin line” or the “optimal
separating line”

18
TRACE KTU

19
▷ Support vectors :The data points which are closest to
the maximum margin line are called the “support
vectors”.

TRACE KTU
▷ The required criterion:
○ As per theory of support vector machines, the equation of
the maximum margin line is used to devise a criterion for
taking a decision on whether to play tennis or not.

20
TRACE KTU

21
▷ Then the decision as to whether play tennis on
that day is “yes”
○ if 7x+6y−995.5<0

TRACE KTU
○ and “no” if 7x+6y−995.5>0.

22
“Street”of maximum width separating “yes” points and “no”
points.

▷ Draw a line through the support vectors 1 and 2

parallel to the maximum margin line, and a line
through support vector 3 parallel to the maximum
TRACE KTU
margin line.
▷ The region between these two dashed lines can
be thought of as a “road” or a “street” of
maximum width that separates the “yes” data
points and the “no” data points.

23
TRACE KTU

24
TRACE KTU

25
Linear SVM

▷ Linear model:
 
 1 if w • x + b  1
f ( x) =   
 − 1 if w • x + b  −1
TRACE KTU
▷ Learning the model is equivalent to

determining the values of w and b

○ How to find w and b from training data?
Learning Linear SVM

▷ Objective is to maximize: Margin = 2

|| w ||  2
○ Which is equivalent to minimizing:  || w ||
L( w) =
○ Subject to the following constraints: 2
TRACE KTU
1
 
if w • x i + b  1
yi =   
− 1 if w • x i + b  −1
or

yi ( w • x i + b)  1, i = 1,2,..., N
■ This is a constrained optimization problem
● Solve it using Lagrange multiplier method
The SVM classifier

▷ The solution of the SVM problem gives us a

clasifier for classifying unclassified data
instances.
TRACE KTU
▷ This is known as the SVM classifier for a
given dataset.
The classifier

Let⃗ x be an unclassified data instance.

• Assign the class label +1 to⃗ x
if⃗ w∗⋅⃗ x+b∗>0.
TRACE KTU
• Assign the class label−1 to⃗ x
if⃗ w∗⋅⃗ x+b∗<0.
TRACE KTU
TRACE KTU
TRACE KTU
TRACE KTU
An algorithm to find the SVM classifier

TRACE KTU
TRACE KTU
Soft margin hyperlanes

▷ The algorithm for finding the SVM classifier will

give give a solution only if the the given two-class
dataset is linearly separable.
TRACE KTU
▷ But, in real life problems, two-class datasets are
only rarely linearly separable.

36
Soft margin hyperlanes

▷ In such a case we introduce additional variables, ξi,

called slack variables which store deviations from
the margin.
TRACE KTU

37
Soft margin hyperlanes

TRACE KTU

38
▷ if ξi = 0, then x⃗i is correctly classified and there is no
problem with x⃗i .
▷ If 0 < ξi < 1 then x⃗i is correctly classified but it is in the
margin.
▷ TRACE KTU
If ξi > 1, x⃗i is misclassified.

N
▷ The sum
i =1
ξi is defined as the soft error
▷ and this is added as a penalty to the function to be
minimized.
▷ We also introduce a factor C to the soft error.

39
TRACE KTU

40
Kernel functions

TRACE KTU

41
Kernel functions

▷ In machine learning, a “kernel” is usually used

to refer to the kernel trick, a method of using a
linear classifier to solve a non-linear problem.
TRACE KTU
▷ The kernel function is what is applied on each
data instance to map the original non-linear
observations into a higher-dimensional space
in which they become separable.

42
TRACE KTU

43
Kernel functions - Definition

TRACE KTU

44
Some important kernel functions

TRACE KTU

45
Some important kernel functions

TRACE KTU

46
Using Homogenous polynomial
function

TRACE KTU

47
TRACE KTU

48
TRACE KTU
Expand

49
TRACE KTU

50
The kernel method (kernel trick)

TRACE KTU

51
TRACE KTU

52
 THANK YOU
TRACE KTU

53
Ensemble Learning-Combining Multiple
learners

▷ In general there are several algorithms for

learning the same task.
▷ Though these are generally successful, no one
TRACE KTU
single algorithm is always the most accurate.

54
Why combine many learners

▷ Each learning algorithm carries with it a set of

assumptions.
○ This leads to error if the assumptions do not hold.
○ We cannot be fully sure whether the assumptions
TRACE KTU
are true in a particular situation.
▷ With finite data, each algorithm may converge
to a different solution and may fail in certain
circumstances.

55
Why combine many learners

▷ The performance of a learner may be fine-tuned

to get the highest possible accuracy on a
validation set.
○ But this fine-tuning is a complex task and still there are
TRACE KTU
instances on which even the best learner is not
accurate enough.
▷ It has been proved that there is no single learning
algorithm that always produces the most accurate
output.

56
 Ways to achieve diversity

▷ When many learning algorithms are combined,

the individual algorithms in the collection are
called the base learners of the collection.
▷ There are several different ways for selecting the
TRACE KTU
base learners.
1. Use different learning algorithms
2. Use the same algorithm with different hyper
parameters
3. Use different representations of the input object.
4. Use different training sets to train different base-
learners
57
Ways to achieve diversity

5. Multi expert combination methods

6. Multistage combination methods

TRACE KTU

58
Model combination schemes

▷ Voting - This is the simplest procedure for

combining the outcomes of several learning
algorithms.
TRACE KTU

59
 Binary classification problem
▷ Consider a binary classification problem with class
labels−1 and+1.
▷ Let there be L base learners and let x be a test
instance.
▷
▷ TRACE KTU
Each of the base learners will assign a class label to x.
If the class label assigned is+1, we say that the learner
votes for+1 and that the label +1 gets a vote.
▷ The number of votes obtained by the class labels
when the different base learners are applied is
counted.
▷ In the voting scheme for combining the learners, the
label which gets the majority votes is assigned to x. 60
 Bagging-Boostrap Aggregation
▷ Bagging is a voting method where by base-
learners are made different by training them
over slightly different training sets.

TRACE KTU

61
▷ Training
○ Given a set D of d tuples, at each iteration i, a training
set Di of d tuples is sampled with replacement from D
(i.e., bootstrap)
○ A classifier model Mi is learned for each training set Di
▷ TRACE KTU
Classification: classify an unknown sample X
○ Each classifier Mi returns its class prediction
○ The bagged classifier M* counts the votes and assigns
the class with the most votes to X

62
▷ Prediction: can be applied to the prediction of continuous values
by taking the average value of each prediction for a given test tuple
▷ Accuracy
○ Often significantly better than a single classifier derived from
D
TRACE KTU
○ For noise data: not considerably worse, more robust
○ Proved improved accuracy in prediction

63
Boosting Method

▷ In boosting, we actively try to generate

complementary base-learners by training the next
learner on the mistakes of the previous learners.
TRACE KTU
▷ The original boosting algorithm combines three
weak learners to generate a strong learner.

64
▷ How boosting works?
○ Weights are assigned to each training tuple
○ A series of k classifiers is iteratively learned
○ After a classifier Mi is learned, the weights are updated
to allow the subsequent classifier, Mi+1, to pay more
attention to the training tuples that were misclassified
by Mi
○ The final M* combines the votes of each individual
classifier, where the weight of each classifier's vote is a
function of its accuracy
▷ Comparing with bagging: Boosting tends to have greater
accuracy, but it also risks overfitting the model to
misclassified data

65
66
Ensemblelearning

▷ The word “ensemble” literally means “a group of things

or people acting or taken together as a whole, especially a
group of musicians who regularly play together.”
▷ In machine learning, an ensemble learning method
consists of the following two steps:
○ 1. Create different models for solving a particular problem using
a given data.
○ 2. Combine the models created to produce improved results.

67
▷ The different models may be chosen in many different
ways:
○ The models may be created using appropriate different
algorithms like k-NN algorithm,NaiveBayes algorithm, decision
tree algorithm, etc.
○ The models may be created by using the same algorithm but
using different splits of the same dataset into training data and
test data.
○ The models may be created by assigning different initial values to
the parameters in the algorithm as in ANN algorithms.

68
▷ The models created in the ensemble learning methods are
combined in several ways.
○ Simple majority voting in classification problems: Every model
makes a prediction (votes) for each test instance and the final
output prediction is the one that receives more than half of the
votes.
○ Weighted majority voting in classification problem: In weighted
voting we count the prediction of the better models multiple
times. Finding a reasonable set of weights is up to us.

69
○ Simple averaging in prediction problems: In simple
averaging method, for every instance of test dataset,
the average predictions are calculated.
○ Weighted averaging in prediction problems: In this
method, the prediction of each model is multiplied by
the weight and then their average is calculated.

70