Support Vector Machines

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 3
What is the difference among Linear
Regression, Logistic Regression, and
SVM?

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 4
Linear R VS Logistic R Vs SVM

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 5
 Support Vector Machines

• SVM: Problem definition

– Assumptions:
• Binary classification:
Let’s assume there are only two classes
(e.g. spam/non-spam or relevant/non-relevant)
• Vector representation:
Any item to be classified can be represented as a
d-dimensional real vector
– Task:
• Find a linear classifier (i.e. a hyperplane) that
divides the ℝd into two parts

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 6
 Support Vector Machines

• Example:A two-dimensional example training set

– Task:Separate it by a line!

Any of these linear classifiers would be fine…

Which one is best?

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 7
 SVM Margin

• Which line is better? Idea:measure the quality of

a linear classifier by its margin! Margin = The width that the
boundary could be increased
without hitting a data point

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 8
 SVM Margin

• Margins (2)

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 9
 SVM Margin

• Margins (3)

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 10
 Support Vector Machines

• A maximum margin classifier is the

linear classifier with a maximum margin

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 11
 Maximum Margin Classifier

• The maximum margin classifier is

the simplest kind of support vector machine,
called a linear SVM
– Let’s assume for now that there always is such a
classifier, i.e. the training set is linearly separable!

The data points that

the margin pushes
against are called
support vectors

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 12
 Maximum Margin Classifier

• Why maximum margin?

– It’s intuitive to divide the two classes by a large
margin
– The largest margin guards best against small
errors in choosing the“right” separator
– This approach is robust since usually only a
small fraction of all data points are support vectors
– There are some theoretical arguments why
this is a good thing
– Empirically,it works very well
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 13
 Maximum Margin Classifier
• This is a constrained optimization problem.
• How to formalize this approach?
• Training data:
– Let there be n training examples
– The i-th training example is a pair (yi, zi),
where yi is a d-dimensional real vector and zi ∈ {−1, 1}
– “−1” stands for the first class and
“1” stands for the second class
− (1, 2), −1

(−1, 1), −1 − + (4, 1), 1

−
(1, 0), −1
+ (5, −1), 1

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 14
 Finding MM Classifier
• What’s a valid linear separator?
• Any hyperplane can be defined by a real row vector w
and a scalar b
– The set of points located on the hyperplane is given by

– w is a normal vector of the hyperplane,

i.e. w is perpendicular to it
– b represents a shift from the origin of the coordinate system
− x1 − x2 − 2 = 0
(1, 2)
(−1, 1) − + (4, 1)
(1, 0)
−

+ (5, −1)
x1 − x2 − 2 < 0
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 15
 Finding MM Classifier

• Therefore,any valid separating hyperplane (w,b)

must satisfy the following constraints, for any i
= 1,…,n:
– If zi = −1,then w · yi + b < 0
– If zi = 1,then w · yi + b > 0
− x1 − x2 − 2 = 0
(1, 2)
(−1, 1) − + (4, 1)
(1, 0)
−

+ (5, −1)
x1 − x2 − 2 < 0 x1 − x2 − 2 > 0

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 16
 Finding MM Classifier

• Furthermore, if (w, b) is a valid separating hyperplane, then

there are scalars r+ > 0 and r− > 0 such that
w · x + b + r− = 0 and w · x + b − r+ = 0
are the hyperplanes that define the boundaries to
the “−1” class and the “1” class, respectively
– The support vectors are located on these hyperplanes!
w·x+b=0
−
w · x + b − r+ = 0
− +

−
w · x + b + r− = 0 support vector
+

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 17
 Finding MM Classifier

• Let (w, b) be a valid separating hyperplane with scalars r+

and r− as defined above
• Observation 1:
Define b’ = b + (r− − r+) / 2. Then, the hyperplane
w · x + b’ = 0 is a valid separating hyperplane with
equal shift constants r’ = (r− − r+) / 2 to
its bounding hyperplanes (the margin width is the same)
w·x+b=0
− w · x + b − r+ = 0
− + w · x + b’ − r’ = 0

−
w · x + b + r− = 0
w · x + b’ + r’ = 0 +
w · x + b’ = 0
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 18
 SVM

• At the beginning we assumed that our training

data set is linearly separable…
• What if it looks like this?

A MIXTURE

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 19
 Soft Margins IF NOT LINEARLY SEPEARABLE

• So-called soft margins can be used to handle

such cases
• We allow the classifier to make some mistakes on
the training data
• Each misclassification gets assigned an error,
the total classification error then is to be
minimized −

− +

−
−
+
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 20
 SVM
• At the beginning, we also assumed that there are only
• two classes in the training set
• How to handle more than that?
• Some ideas:
– One-versus-all classifiers:
• Build an SVM for any class that occurs in the
training set; To classify new items, choose the greatest
margin’s class
– One-versus-one classifiers:
• Build an SVM for any pair of classes in the training
set; To classify new items, choose the class
selected by most SVMs
– Multiclass SVMs
• …
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 21
 Overfitting

• One problem in using SVMs remains:

If we use a mapping to a high-dimensional space that is
“complicated enough,” we could find a perfect linear
separation in the transformed space, for any training set
• So, what type of SVM is the “right” one?
• Example: How to separate this data set into two parts?
+ +
− −
+ +
− + +
− +
− +
−
−
+
Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 22
 Overfitting
• A perfect classification for the training set
could generalize badly on new data
• Fitting a classifier too strongly to the specific
properties of the training set is called overfitting
• What can we do to avoid it?
• Cross-validation:
– Randomly split the available data into two parts
(training set + test set)
– Use the first part for learning the classifier and the
second part for checking the classifier’s performance
– Choose a classifier that maximizes performance on the
test set

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 23
Summary
– Support Vector Machines
• Binary classification
• Finding the maximum margin classifier

Acknowledgment - Thanks to Wolf-Tilo Balke and Silviu Homoceanu - TU Braunschweig for the slides 24