UT Dallas CS 6375 - Support Vector Machines
Pages 23

Unformatted text preview:

Support Vector Machines Nicholas Ruozzi University of Texas at Dallas Slides adapted from David Sontag and Vibhav Gogate Support Vector Machines How can we decide between perfect classifiers 2 Support Vector Machines How can we decide between perfect classifiers 3 Support Vector Machines Define the margin to be the distance of the closest data point to the classifier 4 Support Vector Machines Support vector machines SVMs Choose the classifier with the largest margin Has good practical and theoretical performance 5 Some Geometry 0 0 6 In dimensions a hyperplane is a solution to the equation with The vector hyperplane is sometimes called the normal vector of the Some Geometry 0 In dimensions a hyperplane is a solution to the equation Note that this equation is scale invariant for any scalar 0 0 7 Some Geometry 0 The distance between a point is the length of the segment perpendicular to the line to the point and a hyperplane 0 The vector from to is given by 8 Scale Invariance 0 By scale invariance we can assume that The maximum margin is always attained by choosing 1 so that it is equidistant from the closest data point classified as 1 and the closest data point classified as 1 0 9 Scale Invariance 0 We want to maximize the margin subject to the constraints that But how do we compute the size of the margin 1 10 Some Geometry 1 0 1 Putting it all together and 1 0 and 1 which gives 1 11 SVMs This analysis yields the following optimization problem such that max 1 Or equivalently 1 for all such that 2 min 1 for all 12 SVMs such that 2 min This is a standard quadratic programming problem 1 for all Falls into the class of convex optimization problems Can be solved with many specialized optimization tools e g quadprog in MATLAB 13 SVMs 1 0 1 Where does the name come from The set of all data points such that called support vectors are 1 The SVM classifier is completely determined by the support vectors can delete the rest and get the same answer 14 SVMs What if the data isn t linearly separable What if we want to do more than just binary classification i e if 1 2 3 15 SVMs What if the data isn t linearly separable Use feature vectors Relax the constraints coming soon What if we want to do more than just binary classification i e if 1 2 3 16 Multiclass Classification 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 3 1 3 3 3 3 3 3 3 3 17 One Versus All SVMs 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 3 1 3 3 3 3 3 3 3 3 18 One Versus All SVMs 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 3 1 3 3 3 3 3 3 3 3 19 Regions correctly classified by exactly one classifier One Versus All SVMs Compute a classifier for each label versus the remaining labels i e and SVM with the selected label as plus and the remaining labels changed to minuses Let be the classifier for the label For a new datapoint classify it as Drawbacks argmax If there are possible labels requires learning classifiers over the entire data set 20 One Versus All SVMs 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 3 1 3 3 3 3 3 3 3 3 21 Regions in which points are classified by highest value of One Versus One SVMs Alternative strategy is to construct a classifier for all possible pairs of labels Given a new data point can classify it by majority vote i e find the most common label among all of the possible classifiers If there are labels requires computing different classifiers each of which uses only a fraction of the data 2 Drawbacks Can overfit if some pairs of labels do not have a significant amount of data plus it can be computationally expensive 22 One Versus One SVMs 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 23 Regions determined by majority vote over the classifiers

View Full Document

UT Dallas CS 6375 - Support Vector Machines

Pages: 23
Documents in this Course

26 pages

39 pages

26 pages

17 pages

59 pages

41 pages

21 pages

28 pages

30 pages

12 pages

17 pages

17 pages

41 pages

9 pages

23 pages

19 pages

24 pages

16 pages

18 pages

18 pages

16 pages

20 pages

16 pages

19 pages

11 pages

19 pages

26 pages

28 pages

10 pages

6 pages

20 pages

26 pages

28 pages

10 pages

6 pages

20 pages

17 pages

17 pages

41 pages

9 pages

23 pages

19 pages

24 pages

16 pages

18 pages

18 pages

16 pages

26 pages

20 pages

16 pages

19 pages

11 pages

19 pages

24 pages

16 pages

18 pages

18 pages

16 pages

26 pages

20 pages

16 pages

19 pages

11 pages

19 pages

26 pages

28 pages

10 pages

6 pages

20 pages

17 pages

17 pages

41 pages

9 pages

23 pages

19 pages

24 pages

16 pages

18 pages

18 pages

16 pages

26 pages

20 pages

16 pages

19 pages

11 pages

19 pages

26 pages

28 pages

10 pages

6 pages

20 pages

17 pages

17 pages

41 pages

9 pages

23 pages

19 pages

2 pages

2 pages

4 pages

2 pages

2 pages

2 pages

2 pages

3 pages

3 pages

19 pages

17 pages

23 pages

16 pages

16 pages

18 pages

24 pages

17 pages

6 pages

20 pages

26 pages

28 pages

9 pages

26 pages

11 pages

16 pages

20 pages

19 pages

41 pages

19 pages

10 pages

18 pages

2 pages

3 pages

2 pages

2 pages

2 pages

4 pages

2 pages

25 pages

18 pages

19 pages

8 pages

7 pages

5 pages

7 pages

8 pages

3 pages

4 pages

3 pages

3 pages

3 pages

19 pages

4 pages

20 pages

36 pages

5 pages

3 pages

2 pages

2 pages

2 pages

2 pages

3 pages

3 pages

3 pages

2 pages

4 pages

3 pages

2 pages

2 pages

2 pages

3 pages

2 pages

2 pages

39 pages

2 pages

2 pages

2 pages

4 pages

2 pages

2 pages

3 pages

3 pages

2 pages

4 pages

26 pages

28 pages

9 pages

26 pages

11 pages

16 pages

20 pages

19 pages

41 pages

19 pages

18 pages

24 pages

17 pages

6 pages

20 pages

2 pages

4 pages

2 pages

2 pages

3 pages

3 pages

28 pages

9 pages

26 pages

11 pages

16 pages

20 pages

19 pages

41 pages

19 pages

6 pages

20 pages

26 pages