1 00:00:07,150 --> 00:00:10,189 When we build the supervised learning model, 2 00:00:10,189 --> 00:00:12,710 whether it's for classification or regression, 3 00:00:12,710 --> 00:00:14,839 it's not only important for the model to make 4 00:00:14,839 --> 00:00:18,214 correct predictions on the examples it saw in the training data. 5 00:00:18,214 --> 00:00:20,149 If that were the only definition of success, 6 00:00:20,149 --> 00:00:22,934 then supervised learning algorithms could simply memorize all of 7 00:00:22,934 --> 00:00:27,199 the training data and always have a 100 percent accuracy. 8 00:00:27,199 --> 00:00:29,655 Of course, that's not what happens in the real world. 9 00:00:29,655 --> 00:00:30,980 What we actually want from 10 00:00:30,980 --> 00:00:34,570 a supervised machine learning algorithm is the ability to predict a class 11 00:00:34,570 --> 00:00:40,390 or target value correctly on a test set of future examples that haven't been seen before. 12 00:00:40,390 --> 00:00:42,140 This ability to perform well on 13 00:00:42,140 --> 00:00:47,359 a held out test set is the algorithms ability to generalize. 14 00:00:47,359 --> 00:00:50,895 How do we know that our trained supervised model will generalize well? 15 00:00:50,895 --> 00:00:54,234 In other words, perform well on an unseen test set. 16 00:00:54,234 --> 00:00:56,270 Well, typically machine learning makes 17 00:00:56,270 --> 00:01:00,530 an important assumption that the future test set has the same properties, 18 00:01:00,530 --> 00:01:06,500 or, more technically, as drawn from the same underlying distribution as the training set. 19 00:01:06,500 --> 00:01:10,265 This means that if we observe our model has good accuracy on the training set, 20 00:01:10,265 --> 00:01:13,265 and the training set and test sets are similar, 21 00:01:13,265 --> 00:01:17,144 we can also expect that it will do well on the test set. 22 00:01:17,144 --> 00:01:20,030 Unfortunately, sometimes this doesn't happen 23 00:01:20,030 --> 00:01:23,150 due to an important problem known as 'overfitting'. 24 00:01:23,150 --> 00:01:26,930 Informally, overfitting typically occurs when we try to fit 25 00:01:26,930 --> 00:01:31,430 a complex model with an inadequate amount of training data. 26 00:01:31,430 --> 00:01:36,230 And overfitting model uses its ability to capture complex patterns by being great at 27 00:01:36,230 --> 00:01:37,459 predicting lots and lots of 28 00:01:37,459 --> 00:01:41,915 specific data samples or areas of local variation in the training set. 29 00:01:41,915 --> 00:01:44,719 But it often misses seeing global patterns in 30 00:01:44,719 --> 00:01:48,980 the training set that would help it generalize well on the unseen test set. 31 00:01:48,980 --> 00:01:52,144 It can't see these more global patterns because, intuitively, 32 00:01:52,144 --> 00:01:56,404 there's not enough data to constrain the model to respect these global trends. 33 00:01:56,404 --> 00:01:58,849 As a result, the training set accuracy is 34 00:01:58,849 --> 00:02:01,340 a hopelessly optimistic indicator for 35 00:02:01,340 --> 00:02:06,469 the likely test set accuracy if the model is overfitting. 36 00:02:06,469 --> 00:02:09,289 Understanding, detecting, and avoiding overfitting is perhaps 37 00:02:09,289 --> 00:02:11,389 the most important aspect of applying 38 00:02:11,389 --> 00:02:14,789 supervised machine learning algorithms that you should master. 39 00:02:14,789 --> 00:02:18,419 There are serious real world consequences to overfitting. 40 00:02:18,419 --> 00:02:20,240 The reading for this week contains 41 00:02:20,240 --> 00:02:24,599 one example from the medical world you might find interesting. 42 00:02:24,599 --> 00:02:27,129 To understand the phenomenon of overfitting better. 43 00:02:27,129 --> 00:02:29,812 Let's look at a few visual examples. 44 00:02:29,812 --> 00:02:34,180 The first example that we'll look at for overfitting involves regression. 45 00:02:34,180 --> 00:02:36,685 In this chart on the x axis, 46 00:02:36,685 --> 00:02:40,139 we have a single input variable that might be, 47 00:02:40,139 --> 00:02:42,675 for example, the size of a piece of property. 48 00:02:42,675 --> 00:02:45,990 And we have a target variable on the y axis. 49 00:02:45,990 --> 00:02:47,430 For example, this might be 50 00:02:47,430 --> 00:02:52,139 that market selling price of a house that sits on that piece of property. 51 00:02:52,139 --> 00:02:54,449 So in regression, we're looking to find 52 00:02:54,449 --> 00:02:58,814 the relationship between the input variable and the target variable. 53 00:02:58,814 --> 00:03:01,830 And we start off with the idea of 54 00:03:01,830 --> 00:03:06,840 a model that we want to fit that might explain this relationship. 55 00:03:06,840 --> 00:03:10,314 So, one example of a model that we could try to fit would be a linear model. 56 00:03:10,314 --> 00:03:12,419 So trying to predict that there's 57 00:03:12,419 --> 00:03:17,305 a linear relationship between the input variable and the target variable. 58 00:03:17,305 --> 00:03:23,460 So, the regression model might fit a straight line to these points. 59 00:03:23,460 --> 00:03:27,805 In this case the model has under-fit the data. 60 00:03:27,805 --> 00:03:33,819 The model is too simple for the actual trends that are present in the data. 61 00:03:33,819 --> 00:03:36,119 It doesn't even do well on the training points. 62 00:03:36,119 --> 00:03:38,319 So these blue points would represent the training points, 63 00:03:38,319 --> 00:03:41,405 the input to the training process for the regression. 64 00:03:41,405 --> 00:03:45,030 And when we underfit, we have a model that's too simple, 65 00:03:45,030 --> 00:03:47,469 doesn't even do well on the training data and thus, 66 00:03:47,469 --> 00:03:52,074 is not at all likely to generalize well to test data. 67 00:03:52,074 --> 00:03:56,055 On the other hand, if we pick a better model, for example, 68 00:03:56,055 --> 00:04:00,747 the idea that this might be a quadratic relationship, 69 00:04:00,747 --> 00:04:06,930 we might actually be able to apply that and get what looks like a much better fit. 70 00:04:06,930 --> 00:04:09,919 So this would be example of a reasonably good model fit. 71 00:04:09,919 --> 00:04:13,259 We've captured both the general trend of 72 00:04:13,259 --> 00:04:22,970 the points while also ignoring the little variations that might exist due to noise. 73 00:04:22,970 --> 00:04:24,185 A third example might be, 74 00:04:24,185 --> 00:04:28,500 we might hypothesize that the relationship between 75 00:04:28,500 --> 00:04:33,273 the input variable and the target variable is a function of several different parameters. 76 00:04:33,273 --> 00:04:39,754 Let's say, a polynomial so something that's very bumpy. 77 00:04:39,754 --> 00:04:44,084 If we try to fit a more complex model to this set of training data, 78 00:04:44,084 --> 00:04:54,290 we might end up with something that looks like this. 79 00:04:54,290 --> 00:04:57,079 So, this more complex model has more parameters so 80 00:04:57,079 --> 00:05:00,694 it's able to capture more subtle behavior. 81 00:05:00,694 --> 00:05:06,845 But it's also much higher variance here as you can see so it's more focused on capturing 82 00:05:06,845 --> 00:05:11,060 the more local variations in the training data rather than trying to 83 00:05:11,060 --> 00:05:15,410 find the more global trend that we can see as humans in the data. 84 00:05:15,410 --> 00:05:18,350 So, this is an example of overfitting. 85 00:05:18,350 --> 00:05:22,579 In this case there's not enough data to really constrain the parameters of the model 86 00:05:22,579 --> 00:05:29,264 enough so that it can recognize the global trend. 87 00:05:29,264 --> 00:05:33,649 The second example will look at overfitting in classification. 88 00:05:33,649 --> 00:05:37,834 So, this diagram shows a simple two dimensional classification problem 89 00:05:37,834 --> 00:05:42,519 where each data instance is represented by a point, 90 00:05:42,519 --> 00:05:46,745 and where there are two features associated with each data instance. 91 00:05:46,745 --> 00:05:50,779 This is a binary classification problem so points are labeled 92 00:05:50,779 --> 00:05:57,196 either red over here or blue. 93 00:05:57,196 --> 00:06:02,720 And the problem in classification is to find a decision boundary. 94 00:06:02,720 --> 00:06:08,000 So as we saw with K nearest neighbors we want to take this feature space and 95 00:06:08,000 --> 00:06:14,814 find regions that are associated with the different labels. 96 00:06:14,814 --> 00:06:17,329 So, one type of classifier that we'll look 97 00:06:17,329 --> 00:06:20,209 at shortly is called the linear classifier where we try 98 00:06:20,209 --> 00:06:29,319 to find a decision body that's essentially a straight line through the space. 99 00:06:29,319 --> 00:06:30,680 So just as in regression, 100 00:06:30,680 --> 00:06:33,995 we can have underfitting models, 101 00:06:33,995 --> 00:06:37,165 good fitting models, and overfitting models. 102 00:06:37,165 --> 00:06:39,800 So, an example of an underfitting model would be something 103 00:06:39,800 --> 00:06:46,920 that really didn't look much at the data. 104 00:06:46,920 --> 00:06:53,040 Maybe something like this that only looked at one feature for example. 105 00:06:53,040 --> 00:06:56,160 So again, this is an overly simplistic model. 106 00:06:56,160 --> 00:06:59,279 It doesn't even capture the patterns. 107 00:06:59,279 --> 00:07:01,920 The division between the classes in the training data 108 00:07:01,920 --> 00:07:07,539 well and so would be unlikely to generalize so this in an underfitting model. 109 00:07:07,539 --> 00:07:13,379 A reasonably good model that fits well would be. 110 00:07:13,379 --> 00:07:16,709 You know, a linear model that finds 111 00:07:16,709 --> 00:07:20,144 this general difference between 112 00:07:20,144 --> 00:07:24,040 the positive class over here and the negative class over here. 113 00:07:24,040 --> 00:07:29,100 So you can see that it's aware of this sort of global pattern of having most of 114 00:07:29,100 --> 00:07:32,490 the blue negative points in the upper left 115 00:07:32,490 --> 00:07:36,385 and most of the red positive points more toward the lower right. 116 00:07:36,385 --> 00:07:41,339 And it's robust enough in the sense that it ignores the fact that there may 117 00:07:41,339 --> 00:07:46,170 be occasionally a blue point in the red region or red point in the blue region. 118 00:07:46,170 --> 00:07:52,854 Instead, it's found this sort of more global separation between these two classes. 119 00:07:52,854 --> 00:07:56,399 So, this is a reasonably well fitting model. 120 00:07:56,399 --> 00:07:59,579 An overfitting model on the other hand would 121 00:07:59,579 --> 00:08:03,697 typically be a model that has lots of parameters so it can capture complex behavior. 122 00:08:03,697 --> 00:08:06,240 And so, it would try to find something very clever, 123 00:08:06,240 --> 00:08:11,160 where it tried to completely separate the red points from 124 00:08:11,160 --> 00:08:20,475 the blue points in a way that resulted in a highly variable decision boundary. 125 00:08:20,475 --> 00:08:24,490 So this has the advantage that, a questionable advantage, 126 00:08:24,490 --> 00:08:30,079 that it does capture the training data classes very well. 127 00:08:30,079 --> 00:08:32,995 It predicts the training data classes almost perfectly. 128 00:08:32,995 --> 00:08:39,565 But as you can see, if the actual division between the classes, 129 00:08:39,565 --> 00:08:42,570 it's captured by this linear model, 130 00:08:42,570 --> 00:08:45,330 the overfit model is going to make lots of 131 00:08:45,330 --> 00:08:51,690 mistakes in the regions where it's trying to be too perfect in some sense. 132 00:08:51,690 --> 00:08:56,029 So, you'll see this typically with overfitting. 133 00:08:56,029 --> 00:08:59,710 The overfit model is highly variable. 134 00:08:59,710 --> 00:09:02,190 And again, it's trying to capture too many of 135 00:09:02,190 --> 00:09:05,759 the local fluctuations and does not have enough data to see 136 00:09:05,759 --> 00:09:08,639 the global trend that would result in 137 00:09:08,639 --> 00:09:13,470 better overall generalization performance on new unseen data. 138 00:09:13,470 --> 00:09:18,320 This third example shows the effect of modifying 139 00:09:18,320 --> 00:09:24,980 the K parameter in the K nearest neighbors classifier that we saw previously. 140 00:09:24,980 --> 00:09:35,460 The three plots shown here show the decision boundaries for K=10, K=5, and K=1. 141 00:09:35,460 --> 00:09:40,129 And here we're using the fruit dataset again with the height of a piece of fruit 142 00:09:40,129 --> 00:09:45,215 on the x axis and the width on the y axis. 143 00:09:45,215 --> 00:09:47,179 So the K=10 case, 144 00:09:47,179 --> 00:09:50,544 as you recall, K=10 means that, 145 00:09:50,544 --> 00:09:56,409 for each query point that we want to get a prediction for, 146 00:09:56,409 --> 00:09:59,589 let's say over here, 147 00:09:59,589 --> 00:10:07,967 we have to look at the 10 nearest points to the query point and we'll take those. 148 00:10:07,967 --> 00:10:09,595 We won't go through all 10 here, 149 00:10:09,595 --> 00:10:14,664 but let's just say there are several here that are 150 00:10:14,664 --> 00:10:21,879 nearby and will average or combine their votes to predict the label for this point. 151 00:10:21,879 --> 00:10:24,085 So in the K=10 case, 152 00:10:24,085 --> 00:10:26,695 we need the votes from 153 00:10:26,695 --> 00:10:31,154 10 different data instances in the training set to make our prediction. 154 00:10:31,154 --> 00:10:34,735 And as we reduce K, so K=5, 155 00:10:34,735 --> 00:10:39,879 we only need five neighbors to make a prediction. 156 00:10:39,879 --> 00:10:42,345 So for example, if the query point was here, 157 00:10:42,345 --> 00:10:46,259 we'd look at these four and then possibly whatever was the closest 158 00:10:46,259 --> 00:10:52,830 in this let's say, that one or this one. 159 00:10:52,830 --> 00:10:55,304 And then finally, in the K=1 case, 160 00:10:55,304 --> 00:10:59,850 that's the most unstable in the sense that for any query point, 161 00:10:59,850 --> 00:11:04,590 we only look at the single nearest neighbor to that point. 162 00:11:04,590 --> 00:11:07,745 And so, the effect of reducing K in the k-nearest neighbors 163 00:11:07,745 --> 00:11:13,875 classifier is to increase the variance of the decision boundaries, 164 00:11:13,875 --> 00:11:18,235 because the decision boundary can be affected by outliers. 165 00:11:18,235 --> 00:11:20,985 If there's a point far, 166 00:11:20,985 --> 00:11:22,845 far away, it might have, 167 00:11:22,845 --> 00:11:27,029 it has much greater effect on the decision boundary in the K=1 case, 168 00:11:27,029 --> 00:11:29,490 than it would in the K=10 case, 169 00:11:29,490 --> 00:11:34,679 when the votes of nine other neighbors are also needed. 170 00:11:34,679 --> 00:11:37,620 And so, you can see that by 171 00:11:37,620 --> 00:11:40,710 adjusting the value of K for the k-nearest neighbors classifier, 172 00:11:40,710 --> 00:11:42,330 we can control in some sense, 173 00:11:42,330 --> 00:11:47,735 the degree of model fitting that's appropriate for a dataset. 174 00:11:47,735 --> 00:11:51,240 Now, the actual value of k that works best can 175 00:11:51,240 --> 00:11:55,195 only be determined by evaluating on a test set. 176 00:11:55,195 --> 00:12:00,659 But the general idea is that as we decrease K for k-NN classifiers, 177 00:12:00,659 --> 00:12:03,825 we increase the risk of overfitting. 178 00:12:03,825 --> 00:12:07,320 Because, for the reasons I mentioned before, 179 00:12:07,320 --> 00:12:09,509 where K=1 for example, 180 00:12:09,509 --> 00:12:14,730 we're trying to capture very local changes in 181 00:12:14,730 --> 00:12:21,800 the decision boundary that may not lead to good generalization behavior for future data.