WEBVTT 00:00:00.046 --> 00:00:03.252 Suppose red and blue are two classes in a training set. 00:00:03.355 --> 00:00:06.279 We want a line that puts every red point on one side 00:00:06.362 --> 00:00:08.546 and every blue point on the other. 00:00:08.742 --> 00:00:13.364 This data is linearly separable, so at least one such line exists. 00:00:14.160 --> 00:00:17.308 In fact, one separating line is easy to draw. 00:00:17.504 --> 00:00:21.684 Every red point lies above it, and every blue point lies below it. 00:00:21.997 --> 00:00:24.970 But this line runs rather close to the blue class. 00:00:25.767 --> 00:00:30.551 Another line also separates the data, but now it passes close to the red class. 00:00:30.863 --> 00:00:32.954 A tilted line works too. 00:00:33.151 --> 00:00:37.888 Correct classification alone does not tell us which of these choices is preferable. 00:00:38.685 --> 00:00:41.925 Imagine placing an empty corridor around a separator. 00:00:42.121 --> 00:00:44.349 Its walls remain parallel to the line, 00:00:44.432 --> 00:00:48.821 and we widen them until one wall would hit red or the other would hit blue. 00:00:49.134 --> 00:00:53.279 The corridor's width measures how much room the classifier has before a training 00:00:53.279 --> 00:00:54.975 point changes sides. 00:00:55.887 --> 00:00:58.416 Now slide the centre line inside that gap. 00:00:58.499 --> 00:01:01.507 If it moves down, the lower clearance shrinks. 00:01:01.820 --> 00:01:04.723 If it moves up, the upper clearance shrinks. 00:01:04.920 --> 00:01:08.146 The best position balances the nearest points on the two sides 00:01:08.229 --> 00:01:10.702 and maximizes the smaller clearance. 00:01:11.754 --> 00:01:14.646 The points that stop the two walls are special. 00:01:14.843 --> 00:01:19.545 Three red points touch the upper wall, and two blue points touch the lower wall. 00:01:19.742 --> 00:01:21.331 These are the support vectors, 00:01:21.414 --> 00:01:24.352 because they physically support the widest corridor. 00:01:25.055 --> 00:01:28.493 Points farther away do not determine the final position. 00:01:28.689 --> 00:01:32.881 We could move one of those distant points slightly without changing either wall. 00:01:33.078 --> 00:01:34.806 Move a support vector, however, 00:01:34.889 --> 00:01:38.674 and the maximum-margin separator generally has to move with it. 00:01:39.471 --> 00:01:43.222 So an SVM does not merely search for zero training errors. 00:01:43.534 --> 00:01:45.668 Among all separating hyperplanes, 00:01:45.751 --> 00:01:49.003 it chooses the one with the largest geometric margin. 00:01:49.200 --> 00:01:52.799 Next we will turn this corridor into an optimization problem. 00:01:53.909 --> 00:01:55.601 A line in two dimensions, 00:01:55.685 --> 00:02:01.537 or a hyperplane in any dimension, can be written as w dot x plus b equals zero. 00:02:01.989 --> 00:02:06.030 The vector w is perpendicular to the separator, while b shifts it 00:02:06.030 --> 00:02:08.271 without changing its orientation. 00:02:09.068 --> 00:02:15.299 The expression w dot x plus b is a signed score. Positive scores lie on one side, 00:02:15.383 --> 00:02:20.214 negative scores lie on the other, and its sign becomes the predicted class. 00:02:21.010 --> 00:02:27.478 Let each training label y sub i be plus one for red and minus one for blue. 00:02:27.791 --> 00:02:31.670 Correct classification then has one compact condition: 00:02:31.773 --> 00:02:34.851 y sub i times the score must be positive. 00:02:35.647 --> 00:02:42.172 There is a scaling ambiguity. Multiplying both w and b by any positive number leaves 00:02:42.172 --> 00:02:47.363 the zero set unchanged, so it leaves the separating hyperplane unchanged. 00:02:47.815 --> 00:02:52.100 We use that freedom to make the closest signed scores equal to one. 00:02:52.896 --> 00:02:57.514 After this normalization, every red point must have score at least plus one, 00:02:57.598 --> 00:03:00.986 and every blue point must have score at most minus one. 00:03:01.070 --> 00:03:02.742 The support vectors are precisely 00:03:02.742 --> 00:03:06.365 the points where the combined inequality becomes an equality. 00:03:07.579 --> 00:03:12.676 The perpendicular distance from a point x to the central hyperplane is the absolute 00:03:12.676 --> 00:03:15.092 score divided by the length of w. 00:03:15.404 --> 00:03:17.805 Each wall has score one in magnitude, 00:03:17.889 --> 00:03:21.326 so each wall is one over the length of w from the centre. 00:03:22.122 --> 00:03:26.094 The full corridor therefore has width two over the length of w. 00:03:26.290 --> 00:03:30.761 To make that width large, we must make the length of w small. 00:03:30.865 --> 00:03:35.138 Squaring it changes neither the minimizing choice nor the geometry. 00:03:35.935 --> 00:03:39.338 We have reached the hard-margin optimization problem. 00:03:39.534 --> 00:03:41.993 Minimize one half w dot w, 00:03:42.077 --> 00:03:45.398 which is one half the squared length of the normal vector. 00:03:46.311 --> 00:03:50.166 The minimization is subject to one constraint per training example: 00:03:50.363 --> 00:03:55.495 y sub i times w dot x sub i plus b must be at least one. 00:03:55.692 --> 00:03:59.462 These inequalities say that every point lies outside the empty corridor 00:03:59.546 --> 00:04:01.335 on its proper side. 00:04:02.132 --> 00:04:05.279 Only a few of those constraints are tight at the solution. 00:04:05.383 --> 00:04:08.762 Those active constraints belong to the support vectors. 00:04:08.959 --> 00:04:11.908 The remaining points satisfy their inequalities with room 00:04:11.908 --> 00:04:14.834 to spare and do not pin the optimum. 00:04:15.631 --> 00:04:18.348 This completes the geometric derivation. 00:04:18.452 --> 00:04:21.631 A wide corridor became a small normal vector, 00:04:21.715 --> 00:04:23.584 correct classification became a family 00:04:23.584 --> 00:04:28.507 of inequalities, and the points touching equality became the support vectors. 00:04:29.625 --> 00:04:34.906 Real classes often overlap. A red example may sit deep among blue examples, 00:04:34.989 --> 00:04:37.811 while a blue example may sit among red ones. 00:04:38.007 --> 00:04:42.629 No line can put every point on its requested side in this training set. 00:04:43.426 --> 00:04:45.873 If we insist on the hard-margin constraints, 00:04:45.956 --> 00:04:49.429 the optimization problem has no feasible answer. 00:04:49.625 --> 00:04:50.564 The red point below 00:04:50.647 --> 00:04:55.083 and the blue point above cannot both satisfy the same perfect separation. 00:04:55.879 --> 00:04:59.165 A soft-margin SVM relaxes each constraint 00:04:59.165 --> 00:05:02.858 with a nonnegative slack variable xi sub i. 00:05:02.961 --> 00:05:07.118 Instead of demanding a signed score of at least one, it permits the score 00:05:07.118 --> 00:05:09.313 to fall short by xi sub i. 00:05:10.109 --> 00:05:13.477 Draw the central separator and its two margin walls. 00:05:13.674 --> 00:05:17.332 A point outside its correct wall needs zero slack. 00:05:17.435 --> 00:05:20.196 A point inside the corridor needs some slack, 00:05:20.279 --> 00:05:23.856 because it has not reached the wall required by its label. 00:05:24.653 --> 00:05:27.879 This red point is not merely inside the margin. 00:05:27.962 --> 00:05:32.432 It lies on the blue side of the separator, so its slack exceeds one. 00:05:32.629 --> 00:05:35.439 The same is true in reverse for this blue point. 00:05:35.636 --> 00:05:37.342 Slack records the degree of each 00:05:37.342 --> 00:05:41.105 violation rather than pretending the data is perfectly separable. 00:05:41.901 --> 00:05:44.561 The new objective contains two costs. 00:05:44.757 --> 00:05:48.540 One half w dot w still rewards a wide margin. 00:05:48.623 --> 00:05:52.327 The sum of the slacks penalizes points that enter the margin or cross 00:05:52.327 --> 00:05:57.343 the separator, and the constant C controls how heavily that penalty is counted. 00:05:58.256 --> 00:06:01.589 This is not permission to ignore errors for free. 00:06:01.785 --> 00:06:04.256 Every violation raises the objective. 00:06:04.339 --> 00:06:08.229 The optimizer accepts a violation only when avoiding it would require 00:06:08.229 --> 00:06:11.991 a sufficiently narrower or more contorted decision boundary. 00:06:12.788 --> 00:06:16.387 With a smaller C, slack is relatively inexpensive. 00:06:16.491 --> 00:06:17.966 The optimizer is more willing 00:06:17.966 --> 00:06:23.029 to tolerate unusual training points in exchange for a broad, stable corridor. 00:06:24.081 --> 00:06:27.016 With a larger C, violations are expensive. 00:06:27.099 --> 00:06:29.061 The separator bends its linear choice 00:06:29.061 --> 00:06:34.484 as far as it can toward fitting difficult examples, often leaving a narrower margin. 00:06:34.681 --> 00:06:38.072 The drawing is schematic, but the trade is exact: 00:06:38.176 --> 00:06:40.638 margin width against total slack. 00:06:41.690 --> 00:06:44.953 Small C can underreact to genuine structure. 00:06:45.149 --> 00:06:49.875 Very large C can overreact to noise or mislabeled examples. 00:06:50.072 --> 00:06:53.414 In practice C is a regularization hyperparameter, 00:06:53.497 --> 00:06:57.561 chosen by validation rather than by demanding zero training error. 00:06:58.474 --> 00:07:01.456 Support vectors still matter in the soft-margin model. 00:07:01.539 --> 00:07:06.393 They now include points touching a margin wall and points lying inside or beyond it. 00:07:06.496 --> 00:07:10.387 These are the examples that exert force on the final decision boundary. 00:07:11.559 --> 00:07:14.126 Now consider a different training set. 00:07:14.438 --> 00:07:17.373 The red examples form a compact inner cluster, 00:07:17.457 --> 00:07:20.186 while the blue examples make a ring around them. 00:07:20.499 --> 00:07:24.969 This is a simple nonlinear pattern with no noise and no overlap. 00:07:25.882 --> 00:07:27.833 Try a slanted line. 00:07:28.146 --> 00:07:31.058 It can place some blue points opposite the red cluster, 00:07:31.142 --> 00:07:33.662 but blue points remain on both sides. 00:07:33.858 --> 00:07:38.097 Rotating the line merely changes which part of the ring is misclassified. 00:07:38.893 --> 00:07:41.309 Move the line above the centre instead. 00:07:41.506 --> 00:07:43.674 The red points may all fall below it, 00:07:43.758 --> 00:07:47.010 but so do the blue points around the lower half of the ring. 00:07:47.206 --> 00:07:49.773 No translation fixes the problem either. 00:07:50.987 --> 00:07:55.330 There is a geometric reason, not just a failure of imagination. 00:07:55.527 --> 00:07:58.929 Join the outer blue points to form their convex hull. 00:07:59.126 --> 00:08:02.470 The entire red cluster lies inside that hull. 00:08:03.267 --> 00:08:06.658 A straight line divides the plane into two half-planes. 00:08:06.970 --> 00:08:10.021 If every blue vertex lies in one half-plane, 00:08:10.105 --> 00:08:14.146 then every convex combination of those vertices lies there too. 00:08:14.343 --> 00:08:19.685 The red points inside their hull therefore cannot all occupy the opposite half-plane. 00:08:20.597 --> 00:08:25.590 The useful feature here is not left versus right or up versus down. 00:08:25.787 --> 00:08:27.959 It is distance from the centre. 00:08:28.272 --> 00:08:35.123 Square that distance and call it q of x: x one squared plus x two squared. 00:08:35.826 --> 00:08:38.857 Every red point has a small value of q. 00:08:39.054 --> 00:08:41.667 Every blue point has a much larger value. 00:08:41.771 --> 00:08:47.240 A threshold at two separates them perfectly: red below two, blue above two. 00:08:48.036 --> 00:08:53.424 Back in the original plane, the threshold q equals two is a circle, not a line. 00:08:53.737 --> 00:08:57.255 So the data is nonlinear in its original coordinates. 00:08:57.568 --> 00:09:00.584 The next move is to change coordinates rather than abandon 00:09:00.668 --> 00:09:02.979 maximum-margin separation. 00:09:04.022 --> 00:09:08.005 A feature map replaces each original input by a new vector. 00:09:08.201 --> 00:09:13.087 For this problem, map x one and x two to three quadratic features: 00:09:13.170 --> 00:09:19.406 x one squared, square root two times x one x two, and x two squared. 00:09:20.319 --> 00:09:24.766 At first I have placed the points in a flat copy of their familiar arrangement. 00:09:24.962 --> 00:09:26.702 Now apply the feature map. 00:09:26.785 --> 00:09:30.733 Each point moves to the three coordinates computed from its original two. 00:09:31.530 --> 00:09:35.258 The inner red points remain near the origin of feature space. 00:09:35.454 --> 00:09:38.181 The outer blue points rise onto a distant sheet 00:09:38.264 --> 00:09:43.884 because x one squared plus x two squared is large for every point on the ring. 00:09:44.797 --> 00:09:48.905 In this three-dimensional space, one flat plane separates the classes. 00:09:48.988 --> 00:09:52.994 Its equation is feature one plus feature three equals two. 00:09:53.098 --> 00:09:56.477 Red points lie below it, and blue points lie above it. 00:09:57.274 --> 00:10:00.212 This is ordinary linear separation again. 00:10:00.408 --> 00:10:03.564 We can place parallel margin planes around this separator, 00:10:03.647 --> 00:10:08.234 maximize their distance, and obtain support vectors exactly as before. 00:10:08.431 --> 00:10:12.065 The only change is that the vectors now live in feature space. 00:10:12.862 --> 00:10:15.034 Now compare the two spaces. 00:10:15.347 --> 00:10:17.936 On the left is the original input plane. 00:10:18.040 --> 00:10:22.104 On the right is the lifted feature space with its flat separating plane. 00:10:22.901 --> 00:10:26.954 The plane above is feature one plus feature three equals two. 00:10:27.266 --> 00:10:31.096 Substitute the definitions of those features and the same condition becomes 00:10:31.179 --> 00:10:35.592 x one squared plus x two squared equals two below. 00:10:36.644 --> 00:10:39.768 That equation draws this circle in the input plane. 00:10:39.871 --> 00:10:44.782 A linear decision surface in feature space has become a nonlinear decision boundary 00:10:44.782 --> 00:10:46.734 in the original coordinates. 00:10:47.530 --> 00:10:50.805 The construction works, but it seems expensive. 00:10:51.001 --> 00:10:54.599 A richer feature map may contain hundreds, millions, 00:10:54.682 --> 00:10:57.225 or even infinitely many coordinates. 00:10:57.538 --> 00:11:01.231 Writing and storing every lifted vector would defeat the purpose. 00:11:02.028 --> 00:11:02.921 The escape comes 00:11:02.921 --> 00:11:07.589 from noticing what the SVM calculation actually asks of those lifted vectors. 00:11:07.902 --> 00:11:10.957 It does not need to inspect their coordinates one at a time. 00:11:11.409 --> 00:11:13.708 It needs inner products between them. 00:11:14.778 --> 00:11:16.935 Return to the quadratic feature map. 00:11:17.018 --> 00:11:21.301 To compare two lifted examples phi of x and phi of z, 00:11:21.384 --> 00:11:23.834 the SVM needs their inner product. 00:11:24.031 --> 00:11:28.002 Let us calculate that inner product once and see what remains. 00:11:28.799 --> 00:11:31.319 Multiply matching lifted coordinates. 00:11:31.423 --> 00:11:35.777 The first contribution is x one squared z one squared. 00:11:35.951 --> 00:11:38.526 The middle contribution contains the factor two, 00:11:38.609 --> 00:11:41.803 and the last is x two squared z two squared. 00:11:42.576 --> 00:11:45.410 Those three terms form a familiar square. 00:11:45.583 --> 00:11:50.472 They equal x one z one plus x two z two, all squared. 00:11:51.501 --> 00:11:57.724 But x one z one plus x two z two is simply the ordinary dot product x dot z. 00:11:57.921 --> 00:12:01.216 Therefore the lifted inner product is the square of one dot product 00:12:01.299 --> 00:12:03.761 in the original two-dimensional space. 00:12:04.674 --> 00:12:08.924 Define K of x z to be that squared dot product. 00:12:09.539 --> 00:12:13.765 Evaluating K gives exactly the number we would have obtained by constructing both 00:12:13.765 --> 00:12:17.620 three-dimensional feature vectors and taking their inner product. 00:12:18.324 --> 00:12:20.588 That replacement is the kernel trick. 00:12:21.040 --> 00:12:23.535 We behave as if the data had been lifted, 00:12:23.618 --> 00:12:27.357 while every computation stays in the original input space. 00:12:27.553 --> 00:12:29.386 The feature coordinates disappear, 00:12:29.469 --> 00:12:32.535 but their geometry remains in the kernel values. 00:12:33.448 --> 00:12:35.631 Why are inner products enough? 00:12:35.735 --> 00:12:37.696 At the optimum, the normal vector 00:12:37.696 --> 00:12:42.422 in feature space can be written as a weighted sum of lifted training examples. 00:12:42.874 --> 00:12:46.985 Each weight is alpha sub i times the label y sub i. 00:12:47.782 --> 00:12:53.158 To classify a new input, begin with w dot phi of x plus b. 00:12:53.471 --> 00:12:57.627 Substitute the weighted expansion of w, and the calculation becomes a sum 00:12:57.627 --> 00:13:01.726 of inner products between training features and the new feature vector. 00:13:02.523 --> 00:13:07.527 Now replace every lifted inner product by K of x sub i and x. 00:13:07.631 --> 00:13:08.920 Prediction can be performed 00:13:08.920 --> 00:13:13.890 without forming w and without explicitly forming phi of any example. 00:13:15.104 --> 00:13:18.402 Most coefficients alpha sub i are zero. 00:13:18.506 --> 00:13:21.186 Only support vectors have nonzero coefficients 00:13:21.269 --> 00:13:23.476 and contribute to the final sum. 00:13:23.580 --> 00:13:24.718 The same small set 00:13:24.718 --> 00:13:28.909 of geometrically decisive points now makes prediction sparse. 00:13:29.706 --> 00:13:33.712 Training can also be written entirely in terms of pairwise kernels. 00:13:33.908 --> 00:13:38.761 The dual objective contains K of x sub i and x sub j for pairs 00:13:38.761 --> 00:13:40.083 of training examples, 00:13:40.166 --> 00:13:44.950 together with nonnegative coefficients whose label-weighted sum is zero. 00:13:45.747 --> 00:13:49.994 The optimization therefore needs a matrix of pairwise kernel values, 00:13:50.077 --> 00:13:52.423 often called the Gram matrix. 00:13:52.527 --> 00:13:54.685 Once those values are available, 00:13:54.768 --> 00:13:58.460 the algorithm can operate as though it knew every lifted coordinate. 00:13:58.657 --> 00:14:03.046 A kernel supplies exactly the required feature-space inner product. 00:14:03.843 --> 00:14:07.141 Different kernels encode different notions of similarity. 00:14:07.337 --> 00:14:10.087 The linear kernel is the ordinary dot product, 00:14:10.170 --> 00:14:12.981 so it gives the original linear SVM. 00:14:13.777 --> 00:14:18.225 A polynomial kernel raises a shifted dot product to a degree d. 00:14:18.537 --> 00:14:22.485 Our quadratic example used degree two with no shift. 00:14:22.682 --> 00:14:23.841 Higher degrees represent 00:14:23.924 --> 00:14:27.211 richer interactions among the original coordinates. 00:14:28.007 --> 00:14:30.817 The radial basis kernel decreases exponentially 00:14:30.817 --> 00:14:33.650 with squared distance between two inputs. 00:14:33.754 --> 00:14:37.620 It corresponds to a very rich feature space and produces flexible local 00:14:37.620 --> 00:14:42.288 boundaries, with gamma controlling how quickly similarity falls away. 00:14:43.085 --> 00:14:47.242 A kernel is not magic permission to use any similarity formula. 00:14:47.346 --> 00:14:51.236 It must behave like a genuine inner product in some feature space. 00:14:51.340 --> 00:14:52.348 When it does, 00:14:52.431 --> 00:14:56.693 the maximum-margin optimization remains mathematically well formed. 00:14:57.396 --> 00:14:59.452 Let us connect the whole argument. 00:14:59.649 --> 00:15:04.421 First, maximum margin chooses the separator with the widest empty corridor. 00:15:04.618 --> 00:15:08.275 The nearest points become support vectors because their constraints pin 00:15:08.275 --> 00:15:10.041 that corridor in place. 00:15:11.093 --> 00:15:15.189 When classes overlap, slack variables measure margin violations, 00:15:15.272 --> 00:15:19.673 and C trades a wider corridor against the cost of those violations. 00:15:20.470 --> 00:15:22.581 When no straight boundary works, 00:15:22.664 --> 00:15:27.704 a feature map can lift the examples into a space where a hyperplane does work. 00:15:27.900 --> 00:15:31.070 The decision surface is linear there even though it is curved 00:15:31.070 --> 00:15:32.882 in the original coordinates. 00:15:33.678 --> 00:15:37.161 Finally, the kernel trick computes only the inner products required 00:15:37.161 --> 00:15:38.985 by training and prediction. 00:15:39.181 --> 00:15:42.003 It preserves the lifted geometry without paying the cost 00:15:42.003 --> 00:15:44.616 of explicitly writing the lifted vectors. 00:15:45.412 --> 00:15:49.163 That is the support vector machine in one connected picture: 00:15:49.267 --> 00:15:51.645 maximize geometric separation, 00:15:51.728 --> 00:15:56.684 let a small set of points determine the answer, tolerate overlap when necessary, 00:15:56.767 --> 00:16:01.748 and use kernels when the useful separation lives in a nonlinear feature space.