Transcript CSE5334 Data Mining - University of Texas at Arlington

CSE4334/5334
DATA MINING
CSE4334/5334 Data Mining, Fall 2014
Lecture 9: SVM
Department of Computer Science and Engineering, University of Texas at Arlington
Chengkai Li
(Slides courtesy of Vipin Kumar)
Support Vector Machines

Find a linear hyperplane (decision boundary) that will separate the data
Support Vector Machines
B1

One Possible Solution
Support Vector Machines
B2

Another possible solution
Support Vector Machines
B2

Other possible solutions
Support Vector Machines
B1
B2


Which one is better? B1 or B2?
How do you define better?
Support Vector Machines
B1
B2
b21
b22
margin
b12

b11
Find hyperplane maximizes the margin => B1 is better than B2
Support Vector Machines
B1
 
w x b  0
 
w  x  b  1
 
w  x  b  1
b11
 
if w  x  b  1
1

f ( x)  
 
 1 if w  x  b  1
b12
2
Margin   2
|| w ||
Support Vector Machines

We want to maximize:
2
Margin   2
|| w ||

Which is equivalent to minimizing this objective function:

But subjected to the following constraints:
 2
|| w ||
L( w) 
2

 
if w  x i  b  1
1

f ( xi )  
 

1
if
w

x

b


1

i
This is a constrained optimization problem

Numerical approaches to solve it (e.g., quadratic programming)
Support Vector Machines

What if the problem is not linearly separable?
Support Vector Machines

What if the problem is not linearly separable?
 Introduce
slack variables

Need to minimize:

Subject to:
 2
|| w ||
 N k
L( w) 
 C  i 
2
 i 1 
 
if w  x i  b  1 - i
1

f ( xi )  
 
 1 if w  x i  b  1  i
Nonlinear Support Vector Machines

What if decision boundary is not linear?
Nonlinear Support Vector Machines

Transform data into higher dimensional space