DOC PREVIEW
UW-Madison CS 540 - Support Vector Machines

This preview shows page 1-2-3-25-26-27-28-50-51-52 out of 52 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Support Vector MachinesAnnouncementsAnnoucementsThings You Should KnowSlide 5What is a Support Vector Machine?What are Support Vector Machines Used For?Linear ClassifiersSlide 9Slide 10Slide 11Slide 12Classifier MarginMaximum MarginSlide 15Why Maximum Margin?Specifying a Line and MarginSlide 18Computing the MarginSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Learning the Maximum Margin ClassifierLearning via Quadratic ProgrammingUh-oh!Slide 32Slide 33Slide 34Slide 35Suppose we’re in 1 DimensionSlide 45Harder 1-Dimensional DatasetSlide 47Slide 48Slide 49Slide 50Common SVM Basis FunctionsSVM Kernel FunctionsThe Federalist PapersDescription of the DataFunction Words Based on Relative FrequenciesSLA Feature Selection for Classifying the Disputed Federalist PapersHyperplane Classifier Using 3 WordsResults: 3D Plot of HyperplaneMulti-Class ClassificationSummaryCase StudyCase Study -- ModelsCase Study ResultsSupport Vector MachinesLouis [email protected] section 2Announcements•Projects Due Today•I’ll put links on course website tomorrow.•Check out projects Courses before next week•Presentations next Week•15 minutes total•Leave a few minutes for questions•5 teams each day•Presentations In order as they appear on website•Email me any slides you want to use (or bring your own laptop)•Questions on final may be taken from presentations or project web-sitesAnnoucements•Things left in the course:•Presentations next week•Evaluate each-others projects (week after presentations)•2 more lectures after presentations•Reading:•Chapter 20 section 6 and 7 on Support Vector MachinesThings You Should Know•In Depth•K-NN, Decision Trees, Perceptron, Neural Network, Ensembles, Naïve Bayes, Bayesian Network, K-Means clustering•Induction•Inference•How they Divide up feature space•Important aspects of each modelThings You Should Know•Overview•Inductive Logic Programming•FOIL•PROGOL•GOLEM•Support Vector Machines•Re-enforcement Learning•Q-Learning•Understand the important points of each model•When are they used, how are the models more or less expressive•Important terms•General Idea of how the algorithm worksWhat is a Support Vector Machine?• An optimally defined surface • Typically nonlinear in the input space• Linear in a higher dimensional space• Implicitly defined by a kernel functionAcknowledgments: These slides combine and modify ones provided by Andrew Moore (CMU), Glenn Fung (Wisconsin), and Olvi Mangasarian (Wisconsin), and Chuck Dyer (Wisconsin)What are Support Vector Machines Used For?• Classification• Regression and data-fitting• Supervised and unsupervised learningLinear Classifiersf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)How would you classify this data?Linear Classifiersf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)How would you classify this data?Linear Classifiersf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)How would you classify this data?Linear Classifiersf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)How would you classify this data?Linear Classifiersf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)Any of these would be fine …… but which is best?Classifier Marginf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)Define the margin of a linear classifier as the width that the boundary could be increased by before hitting a data pointMaximum Marginf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)The maximum margin linear classifier is the linear classifier with the, um, maximum margin.This is the simplest kind of SVM (Called an LSVM)Linear SVMMaximum Marginf xydenotes +1denotes -1f(x,w,b) = sign(w · x + b)The maximum margin linear classifier is the linear classifier with the, um, maximum margin.This is the simplest kind of SVM (Called an LSVM)Support Vectors are those data points that the margin pushes up againstLinear SVMWhy Maximum Margin?denotes +1denotes -1f(x,w,b) = sign(w. x - b)The maximum margin linear classifier is the linear classifier with the, um, maximum margin.This is the simplest kind of SVM (Called an LSVM)Support Vectors are those data points that the margin pushes up against1. Intuitively this feels safest 2. If we’ve made a small error in the location of the boundary (it’s been jolted in its perpendicular direction) this gives us least chance of causing a misclassification3. Robust to outliers since the model is immune to change/removal of any non-support-vector data points4. There’s some theory (using VC dimension) that is related to (but not the same as) the proposition that this is a good thing5. Empirically it works very wellSpecifying a Line and Margin•How do we represent this mathematically?•… in m input dimensions?Plus-PlaneMinus-PlaneClassifier Boundary“Predict Class = +1” zone“Predict Class = -1” zoneSpecifying a Line and Margin•Plus-plane = { w · x + b = +1 }•Minus-plane = { w · x + b = -1 }Plus-PlaneMinus-PlaneClassifier Boundary“Predict Class = +1” zone“Predict Class = -1” zoneClassify as..+1 if w · x + b  1-1 if w · x + b ≤ -1Universe explodesif -1 < w · x + b < 1wx+b=1wx+b=0wx+b=-1Computing the Margin•Plus-plane = { w x + b = +1 }•Minus-plane = { w x + b = -1 }Claim: The vector w is perpendicular to the Plus-Plane“Predict Class = +1” zone“Predict Class = -1” zonewx+b=1wx+b=0wx+b=-1M = Margin (width)How do we compute M in terms of w and b?wComputing the Margin•Plus-plane = { w x + b = +1 }•Minus-plane = { w x + b = -1 }•The vector w is perpendicular to the Plus Plane•Let x- be any point on the minus plane•Let x+ be the closest plus-plane-point to x-“Predict Class = +1” zone“Predict Class = -1” zonewx+b=1wx+b=0wx+b=-1M = MarginHow do we compute M in terms of w and b?x-x+Any location in m: not necessarily a datapointAny location in Rm: not necessarily a data pointwComputing the Margin•Plus-plane = { w x + b = +1 }•Minus-plane = { w x + b = -1 }•The vector w is perpendicular to the Plus Plane•Let x- be any point on the minus plane•Let x+ be the closest plus-plane-point to x-•Claim: x+ = x- +  w for some value of . Why?“Predict Class = +1” zone“Predict Class = -1” zonewx+b=1wx+b=0wx+b=-1M = MarginHow do we compute M in terms of w and b?x-x+wComputing the Margin•Plus-plane = { w x + b = +1 }•Minus-plane = { w x + b = -1 }•The vector w is perpendicular to the Plus Plane•Let x- be


View Full Document

UW-Madison CS 540 - Support Vector Machines

Download Support Vector Machines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Support Vector Machines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Support Vector Machines 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?