# 16. Learning: Support Vector Machines

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=_PwhiWxHK8o
**Transcript page:** https://www.withtranscript.ai/video/_PwhiWxHK8o

## Chapters

- 0:09 — Chapter 1 (0:09)
- 6:46 — Chapter 2 (6:46)
- 10:48 — Chapter 3 (10:48)
- 13:49 — Chapter 4 (13:49)
- 15:04 — Chapter 5 (15:04)
- 17:58 — Chapter 6 (17:58)
- 20:24 — Chapter 7 (20:24)
- 22:30 — Chapter 8 (22:30)
- 30:10 — Chapter 9 (30:10)
- 34:48 — Chapter 10 (34:48)
- 38:57 — Chapter 11 (38:57)
- 41:49 — Chapter 12 (41:49)

## Transcript

**[0:09]:** So, where are we? We started off with a simple methods for learning stuff. Then we talked a little about uh learning approaches to learning that were vaguely inspired by the fact that our heads are stuffed with neurons and that we seem to evolve from primates. Uh then uh we talked about looking at the problem and address the issue of phonology and how it's possible to learn concepts. Uh but now we're coming uh full circle back to the beginning and thinking about how to divide up a space with decision boundaries. But whereas you do it with a neural net or a nearest neighbors or a ID tree, those are very simple ideas that work very often. Today we're going to talk about a very sophisticated idea that still has a simple implementation. So, this needs to be in the tool bag of every civilized person. This is about support vector machines.

**[1:18]:** Uh an idea that was developed Well, I want to talk to you today about how ideas develop actually. Because you look at stuff like this in a book and you think, well, um Vladimir Vapnik just uh figured this out one Saturday afternoon when it was the weather was too bad to go outside. That's not how it happens. It happens very differently. I want to talk to you a little bit about that. The nice thing about about things that were great things that were done by people are still alive is you can ask them how they did it. You can't do that with Fourier. You can't say to Fourier, how did you do it? Did you dream it up on a Saturday afternoon? But you can call Vapnik on the phone and ask him questions. That's the stuff I'm going to talk about toward the end of the hour.

**[2:04]:** Well, it's all about decision boundaries and now we have several techniques that uh we can use to uh draw some decision boundaries. And here's the same problem. And if we uh drew decision boundaries in here, uh we might get something that would uh look like maybe this if we were doing a nearest neighbor approach. And if we're doing ID trees, we'd just draw in a line like that. And if we're doing neural nets, well, you know, you can put in a lot of straight lines wherever you like with a neural net depending on how it's trained up or if you just simply go in there and design it so you could you could do that if you wanted. And you would think that uh after people have been working on this sort of stuff for 50 or 75 years that uh there wouldn't be any tricks in the bag left.

**[2:54]:** And uh that's when everybody got surprised because around um the early '90s, uh Vladimir Vapnik introduced the ideas I'm about to talk to you about. So, what Vapnik says uh is uh something like this. Here you have a space and you have some negative examples and you have some positive examples. How do you divide the positive examples from the negative examples? And what he wants to what he says we want to do is we want to we want to draw a straight line. But which straight line is the question? Well, we want to draw a straight line. Well, would this be a good straight line? One that went up like that? Probably not so hot. How about one that's just right here? Well, that's my separate them, but seems awfully close to the negative examples. So, maybe what we ought to do is we ought to draw our straight line in here sort of like this.

**[4:00]:** And that line is drawn with a view toward putting in the widest street that separates the positive samples from the negative samples. That's why I call it the widest street approach. So, Vapnik's way of putting in the decision boundary is to put in a straight line, but in contrast with the way ID tree puts in a straight line, it tries to put the line in in such a way as the separation between the positive and negative examples, that's that street, is as wide as possible. All right? So, you might think to do that in a Europe project and then let it go with that. Um you know, what's the big deal? So, what we got to do is we're going to kind of go through why it's a big deal. So, first of all, we we kind of like to think about uh how you would uh make a decision rule that would use that decision boundary.

**[4:59]:** So, what I'm going to ask you to imagine is that we've got a vector of any length you like constrained to be perpendicular to the median. Or if you like, perpendicular to the gutters. It's perpendicular to the to the median line of the street. All right? It's drawn in such a way that that's true. You We don't know anything about its length yet. Then we also have some unknown uh say right here and we have a vector that points to it like so. So, now what we're really interested in is whether or not that unknown is on the right side of the street or on the left side of the street. So, what we want to do is we want to project that vector U down on the one that's perpendicular to the street. Because what then we'll have the distance in this direction or a number that's proportional to the distance in this direction.

**[5:58]:** And uh and the further out we go, the closer we'll get to being on the right side of the street. Where the right side of the street is not the correct side, but actually the right side of the street. So, what we can do is we can say, let's take W and dot it with U and measure whether or not that number is equal to or greater than some constant C. So, remember that the dot product is taking the projection onto W. And the bigger that projection is, the further out along this line the projection will lie and eventually be so big that that that projection crosses the median line of the street and we'll say it must be a positive sample.

**[6:46]:** Or we could say, without loss of generality, that the dot product plus some constant B is equal to or greater than zero. If that's true,

**[7:00]:** then it's a positive sample. So, that's our decision rule.

**[7:11]:** And this is the first in several elements that we're going to have to line up to understand what this idea called support vector machines. So, that's the decision rule and the trouble is we don't know what constant we to use and we don't know which W to use either. We know that W has to be perpendicular to the median line of the street, but there are lots of Ws that are perpendicular to the median line of the street because they can be of any length. So, we don't have any enough constraint here to fix a particular B or a particular W. Are you with me so far? Yeah. All right. So, what we're going to do next, and this by the way we get just by saying that C equals minus B.

**[8:03]:** What we're going to do next is we're going to put uh lay on some additional constraints with a view toward putting enough constraint on the situation that we can ac- actually calculate calculate a B and a W. So, what we're going to say is this. That this if we if we look at this quantity that we're checking out to be greater than or less than zero to make our decision, then what we're going to do is we're going to say that if we take that vector W and we take the dot product of that with some X plus some positive sample now. This is not an unknown. This is a positive sample. If we take those the dot product of those two vectors and we add B just like in our decision rule, we're going to want that to be equal to or greater than one.

**[8:54]:** So, in other words, you can be an unknown anywhere in this street and be just a little bit uh greater or just a little bit less than zero. But if you're a positive sample, we're going to insist that this decision function gives a value of one or greater. Likewise, if W dotted with some negative sample

**[9:20]:** uh is provided to us, then we're going to say that that has to be equal to or less than minus one. All right? So, if you're a minus sample, like one of these two guys or any minus sample that may lie down here, this function that gives us the decision rule must return minus one or less. So, there's a separation of distance here of minus one to plus one for all of the samples.

**[9:51]:** So, that's cool. But uh we're not quite done because I don't know. This is carrying around two equations like this is kind of a pain. So, what we're going to do is we're going to introduce um another variable to make things make life a little easier.

**[10:11]:** Like many things we do when we develop this kind of stuff uh introducing this variable is not something that God says has to be done. It's just a minus uh what is it? It's uh we we we introduce this additional stuff to do what? To make the mathematics more convenient. It's a mathematical convenience. So, what we're going to do is we're going to introduce a variable Y sub I such that

**[10:48]:** Y sub I is equal to +1 for plus samples.

**[10:58]:** And minus one

**[11:08]:** for negative samples. All right? So, for each sample we're going to have a value for this new quantity we've introduced Y. And the value of Y is going to to be determined by whether it's a positive sample or negative sample. It's a positive sample, it's going to be +1. For this situation up here, and it's going to be minus one for this situation down here. So, what we're going to do with this first equation is we're going to multiply it by Y sub I and that that is now X sub I plus B is equal to or greater than one. And then you know what we're going to do? We're going to multiply the the left side of this equation by We're going to multiply left side of this equation by Y sub I as well. So, the the second equation becomes Y sub I times X sub I plus B.

**[12:03]:** And now what do we What does that do over here? We We multiplied this guy times minus one. So, it used to be the case that that was less than minus one. So, if we multiply it by minus one, then it has to be greater than plus one. Oh, oops. The The two equations are the same. Because of that introduces this little mathematical convenience. So, now we can say that uh Y sub I times X sub I plus B Well, what we're going to do Right? Oh, would I leave out a W? I'm sorry. Thank you. Yeah, I wouldn't have got very far without So, that's dot of a W, dot of a W. Thank you, Brett. Those are all vectors. I'll pretty soon forget to put the little vector marks on there, but you know what I mean. So, that's W plus B. And now let me bring that that one over to the left side and that's equal to or greater than zero.

**[13:13]:** All right? Now, with Brett's correction, I think everything's okay. But, we're going to take one more step and and and and we're going to say that Y sub I times X sub I times W plus B minus one You know, it's always going to be equal to or greater than zero, but what I'm going to say is that for for X sub I in the gutter

**[13:49]:** So, they always got to be greater than zero, but we're going to say we're going to add the additional constraint that it's going to be exactly zero for all of the samples that end up in the in the in the gutters here of the street. So, the value of that expression is going to be exactly zero for that sample. Exactly Sorry. Zero for this sample and this sample. Not zero for that sample. It's going to be greater than one. All right? So, that's step number two.

**[14:25]:** And this is step number one.

**[14:31]:** Okay, so now we've just got some expressions that talk about some constraints. Now, what are we trying to do here? I forgot. What are we Oh, I remember now. We're trying to get We're trying to figure out how to arrange for the line to be such that the street separating the pluses from the minuses is as wide as possible. So, maybe we better figure out how we can express the distance between the two gutters.

**[15:04]:** Let's just uh repeat our our drawing. We got some minuses here. We got pluses out here. And we got gutters that are going down here. And now we've got a vector here to a minus. And we've got a vector here to a plus. So, that's We'll call that X plus and this X minus. So, what's the What's the width of the street? I don't know yet. But, uh what we can do is we can take the difference of those two vectors. And that will be a vector that looks like this, right? So, that's X plus minus X minus. So, now if I only had a unit normal that's normal to the median line of the street if it's a unit normal, then I could just take the dot product of that unit normal and this difference vector, and that would be the width of the street, right?

**[16:06]:** So, in other words if I had a unit vector in that direction then I could just dot the two together, and that would be the width of the street. So, let me write that down before I forget. So, the width is equal to X plus minus X minus. Okay? That's the difference vector, and now I got to multiply it by a unit vector, but wait a minute. I I said that that W was a a normal. Right? W is a normal. So, what I can do is I can multiply this times W. And then we'll divide by the magnitude of W. And that will make it a unit vector. So, that that that dot product not not a product, that dot product is in fact a scalar, and it's the width of the street. Doesn't do us much good because doesn't look like we can get much out of it.

**[17:17]:** Oh, but I don't know. Let's see. What can we get out of it? Oh, gee, you know, we got this equation over here. This This equation that constrains the samples that lie in the gutter. So, if we have a positive sample, for example then this is plus one and we have this equation. So, it says that X plus times W is equal to Oh, one minus B.

**[17:58]:** See, I'm just taking this part here. This This vector here, and I'm dotting it with X plus. So, that's this piece right here. Y is one for this kind of sample. So, I'll just take the one and the B back over to the other side, and I've got one minus B. Okay? Well, we can do the same trick with X minus. If we've got a negative sample then Y sub I is negative. That gives us our negative W times dot of a with X sub I. And now we take this stuff back over to the right side and we get one minus B. One plus B. Right? So, that all licenses to rewrite this thing as two over the magnitude of W. How did I get there? Well, I decided I was going to enforce this constraint. I noted that the width of the street is got to be this difference vector times a unit vector.

**[19:06]:** Then I used the constraint to plug back some values here, and I discovered to my delight and amazement that the width of the street is two over the magnitude of W. Yes, Brett. So, here first so, X plus is one and B, and X minus is one and B. Yeah. Let's see. If I've got a a minus here then that makes that minus, and then the B is minus. So, when I take the B over to the other side, it becomes plus. Yeah, so if you subtract

**[19:41]:** No. No, sorry. This This expression here is one minus one plus B. Okay? Trust me, it works. I haven't got my legs all tangled up like last Friday. But not yet, anyway. It's possible. There's going to be a lot of algebra here eventually. So, uh this quantity here, this is miracle number three. This This This quantity here is the width of the street. And what we're trying to do is we're trying to maximize that, right? So, we want to maximize two over

**[20:24]:** the magnitude of W if we're to get the widest street under the constraints that we've decided we're going to work with. All right? So, that means that it's okay to maximize one over W instead. We just dropped the constant. And that means that it's okay to minimize the magnitude of W. Right?

**[21:00]:** And that means that it's okay to minimize

**[21:06]:** one half times the magnitude of W squared. Right, Brett? Why did I do that? Why did I multiply by half and square it? It was mathematically convenient. Thank you. So, this is a This is point number three in the development. So, where do we go? We We We decided that was our going to be our decision rule. We're going to see which side of the line we're on. We decided to constrain the situation so that the value of the decision rule is plus one in the gutters for the positive samples and minus one in the gutters for the negative samples. And then we discovered that maximizing the width of the street led us to an expression like that which we wish to maximize.

**[21:55]:** Are we Are we Should we take a break? Should we get coffee? Too bad we can't do that in this kind of situation, but we would if we could. And I'm sure when Vapnik got to this point, he went out for coffee. So, now we back up and we say, "Well, let's let these expressions start developing into a song." Like not like that. That's vapid. Speaking of Vapnik.

**[22:30]:** What song is it going to sing? We've got an expression here that we'd like to find the minimum of, the extremum of. And we've got some constraints here that we would like to honor. What are we going to do? Let me put what we're going to do to you in the form of a puzzle. Is it got something to do with Legendre? Has it got something to do with um Laplace? Or does it have something to do with Lagrange? She says Lagrange. Actually, all three were said to be on Fourier's doctoral defense committee. Must have been quite an exam. But we want to talk about Lagrange because we're going to We got a situation here. Is this 1801? 1802? 1802. We learned in 1802 that if we're going to find the extremum of a function with constraints, then we're going to have to use the Lagrange multipliers.

**[23:36]:** That will give us a new expression which we can maximize or minimize without thinking about the constraints anymore. That's how Lagrange multipliers work. So, this brings us to miracle number four. Piece of the developmental piece number four. And it sort of works like this. We're going to say that L, the thing we're going to try to maximize in order to maximize the width of the street, is equal to one half times the magnitude of that vector W squared minus And now we got to have a summation over all the constraints. And each of those constraints is going to have a multiplier alpha sub I. And then we write down the constraint. And when we write down the constraint, there it is up there. But I've got to be hyper careful here because otherwise I'll get lost in the algebra. So, the constraint is Y sub I times vector W dotted with vector X sub I plus B And now I've got a closing parenthesis.

**[24:50]:** A minus one. That's the end of my constraint. Like so.

**[25:00]:** I sure hope I've got that right. Cuz I'll be in deep trouble if that's wrong. Does everybody Anybody see any bugs in that? That looks right, doesn't it? We got the We got We got the original thing we're trying to work with. Now we got Lagrange multipliers all multiplied uh with respect to that constraint up there where each constraint is constrained to be zero. Well, there's a little bit of mathematical slight of hand here because in the end the ones that are going to be zero, the Lagrange multipliers here, the ones that are going to be non-zero are going to be the ones connected with vectors that lie on the gutter. The rest are going to be zero. But in any event, we can pretend that this is what we're doing. And then we got to find the max. I don't care whether it's a maximum or minimum.

**[25:48]:** I've lost track, but what we're going to do is we're going to try to find an extremum of that. So, what do we do? What is 1801 teach us about finding the maximum? Well, we got to find the derivatives and set them to zero. And then after we've done a little bit of that manipulation, we're going to see a a wonderful song start to emerge. So, let's see if we can do it. Let's take the partial of L, the Lagrangian, with respect to the vector W. Oh my god, how do you differentiate with respect to a vector?

**[26:25]:** Turns out that it has a form that looks exactly like differentiating with respect to a scalar. And the way you prove that to yourself is you just expand everything in terms of all the vector's components. You differentiate those with respect to what you're differentiating with respect to, and everything turns out the same. So, what you get when you differentiate this with respect to the vector W is two comes down and we have just magnitude of W. Is it the magnitude of W? Yeah. Like so.

**[27:02]:** Is it the magnitude of W? Well, in any event, we got to It's not the magnitude of W. It's just W. Like so. No magnitude involved. Then we got a W over here that we got to We got So, we got to differentiate this part of it with respect to W as well, but that part's a lot easier cuz all we have there is a W. It's not There's no magnitude. It's not raised to any power. So, what's W multiplied by? Well, it's multiplied by X and Y sub I and alpha sub I. Right? So, that's means that that this expression this derivative of the Lagrangian with respect to W is going to be equal to W minus the sum of alpha sub I uh Y sub I X sub I. And that's all got to be set to zero. And that implies that W is equal to the sum of some alpha I, some scalars, times this minus one or plus one variable times X sub I over I.

**[28:11]:** And now the math is beginning to sing. Because it tells us that the vector W is a linear sum of of the samples. Some sub All the samples are some of the samples. It didn't have to be that way. It could have been raised to a power. There could have been a logarithm. All sorts of horrible things could have happened when we did this. But when we did this, we discovered that W is going to be equal to a linear sum of these vectors here. Some of the vectors in the sample set. And I say some because for for some alpha will be zero. Right? So, this is something that we want to take note of as something important. Now, of course, we got to differentiate L with respect to the anything else that might vary. So, we got to differentiate L with respect to B as well.

**[29:18]:** So, what's that going to be too? Well, there's no B in here, so that makes no contribution. Uh this part here doesn't have a B in it, so that makes no contribution. There's no B over here, so that makes no contribution. So, we got alpha I times Y sub I times B. That has a contribution. So, that's going to be the sum of alpha I times Y sub I. Then we differentiate We're differentiating with respect to b so that disappears. There's a minus sign here and that's equal to zero or that implies that the sum of the alpha i times y sub i is equal to zero. Hmm, that looks like that might be helpful somewhere.

**[30:10]:** Now it's time for more coffee. By the way, these coffee periods take months. You stare at it, you work on something else. Uh you got to worry about your finals. And you think about it some more. And eventually you come back from coffee and do the next thing. Oh, what is the next thing? Well, we still got this expression that we're trying to find uh the um minimum for. And you know, you say to yourself, this is really a a job for the numerical analyst. Those guys know about this sort of stuff. Because of that little power in there that square, this is a so-called quadratic uh optimization problem. So at this point you'd be inclined to hand this problem over to a numerical analyst. They'll come back in a few weeks with an algorithm. You implement the algorithm and maybe things work, maybe they don't converge, but in any case, you don't worry about it.

**[31:08]:** But we're not going to do that because we want to do a little bit more math because we're interested in stuff like this. We're interested in the fact that the decision vector is a linear sum of the samples. So we're going to work a little harder on this stuff. And in particular now that we've got an expression for w, this one right here we're going to plug it back in there and we're going to plug it back in here and see what happens to that thing we're trying to find the extremum of.

**[31:47]:** Everybody kind of relax, take a deep breath. This isn't actually this is the easiest part. This is just some just doing a little bit of the algebra. So the thing we're trying to to maximize or minimize is equal to 1/2 and now we got to have the the the the magnitude of those the magnitude you know we got to have this vector here uh uh in there in there twice. Right? Cuz we're we're we're multiplying it to to together. So let's see. Um we've got from that expression up there, one of those w's will just be the sum of the alpha i times the y sub i times the vector x sub i. And then we got the other one, too. So that's just going to be the sum of alpha now I want to keep things I'm going to actually eventually squish those two sums together into a double summation.

**[32:47]:** So I have to keep the indexes straight. So I'm just going to write that as alpha sub j y sub j x sub j. So those are my two vectors and I'm going to take the dot product of those. That's the first piece, right? Well, this is this is not this is hard. So minus and now the next term looks like alpha i y sub i x sub i times w. So we've got a whole bunch of of these. We got a sum of alpha i times y sub i times x sub i and then that gets multiplied times w. So we'll put this like this. I have a sum of alpha j y sub j x sub j in there like that. And then that's the dot product of that. Well, that wasn't as bad as I thought.

**[33:50]:** Now I've got to deal with the next term, the alpha i times y sub i times b. So that's my is that a that's a minus sum of alpha i times y sub i times b. And then to finish it off we have plus the sum of alpha sub i. That's that minus one up there, minus one in front of the summation. So it's just the sum of the alphas. Are you with me so far? Just a little algebra. It looks good. I think I'm I think I haven't messed it yet. Let's see. Alpha i times y sub i times b. B is a constant. So we'll pull that out there and then I just got the sum of alpha alpha sub i times y sub i. Oh, that's good. That's zero.

**[34:48]:** And now so so for every one of these terms we dotted with this whole expression. So that's just like taking this thing here and and dotting those two things together, right? Oh, but that's just the same thing we've got here. Right? So now what we can do is we can say that we can rewrite this Lagrangian as We got we got the that sum of alpha i. That's the positive element. And then we got we got one of these and a half of these. So that's minus 1/2 and now I'll just convert that whole works into a double sum over both i and j of alpha i uh times alpha j times y sub i times y sub j times x sub i dotted with x sub j. We sure went through a lot of trouble to get there, but now we've got it and we know that what we're trying to do is we're trying to find a maximum of that expression.

**[36:07]:** And that's the one we're going to hand off to the numerical analyst. So if we're going to hand this off to the numerical analyst anyway, why did I go to all this trouble? Good question. Wanda, do you have any idea why I went to all this trouble? Because I wanted to find out the dependence of this expression as Wanda is telling me as I I'm I'm translating as I go. She's telling me in Romanian. I want to find what this maximization depends on with respect to the the these these these vectors, the x the sample vectors. And what I've discovered is that the optimization depends only on the dot product of pairs of samples. And that's something we want to keep in mind. That's why I put it in royal purple. Now up here, so so let's see. Let's let's What do we call that one up there?

**[37:04]:** That's two. I guess this uh we'll call this piece here three. This piece here is four. And now there's one more piece. Cuz I want to take that that w and not only stick it back into that Lagrangian, I want to stick it back into the decision rule. So now my decision rule with this expression for w is going to be w plugged into that thing. So the decision rule is going to look like the sum of alpha i times y sub i times x sub i dotted with the unknown vector like so. And we're going to subtract I guess add b and we're going to say if that's greater than or equal to zero then plus. So you know you see see why the math math is beginning to sing to us now? Because now we discover that the decision rule also depends only of the on the dot product of those sample vectors and the unknown.

**[38:15]:** So the total there's a total dependence of all of the math on the dot products. Right? And now I hear a whisper. Someone is saying I don't believe the mathematicians can do it. I don't think those numerical analysts can find the optimization.

**[38:37]:** I want to be sure of it. Give me ocular proof. So I'd like to run a demonstration of it.

**[38:57]:** Okay, there's our sample problem, the one I started the hour out with. Now if if the optimization algorithm it doesn't get stuck in a local maximum or something, it should find a nice straight line separating those two guys defining the widest street between the minuses and the pluses. So in just a couple of steps, you can see down there at step 11 it's decided that it's done as much as it can on the optimization. And it's got three alphas. And you can see that the two negative the two negative samples both figure into the solution. The weights on the the Lagrangian multipliers are given by those little yellow bars. So the two negatives participate in the solution as does one of the positives, but the other positive doesn't, so it has a zero weight. So, everything worked out well. Now, I said as long as it doesn't get stuck in a local maximum, guess what?

**[39:52]:** Those mathematical friends of ours can tell us and prove to us that this thing is a convex space. That means it can never get stuck in a local maximum. So, in contrast with things like neural nets where where where you have a plague of local maxima, this guy never gets stuck in a local maximum. Let's try some other examples. Here's two vertical points. No surprises there, right? Uh well, you say, "Well, maybe it can't deal with diagonal points." Sure it can. Uh how about um this thing here? Yeah, it only needed two of the points. Since any any two of those pluses any two a plus and a minus will define the street. Let's try this guy. Oh. What do you think will happen here? Well, we're screwed, right? Because it's linearly unseparable.

**[40:57]:** Bad news. So, in situations where it's linearly unseparable, the math the the the mechanism struggles and eventually will just slow down and you truncate it because it's not making any progress and you see the red light the red dots there are ones that it got wrong. So, you say, "Well, too bad for our side. Doesn't look like it's all that good anyway." But then, a powerful idea comes to the rescue. When stuck, switch to another perspective. So, if we don't like the space that we're in because it it it gives us samples that are not linearly acceptable, linearly separable, then we can say, "Uh shoot." Here's our space. Here are two points.

**[41:49]:** Here are two other points. We can't separate them, but if we could somehow get them into another space, maybe we can separate them because they look like this

**[42:06]:** in the other space and they're easy to separate. So, what we need then is a transformation that will take us from the space we're in into a space where things are more convenient, so we're going to call that transformation fee of the vector X. That's the transformation. And now, here's the reason for all the magic. I said that the maximization only depends on dot products. So, all I need to do the maximization is the is the transformation of one vector dotted with the transformation of another vector. Like so. That's what I need to maximize. Or to find the maximum one. Then, in order to recognize where did they go? Underneath the chalkboard.

**[43:05]:** Oh, yes, here it is. To recognize, all I need is dot products, too. So, for that one I need fee of X dotted with fee of U. And just to make this a little bit more consistent in notation, I'll call it X sub J and this X sub I. And that's X sub I. Those are the quantities I need in order to do it. So, that means that if I have a function, let's call it K of X sub I and X sub J, that's equal to fee of X sub I dotted with fee of X sub J, then I'm done. This is what I need. I don't actually need this. All I need is that function K, which happens to be called a kernel function, which provides me with the dot product of those two vectors in another space. I don't have to know the transformation into the other space.

**[44:11]:** And that's the reason that this stuff is a miracle. So, what are some of those What are some of the kernels that are popular? One is the linear kernel that says that U dotted with with V plus one to the nth is such a is such a kernel because it's got U in it and V in it. The two dotted the two vectors and this is what the dot product is in the other space. So, that's one choice. Another choice is a kernel that looks like this. E to the minus let's take the dot product of those two the difference of those two guys. Let's take the magnitude of that and divide it by some sigma. That's a second kind of kernel that we can use. So, let's go back and see if we can solve this problem by transforming into another space where we have another perspective.

**[45:10]:** So, let's That's the That's That's it. That's a That's a That's another kernel. And so, sure we can. And that's the answer when transformed back into the original space. We can also try doing that with a so-called radio basis kernel. That's the one with the exponential in it. We can learn on that one. Boom. No problem. So, we've got a general method that's convex and guaranteed to produce a global solution. We've got a mechanism that easily and allows us to transform this into another space. So, it works like a charm. Of course, it doesn't remove all possible problems. Look at that exponential thing here. If we choose a sigma that is small enough, then those sigmas are essentially shrunk right around the sample points and we can get over fitting. So, it doesn't immunize us against over fitting. But it does immunize us against local maxima and does it provide us with a general mechanism for uh doing a transformation into another space with a better perspective.

**[46:19]:** Now, the history lesson. All this stuff feels fairly new. It feels like it's younger than you are. Here's the history of it. Uh Vapnik emigrated from the Soviet Union to the United States in about 1991. Nobody ever heard of this stuff before he emigrated. He actually had done this work on the basics of support vector idea in his PhD thesis at Moscow University in the early '60s. But it wasn't possible for him to do anything with it because he didn't have any computers that he could try anything out with. So, he spent the next 25 years at some oncology institute in the Soviet Union doing applications. Somebody from Bell Labs discovers him, invites him over to the United States where subsequently he decides to emigrate. In 1992 or thereabouts, Vapnik submits three papers to the to NIPS, the Neural Information Processing Systems journal. All of them were rejected.

**[47:19]:** He's still sore about it. But it's motivating. So, around 1992, 1993, Bell Labs was interested in handwritten character recognition and in neural nets. Vapnik thinks that neural nets What would be a good word to use? Uh I can think of the vernacular, but he thinks that they're not very good. So, he bets a colleague a good dinner that support vector machines will eventually do better at handwriting recognition than neural nets. And it's a dinner bet, right? It's not that big a deal, but as Napoleon said, "It's amazing what a soldier will do for a bit of ribbon." So, Vapnik's colleague, who's working on this on this on this problem of handwritten recognition, decides to try a support vector machine with a kernel in which n equals two. Just slightly non-linear. Works like a charm. Has Was this the first time anybody tried a kernel? Vapnik actually had the idea in his thesis, but never thought of it as very important.

**[48:25]:** As soon as it was shown to work in the early '90s on the problem of handwriting recognition, Vapnik resuscitated the idea of the kernel, began to develop it, and became an essential part of the whole approach of using support vector machines. So, the main point about this is that it was 30 years in between the concept and anybody ever hearing about it. It was 30 years between Vapnik's understanding of kernels and his appreciation of their importance. And that's the way things often go. Great ideas followed by long periods of nothing happening, followed by an epiphanous moment when the original idea is seen to have great power with just a a little bit of a twist, and then the world never looks back. And Vapnik, who nobody ever heard of until the early '90s, becomes famous for something that everybody knows about today who does machine learning.
