Machine Learning (CSPC41)

Support Vector Machine

Ref, Source & Ack:

1. Dr Anoop Kumar, Computer Engg Dept, NIT Kurukshetra
2. Jiawei Han, Micheline Kamber, and Jian Pei, University of Illinois
at Urbana-Champaign & Simon Fraser University, USA.
1
Linear classifiers: Which Hyperplane?

• Lots of possible solutions for a, b, c.

• Some methods find a separating hyperplane,
but not the optimal one. This line represents the
• Support Vector Machine (SVM) finds an decision boundary:
optimal* solution. ax + by − c = 0

– Maximizes the distance between the

hyperplane and the “difficult points” close to
decision boundary
– One intuition: if there are no points near the
decision surface, then there are no very
uncertain classification decisions
* But note that Naïve Bayes also finds an
optimal solution, just under a different
definition of optimality.
 Non-Linear classifiers
• For non-linear data, SVM is more complex
• use Kernelized SVM for non-linearly
separable data.
• Say, we have some non-linearly separable
data in one dimension. We can transform
this data into two dimensions and the
data will become linearly separable in
two dimensions. This is done by mapping
each 1-D data point to a corresponding 2-
D ordered pair.
• So for any non-linearly separable data in
any dimension, we can just map the data
to a higher dimension and then make it
linearly separable.
• Kernelized SVM the similarity is between
the points in the newly transformed
feature space.
 Sec. 15.1

Support Vector Machine (SVM)

Support vectors
• SVMs maximize the margin
around the separating hyperplane.
• large margin classifiers
• The decision function is fully
specified by a subset of training
samples, the support vectors
(tuples falling on the hyperplane).
Maximizes
• Solving SVMs is a quadratic Narrower
margin
programming problem margin
• Seen by many as the one of the
most successful text classification
method* *but other discriminative methods often
perform very similarly 4
 Support Vector Machine
• Decision surface: a hyperplane in feature space
• One of the most important tools in the machine learning
toolbox
• In a nutshell:
–map the data to a predetermined very high-dimensional
space via a kernel function
–Find the hyperplane that maximizes the margin between
the two classes
–If data are not separable -find the hyperplane that
maximizes the margin and minimizes the (weighted
average of the) misclassifications
 Support Vector Machine
Three main ideas:
[Link] what an optimal hyperplane is (taking into
account that it needs to be computed efficiently):
maximize margin
[Link] to non-linearly separable problems: have a
penalty term for misclassifications
[Link] data to high dimensional space where it is easier
to classify with linear decision surfaces: reformulate
problem so that data are mapped implicitly to this
space
 Support Vector Machine
Three main ideas:
[Link] what an optimal hyperplane is (taking into
account that it needs to be computed efficiently):
maximize margin
[Link] to non-linearly separable problems: have a
penalty term for misclassifications
[Link] data to high dimensional space where it is easier
to classify with linear decision surfaces: reformulate
problem so that data are mapped implicitly to this
space
Which Hyperplane to use for
Separation?
Maximizing the Margin
 Sec. 15.1

Maximum Margin: Formalization

• w: decision hyperplane normal vector
• xi: data point I,
• b is called bias (or zero-intercept like in line-eqn:
mx+c)
• yi:class of data point i(+1 or -1)(Note:It classifies as +1 or
-1,not as 1/0)
• Gen hyperplane eqn:(w*x +b=0) So Classifier: f(xi)=sign(wTxi + b)
• w and x are n-dim vectors, T for Transpose, Why wT is used?
• If w and x are initially vertical vectors, wT means horizontal vector,
so that matrix multiplication of w and x becomes compatible,
• In some books/notes, T might not be mentioned, so w as well as wT
are used interchangeably. Remember this while reading. 10
Support Vectors
Setting Up the Optimization Problem
Setting Up the Optimization Problem
 Sec. 15.1

Maximum Margin: Formalization

• Point lying above the hyperplane will have w*xi+b > 0 yi as +1
• Point lying below the hyperplane will have w*xi+b < 0 yi is -1
• The weights can be adjusted so that the hyperplane defining the
"sides" of the margin can be written as :
H1: w*xi+b >= +1 for yi to be +1
H2: w*xi+b <= -1 for yi to be -1
• Any tuple falling on or above H1 will be classified as +1 and any
tuple falling on or below H2 will be classified as -1
• Combining above two inequalities yi(w*xi+b) >= +1
• Above defines the Functional Margin of point xi as yi (wTxi + b)
– But note that we can increase this margin simply by scaling w, b….
• Functional margin of dataset is twice the minimum functional
margin for any point(factor of 2 comes from measuring the whole width
of the margin) 14
 Sec. 15.1

How to Maximize Formalization

• Recall: Distance between two planes: P1: w1x + w2y + w3z + d1 =
0 and P2: w1x + w2y + w3z + d2 = 0. Then, the formula for the
distance between two planes that are parallel is
d = |d2 - d1|/√(w12 + w22 + w32)
• √(w12 + w22 + w32) is Euclidean distance, notated as || w ||
• So distance of point on H1 from the separating hyperplane:
• 1/ ||w|| (point on H1 has w1x + w2y + w3z + d1= +1
w1x + w2y + w3z + d1-1 = 0
point on Sep. Hyp. has w1x + w2y + w3z + d1- 0 = 0
• Similarly distance of point on H2 will also be 1/ ||w||
• Maximal Margin: 2/ ||w||

15
 Sec. 15.1

Linear SVMs Mathematically (cont.)

• Then we can formulate the quadratic optimization problem:
Find w and b such that
2
k is maximized; and for all {(xi , yi)}
w
wTxi + b ≥ 1 if yi=1; wTxi + b ≤ -1 if yi = -1

• A better formulation (min ||w|| = max 1/ ||w|| ):

Find w and b such that

Φ(w) =½ wTw is minimized;

and for all {(xi ,yi)}: yi (wTxi + b) ≥ 1

16
 Sec. 15.1

Solving the Optimization Problem

Find w and b such that
Φ(w) =½ wTw is minimized;
and for all {(xi ,yi)}: yi (wTxi + b) ≥ 1

• This is now optimizing a quadratic function subject to linear constraints

• Quadratic optimization problems are a well-known class of mathematical
programming problem, and many (intricate) algorithms exist for solving them
(with many special ones built for SVMs)
• The solution involves constructing a dual problem where a Lagrange
multiplier αi is associated with every constraint in the primary problem:

Find α1…αN such that

Q(α) =Σαi - ½ΣΣαiαjyiyjxiTxj is maximized and
(1) Σαiyi = 0
(2) αi ≥ 0 for all αi
17
 Sec. 15.1

The Optimization Problem Solution

• The solution has the form:

w =Σαiyixi b= yk- wTxk for any xk such that αk 0

• Each non-zero αi indicates that corresponding xi is a support vector.

• Then the classifying function will have the form:

f(x) = ΣαiyixiTx + b

• Notice that it relies on an inner product between the test point x and the
support vectors xi
• Also keep in mind that solving the optimization problem involved
computing the inner products xiTxj between all pairs of training points.

18
 Support Vector Machine: Idea 2
Three main ideas:
[Link] what an optimal hyperplane is (taking into
account that it needs to be computed efficiently):
maximize margin
[Link] to non-linearly separable problems: have a
penalty term for misclassifications
[Link] data to high dimensional space where it is easier
to classify with linear decision surfaces: reformulate
problem so that data are mapped implicitly to this
space
 Sec. 15.2.1

Soft Margin Classification

• If the training data is not
linearly separable, slack
variables ξi can be added to
allow misclassification of
difficult or noisy examples.
• Allow some errors
ξi
– Let some points be
ξj
moved to where they
belong, at a cost
• Still, try to minimize training
set errors, and to place
hyperplane “far” from each
class (large margin)
20
 Sec. 15.2.1

Soft Margin Classification

Mathematically
• The old formulation:

Find w and b such that

Φ(w) =½ wTw is minimized and for all {(xi ,yi)}
yi (wTxi + b) ≥ 1

• The new formulation incorporating slack variables:

Find w and b such that

Φ(w) =½ wTw + CΣξi is minimized and for all {(xi ,yi)}
yi (wTxi + b) ≥ 1- ξi and ξi ≥ 0 for all i
• Parameter C can be viewed as a way to control overfitting
– A regularization term

21
 Sec. 15.2.1

Soft Margin Classification – Solution

• The dual problem for soft margin classification:

Find α1…αN such that

Q(α) =Σαi - ½ΣΣαiαjyiyjxiTxj is maximized and
(1) Σαiyi = 0
(2) 0 ≤ αi ≤ C for all αi
• Neither slack variables ξi nor their Lagrange multipliers appear in the dual
problem!
• Again, xi with non-zero αi will be support vectors.
• Solution to the dual problem is:

w is not needed explicitly for

w = Σαiyixi classification!
b = yk(1- ξk) - wTxk where k = argmax αk’
k’ f(x) = ΣαiyixiTx + b
22
 Sec. 15.1

Classification with SVMs

• Given a new point x, we can score its projection
onto the hyperplane normal:
– I.e., compute score: wTx + b = ΣαiyixiTx + b
• Decide class based on whether < or > 0

– Can set confidence threshold t.

Score > t: yes

Score < -t: no
Else: don’t know 1
0
-1
23
 Support Vector Machine: Idea 3
Three main ideas:
[Link] what an optimal hyperplane is (taking into
account that it needs to be computed efficiently):
maximize margin
[Link] to non-linearly separable problems: have a
penalty term for misclassifications
[Link] data to high dimensional space where it is easier
to classify with linear decision surfaces: reformulate
problem so that data are mapped implicitly to this
space
 Sec. 15.2.3

Non-linear SVMs
• Datasets that are linearly separable (with some noise) work
out great:

0 x

• But what are we going to do if the dataset is just too hard?

0 x

• How about … mapping data to a higher-dimensional space:

x2

0 x
25
 Sec. 15.2.3

Non-linear SVMs: Feature spaces

• General idea: the original feature space can

always be mapped to some higher-
dimensional feature space where the training
set is separable:
Φ: x → φ(x)

26
 SVM: Adv Features: Kernels
Map data to high dimensional space where it is easier to
classify with linear decision surfaces: reformulate problem so
that data are mapped implicitly to this space
• The linear classifier relies on an inner product between
vectors K(xi,xj)=xiTxj
• If every data point is mapped into high-dimensional space
via some transformation Φ: x → φ(x), the inner product
becomes: K(xi,xj)= φ(xi) Tφ(xj)
• A kernel function is some function that corresponds to an
inner product in some expanded feature space.
 SVM: Adv Features: Kernels
• Common kernels
– Linear
– Polynomial K(x,z) = (1+xTz)d
• Gives feature conjunctions
– Radial basis function (infinite dimensional space)
• Haven’t been very useful in text classification
 Sec. 15.2.1

SVMs: Summary
• The classifier is a separating hyperplane.
• The most “important” training points are the support vectors;
they define the hyperplane.
• Quadratic optimization algorithms can identify which training
points xi are support vectors with non-zero Lagrangian
multipliers αi.
• Margin Maximization is the aim
• For non-linearly separable data, if few points get misclassified
through separating hyperplane: penalize for the misclassified
points and minimize the penalty alongwith maximization of
the margin
• If data is mostly non-linearly separable, use kernel function,
map data to high dimensions and then optimize for finding
separating hyperplane with max margin in high-dim space
29