Instance based Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 19th 2007 2005 2007 Carlos Guestrin 1 Why not just use Linear Regression 2005 2007 Carlos Guestrin 2 1 Using data to predict new data 2005 2007 Carlos Guestrin 3 Nearest neighbor 2005 2007 Carlos Guestrin 4 2 Univariate 1 Nearest Neighbor Given datapoints x1 y1 x2 y2 xN yN where we assume yi f xi for some unknown function f Given query point xq your job is to predict q Nearest Neighbor 1 Find the closest xi in our set of datapoints y f x i nn argmin xi xq i Here this is the closest datapoint H th ere da e clo this tap se is oin st t Here s a dataset with one input one output and four datapoints is s hi est t e s t e r lo in H he c apo t at d H th e r d a e c e th ta lo s is p o e is in t s t 2 Predict y yi nn y x 5 2005 2007 Carlos Guestrin 1 Nearest Neighbor is an example of Instance based learning A function approximator that has been around since about 1910 x1 x2 x3 To make a prediction search database for similar datapoints and fit with the local points xn y1 y2 y3 yn Four things make a memory based learner A distance metric How many nearby neighbors to look at A weighting function optional How to fit with the local points 2005 2007 Carlos Guestrin 6 3 1 Nearest Neighbor Four things make a memory based learner 1 A distance metric Euclidian and many more 2 How many nearby neighbors to look at One 3 A weighting function optional Unused 4 How to fit with the local points Just predict the same output as the nearest neighbor 7 2005 2007 Carlos Guestrin Multivariate 1 NN examples Regression Classification 2005 2007 Carlos Guestrin 8 4 Multivariate distance metrics Suppose the input vectors x1 x2 xn are two dimensional x1 x11 x12 x2 x21 x22 xN xN1 xN2 One can draw the nearest neighbor regions in input space Dist xi xj xi1 xj1 2 xi2 xj2 2 Dist xi xj xi1 xj1 2 3xi2 3xj2 2 The relative scalings in the distance metric affect region shapes 9 2005 2007 Carlos Guestrin Euclidean distance metric Or equivalently where D x x 2 2 x x i i i i D x x x x T x x 12 0 0 22 L L 0 0 L 0 L 0 L L L 2N Other Metrics Mahalanobis Rank based Correlation based 2005 2007 Carlos Guestrin 10 5 Notable distance metrics and their level sets Scaled Euclidian L2 L1 norm absolute Mahalanobis here on the previous slide is not necessarily diagonal but is symmetric L1 max norm 2005 2007 Carlos Guestrin 11 Consistency of 1 NN Consider an estimator fn trained on n examples Estimator is consistent if true error goes to zero as amount of data increases e g for no noise data consistent if Regression is not consistent e g 1 NN neural nets regression Representation bias 1 NN is consistent under some mild fineprint What about variance 2005 2007 Carlos Guestrin 12 6 1 NN overfits 2005 2007 Carlos Guestrin 13 k Nearest Neighbor Four things make a memory based learner 1 A distance metric Euclidian and many more 2 How many nearby neighbors to look at k 1 A weighting function optional Unused 2 How to fit with the local points Just predict the average output among the k nearest neighbors 2005 2007 Carlos Guestrin 14 7 k Nearest Neighbor here k 9 K nearest neighbor for function fitting smoothes away noise but there are clear deficiencies What can we do about all the discontinuities that k NN gives us 2005 2007 Carlos Guestrin 15 Weighted k NNs Neighbors are not all the same 2005 2007 Carlos Guestrin 16 8 Kernel regression Four things make a memory based learner 1 A distance metric Euclidian and many more 2 How many nearby neighbors to look at All of them 3 A weighting function optional wi exp D xi query 2 Kw2 Nearby points to the query are weighted strongly far points weakly The KW parameter is the Kernel Width Very important 4 How to fit with the local points Predict the weighted average of the outputs predict wiyi wi 2005 2007 Carlos Guestrin 17 Weighting functions wi exp D xi query 2 Kw2 Typically optimize Kw using gradient descent Our examples use Gaussian 2005 2007 Carlos Guestrin 18 9 Kernel regression predictions KW 10 KW 20 KW 80 Increasing the kernel width Kw means further away points get an opportunity to influence you As Kw 1 the prediction tends to the global average 2005 2007 Carlos Guestrin 19 Kernel regression on our test cases KW 1 32 of x axis width KW 1 32 of x axis width KW 1 16 axis width Choosing a good Kw is important Not just for Kernel Regression but for all the locally weighted learners we re about to see 2005 2007 Carlos Guestrin 20 10 Kernel regression can look bad KW Best KW Best KW Best Time to try something more powerful 2005 2007 Carlos Guestrin 21 Locally weighted regression Kernel regression Take a very very conservative function approximator called AVERAGING Locally weight it Locally weighted regression Take a conservative function approximator called LINEAR REGRESSION Locally weight it 2005 2007 Carlos Guestrin 22 11 Locally weighted regression Four things make a memory based learner A distance metric Any How many nearby neighbors to look at All of them A weighting function optional Kernels wi exp D xi query 2 Kw2 How to fit with the local points General weighted regression N 2 argmin wk y k T x k 2 k 1 23 2005 2007 Carlos Guestrin How LWR works Query Linear regression Locally weighted regression Same parameters for all queries Solve weighted linear regression for each query 1 WXT WX WXT WY 1 X T X X T Y 2005 2007 Carlos Guestrin w1 0 W 0 0 0 0 0 w2 0 0 0 O 0 0 0 wn 24 12 Another view of LWR Image from Cohn D A Ghahramani Z and Jordan M I 1996 Learning with Statistical Models JAIR Volume 4 pages25 129 145 2005 2007 Carlos Active Guestrin LWR on our test cases KW 1 16 of x axis width KW 1 32 of x axis width 2005 2007 Carlos Guestrin KW 1 8 of x axis width 26 13 Locally weighted polynomial regression Kernel Regression Kernel width KW at optimal level LW Linear Regression Kernel width KW at optimal level LW Quadratic Regression Kernel width KW at optimal level KW 1 100 x axis KW 1 40 x axis KW 1 15 x axis Local quadratic regression is easy just add quadratic terms to the WXTWX matrix As the regression degree increases the kernel width can increase without introducing bias 2005 2007 Carlos Guestrin 27 Curse of dimensionality for instance based learning Must store and retreve all data Most …
View Full Document
Unlocking...