1 00:00:00,520 --> 00:00:02,980 So we are starting a new module in this class. 2 00:00:02,980 --> 00:00:05,570 The module is about large scale machine learning. 3 00:00:05,570 --> 00:00:08,690 So what we will talk about is a class, class of methods for 4 00:00:08,690 --> 00:00:12,920 working with data that falls under the umbrella of machine learning. 5 00:00:12,920 --> 00:00:17,500 Where the idea is that based on, we want to analyze the data so that based on 6 00:00:17,500 --> 00:00:22,120 the features of the data we want to predict certain properties of items or 7 00:00:22,120 --> 00:00:26,350 data points that we haven't yet seen, or that we are going to see in the future. 8 00:00:26,350 --> 00:00:29,660 And the simplest method that we will talk about today is called 9 00:00:29,660 --> 00:00:31,650 Nearest Neighbor, classifier. 10 00:00:31,650 --> 00:00:34,770 And based on this idea of Nearest Neighbor classifiers, we will then 11 00:00:34,770 --> 00:00:39,790 develop this into more complicated and more advanced Machine Learning, models. 12 00:00:39,790 --> 00:00:43,990 The idea of Machine Learning or what is known also as Supervised Learning is that, 13 00:00:43,990 --> 00:00:49,030 we would like to learn, a function that is basically making predictions for us. 14 00:00:49,030 --> 00:00:52,290 So in, in an abstract way, we would like to estimate based on 15 00:00:52,290 --> 00:00:57,370 the data a function f of x so that given f, we can predict y. 16 00:00:57,370 --> 00:01:01,440 Now, of course, the question is what is x and what is y. 17 00:01:01,440 --> 00:01:07,730 Most generally, there kind of two way, two separate things what y can represent. 18 00:01:07,730 --> 00:01:12,030 If y represent a real number, then this is what is known as regression. 19 00:01:12,030 --> 00:01:16,210 Based on some value of x, I want to predict a real number y. 20 00:01:16,210 --> 00:01:20,490 So for example if I would want to, given someone's age and 21 00:01:20,490 --> 00:01:25,230 someone's, ethnicity and so on, maybe I would want to predict their life 22 00:01:25,230 --> 00:01:29,970 expectancy then this would be an example of, a regression problem. 23 00:01:29,970 --> 00:01:33,310 However y can also be our categorical variable, right? 24 00:01:33,310 --> 00:01:37,700 Which, you can think of it as a binary variable or something like that. 25 00:01:37,700 --> 00:01:39,200 Right? This predicting of 26 00:01:39,200 --> 00:01:42,850 the categorical variable is known as a problem of classification. 27 00:01:42,850 --> 00:01:47,180 Right, so for example, one, one case of classification would be that I give you 28 00:01:47,180 --> 00:01:52,010 a document, and I, or an email, and I want to ask you, is this spam email or not? 29 00:01:52,010 --> 00:01:55,370 Right, so given a document you want to decide, return a binary var, 30 00:01:55,370 --> 00:01:58,700 variable, 0 or 1, where 0 means not spam, and 31 00:01:58,700 --> 00:02:01,500 1 means yes this is spam, let's discard this email. 32 00:02:02,800 --> 00:02:05,620 Of course you can also predict kind of more complex objects. 33 00:02:05,620 --> 00:02:09,500 For example you can sometimes y could be a ranking. 34 00:02:09,500 --> 00:02:10,740 An ordering of things. 35 00:02:10,740 --> 00:02:13,840 Or it could be for example if you are working with sentences. 36 00:02:13,840 --> 00:02:15,530 Y could be a whole Parse tree. 37 00:02:15,530 --> 00:02:19,240 But what we focus on in our lecture is mostly on classification. 38 00:02:19,240 --> 00:02:21,790 So basically, given a set of Xs, 39 00:02:21,790 --> 00:02:26,020 decide what is the label, the binary label of every x. 40 00:02:26,020 --> 00:02:29,560 And, what is, why do we call this whole thing supervised learning is 41 00:02:29,560 --> 00:02:32,210 because we think of our data as labeled. 42 00:02:32,210 --> 00:02:36,250 We are thinking that we are getting a set of many pairs, x and y. 43 00:02:36,250 --> 00:02:40,300 Where x is, is, x is the data that we are getting and 44 00:02:40,300 --> 00:02:43,720 y is the variable or the class that we want to predict. 45 00:02:43,720 --> 00:02:47,400 So we can think of x as a vector of binary categorical or 46 00:02:47,400 --> 00:02:52,250 real, valued features and y as the class, let's say plus 1, 47 00:02:52,250 --> 00:02:56,040 minus 1, or a real number if you are working with regression. 48 00:02:56,040 --> 00:02:59,990 And if you think about this case basically we can think of x as a set of 49 00:02:59,990 --> 00:03:03,140 features representing our data point and 50 00:03:03,140 --> 00:03:06,260 y is the property of the data point we want to predict. 51 00:03:06,260 --> 00:03:09,750 So, if I want to predict, spam then for 52 00:03:09,750 --> 00:03:12,500 example x could be a set of words in the email. 53 00:03:12,500 --> 00:03:17,230 And y is a a binary variable that tells us whether that email is spam or not. 54 00:03:17,230 --> 00:03:20,620 If I would want to for example, model, human diseases. 55 00:03:20,620 --> 00:03:27,120 I could, x could be a set of, symptoms or set of characteristics of a patient and 56 00:03:27,120 --> 00:03:30,940 y could be whether that patient suffers from that disease or not. 57 00:03:30,940 --> 00:03:32,040 So this is the first idea. 58 00:03:32,040 --> 00:03:33,930 The idea of having a set of features, and 59 00:03:33,930 --> 00:03:37,060 then having the dependant variable that you want to predict. 60 00:03:37,060 --> 00:03:39,800 Based on that set of features using our function F. 61 00:03:41,070 --> 00:03:44,370 Another important idea is that we will think of our daytime sometimes as 62 00:03:44,370 --> 00:03:46,310 coming as this big matrix, right. 63 00:03:46,310 --> 00:03:50,580 Where we can take our features, feature vectors, and stack them together in 64 00:03:50,580 --> 00:03:55,520 a matrix and then we can think of, our depend dependent variable's Y, so 65 00:03:55,520 --> 00:03:59,360 the class value that TBN could predict has a long thin vector. 66 00:03:59,360 --> 00:04:03,290 And of course, what you can also do then is to say, based on this what have been 67 00:04:03,290 --> 00:04:08,320 called training data, we want to estimate our function F, so that whenever, 68 00:04:09,320 --> 00:04:13,660 we ob, we observe some new unseen data x prime, 69 00:04:13,660 --> 00:04:17,410 we will able to predict what are the associated class values. 70 00:04:17,410 --> 00:04:20,020 With this unseen data, right? 71 00:04:20,020 --> 00:04:23,920 So the idea is that if you want to learn our function F based on 72 00:04:23,920 --> 00:04:28,930 the training data set that is labeled in a sense that we have both x's and y's, and 73 00:04:28,930 --> 00:04:31,400 then in the future, our hope is that we will, 74 00:04:31,400 --> 00:04:36,170 we will get this new data set, this we call it a testing data set. 75 00:04:36,170 --> 00:04:41,340 Where we only know x's and from x's we will try to predict, these y's. 76 00:04:41,340 --> 00:04:45,190 So we will always kind of think about the training stage of our category system and 77 00:04:45,190 --> 00:04:47,780 then the testing or application state of our algorithm. 78 00:04:49,240 --> 00:04:53,830 So in this module, we will talk about several different, machine learning at, 79 00:04:53,830 --> 00:04:56,970 methods where we will be kind of focusing on large scale data. 80 00:04:56,970 --> 00:05:01,370 In particular, we will talk today about, k-Nearest neighbor, which is in, 81 00:05:01,370 --> 00:05:05,200 which is something that a method in a class of instance based learning. 82 00:05:05,200 --> 00:05:08,740 And then we will also talk about support vector machines and decision trees. 83 00:05:08,740 --> 00:05:12,110 And kind of the main question when working with machine learning methods is, 84 00:05:12,110 --> 00:05:13,770 how do we efficiently train? 85 00:05:13,770 --> 00:05:16,740 Or build a model based on the based on the data? 86 00:05:16,740 --> 00:05:21,020 So in a sense the main question that arises in machine learning is how do I 87 00:05:21,020 --> 00:05:22,550 find this function f. 88 00:05:22,550 --> 00:05:27,720 That takes the input features and predicts the, the class variable. 89 00:05:27,720 --> 00:05:29,810 Right? So, learning or 90 00:05:29,810 --> 00:05:34,840 estimating this function F is the hardest part of of machine learning. 91 00:05:35,990 --> 00:05:38,950 So an example of instance based learning, 92 00:05:38,950 --> 00:05:42,240 the idea here is that we want to use existing in, instances or 93 00:05:42,240 --> 00:05:47,020 resisting data points to make predictions about unknown or unlabeled data points. 94 00:05:47,020 --> 00:05:50,940 So the example of such a method is called nearest neighbor. 95 00:05:50,940 --> 00:05:54,720 Right, where the idea is, we take all our training data, all our x, 96 00:05:54,720 --> 00:05:58,950 y pairs, lets say in memory or on the disk, and then whenever a new, 97 00:05:58,950 --> 00:06:05,220 new query example, let's call it q comes, we find other examples, x, 98 00:06:05,220 --> 00:06:08,330 x prime that are, that are, similar to it. 99 00:06:08,330 --> 00:06:12,370 And then based on the value, the labels of those examples, we also predict the value, 100 00:06:13,820 --> 00:06:17,570 y, y* for the, for the given query point q. 101 00:06:17,570 --> 00:06:20,610 So what is interesting about nearest neighbor, is that is, 102 00:06:20,610 --> 00:06:23,530 that it works both for regression and classification. 103 00:06:23,530 --> 00:06:28,720 And if we think about recommended systems, in particular, collaborative filtering. 104 00:06:28,720 --> 00:06:33,220 Collaborative filtering is an example of a nearest neighbor classifier, right? 105 00:06:33,220 --> 00:06:36,390 There, there the idea was that when a user comes, 106 00:06:36,390 --> 00:06:41,120 we find k most similar users to our given query user q. 107 00:06:41,120 --> 00:06:44,390 Then we look at what this other k most similar users, 108 00:06:44,390 --> 00:06:45,890 what are the movies they like. 109 00:06:45,890 --> 00:06:48,380 And based on the movies these other users like. 110 00:06:48,380 --> 00:06:51,920 We are making a recommendation to our creative user queue. 111 00:06:51,920 --> 00:06:56,370 So this is exactly an example of our nearest neighbor, where a query arrives. 112 00:06:56,370 --> 00:07:00,400 We find nearest data points based on the labels of the nearest data points, 113 00:07:00,400 --> 00:07:06,140 we kind of try to combine those labels, to talk about the label of the created point. 114 00:07:06,140 --> 00:07:09,610 The simplest of all nearest neighbor classifiers is what is 115 00:07:09,610 --> 00:07:12,210 called a one nearest neighbor classifier. 116 00:07:12,210 --> 00:07:14,420 Right? Where the idea is that whenever we want to 117 00:07:14,420 --> 00:07:20,840 make, a, decide on a label of a given, of a given data point, we simply find the, 118 00:07:20,840 --> 00:07:25,790 the point most similar to it and, and use that label as a prediction. 119 00:07:25,790 --> 00:07:30,215 So in a par, in particular when we want to, em, du, implement the nearest neighbor 120 00:07:30,215 --> 00:07:32,840 classifier, there are several things we have to decide on. 121 00:07:32,840 --> 00:07:35,760 First, is we have to decide on the distance metric, right. 122 00:07:35,760 --> 00:07:40,190 How do we measure the similarities or distances between data points? 123 00:07:40,190 --> 00:07:41,190 So for example, 124 00:07:41,190 --> 00:07:44,920 in the case I will show you here is let's assume we are using euclidean distance. 125 00:07:45,932 --> 00:07:50,310 And then another thing we have to decide is how many neighbors are we looking at? 126 00:07:50,310 --> 00:07:52,890 Are we looking at one nearest neighbor, five nearest neighbors? 127 00:07:52,890 --> 00:07:56,380 How many nearest points do we want to examine? 128 00:07:56,380 --> 00:07:59,840 So in our case, let's look at one nearest neighbor. 129 00:07:59,840 --> 00:08:01,370 Another important thing is, 130 00:08:01,370 --> 00:08:07,530 how are we weighing this different neighbors that we are combining together? 131 00:08:07,530 --> 00:08:09,710 Right? So in this case that I'll show you, 132 00:08:09,710 --> 00:08:11,570 we won't worry about this just yet. 133 00:08:11,570 --> 00:08:16,070 And then another important, question is how do I then, 134 00:08:16,070 --> 00:08:18,450 take all these nearest neighbors and 135 00:08:18,450 --> 00:08:23,480 combine the, their values into a single point that I can use as prediction? 136 00:08:23,480 --> 00:08:27,580 And in our case because we are just using one nearest neighbor, all we have to do 137 00:08:27,580 --> 00:08:33,280 is just predict the same output as at is, as is the value of the nearest neighbor. 138 00:08:33,280 --> 00:08:37,810 For example, now if I, show you how this works, here I have a simple two 139 00:08:37,810 --> 00:08:42,590 dimensional data set where I can think of the x axis as the input feature, and 140 00:08:42,590 --> 00:08:45,250 the y axis is the value I would like to predict. 141 00:08:45,250 --> 00:08:48,350 And, blue points are my data points, and 142 00:08:48,350 --> 00:08:53,350 the black line shows the output of one, nearest neighbor classifier. 143 00:08:53,350 --> 00:08:54,830 You basically see that for 144 00:08:54,830 --> 00:08:58,990 around every point we exactly just predict the value, of that point. 145 00:08:58,990 --> 00:09:04,400 And then if our data set is noisy, our, our prediction jumps around, quite a lot. 146 00:09:04,400 --> 00:09:05,870 If our data set is nice and 147 00:09:05,870 --> 00:09:10,240 smooth, we are basically predicting this almost like, a step function. 148 00:09:10,240 --> 00:09:14,460 So, this seems to be working quite well in this simple example, but 149 00:09:14,460 --> 00:09:17,310 we are seeing the, what the method is suffering from. 150 00:09:17,310 --> 00:09:20,930 It is making lots of very, er, spiky, or 151 00:09:20,930 --> 00:09:25,560 sharp decisions, because we are only looking at the one nearest neighbor. 152 00:09:25,560 --> 00:09:27,480 So we want to generalize this, and 153 00:09:27,480 --> 00:09:31,570 maybe try to kind of use more nearest neighbors to average better. 154 00:09:31,570 --> 00:09:33,600 So let's look at how that works. 155 00:09:33,600 --> 00:09:34,790 Right? So if we want, 156 00:09:34,790 --> 00:09:38,280 want to generalize now our method according to k nearest neighbor, 157 00:09:38,280 --> 00:09:42,160 then now the idea is I, I'm able to use the Euclidean distance. 158 00:09:42,160 --> 00:09:44,570 Now how many, neighbors should we look at. 159 00:09:44,570 --> 00:09:45,450 Will we look k? 160 00:09:45,450 --> 00:09:49,270 When k is some number chosen by the user. 161 00:09:49,270 --> 00:09:52,150 And then how do we combine the labels of all the k neigh, 162 00:09:52,150 --> 00:09:54,420 neighbors into the, into one label? 163 00:09:55,490 --> 00:09:59,640 For example right now let's just say that our output will be the average out, 164 00:09:59,640 --> 00:10:04,300 the average of the, the classes of the k nearest neighbors, so, 165 00:10:04,300 --> 00:10:08,980 very simply for example here is our, data sets from the previous slide. 166 00:10:08,980 --> 00:10:14,440 We are using here k equals 9, which means we are averaging together the y value 167 00:10:14,440 --> 00:10:17,260 of the 9 nearest points to our query point. 168 00:10:17,260 --> 00:10:22,100 And given the blue data, this is the predicted value that we would make. 169 00:10:22,100 --> 00:10:26,750 For example notice that now our predicted function, 170 00:10:26,750 --> 00:10:29,470 our function f of x in, in some sense if you like. 171 00:10:30,500 --> 00:10:33,840 Is much smoother than what is was before. 172 00:10:33,840 --> 00:10:36,660 While nearest neighbor is a very simple method. 173 00:10:36,660 --> 00:10:40,270 One thing that we haven't yet discussed is actually how do we got, go and 174 00:10:40,270 --> 00:10:41,880 find nearest neighbors. 175 00:10:41,880 --> 00:10:47,630 So our, the task here is basically given a set of points, in, in some, 176 00:10:47,630 --> 00:10:50,660 in some space, so this is basically our data set. 177 00:10:50,660 --> 00:10:53,390 Our goal is to find a, 178 00:10:53,390 --> 00:10:56,920 another set of points that are close to our created point, Q. 179 00:10:56,920 --> 00:11:00,460 And, there are two types of queries we may want to ask, 180 00:11:00,460 --> 00:11:06,030 one type of query to say give me nearest K points to our, point Q, 181 00:11:06,030 --> 00:11:09,870 and another way to ask a query would be the range search where he 182 00:11:09,870 --> 00:11:14,230 would say give me all the points that are inside some distance of Q. 183 00:11:14,230 --> 00:11:18,510 In both of these cases, a [INAUDIBLE] solution would require a linear pass over 184 00:11:18,510 --> 00:11:22,530 the data, so it would take linear time, but we already know how to do this better. 185 00:11:22,530 --> 00:11:25,600 For example, using locality sensitive hashing, we could, 186 00:11:25,600 --> 00:11:29,640 we could find, nearest neighbors in near, in near constant time. 187 00:11:29,640 --> 00:11:32,660 So that would be a good way how to really make nearest neighbor 188 00:11:32,660 --> 00:11:35,160 classifiers scale to large scale data.