Two SVM tutorials linked in class website please read both High level presentation with applications Hearst 1998 Detailed tutorial Burges 1998 SVMs Duality and the Kernel Trick cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 1st 2006 2006 Carlos Guestrin 1 SVMs reminder 2006 Carlos Guestrin 2 Today s lecture Learn one of the most interesting and exciting recent advancements in machine learning The kernel trick High dimensional feature spaces at no extra cost But first a detour Constrained optimization 2006 Carlos Guestrin 3 w x b 0 Dual SVM interpretation 2006 Carlos Guestrin 4 Dual SVM formulation the linearly separable case 2006 Carlos Guestrin 5 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 6 2006 Carlos Guestrin number of monomial terms Higher order polynomials d 4 m input features d degree of polynomial d 3 d 2 number of input dimensions 2006 Carlos Guestrin grows fast d 6 m 100 about 1 6 billion terms 7 Dual formulation only depends on dot products not on w 2006 Carlos Guestrin 8 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 2006 Carlos Guestrin 9 Common kernels Polynomials of degree d Polynomials of degree up to d Gaussian kernels Sigmoid 2006 Carlos Guestrin 10 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 2006 Carlos Guestrin 11 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 2006 Carlos Guestrin 12 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 2006 Carlos Guestrin 13 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 2006 Carlos Guestrin 14 SVMs v Kernel Regression SVMs Kernel Regression or 2006 Carlos Guestrin 15 SVMs v Kernel Regression SVMs Kernel Regression or Differences SVMs Learn weights alpha i and bandwidth Often sparse solution KR Fixed weights learn bandwidth Solution may not be sparse Much simpler to implement 2006 Carlos Guestrin 16 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 2006 Carlos Guestrin 17 Kernels in logistic regression Define weights in terms of support vectors Derive simple gradient descent rule on i 2006 Carlos Guestrin 18 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 2006 Carlos Guestrin 19 What you need to know Dual SVM formulation How it s derived The kernel trick Derive polynomial kernel Common kernels Kernelized logistic regression Differences between SVMs and logistic regression 2006 Carlos Guestrin 20 Acknowledgment SVM applet http www site uottawa ca gcaron applets htm 2006 Carlos Guestrin 21 More details General http www learning with kernels org Example of more complex bounds http www research ibm com people t tzhang papers jmlr02 cover ps gz PAC learning VC Dimension and Margin based Bounds Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 1st 2005 2006 Carlos Guestrin 22 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 2006 Carlos Guestrin 23 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 2006 Carlos Guestrin 24 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 2006 Carlos Guestrin 25 But there are many possible hypothesis that are consistent with training data 2006 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 2006 Carlos Guestrin 27 Union bound P A or B or C or D or 2006 Carlos Guestrin 28 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 2006 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 2006 Carlos Guestrin 30 Using a PAC bound Typically 2 use cases 1 Pick and give you m 2 Pick m and give you 2006 Carlos Guestrin 31 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 2006 Carlos Guestrin 32 Limitations of Haussler 88 bound Consistent classifier Size of hypothesis space 2006 Carlos Guestrin 33 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 2006 Carlos Guestrin 34 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 d d coin flips x1 xm where xi 0 1 For 0 1 2006 Carlos Guestrin 35 Using Chernoff bound to estimate error of a single hypothesis 2006 Carlos
View Full Document
Unlocking...