SVMs Duality and the Kernel Trick cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 28th 2007 2005 2007 Carlos Guestrin 1 SVMs reminder 2005 2007 Carlos Guestrin 2 Dual SVM formulation the non separable case 2005 2007 Carlos Guestrin 3 Reminder from last time What if the data is not linearly separable Use features of features of features of features Feature space can get really large really quickly 4 2005 2007 Carlos Guestrin Dual formulation only depends on dot products not on w 2005 2007 Carlos Guestrin 5 Dot product of polynomials 2005 2007 Carlos Guestrin 6 Finally the kernel trick Never represent features explicitly Compute dot products in closed form Constant time high dimensional dotproducts for many classes of features Very interesting theory Reproducing Kernel Hilbert Spaces Not covered in detail in 10701 15781 more in 10702 2005 2007 Carlos Guestrin 7 Common kernels Polynomials of degree d Polynomials of degree up to d Gaussian kernels Sigmoid 2005 2007 Carlos Guestrin 8 Overfitting Huge feature space with kernels what about overfitting Maximizing margin leads to sparse set of support vectors Some interesting theory says that SVMs search for simple hypothesis with large margin Often robust to overfitting 2005 2007 Carlos Guestrin 9 What about at classification time For a new input x if we need to represent x we are in trouble Recall classifier sign w x b Using kernels we are cool 2005 2007 Carlos Guestrin 10 SVMs with kernels Choose a set of features and kernel function Solve dual problem to obtain support vectors i At classification time compute Classify as 2005 2007 Carlos Guestrin 11 Remember kernel regression Remember kernel regression 1 wi exp D xi query 2 Kw2 2 How to fit with the local points Predict the weighted average of the outputs predict wiyi wi 2005 2007 Carlos Guestrin 12 SVMs v Kernel Regression SVMs Kernel Regression or 2005 2007 Carlos Guestrin 13 SVMs v Kernel Regression SVMs Kernel Regression or Differences SVMs Learn weights i and bandwidth Often sparse solution KR Fixed weights learn bandwidth Solution may not be sparse Much simpler to implement 2005 2007 Carlos Guestrin 14 What s the difference between SVMs and Logistic Regression Loss function High dimensional features with kernels SVMs Logistic Regression Hinge loss Log loss Yes No 2005 2007 Carlos Guestrin 15 Kernels in logistic regression Define weights in terms of support vectors Derive simple gradient descent rule on i 2005 2007 Carlos Guestrin 16 What s the difference between SVMs and Logistic Regression Revisited Loss function High dimensional features with kernels Solution sparse Semantics of output SVMs Logistic Regression Hinge loss Log loss Yes Yes Often yes Almost always no Margin Real probabilities 2005 2007 Carlos Guestrin 17 What you need to know Dual SVM formulation How it s derived intuition The kernel trick Derive polynomial kernel Common kernels Kernelized logistic regression Differences between SVMs and logistic regression 2005 2007 Carlos Guestrin 18 Announcements Class projects out next week 2005 2007 Carlos Guestrin 19 PAC learning VC Dimension and Margin based Bounds Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 28th 2007 2005 2007 Carlos Guestrin 20 What now We have explored many ways of learning from data But How good is our classifier really How much data do I need to make it good enough 2005 2007 Carlos Guestrin 21 A simple setting Classification m data points Finite number of possible hypothesis e g dec trees of depth d A learner finds a hypothesis h that is consistent with training data Gets zero error in training errortrain h 0 What is the probability that h has more than true error errortrue h 2005 2007 Carlos Guestrin 22 How likely is a bad hypothesis to get m data points right Hypothesis h that is consistent with training data got m i i d points right Prob h with errortrue h gets one data point right Prob h with errortrue h gets m data points right 2005 2007 Carlos Guestrin 23 But there are many possible hypothesis that are consistent with training data 2005 2007 Carlos Guestrin 24 How likely is learner to pick a bad hypothesis Prob h with errortrue h gets m data points right There are k hypothesis consistent with data How likely is learner to pick a bad one 2005 2007 Carlos Guestrin 25 Union bound P A or B or C or D or 2005 2007 Carlos Guestrin 26 How likely is learner to pick a bad hypothesis Prob h with errortrue h gets m data points right There are k hypothesis consistent with data How likely is learner to pick a bad one 2005 2007 Carlos Guestrin 27 Review Generalization error in finite hypothesis spaces Haussler 88 Theorem Hypothesis space H finite dataset D with m i i d samples 0 1 for any learned hypothesis h that is consistent on the training data 2005 2007 Carlos Guestrin 28 Using a PAC bound Typically 2 use cases 1 Pick and give you m 2 Pick m and give you 2005 2007 Carlos Guestrin 29 Review Generalization error in finite hypothesis spaces Haussler 88 Theorem Hypothesis space H finite dataset D with m i i d samples 0 1 for any learned hypothesis h that is consistent on the training data Even if h makes zero errors in training data may make errors in test 2005 2007 Carlos Guestrin 30 Limitations of Haussler 88 bound Consistent classifier Size of hypothesis space 2005 2007 Carlos Guestrin 31 What if our classifier does not have zero error on the training data A learner with zero training errors may make mistakes in test set What about a learner with errortrain h in training set 2005 2007 Carlos Guestrin 32 Simpler question What s the expected error of a hypothesis The error of a hypothesis is like estimating the parameter of a coin Chernoff bound for m i i d coin flips x1 xm where xi 2 0 1 For 0 1 2005 2007 Carlos Guestrin 33 Using Chernoff bound to estimate error of a single hypothesis 2005 2007 Carlos Guestrin 34 But we are comparing many hypothesis Union bound For each hypothesis hi What if I am comparing two hypothesis h1 and h2 2005 2007 Carlos Guestrin 35 Generalization bound for H hypothesis Theorem Hypothesis space H finite dataset D with m i i d samples 0 1 for any learned hypothesis h 2005 2007 Carlos Guestrin 36 PAC bound and Bias Variance tradeoff or after moving some terms around with probability at least 1 Important PAC bound holds for all h but doesn t guarantee that algorithm finds best h 2005 2007 Carlos Guestrin 37 What about the size of the hypothesis space How
View Full Document
Unlocking...