4.Support Vector Machines.ppt machine learning and development

Cyctybtt

1. 1
Machine Learning
Support Vector Machines

2. 2
Perceptron Revisited: Linear
Separators
Binary classification can be viewed as the task of
separating classes in feature space:
w
T
x + b= 0
w
T
x + b< 0
w
T
x + b> 0
g(x)= sign(w
T
x + b)

3. 3
Linear Discriminant Function
g(x) is a linear function:()
T
gbx w x
x
1
x
2
w
T
x + b < 0
w
T
x + b > 0
A hyper-plane in the feature
space
(Unit-length) normal vector of
the hyper-plane:
w
n
w
n

4. 4
How would you classify these
points using a linear
discriminant function in order
to minimize the error rate?
Linear Discriminant Function
denotes +1
denotes -1
x
1
x
2
Infinite number of answers!

5. 5
How would you classify these
points using a linear
discriminant function in order
to minimize the error rate?
Linear Discriminant Function
denotes +1
denotes -1
x
1
x
2
Infinite number of answers!

6. 6
How would you classify these
points using a linear
discriminant function in order
to minimize the error rate?
Linear Discriminant Function
denotes +1
denotes -1
x
1
x
2
Infinite number of answers!

7. 7
x
1
x
2How would you classify these
points using a linear
discriminant function in order
to minimize the error rate?
Linear Discriminant Function
denotes +1
denotes -1
Infinite number of answers!
Which one is the best?

8. 8
Large Margin Linear Classifier
“safe zone”
The linear discriminant
function (classifier) with the
maximum marginis the best
Margin is defined as the width
that the boundary could be
increased by before hitting a
data point
Why it is the best?
Robust to outliners and thus
strong generalization ability
Margin
x
1
x
2
denotes +1
denotes -1

9. 9
Classification Margin
Distance from example x
ito the separator is
Examples closest to the hyperplane are support vectors.
Marginρof the separator is the distance between support vectors.w
xw b
r
i
T


r
ρ

10. 10
Maximum Margin Classification
Maximizing the margin is good according to intuition and
PAC theory.
Implies that only support vectors matter; other training
examples are ignorable.

11. 11
Large Margin Linear Classifier
We know that
The margin width is:
x
1
x
2
denotes +1
denotes -1 1
1
T
T
b
b



  
wx
wx
Margin
x
+
x
+
x
-()
2
( )
M


  
   
x x n
w
xx
ww
n
Support Vectors

12. 12
Linear SVMs Mathematically (cont.)
Then we can formulate the quadratic optimization problem:
Which can be reformulated as:
Find wand bsuch that
is maximized
and for all (x
i, y
i), i=1..n: y
i(w
T
x
i+ b)≥ 1w
2

Find wand bsuch that
Φ(w)= ||w||
2
=w
T
wis minimized
and for all (x
i, y
i), i=1..n: y
i(w
T
x
i+ b)≥ 1

13. 13
Solving the Optimization Problem
Need to optimize a quadratic function subject to linear constraints.
Quadratic optimization problems are a well-known class of
mathematical programming problems for which several (non-trivial)
algorithms exist.
The solution involves constructing a dual problem where a
Lagrange multiplierα
i is associated with every inequality constraint
in the primal (original) problem:
Find wand b such that
Φ(w)=w
T
wis minimized
and for all (x
i, y
i),i=1..n: y
i(w
T
x
i+ b)≥ 1
Find α
1…α
nsuch that
Q(α)=Σα
i-½ΣΣα
iα
jy
iy
jx
i
T
x
jis maximized and
(1)Σα
iy
i= 0
(2) α
i≥ 0 for all α
i

14. 14
The Optimization Problem Solution
Given a solution α
1…α
nto the dual problem, solution to the primal is:
Each non-zero α
iindicates that corresponding x
iis a support vector.
Then the classifying function is (note that we don’t need w explicitly):
Notice that it relies on an inner productbetween the test point xand the
support vectors x
i
Also keep in mind that solving the optimization problem involved
computing the inner products x
i
T
x
jbetween all training points.
w=Σα
iy
ix
ib = y
k-Σα
iy
ix
i
T
x
kfor any α
k > 0
f(x) = Σα
iy
ix
i
T
x + b

15. 15
Soft Margin Classification
What if the training set is not linearly separable?
Slack variablesξ
ican be added to allow misclassification of difficult
or noisy examples, resulting margin called soft.
ξ
i
ξ
i


R
k
k
εC
1
.
2
1
ww
What should our quadratic
optimization criterion be?
Minimize

16. 16
Soft Margin Classification Mathematically
The old formulation:
Modified formulation incorporates slack variables:
Parameter Ccan be viewed as a way to control overfitting: it
“trades off” the relative importance of maximizing the margin and
fitting the training data.
Find wand b such that
Φ(w)=w
T
wis minimized
and for all (x
i,y
i),i=1..n: y
i(w
T
x
i+ b)≥ 1
Find wand b such that
Φ(w)=w
T
w+ CΣξ
i is minimized
and for all (x
i,y
i),i=1..n: y
i(w
T
x
i+ b)≥ 1 –ξ
i,, ξ
i≥ 0

17. 17
Non-linear SVMs
Datasets that are linearly separable with some noise work out
great:
But what are we going to do if the dataset is just too hard?
How about… mapping data to a higher-dimensional space:
0
0
0
x
2
x
x
x

18. 18
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)

19. 19
The “Kernel Trick”
The linear classifier relies on inner product between vectors K(x
i,x
j)=x
i
T
x
j
If every datapoint is mapped into high-dimensional space via some
transformation Φ: x→φ(x), the inner product becomes:
K(x
i,x
j)= φ(x
i)
T
φ(x
j)
A kernel functionis a function that is equivalent to an inner product in
some feature space.
Example:
2-dimensional vectors x=[x
1 x
2]; let K(x
i,x
j)=(1 + x
i
T
x
j)
2
,
Need to show that K(x
i,x
j)= φ(x
i)
T
φ(x
j):
K(x
i,x
j)=(1 + x
i
T
x
j)
2
,= 1+ x
i1
2
x
j1
2
+ 2 x
i1x
j1x
i2x
j2+ x
i2
2
x
j2
2
+ 2x
i1x
j1 + 2x
i2x
j2=
= [1 x
i1
2
√2 x
i1x
i2 x
i2
2
√2x
i1 √2x
i2]
T
[1 x
j1
2
√2 x
j1x
j2 x
j2
2
√2x
j1 √2x
j2] =
= φ(x
i)
T
φ(x
j), where φ(x) = [1 x
1
2
√2 x
1x
2 x
2
2
√2x
1 √2x
2]
Thus, a kernel functionimplicitly maps data to a high-dimensional space
(without the need to compute each φ(x) explicitly).

20. 20
What Functions are Kernels?
For some functions K(x
i,x
j) checking that K(x
i,x
j)= φ(x
i)
T
φ(x
j) can be
cumbersome.
Mercer’s theorem:
Every semi-positive definite symmetric function is a kernel
Semi-positive definite symmetric functions correspond to a semi-
positive definite symmetric Gram matrix:
K(x
1,x
1)K(x
1,x
2)K(x
1,x
3)… K(x
1,x
n)
K(x
2,x
1)K(x
2,x
2)K(x
2,x
3) K(x
2,x
n)
… … … … …
K(x
n,x
1)K(x
n,x
2)K(x
n,x
3)… K(x
n,x
n)
K=
For any non-zero vector x, x
T
Kx>0

21. 21
Examples of Kernel Functions
Linear: K(x
i,x
j)= x
i
T
x
j
Polynomial of power p: K(x
i,x
j)= (1+x
i
T
x
j)
p
Gaussian (radial-basis function network):
Sigmoid: K(x
i,x
j)= tanh(β
0x
i
T
x
j + β
1))
2
exp(),(
2
2

ji
ji
xx
xx

K

22. 22
Support Vector Machine:
Algorithm
1. Choose a kernel function
2. Choose a value for C
3. Solve the quadratic programming problem (many software
packages available)
4. Construct the discriminant function from the support
vectors

23. 23
Some Issues
Choice of kernel
-Gaussian or polynomial kernel are the mostly used non-linear kernels
-if ineffective, more elaborate kernels are needed
-domain experts can give assistance in formulating appropriate similarity
measures
Choice of kernel parameters
-e.g. σ in Gaussian kernel
-σ is the distance between closest points with different classifications
-In the absence of reliable criteria, applications rely on the use of a
validation set or cross-validation to set such parameters.
Optimization criterion–Hard margin v.s. Soft margin
-a lengthy series of experiments in which various parameters are tested

24. 24
24
Why Is SVM Effective on High Dimensional Data?
The complexity of trained classifier is characterized by the # of
support vectors rather than the dimensionality of the data
The support vectors are the essential or critical training examples —
they lie closest to the decision boundary
If all other training examples are removed and the training is
repeated, the same separating hyperplane would be found
The number of support vectors found can be used to compute an
(upper) bound on the expected error rate of the SVM classifier, which
is independent of the data dimensionality
Thus, an SVM with a small number of support vectors can have good
generalization, even when the dimensionality of the data is high

25. 25
SVM applications
SVMs were originally proposed by Boser, Guyon and Vapnik in 1992 and gained
increasing popularity in late 1990s.
SVMs are currently among the best performers for a number of classification
tasks ranging from text to genomic data.
SVMs can be applied to complex data types beyond feature vectors (e.g.
graphs, sequences, relational data) by designing kernel functions for such data.
SVM techniques have been extended to a number of tasks such as regression
[Vapnik et al.’97], principal component analysis [Schölkopf et al. ’99], etc.
Most popular optimization algorithms for SVMs use decomposition to hill-climb
over a subset of α
i’s at a time, e.g. SMO [Platt ’99] and [Joachims ’99]
Tuning SVMs remains a black art: selecting a specific kernel and parameters is
usually done in a try-and-see manner.

26. 26
SVM vs. Neural Network
SVM
Relatively new concept
Deterministic algorithm
Nice Generalization
properties
Hard to learn –learned in
batch mode using quadratic
programming techniques,
but faster with good
optimization methods
Using kernels can learn very
complex functions
Neural Network
Relatively old
Nondeterministic algorithm
Generalizes well but doesn’t
have strong mathematical
foundation
Can easily be learned in
incremental fashion
To learn complex functions—
use multilayer perceptron (not
that trivial)

27. 27
Summary: Support Vector
Machine
1. Large Margin Classifier
Better generalization ability & less over-fitting
2. The Kernel Trick
Map data points to higher dimensional space in order
to make them linearly separable.
Since only dot product is used, we do not need to
represent the mapping explicitly.

28. 28
SVM resources
http://www.kernel-machines.org
http://www.csie.ntu.edu.tw/~cjlin/libsvm/

29. 29
Model Evaluation
Metrics for Performance Evaluation
How to evaluate the performance of a model?
Methods for Performance Evaluation
How to obtain reliable estimates?
Methods for Model Comparison
How to compare the relative performance among
competing models?

30. 30
Metrics for Performance Evaluation
Focus on the predictive capability of a model
Rather than how fast it takes to classify or build
models, scalability, etc.
Confusion Matrix:
PREDICTED CLASS
ACTUAL
CLASS
Class=YesClass=No
Class=Yes a b
Class=No c d
a: TP (true positive)
b: FN (false negative)
c: FP (false positive)
d: TN (true negative)

31. 31
Metrics for Performance Evaluation…
Most widely-used metric:
PREDICTED CLASS
ACTUAL
CLASS
Class=YesClass=No
Class=Yes a
(TP)
b
(FN)
Class=No c
(FP)
d
(TN)FNFPTNTP
TNTP
dcba
da





Accuracy

32. 32
Limitation of Accuracy
Consider a 2-class problem
Number of Class 0 examples = 9990
Number of Class 1 examples = 10
If model predicts everything to be class 0,
accuracy is 9990/10000 = 99.9 %
Accuracy is misleading because model does not detect
any class 1 example

33. 33
Cost Matrix
PREDICTED CLASS
ACTUAL
CLASS
C(i|j)Class=YesClass=No
Class=YesC(Yes|Yes)C(No|Yes)
Class=NoC(Yes|No)C(No|No)
C(i|j): Cost of misclassifying class j example as class i

34. 34
Cost-Sensitive Measurescba
a
pr
rp
ba
a
ca
a








2
22
(F) measure-F
(r) Recall
(p)Precision
Precision is biased towards C(Yes|Yes) & C(Yes|No)
Recall is biased towards C(Yes|Yes) & C(No|Yes)
F-measure is biased towards all except C(No|No)dwcwbwaw
dwaw
4321
41
Accuracy Weighted




35. 35
Model Evaluation
Metrics for Performance Evaluation
How to evaluate the performance of a model?
Methods for Performance Evaluation
How to obtain reliable estimates?
Methods for Model Comparison
How to compare the relative performance among
competing models?

36. 36
Methods for Performance Evaluation
How to obtain a reliable estimate of
performance?
Performance of a model may depend on other
factors besides the learning algorithm:
Class distribution
Cost of misclassification
Size of training and test sets

37. 37
Learning Curve
Learning curve shows
how accuracy changes
with varying sample size
Requires a sampling
schedule for creating
learning curve:
Arithmetic sampling
(Langley, et al)
Geometric sampling
(Provost et al)
Effect of small sample size:
-Bias in the estimate
-Variance of estimate

38. 38
Methods of Estimation
Holdout
Reserve 2/3 for training and 1/3 for testing
Random subsampling
Repeated holdout
Cross validation
Partition data into k disjoint subsets
k-fold: train on k-1 partitions, test on the remaining one
Leave-one-out: k=n
Stratified sampling
oversampling vs undersampling
Bootstrap
Sampling with replacement

39. 39
Model Evaluation
Metrics for Performance Evaluation
How to evaluate the performance of a model?
Methods for Performance Evaluation
How to obtain reliable estimates?
Methods for Model Comparison
How to compare the relative performance among
competing models?

40. 40
ROC (Receiver Operating Characteristic)
Characterize the trade-off between positive hits
and false alarms
ROC curve plots TP (on the y-axis) against FP (on
the x-axis)
Performance of each classifier represented as a
point on the ROC curve
changing the threshold of algorithm, sample
distribution or cost matrix changes the location of the
point

41. 41
ROC Curve
At threshold t:
TP=0.5, FN=0.5, FP=0.12, FN=0.88
-1-dimensional data set containing 2 classes (positive and negative)
-any points located at x > t is classified as positive

42. 42
ROC Curve
(TP,FP):
(0,0): declare everything
to be negative class
(1,1): declare everything
to be positive class
(1,0): ideal
Diagonal line:
Random guessing
Below diagonal line:
prediction is opposite of the
true class

43. 43
Using ROC for Model Comparison
No model consistently
outperform the other
M
1is better for
small FPR
M
2is better for
large FPR
Area Under the ROC
curve
Ideal:
Area = 1
Random guess:
Area = 0.5