1 00:00:07,814 --> 00:00:11,478 Let's look at how linear models are also used for classification, 2 00:00:11,478 --> 00:00:13,670 starting with binary classification. 3 00:00:15,220 --> 00:00:19,335 This approach to prediction uses the same linear functional form as we saw for 4 00:00:19,335 --> 00:00:20,109 regression. 5 00:00:20,109 --> 00:00:24,267 But instead of predicting a continuous target value, we take the output of 6 00:00:24,267 --> 00:00:28,359 the linear function and apply the sine function to produce a binary output 7 00:00:28,359 --> 00:00:32,660 with two possible values, corresponding to the two possible class labels. 8 00:00:33,790 --> 00:00:38,858 If the target value is greater than zero, the function returns plus one and 9 00:00:38,858 --> 00:00:42,808 if it's less than zero, the function returns minus one. 10 00:00:42,808 --> 00:00:43,940 Here's a specific example. 11 00:00:46,090 --> 00:00:50,710 So let's take a look at a simple linear classification problem, 12 00:00:50,710 --> 00:00:54,490 a binary problem that has two different classes, and 13 00:00:54,490 --> 00:00:59,538 where each data instance is represented by two informative features. 14 00:00:59,538 --> 00:01:04,605 So we're going to call these features x1 15 00:01:04,605 --> 00:01:09,525 on the x-axis and x2 on the y-axis. 16 00:01:09,525 --> 00:01:14,658 Now, how do we get from taking a data instance that's 17 00:01:14,658 --> 00:01:21,860 described by a particular combination of x1, x2 to a class prediction. 18 00:01:22,910 --> 00:01:24,926 Well in a linear classifier, 19 00:01:24,926 --> 00:01:30,098 what we do is we take the feature values assigned to a particular data point. 20 00:01:30,098 --> 00:01:33,474 So in this case, 21 00:01:33,474 --> 00:01:38,549 it might be 2.1,0. 22 00:01:39,847 --> 00:01:45,817 So that represents the x1 and x2 feature values for this particular instance, 23 00:01:45,817 --> 00:01:50,660 let's say, and so that corresponds to the input here. 24 00:01:50,660 --> 00:01:54,031 And then we take those two x1, x2 values and 25 00:01:54,031 --> 00:01:57,234 put them through a linear function f here. 26 00:01:57,234 --> 00:02:00,480 And the output of this f needs to be a class value. 27 00:02:00,480 --> 00:02:05,161 So either we want it to return +1, if it's in one class and 28 00:02:05,161 --> 00:02:07,794 -1 if it's in the other class. 29 00:02:07,794 --> 00:02:12,451 So the linear classifier does that by computing a linear function of x1, 30 00:02:12,451 --> 00:02:16,220 x2 that's represented by this part of the equation here. 31 00:02:17,520 --> 00:02:21,251 So this w is a vector of weights. 32 00:02:21,251 --> 00:02:24,283 This x represents the vector of feature values. 33 00:02:24,283 --> 00:02:28,780 And then b is a bias term that gets added in. 34 00:02:28,780 --> 00:02:31,720 So this is a dot product, this circle here is a dot product. 35 00:02:31,720 --> 00:02:35,898 Which means that, let's say, 36 00:02:35,898 --> 00:02:41,623 the simple case where we had (w1, w2), 37 00:02:41,623 --> 00:02:46,587 and a future vector of (x1, x2). 38 00:02:46,587 --> 00:02:52,104 The dot product of those is simply the linear 39 00:02:52,104 --> 00:02:56,437 combination of w1 x1 + w2 x2. 40 00:03:00,438 --> 00:03:05,146 We take the X values, and we have certain weights that are learned for 41 00:03:05,146 --> 00:03:06,372 the classifier. 42 00:03:06,372 --> 00:03:10,095 So we compute w1 x1 + w2 x2. 43 00:03:10,095 --> 00:03:13,100 Then we feed that, and then plus a bias term, if there is one. 44 00:03:14,720 --> 00:03:19,708 And we feed the output of that through the sign function that 45 00:03:19,708 --> 00:03:22,112 converts the value in here. 46 00:03:22,112 --> 00:03:26,296 If it's above 0, it'll convert to +1, and if it's below 0, 47 00:03:26,296 --> 00:03:30,950 it'll convert it to -1 and that's what the equation represents here. 48 00:03:30,950 --> 00:03:34,808 So that is the very simple rule that we use to convert 49 00:03:34,808 --> 00:03:39,766 a data instance with its input features to an output prediction. 50 00:03:39,766 --> 00:03:44,613 Okay, let's take a look using a specific linear function to see 51 00:03:44,613 --> 00:03:46,783 how this works in practice. 52 00:03:46,783 --> 00:03:52,472 So what I've done here is drawn a straight line through 53 00:03:52,472 --> 00:03:58,416 the space that is defined by the equation x1- x2 = 0. 54 00:03:58,416 --> 00:04:04,180 In other words, every point on this line satisfies this equation. 55 00:04:04,180 --> 00:04:09,609 So you can see, for example, that x1 = -1 and 56 00:04:09,609 --> 00:04:14,785 x2 = -1 and if you subtract them you get 0. 57 00:04:14,785 --> 00:04:20,424 Essentially, it's just the line that represents all the points where x1 and 58 00:04:20,424 --> 00:04:21,542 x2 are equal. 59 00:04:24,670 --> 00:04:29,921 So this corresponds to, so we can rewrite 60 00:04:29,921 --> 00:04:35,471 this x1- x2 = 0 into a form that uses a dot 61 00:04:35,471 --> 00:04:41,035 product of weights with the input vector x. 62 00:04:41,035 --> 00:04:46,584 So in order to get x1- x2 = 0 that's equivalent 63 00:04:46,584 --> 00:04:53,555 writing a linear function where you have a weight vector of 1 and 64 00:04:53,555 --> 00:04:58,833 -1 and a bias term of 0 So 65 00:04:58,833 --> 00:05:02,126 for example, so 66 00:05:02,126 --> 00:05:07,300 if we have weights (w1, 67 00:05:07,300 --> 00:05:12,485 w2) dot (x1, x2). 68 00:05:12,485 --> 00:05:21,008 We call that this is just the same as computing w1 x1 + w2 x2. 69 00:05:21,008 --> 00:05:26,699 And so in this case, if w is 1 and -1, 70 00:05:26,699 --> 00:05:31,710 that's equivalent to x1- x2. 71 00:05:36,510 --> 00:05:41,753 So all I've done here then is just convert the description 72 00:05:41,753 --> 00:05:48,387 of this line into a form that can be used as a decision rule for classifier. 73 00:05:48,387 --> 00:05:49,940 So I might have to look at a specific point. 74 00:05:49,940 --> 00:05:54,832 So suppose that we wanted to classify the point here 75 00:05:54,832 --> 00:05:59,740 that had coordinates -0.75 and -2.25. 76 00:05:59,740 --> 00:06:01,764 So this point right here. 77 00:06:01,764 --> 00:06:07,066 So all we would do to have a classifier make a decision with 78 00:06:07,066 --> 00:06:12,700 this decision boundary would be to plug in those coordinates 79 00:06:12,700 --> 00:06:17,670 into this part of the function, apply the weights and 80 00:06:17,670 --> 00:06:22,540 the bias term that describe the decision boundary. 81 00:06:24,280 --> 00:06:26,349 So here we're computing. 82 00:06:26,349 --> 00:06:33,790 So this expression here corresponds to this part of the equation. 83 00:06:36,050 --> 00:06:43,100 And so, if we compute w1 times x1 + w2 times x2 plus 0, 84 00:06:43,100 --> 00:06:50,301 we get a value of 0.15 that's inside the sign function. 85 00:06:50,301 --> 00:06:54,698 And then the sign function will output 1 if this value is greater than zero, 86 00:06:54,698 --> 00:06:57,870 which it is or minus 1, if the value is less than zero. 87 00:06:57,870 --> 00:07:00,042 So in this case, because it's greater than zero, 88 00:07:00,042 --> 00:07:02,423 the output from the decision function would be plus 1. 89 00:07:02,423 --> 00:07:08,120 So this has classified this point as being class one. 90 00:07:12,540 --> 00:07:15,220 If we look at a different point, 91 00:07:15,220 --> 00:07:20,201 let's take a look at the point -1.75 and -0.25. 92 00:07:20,201 --> 00:07:22,938 So again, we're just going to up, so 93 00:07:22,938 --> 00:07:26,785 this is corresponding to the value of x1 and x2. 94 00:07:26,785 --> 00:07:30,421 And again, if we just take these values and 95 00:07:30,421 --> 00:07:33,960 plug them into this part of the equation. 96 00:07:33,960 --> 00:07:35,701 Apply the weights and 97 00:07:35,701 --> 00:07:41,320 the bias term that describe the decision boundary as you did before. 98 00:07:41,320 --> 00:07:46,578 We do this computation, we find out that, in fact, 99 00:07:46,578 --> 00:07:50,888 classifier predicts a class of -1 here. 100 00:07:50,888 --> 00:07:55,037 So you see that by applying a simple linear formula, 101 00:07:55,037 --> 00:07:58,527 we've been able to produce a class value for 102 00:07:58,527 --> 00:08:02,604 any point in this two dimensional features space. 103 00:08:05,170 --> 00:08:10,436 So one way to define a good classifier is to reward classifiers for 104 00:08:10,436 --> 00:08:15,911 the amount of separation that can provide between the two classes. 105 00:08:15,911 --> 00:08:20,650 And to do this, we need define the concept of classifier margin. 106 00:08:20,650 --> 00:08:25,827 So informally, for our given classifier, The margin is 107 00:08:25,827 --> 00:08:30,180 the width that the decision boundary can be increased before hitting a data point. 108 00:08:30,180 --> 00:08:37,073 So what we do is we take the decision boundary, and we grow a region around it. 109 00:08:37,073 --> 00:08:41,155 Sort of in this perpendicular to the line in this direction and that direction, and 110 00:08:41,155 --> 00:08:43,330 we grow this width until we hit a data point. 111 00:08:43,330 --> 00:08:48,026 So in this case, we were only able to grow the margin 112 00:08:48,026 --> 00:08:53,061 a small amount here, before hitting this data point. 113 00:08:53,061 --> 00:08:57,130 So this width here between the decision boundary and 114 00:08:57,130 --> 00:09:02,969 nearest data point represents the margin of this particular classifier. 115 00:09:07,292 --> 00:09:11,068 Now you can imagine that for every classifier that we tried, 116 00:09:11,068 --> 00:09:15,080 we can do the same calculation or simulation to find the margin. 117 00:09:16,630 --> 00:09:21,944 And so among all possible classifiers that separate these two classes then, 118 00:09:21,944 --> 00:09:26,849 we can define the best classifier as the classifier that has the maximum 119 00:09:26,849 --> 00:09:30,876 amount of margin which corresponds to the one shown here. 120 00:09:30,876 --> 00:09:35,339 So you recall that the original classifier on the previous slide had a very small 121 00:09:35,339 --> 00:09:35,880 margin. 122 00:09:35,880 --> 00:09:39,641 This one manages to achieve a must larger margin. 123 00:09:39,641 --> 00:09:44,914 So again, the margin is the distance the width that we can go from 124 00:09:44,914 --> 00:09:50,300 the decision boundary perpendicular to the nearest data point. 125 00:09:52,555 --> 00:09:57,401 So you can see that by defining this concept of margin that sort of 126 00:09:57,401 --> 00:10:02,520 quantifies the degree to which the classifier can split the classes 127 00:10:02,520 --> 00:10:08,560 into two regions that have some amount of separation between them. 128 00:10:08,560 --> 00:10:14,018 We can actually do a search for the classifier that has the maximum margin. 129 00:10:14,018 --> 00:10:19,972 This maximum margin classifier is called the Linear Support Vector Machine, 130 00:10:19,972 --> 00:10:25,219 also known as an LSVM or a support vector machine with linear kernel. 131 00:10:25,219 --> 00:10:29,481 Now we'll explain more about what the concept of a kernel is and how you can 132 00:10:29,481 --> 00:10:34,410 define nonlinear kernels as well as kernels, and why you'd want to do that. 133 00:10:34,410 --> 00:10:39,617 We'll cover those shortly in a continuation of our support 134 00:10:39,617 --> 00:10:44,521 vector machine lecture later in this particular week. 135 00:10:44,521 --> 00:10:49,145 Here's an example in the notebook on how to use the default linear support vector 136 00:10:49,145 --> 00:10:53,571 classifier in scikit-learn, which is defined in the sklearn SVM library. 137 00:10:54,630 --> 00:10:59,252 The linear SVC class implements a linear support vector classifier and 138 00:10:59,252 --> 00:11:02,410 is trained in the same way as other classifiers, 139 00:11:02,410 --> 00:11:05,814 namely by using the fit method on the training data. 140 00:11:05,814 --> 00:11:09,384 Now in the simple classification problem I just showed you, 141 00:11:09,384 --> 00:11:13,451 the two classes were perfectly separable with a linear classifier. 142 00:11:13,451 --> 00:11:18,158 In practice though, we typically have noise or just more complexity in the data 143 00:11:18,158 --> 00:11:21,742 set that makes a perfect linear separation impossible, but 144 00:11:21,742 --> 00:11:27,050 where most points can be separated without errors by linear classifier. 145 00:11:27,050 --> 00:11:32,068 And our simple binary classification dataset here is an illustration of that. 146 00:11:32,068 --> 00:11:37,808 So how tolerant the support vector machine is of misclassifying training points, 147 00:11:37,808 --> 00:11:42,646 as compared to its objective of minimizing the margin between classes 148 00:11:42,646 --> 00:11:47,484 is controlled by a regularization parameter called C which by default 149 00:11:47,484 --> 00:11:49,700 is set to 1.0 as we have here. 150 00:11:53,710 --> 00:11:57,040 Larger values of C represent less regularization and 151 00:11:57,040 --> 00:12:01,924 will cause the model to fit the training set with these few errors as possible, 152 00:12:01,924 --> 00:12:05,702 even if it means using a small immersion decision boundary. 153 00:12:05,702 --> 00:12:10,231 Very small values of C on the other hand use more regularization that 154 00:12:10,231 --> 00:12:14,999 encourages the classifier to find a large marge on decision boundary, 155 00:12:14,999 --> 00:12:20,040 even if that decision boundary leads to more points being misclassified. 156 00:12:20,040 --> 00:12:24,909 Here's an example in the notebook showing the effect of varying C on this basic 157 00:12:24,909 --> 00:12:26,621 classification problem. 158 00:12:26,621 --> 00:12:30,329 On the right, when C is large, the decision boundary is adjusted so 159 00:12:30,329 --> 00:12:33,986 that more of the black training points are correctly classified. 160 00:12:33,986 --> 00:12:36,317 While on the left, for small values of C, 161 00:12:36,317 --> 00:12:40,183 the classifier is more tolerant of these errors in favor of capturing 162 00:12:40,183 --> 00:12:43,600 the majority of data points correctly with a larger margin. 163 00:12:46,500 --> 00:12:50,822 Finally, here's an example of applying the Linear Support Vector Machine 164 00:12:50,822 --> 00:12:54,812 to a real world data set, the breast cancer classification problem. 165 00:12:54,812 --> 00:12:57,750 And here, we can see that it achieves reasonable accuracy without 166 00:12:57,750 --> 00:12:58,857 much parameter tuning. 167 00:13:02,060 --> 00:13:05,636 On the positive side, linear models, in the case of linear and 168 00:13:05,636 --> 00:13:08,680 logistic regression, are simple and easy to train. 169 00:13:08,680 --> 00:13:11,861 And for all types of linear models, prediction's very fast because, 170 00:13:11,861 --> 00:13:14,100 of the linear nature of the prediction function. 171 00:13:15,910 --> 00:13:20,217 Linear models including Linear Support Vector Machines also perform 172 00:13:20,217 --> 00:13:23,794 effectively on high dementional data set, especially, 173 00:13:23,794 --> 00:13:26,646 in cases where the data instances are sparse. 174 00:13:26,646 --> 00:13:29,630 Linear Models scale well to very large datasets as well. 175 00:13:30,780 --> 00:13:33,171 In the case of Linear Support Vector Machines, 176 00:13:33,171 --> 00:13:36,479 they only use a subset of training points and decision function. 177 00:13:36,479 --> 00:13:38,600 These training points are called support vectors. 178 00:13:39,860 --> 00:13:42,470 So the algorithm can be implemented in a memory efficient way.