Lecture 13 Fall 2025: Support Vector Machines transcript

All right, welcome back everybody. So today we are going to finally talk about support vector machines. And this is a way of performing classification that has a rich history, lots of beautiful theory and was one of the main um most widely used classifiers uh for many many years. Um I think in recent years people tend to opt more towards neural networks, but there's a lot of important concepts that show up in support vector machines that are worth knowing and understanding.

So to get started, I want to go back to last week when we talked about ridge regression. And if you recall, we said that the learned weight vector with ridge regression had a particular form. So we we first derived it from a um regularized le squares perspective but then we started thinking about how to interpret it using the singular value decomposition of x. So we're going to think about our feature matrix X as having singular value decomposition U sigma VRpose.

And then we can write the ridge regression weight vector as V sigma transpose uranspose time U sigma sigpose plus lambda identity inverse time uranspose y. So this was the form that we derived at the end of class last week and we can factoriize this into two components where the first component right here this is simply x transpose right if we look at the singular value decomposition of x and we take the transpose of both sides of this equation then we get u sigma transpose uranspose And then everything else here we just call alpha.

So we are defining alpha the vector alpha to be this product. And if we think about what's happening here, we are taking the vector of labels y from our training data. Then we are applying this orthogonal transformation. You can think about it perhaps as a rotation. Then in that rotated space we are um reweighing each one of the coordinates and then we're undoing that rotation. Okay. So the other point that we talked about last time is that this vector or this representation of W hat R as Xrpose time alpha tells us that this weight vector is equal to a weighted sum of the columns of XRPOSE. where the alpha i's are the weights and if we think about well what are the columns of xrpose those are actually our features so this is a weighted sum so the columns of xrpose are the rows of x so this is a weighted sum of our feature training feature vectors the x i's with the alpha i's um the weight um as the weights.

So this is giving us a new perspective um on how to interpret the ridge regression weight vector. It's just a weighted sum of our training samples and this expression for alpha is telling us how to compute those weights. it depends on the label. So, we're going to give different weights to different samples depending on what their label is. Um, but we're using the SVD to figure out what those those weights should be.

Okay. So I can similarly and maybe more efficiently write this because I can take this vector alpha and what I can do is I can move remember that um uranspose is equal to u inverse with the singular value decomposition. So what I can do then is I can actually move the 's into this inverse matrix and I can write alpha now [snorts] as being equal to um I'm going to have just want to make sure I get it right. Yep. U sigma sigma transpose uranspose plus lambda u uranspose inverse time y.

And this is useful because now I can actually oh well okay this is still identity but now I can think about this in terms of x I can write this as xrpose plus lambda identity inverse * y so putting the pieces together if I come over here we have that our ridge regression weight vector is equal to xrpose alpha where alpha is equal to xxrpose plus lambda identity inverse * y. Okay, so we derived that last time and then we said not only is this very good for doing linear classification and linear regression um where we want to think about um weights on our various features but also we can think about mapping all of our features to a higher dimensional feature space.

So in particular we said imagine that we have a function f that inputs a feature vector x and maps it into a new space. So our feature vector x as always is pd dimensional but this f function can map it into something where often the new dimension of f ofx is higher dimensional than um p. And so as an example, we could have for instance that V of well, let me just do an example where I've got two coordinates X1 and X2.

What I could have is that that would give me a new vector that's say X1 X2 X1 2AR X2 2 X1 X2. So now what I've done is I've gone from a two-dimensional feature vector to a fivedimensional feature vector that's capturing quadratic relationships or quadratic functions of my features, not just the raw features. And what we said is that once we've done that mapping, we can actually think about doing ridge regression in this new feature space instead.

And so to do that we defined a new matrix capital fee which is going to be our new feature matrix in this highdimensional space. So the first row would be f of x1 transpose. The second row would be f of x2 transpose all the way down to v of xn transpose. So this matrix now still has whoops still has n rows just like before but now it's got d columns. So it's much wider potentially than the original x matrix. But now we can start thinking about ridge regression using this.

So we can say in this new highdimensional feature space we can think about doing ridge regression where now our ridge regression weight vector corresponds to the argument or the pos or the weight vector that minimizes y - v * the set of weights 2 norm^ 2 plus lambda * the 2 norm term of the weight vector squared. So it's just like before only instead of using our raw feature matrix X, we're using this mapped um feature matrix FE that has these more complex relationships embedded.

But our work is basically done. we can actually take exactly the expression for the ridge regression predictor that we derived for the xace and just plug in v instead. So now we would have that the weight vector that we seek is going to be capital P transpose * alpha where alpha now is going to be equal to V franspose plus lambda identity inverse time Y. So exactly the same concept. We've just essentially done a little pre-processing step to our features before we solve ridge regression.

So are there any questions about this so far? Okay. So I want to talk a little bit now about dimensionality. So in particular when we did ridge regression before remember we interpreted our weights our weight vector as being a weight on each one of the different features. So this weight vector was a vector in RP and now when we're in this higher dimensional feature space our ridge regression weight vector is in R D. And there are many settings where D can be extremely large.

Um just as an example, right? Imagine that my original features are say 100 dimensional and then I want to do this quadratic mapping. So then D in that setting is going to be like 100 squared or 10,000. Right? So I've immediately by doing this highdimensional feature mapping gotten to a space where my weight vector is huge. And this is a even what I just described is still relatively low dimensional. And so what we're going to do now is we are going to talk about something called the kernel trick that's going to allow us to compute these sorts of predictors but sidestep trying to have to having to compute things explicitly in d-dimensional space which could be huge.

So this is going to give us some real computational savings. It also leads to some really beautiful theory. Um, define a kernel function [clears throat] lowercase k. And what that function is going to do is it's going to have two inputs. Let's just call them x i and xj. So two different feature vectors. And what this function is going to compute is the inner product v of x i transpose time v of xj. So in a little bit we are going to see that there are many different kernel functions that we can use where we never explicitly have to compute this fee vector where we can just directly compute this inner product very efficiently and I'll give you some explicit examples of it in a little bit but for now we're just going to assume that we have access to this kernel function and talk about what we would do with it.

So in particular we can say we can also define the kernel matrix capital K. So that if I were to look at the i J entry of that matrix, it's going to be equal to my kernel function applied to features x i and xj. So I can take every pair of feature vectors that I have and compute the inner product in this P space or compute this kernel function and use it to populate my kernel matrix. So just to be really explicit, this inner product here is just a scalar.

It's just a number. And when we form our kernel matrix, it's we're going to have one entry for every pair of feature vectors. So this matrix will be n by n. It scales with the number of samples that we have but not with d or p or anything about the dimensionality of those samples. Okay. So the reason that I'm bringing this up is because what we can show is that k is equal to capital fe capital transpose. And if you're not convinced, you can just map out, you know, using the definition of fee, what each entry of this product would look like and verify for yourselves that it will be equal to these different inner products.

So what that means then is that we can actually write our ridge regression uh weight vector in terms of this kernel matrix. So it's equal to v transpose * alpha where alpha is equal to this kernel matrix plus lambda identity inverse time y. So we could be in a setting where computing individual V of X's is hard, but computing the kernel matrix is easy. And again, I'll show you some examples in a minute. And once we've got that kernel matrix, we can figure out what alpha is. we can actually figure out how much weight we should be giving to each one of our training samples using that kernel matrix without doing anything explicitly in this feature space.

All I need is this n byn feature or kernel matrix. And in particular um once we have this for a new let's say test feature vector X. We can predict a label as follows. So if we think about in general what we'd like to do, we are going to take this um ridge regression weight vector and compute its inner product with uh v of x. So let me just give myself a little bit of space here. I'm going to say that what we want is that yhat is v of my new feature vector x transpose time w.

So now let's think about what that looks like. So I'm going to keep this um actually you know what I'm going to write it the other way. It's just going to be a little bit convenient in a second. I'm going to say w transpose * v of my new feature vector x. Now what I'm going to do is I'm going to plug in my expression for w. So this is going to be um alpha transpose time capital v times little v of my new x. And if I think about what that means, that is equivalent to looking at the sum over all of my training samples.

And for each one, I've got a weight alpha i. And then when I think about what this product means, what I'm doing is I'm looking at the E row of FE inner product with V of X here. So what I have is V of my E training feature transpose times V of my new test feature V of X. Now when you look here you see that in this expression we just have the inner product of two different fees or you know fee mappings. And so I can actually write this using my kernel function.

So I've got the s um sum from i= 1 to n of alpha i times my kernel function applied to the pair x i and my new test feature x. So if we think about what's happening here, let me get another color of chalk. Um, if we think about what's happening here, I'm saying that once we've computed our kernel matrix and we've got this kernel function, I can take my training data and I can compute this vector of weights alpha. And this is again a length in vector.

So has nothing to do with dimensionality P or D. just having this length end vector that's telling me how much weight I should be giving to each one of my n training samples. Once I've got that weight vector alpha, then when I get a new test feature vector x, I also don't have to use this v mapping. I rather just compute my kernel function for every training sample and my new test feature vector. and I weigh I compute a weighted sum of those outputs of that kernel function where the alphas give me the weights.

So I've got this sort of two-step procedure here where first I'm computing this alpha vector and second I'm making predictions and both of them I'm computing only using my kernel function and if I can I'm I'm saying that the kernel function is equivalent to this inner product in v space but what I'm going to show you very soon now is that I never actually have to do any direct computations in fspace I can just do everything using this kernel function.

Are there any questions so far? Yeah. >> Yes, let's do that right now. Okay, so let's talk about kernel functions. There's a lot of beautiful theory here that says, well, well, that would tell us like what gives us a valid kernel function. Um, but for this class, I'm just going to show you some very commonly used examples. And I'm going to start off with an example where my feature vector X is in 2D. So in particular it's got elements x1 and x2.

And then I'm going to think about a setting where f ofx is x1 squared <unk>2 x1 x2 x2 squared. And so now if I look at the inner product of f of x i and f of xj then I will get x i1 squared xj1^ 2ar + 2 x i1 x j1 x i2 xj2 plus x i2 squared xj2 squared Now this is the same as x i 1 xj1 + x i2 xj2 squared or quantity squared. And this is the same as xirpose xj quantity squared. So mathematically we can think about this as doing this nonlinear mapping to a three-dimensional feature space and then computing an inner product in that 3D space.

But it is exactly equivalent to just doing the inner product in my original 2D space and squaring the result. So in terms of how much computation I'm doing, these things are totally different even though mathematically they're equivalent. So let's think about some more general examples. Oh, first of all, are there any questions? Okay. So some popular kernels. First of all we can have polomials of degree Q. And so in particular, I'm going to say that my kernel function K for a pair of feature vectors X I and XJ is simply going to be this inner product X I transpose XJ to the qth power.

So it's just like our quadratic example, but we can do higher order polomials. So this is a nice example because if I was actually going to compute uh if I was to think about what the corresponding fee was where I'm mapping a vector x to all of the corresponding cubic monomials that vector then in this case d the dimension of f ofx would be roughly on the order of p to the q qth power. So if my feature vectors P were 100 dimensional and I was going to do cubic polomial then the implicit dimension of the fe vector would be 100 cubed.

It'd be very highdimensional but I only ever have to compute inner products in my 100dimensional space. Another thing that we see is polomials up to degree Q. So if we think about what we did over here, every um expression in this vector was exactly quadratic, right? But you could imagine saying, well, I want all the quadratic monomials, but I also want the linear ones, and I also want zeroith order. And so we can alternatively say, let's let this kernel function between two vectors x i and xj correspond to taking that inner product x i transpose xj, but before taking it to the qth power, just adding a one to it and taking that to the qth power.

So very simple change to the um kernel function. Um we still have in this setting that the dimension of the feast space would be on the order of p to the q but this is like saying this is like saying we're only going to have quadratic monomials and this is like saying we would have quadratic but also all the linear versions and all also all the zeroth degree or constant version. Okay. And then finally we have the Gaussian kernel by daylight savings time really changed the sunlight patterns here.

So with the Gaussian kernel again we think about it in terms of two feature vectors let's just say X I and XJ and the kernel function is now going to look like taking I'm going to start with the distance the uklidian distance between X I and XJ and I'm going to square it. Then I'm going to divide it by a tuning parameter or bandwidth H. take the negative of this and then exponentiate. This is extremely widely used. One way that we can think about this is what we're measuring when we compute the kernel function between a pair of feature vectors is how similar those feature vectors are to one another.

I can often think about my kernel matrix as being akin to a similarity matrix. And so imagine that I have a whole bunch of feature vectors that I'm just drawing in this plot here. And here I'm going to have one that's X I right here. And then over here I've got another one XJ. So I'm saying that the corresponding entry in the kernel matrix k is going to depend on how far away. So I can think about having like a little Gaussian bump centered around x i and I'm seeing how far away xj is to it and then I am looking at um the opposite of that and exponentiating.

So if x i and xj are closer together then this kernel function will be larger and if x i and xj are farther apart this kernel function will be smaller. They'll be less similar in that sense. Um and this bandwidth parameter h is telling me how quickly this measure of similarity drops off or gets small as two points x i and xj get further and further apart. And so these in each of these settings we've got a userdefined or a tuning parameter that we have to deal with.

Here it's this bandwidth parameter H. In the polomials we had the polomial degree Q. And just like when we were choosing the ridge regression parameter lambda we would use a hold out validation set to choose it. You would do something similar here. You would use a hold out validation set um data set to select your bandwidth parameter H or your polomial degree Q. The Gaussian kernel is interesting in part because um the corresponding fee function has no explicit form.

So really this is a case where there's implicitly a um highdimensional feature space and in fact you can show that v of x is infinite dimensional but there's no way that we can actually just write down what that looks like explicitly the way we did with polomials. So this is a setting where it's totally impossible to do ridge regression use or or prediction using this explicit fee mapping. We are forced to use the kernel in order to get any kind of prediction using the Gaussian kernel.

Are there any questions so far? Yeah. So here for each kernel function where I kind of implicitly function that's right there's for each kernel function there is an implicit V function um and so I'm not writing it down for the general degree Q but there is an explicit form and it's akin to what we did with the quadratic polomials. Um so it is possible to say exactly what the corresponding fee function would look like just like we did in our example.

It's not possible to do that with the Gaussian kernel. >> Yeah. >> Like the reason why that we can get it to be like x i trans is that we have the square roots uh to add the coefficient right >> and also like if we have need to have it to be to be exponent we also have a specific uh coefficients before each terms. So does it really matter like uh if the coefficient does not like satisfy this kind of like can we still call it kernel because when we define the function I don't think we require any of the >> right so this is a great point and I think to frame it a little bit more broadly than you just did I would say that there are many you know fee mappings that we might be interested in for which there does not exist a kernel So kernel functions that correspond to inner products of the fee functions the way we set things up there's only um there's constraints that you have to satisfy.

So it's not that for any fee function there's going to be a kernel function. Um and so uh there's really some beautiful theory associated with this like how what's the space of possible functions that we're thinking about here. What makes a valid kernel? Um where the kernel function will have for some fee this sort of inner product perspective underlying it. Um and it's beyond the scope of what we'll cover in this class.

But one of the supplementary reading books for this class um which is freely available online is elements of statistical learning and that there's a link to it on the course web page and it has a chapter on kernel methods and it talks a little bit more about some of the underlying theory including things like reproducing Colonel Hilbert spaces. So there's this you're raising an excellent point. We're just not going to go into it in more depth in this course.

Yeah. Yes. >> So question about the kernel function. So every so every row of y >> but bigger than x. So K is going to be bigger than I rows J columns. So what do you do with the extra rows on? >> So the thing to remember um which maybe I think I didn't emphasize as much as I could have over here is that this kernel matrix is n by n. So we are just looking at the pair-wise similarity of every pair x i and xj. So the size of k does not depend in any way on the dimension d or the dimension p.

It's just n byn. So um and the only thing that is ultimately like d-dimensional is this weight vector w. So this is D-dimensional this ridge regression weight vector. But if you note when we talked about how do I make a prediction for a new test sample, I defined that prediction in terms of the weight vector the way we have throughout this course. But then when I actually like map out what that would look like, I never explicitly have to compute that weight vector.

As soon as I've got the alphas, I'm good. there's nothing more that I need to do. So all my computations are based on computing the kernel function and looking at you know similarities between pairs of feature vectors using the kernel function. Does that answer your question? That's going to be a >> Oh, right. I see. >> Yeah. No, this is fine. It like it takes a while. It took took me a while to. So, this is n by p and then once we do the transpose p by n.

So, the product is just n by n or sorry, sorry, not well d. So, all of the inner products in here are canceling out the dimensions. So we just have something that's n byn. So if you're in a setting where um you know you want to say work with really high order polomials so that d is really big but n is relatively small then this is great. You start to run into trouble though if n is huge. Right? Right? If we think about the training data sets that are being used today to train generative models for instance or imageet right um they're highdimensional but also the number of training samples can be in the millions hundreds of millions billions etc.

And so now forming that kernel matrix which is n byn no longer sounds quite as appealing. So um a lot of work has gone into making um this more efficient coming up with approximations to that kernel matrix so that I don't have to look at every pair of training samples which can be a huge number of pairs. Um so you know there there are some kind of key trade-offs if we think about kernel methods versus neural networks. with neural networks.

We're going to talk about how we train those I think next week uh depending on how slowly I move. Um but um we just process one training sample at a time whereas here we have to look at every pair of training samples. So there's a real challenge that arises when we've got huge numbers of training samples. Um on the other hand, there's a lot of theory and interpretability associated with kernel methods that we don't have associated with neural networks.

Um and then finally there's an open question of whether one is fundamentally more powerful than the other and it's not entirely clear. So, one of the things that the research community has been investigating is are there problems that we can solve with neural networks that we cannot solve with kernel methods if we were to choose the right kernel function. Um, and it's hard to say. That was a very long-winded answer to a very simple question.

Are there any other questions? Yeah. space. Um, when we talk about the reproducing kernel Hbert space, that's something that I haven't really defined here and we're not going to go through in this class. But the kernel function is just what I defined here. It's, you know, corresponding to this inner product in this highdimensional feature space. And the common most common ones are the polomial and Gaussian kernels. Okay.

Um so with that um in the lecture notes that I'll post online um I've got some nice images showing the ways in which these methods can give us much better decision boundaries. Um, and I tried to draw one last week, but just as an example, right, let's just imagine we're in 2D. So, we've got our first feature coordinate direction and our second one. And imagine that our samples look something like this. Okay, so this is a case where trying to separate the pluses from the minuses with a straight line would be very hard.

But you can imagine that some kind of polomial decision boundary could work very well and using kernel methods with a polomial kernel and doing kernel regression is actually going to separate them quite nicely. Okay. So, and this is very simple to implement. So, now what we're going to do is we are going to go beyond kernel ridge regression and we're going to consider or we're going to move towards support vector machines.

So to get at that, the first thing that I want to do is now that you know we're 2/ird of the way through the quarter and have talked about le squares all that time is I'm going to say what's wrong with lease squares and the issue is this. So let's consider um binary classification. So our labels y are all either minus1 or + 1's. And now if we think about our squared error loss y - xw or equivalently y minus vw, we're just going to treat them interchangeably at this point.

This is going to be the sum from i = 1 to n y i - x i transpose w^ squared. But now what I can do is I can rewrite this somewhat differently in the setting where um my y's are only + 1's or minus 1's because y squared or y i^2 is always going to be one. Right? So this is the same as i = 1 to n of y i um squared. Well, I'm going to have the y. Yeah, I have yi^ 2 * yi - xirpose w^ squared, which is the same as now I'm just going to pull the yi into this square.

And so what I'm going to have is yi * yi minus xirpose w and multiplying through I'm going to get 1us y i * xirpose w^ squared. Okay, so I just have a new expression for squared or loss here. That is equivalent to what we've been doing all along in this case where all the labels are plus or minus one like we have in this binary classification. But now we can think about what happens in a setting like this. So I'm going to have my first feature direction and my second feature direction.

Maybe I'm even doing nice linear classification and I'm doing a great job separating my data. So here's all my negative samples and here are all my plus samples. But now imagine I've got one plus sample way out here. So it's very far from this decision boundary. So what's happening in that for that sample is this quantity is going to be large. It's got the right sign because I'm correctly classifying it, but it's far from one.

And so when I take the difference between this quantity and one and square it, it's contributing to my loss. So I've got a sample here which is correctly classified but is adding to my loss. It's very counterintuitive. So let's walk through an example where this can actually create a bad classifier if we just try to minimize squared error. Okay. So in this example we are going to say that XI is equal to the height. Um and so it is uh just a scaler and yi is equal to + one if the person plays basketball and -1 otherwise and then imagine that we get four training samples.

So I'm going to have in this example I think this is inches of height. So the 70in person does not play basketball. 71in person does not. the 73 inch person does and the 82 inch person does. And then what I'm going to do is I'm just going to subtract off the mean height. I'm going to center my data. So when I center it, I'm going to get -4, -3, -1, and 8. So let's just plot this now. So here on my x- axis, I've got height and I've got samples at -4, -3, -1, and 8.

And if I think about how these are labeled, I've got my negative samples, and then I've got my positive samples. So just by inspection, it's pretty clear that there exists a classifier here that will perfectly classify this data. Right? If I were to just threshold right at -2, I am perfectly classifying this data, right? But if we were to take this training data and do le squares, we actually get something different.

So in particular, we've got our formula for lease squares. rate hat le squares is remember xrpose x inverse xrpose y and if we plug in our training data for this example what we get is 0.15. So what that tells us is that we should predict Y hat our predicted label should be + one if the observed new test height or distance from the mean is greater than.15 and -1 otherwise. So in blue here we had this sort of ideal classification or decision boundary said if the average height is above -2 or is I don't know if the person's height is -2 from the mean or taller then we should predict positive and that works perfectly on our training data but the least squares classifier is here or the decision boundary.

It's saying we should make a prediction based on whether someone is sorry 0.15 in above the average height. So by doing le squares, we're trying to make sure that our samples are not too far from the decision boundary, even ones that are correctly classified. And so we end up pushing that decision boundary further to the right in this case, than it really needs to be to perfectly classify all of our points. So this is just a simple toy example illustrating how le squares can give you bad classifiers even in easy settings where a perfect classifier exists.

And so what we need then is an alternative to these squares. Any questions about this example? >> Yeah. say >> um actually it you know it's possible that if we did have more data then we would because we're looking at the sum of squared errors. So if we had more data then it is possible that the le squares decision boundary would move around for sure. >> So what would you say is a problem with data collection for having outliers?

Well, because uh you're right. If we had more data, then we would maybe learn a better decision boundary for sure. But at the same time, this is just highlighting a vulnerability of lease squares. And when we're in one dimension, then you know, it's easy to say, yeah, we can just collect more data. But in higher dimensions, the amount of data that you need scales um in general exponentially with the number of dimensions.

So if I were to um yeah it just becomes infeasible and le squares can behave in very unusual ways and ways that are not consistent with our intuition about how things should work. Okay. Yeah. What do I mean by least squares preventing a sample? >> Yeah, like why? So if we go back to over here when we looked at this expression for the squared error then um let's just think about this term here for the sample where someone is 8 in taller than the mean height.

So in that case xiranspose w that's a large positive number and yi is a positive one. Okay. So we've got a large positive number here which generally is good because this this means that we have classified that sample correctly. But now we're taking that and subtracting it from one. And so this quantity squared is going to be very big even though we've correctly s um classified the point. So this outlier is pushing is trying to make sure that well I mean it's doing exactly what we said.

It's trying to minimize the sum of the squared errors. But maybe I I don't want to care about how far this point is from um the it's giving undue emphasis to the outliers and the toy example is is illustrating that. Let's talk more generally about loss functions and we're going to stay focused now on classification and in particular in general if our label yi is + one and we have that our feature vector xi transpose times whatever weight vector we end up choosing is greater than zero then what this means is um um the predict so remember that this is y hat so now y hat i and y i are going to have the same sign and when they have the same sign it means that we are putting this sample on the correct side of the decision boundary.

So predicted label is accurate and similarly if yi is -1 and xirpose w is less than zero then we're accurate. we've made an accurate prediction. Okay. So, what we care about in many settings is exactly this expression that showed up in our least squares expression what we want is that yi and yi hat that product we want that to be positive. That's an indicator of correct classification or equivalently we want yi * xirpose w to be positive.

And so what loss functions are doing is they are ideally going to tell us something about whether we have made an accurate prediction. And so they are going to depend on this product yi * xirpose w. And so I'm actually going to come over here because we want to put everything on one board together. What I'm going to do is I'm going to make a plot, a better plot. And my horizontal axis is going to be yi xirpose w this product that we were just talking about.

And the vertical axis is going to be my loss associated with whatever weight vector I choose. So we're just looking at accuracy or loss for a single training sample at this point. So what I said on the previous board is that we know that the classification is accurate when this thing is positive. So you might say all right then if this thing is positive I don't want to incur any loss. I want to have zero loss because I've correctly classified that point.

And if this product is negative then it means I've made a bad classification. So I'm going to have a loss of one. So this is one loss function and we're going to call this the 01 loss or sometimes people will call it the ideal loss. And this is just equal to one if this product yi x I transpose w is negative and zero otherwise. Okay. So this is the thing that we actually care about. This is just essentially if we sum this across all of our training samples, this will tell us how many times we incorrectly classify points.

And this is what we would like to actually minimize. The problem is that this is not differentiable. We can't do something like take the derivative and set it equal to zero like we did with least squares. We also cannot use numerical optimization routines to find the right w. So this presents practical challenges even though it's ideally like what we care about. So the other thing that we've considered here is quadratic or squared error loss.

And if you recall, we were looking at 1us yi xirpose w^ squared. And so we can now plot this on this plot here. So let's have this point here be one. And so our quadratic loss is going to look like this. So on this side it's great because well we get a little bit of extra loss here. This is a region where we're making a correct classification but we're getting a nonzero loss. But when we're really incorrect, we get a big loss.

That's great. No problem. But as we talked about earlier and in our little toy example, you can have a correct classification and that can still contribute a lot to your loss. So this is really problematic. Was there a question? preconceived ide >> um I'm I'm not quite sure if If I understand the question, I mean maybe if I'm being really uncharitable, you could be asking, "Hey, we've been talking for six weeks now about minimizing squared error loss.

Are you telling us that's all bullshit?" Excuse me. All right, BS. And the answer is no. And in fact, people use le squares all the time. Um but it can cause unexpected behaviors and for the most part when people are doing classification they do not use le squares they use it for regression primarily but when it comes to classification they use other loss functions for the reasons that I'm outlining now a lot of the ideas that showed up in these squares related to you know the shape of the loss function how do we minimize it how do we think about you subspaces and that kind of stuff.

All of it's relevant. So everything we learned in these squares is going to contribute to our understanding of what happens with other loss functions. This was not a waste of time. Um but in practice, the vast majority of the time people use neither of these two things. They will either use hinge loss, which is what we're going to talk about now, or logistic loss, which will come up later in the quarter. >> Yes. for the ideal loss function is greater than zero for for one if the product is so all right let's just make sure so what I'm trying to say here is that this is a case where the sign of my uh inner product has one sign or is one value and the label has a different sign.

So like in order for this to be less than zero, my predicted label and my true label have different signs. So it's a mclassification. So I want to have a loss. Yeah. Any other questions? Yeah. >> So I think we said a long time ago that we can't for classification we can't like when we're computing the loss when we're doing like y when we're doing y - x we apply the sign function to XW for classification because it's hard >> to do computationally. >> So once I've got a W, right?

So so all right, let me just come back over here. So the way we had set this up before is you would first learn a W and then once you have a W at test time or when you deploy it you compute X your new X transpose time W and then you would say your Y hat for instance would be equal to + one if this inner product is positive and -1 otherwise which is sort of well which is exactly the same as the sign of xrpose w. So once you've got a w then you can predict the label of a new sample using the sign function.

There's no problem there at all. The issue that we have is that it would be hard to say find the W. Let's say W hat ideal which is the argument W that minimizes the sum from I = 1 to N of the sign of XRPOSE W * or X I transpose W * YI or something like that. If I wanted to put the sign into my loss function and then optimize over um W's that are inside the sign function, that's when I have a problem. So I have no problem at test time whatsoever.

It's only when I'm trying to search over W's that this is a problem. Does that make sense? >> Yeah. I was asking why is it why? So this sign function is just going to map to zero or one. So I can't for instance take the derivative of this and set it equal to zero to find a minimizer. Um I can't we're going to talk next week about optimization methods like gradient descent. I can't do gradient descent. It just is very hard to work with.

So we don't have good methods. If you told me, oh it's either one w fun w vector or the other and I just have to check which one does better. No problem. But if I've got an infinite number of W's that I'm trying to search over, which is typically the setting that we're in, I don't have tools, computationally efficient tools for doing that search. Great. Okay. So then we can also consider hinge loss and the hinge loss is just going to compute for us 1us yi xirpose w plus and what that means is it's going to be um 1 - yi xirpose w.

If okay, I'm going to do it this way. If I've got some uh quantity a plus that's going to be a if a is positive and zero otherwise. So I'm just going to clip a if it's negative. So I'm going to keep this if it's positive and I'm going to clip it if it's negative. So if we plot that over here, then this quantity inside the parentheses is going to be clipped to zero whenever the thing in parentheses is negative or whenever this product of interest is greater than one.

So in our plot, whenever we're greater than one, we're mapping to zero here. And then on the other side of one, we're just increasing linearly with this product. And so it looks like this. So there are some samples where this product is going to be positive where we are getting a correct classification but we're incurring a little bit of loss with the hinge loss. And when we have an incorrect classification we're going to have even more hinge loss.

But for most of the correct classifications we are going to get zero loss. So much better than squared error loss. And this is something now where we can compute derivatives and we can find minimizers of the hinge loss in a way that we cannot for the um uh 01 ideal loss. Okay. So it kind of is designed to mimic the ideal loss but in a way that allows us to do computation. And so basically when we talk about support vector machines what we're talking about is minimizing hinge loss plus this twoorm regularizer often using kernels.

So we just put all these pieces together and we're going to have a support vector machine. Okay. So a little bit more carefully when we talk about the hinge loss we are going to have the loss associated with a weight vector W is going to be the sum from I = 1 to N of 1 - Y I X I transpose W positive parts. So whenever the thing in parenthesis is negative then we go ahead and we set it equal to uh zero. And we can also talk about the gradient of this loss.

And uh I'll say a bit more about that in a second. But I'm going to for this class write this as the following. So it's going to be equal to um an indicator of whether yi xirpose w is less than 1 time - yi x i. So let me unpack this a little bit. First of all, when we have this indicator function, if I write one and then in brackets below here, this just means one if a is true and zero otherwise. And this thing here technically is not a gradient, but it's called a subgradient.

Because as you might have guessed from the plot, it's not differentiable everywhere. It's not differentiable at one. It's differentiable everywhere else. So when we talk about doing gradient descent, often we will use this subgradient instead. Everything is fine. Um, and I'm not going to go into a whole lot of details about that, but I just wanted to be clear that I recognize that this is not a differentiable function, but we can still use ideas related to gradient descent, which we'll talk about next week, in order to try to minimize this loss.

Okay, so couple of things. First of all, as I just mentioned a support vector machine, with a support vector machine, we are going to minimize with respect to weight vectors W this hinge loss plus lambda * the weight vector 2 norm squared. So we're doing the same kind of regularization that we did with ridge regression, but instead of using squared error loss, we're now using hinge loss. Or we could do the kernel version where we minimize with respect to W the sum from I = 1 to N of 1 - Yi.

And now we've got V of X I transpose W positive part plus lambda W. And typically when people talk about support vector machines, they often are implying that they are using a kernel here. But this corresponds to a very simple kernel. So this is what a support vector machine is doing. It's pulling all these pieces of two regularization that we saw with ridge regression and hinge loss together. And I want to draw a picture now to illustrate what's happening.

So again, let's imagine that we've got two-dimensional features and we make a plot of some training samples here. similar to what we did before. So, I'm going to have Okay, so I've got some pluses and minuses and now I am going to draw a decision boundary that looks like this. Okay, so this corresponds to some weight vector W. So now if we think about what kind of losses we're getting. So this sample way up in the corner that was causing us problems with le squares, this is going to have zero hinge loss loss.

This point here is incorrectly classified with this decision boundary. So, it's going to have um let's just call it largeish hinge loss. And this part point here is correctly classified but very very close to the decision boundary. And so this is going to have small hinge loss. So if we go back to our picture of the loss functions over here, I had mentioned that there were some samples like in this region over here where we could be correctly classifying a point and still incur a little bit of hinge loss.

And that's what I'm illustrating in this diagram here. I've got a sample that is correctly classified but barely correctly classified. If it had been moved a little bit, it would be incorrectly classified. So that's going to also contribute to my hinge loss. So when I minimize the hinge loss, I'm trying to of course make sure that I correctly classify as many points as possible, but also I'm trying to make sure that my training samples are far away from the decision boundary because I could imagine drawing an alternative decision boundary that looks let's say like this where this is supposed to be correctly classified, right?

So the blue and the orange lines are both perfectly classifying or I'm sorry, they're classifying all points except one totally correctly. But we could argue that this orange one is much more susceptible to errors because a lot of the points are just barely on the correct side of the decision boundary. And so when we work with hinge loss, we're saying we really want to have a loss function that not only correctly classifies as many points as possible, but which also classifies them correctly by a large margin.

So we will talk more about that and how you actually compute a support vector machine next week. Have a great weekend. All right, welcome back everybody. So today we are going to start off um by continuing our discussion of the support vector machine. And so if you recall last time we talked about some of the challenges and shortcomings associated with lease squares and we proposed an alternative loss function for classification called the hinge loss where in particular the loss associated with a weight vector W would correspond to computing the sum over our n different training samples.

And we would look at one minus the training label yi and the predicted training label which we wrote as x i transpose times our weight vector. And instead of squaring this like we would with the squared error loss, we have this little um plus sign which says that whenever what's in the parentheses is positive, we just leave it alone. And whenever it's negative, we set it equal equal to zero. And then we said that what we wanted to do was to minimize a regularized version of this loss.

So maybe I'll just say this is the hinge loss. And then our um objective the thing that we are going to minimize is we're going to compute w hat is equal to the argument that minimizes this hinge loss plus a regularization term. So minimize sum i = 1 to n 1 minus. So we have some regularization parameter lambda times the sum of the squares of all of the weights. And we can also do a kernelized version where we would say that our weight vector W hat would be the arg min over W sum from i= 1 to n 1 - yi.

And now instead of working with our original feature vector x i, we would map it to a highdimensional feature space using some function v [clears throat] and do our regression or our s prediction in that space. Okay. Now when we before had talked about kernel ridge regression when we were using squared error, what we said is that there are many settings where this fe vector could be very highdimensional and we wanted to avoid it avoid computing it explicitly and we wanted instead to use a kernel function.

And what we did is we showed how to go from our objective function again with squared error instead of hinge loss to an expression that only used the kernel function and did not use sp. And for a support vector machine where we're using hinge loss, we can do something totally analogous which can be very helpful. And so in order to do that, we need to have a first step that is similar to what we did um with the kernel bridge regression.

So I'm going to call our estimate here W hat. I'm just going to put an SVM as a subscript here just to be really explicit that now we're working with a support vector machine. So over here this is SVM or SVM. So when we are minimizing the hinge loss plus the two norm squared of our weights this is a support vector machine. We'll talk more about where that language and where that name comes from in a little bit. Um and either of these are support vector machines.

In fact this top one is just a special case where the fee mapping is just an identity mapping. So um this support vector machine weight vector that we are going after can be written as a weighted sum of our features either in their original feature space or in the bottom case in our uh highdimensional feature space. So in particular recall that capital F would be our feature matrix in this highdimensional feature space and we can write this weight vector W hat SVM as vanspose time some vector alpha.

So in other words, our weight vector that we are going after the solution to the optimization on the first board is going to be a weighted sum of the rows of this fee matrix. Now our goal is to figure out what that weighted sum looks like just like we did with kernel ridge regression. But we're going to use this fact in order to find that optimal alpha vector. Right? it may only make sense to solve this by finding alpha if this is true.

And so what I want to do now is to show to you that this is in fact true. So, so this is my claim and to show this we are going to assume for the sake of contradiction that this W hat SVM m cannot be written that way. That actually it's going to be vanspose alpha plus some extra stuff that can't be written as a weighted sum of the rows of fe. And I'm just going to call that extra stuff wer. Okay. So let's assume that there's some stuff in this weight vector machine weight vector that can't be encapsulated using the weighted sum of the rows of fee.

And we're going to let WP represent all that extra stuff. What I'm going to do now is I'm going to show that WP has to be equal to zero. All right. So in particular, I want to be a little bit more specific. Um so what we're going to do we have to assume something about WP where WP is orthogonal to the rows of V um or um to the V of X guys. And that's just to I'm just formally stating what I said verbally up here. So the WP is everything that cannot be represented in terms of the rows of VE.

And so in order to say it cannot be represented by the rows of Ve, I'm assuming that it's orthogonal to the rows of FE. Okay. So now if we think about our objective function for the SPM, right? What we're trying to do when we try to find the weight vector is we're trying to minimize again sum over i = 1 to n 1 - y i vx transpose times my weight vector. But now what I'm going to do is I'm going to replace this weight vector with this form that we're interested in.

So instead of having W here, I'm going to have capital V transpose alpha plus W perp and then I have this little plus indicator for my um hinge loss then plus lambda and now I've got the two norm of vranspose alpha + w per squared. And so if I know that my support vector machine has this form, then finding the best weight vector is the same as finding the best alpha and finding the best WP. So now I'm minimizing over alpha and w like that.

Okay. Okay. And now what I'm going to do is I'm just going to unpack this a little bit to make it a little bit easier for us to work with. And in particular, I'm going to write this minimum over alpha and w per sum from i= 1 to n one minus. And off to the side, I just want to remind everyone that when we talk about v transpose alpha, what this means is I'm going to have the sum um so alpha is a length in vector. So I've got the sum from j = 1 to n of alpha j times v of xj.

So that's what we mean when we write capital fepose alpha. And so I am just going to plug that in right here. And so what I'm going to have is y i and then in my brackets here I'm going to have the sum from j = 1 to n of v of x i transpose v of xj and that gets multiplied by this weight alpha j and then I'm going to add to at WP. So I'm going to have V of X I transpose W perp. So I've just expanded this out using what the matrix V transpose alpha means.

Um and then I'm going to have plus lambda. And again, I'm going to have the sum from J = 1 to N of alpha J V of XJ plus WP. Now, now that I've expanded this out, I see something extremely helpful. So remember that we assumed that WP is orthogonal to the rows of capital V to all the FE of X I's. Now we can use that information. So what can I simplify using that information at this point? >> Yeah. >> Xpose W. >> Exactly right.

So another way of writing this orthogonality is that v of x i transpose w per has to be equal to zero. And so in this expression here this term has to be equal to zero. Okay. So now we've simplified this expression. Now the only place in this objective function that wp is showing up is here. Right. So what is the value of WP that's going to make this whole thing as small as possible? Yeah. >> All zeros. >> All zeros.

Right. So our objective is minimized when WP is equal to zero. Okay. So in the lecture notes that are posted online um we go through this in a few extra steps. So if it feels like it was a little bit fast to you the derived notes online um yeah break it down a little bit more. But what we can then see then is that if this is minimized when WP is equal to zero then all of a sudden the best WP is equal to zero and therefore the support vector machine weight vector can be written as a weighted sum of the rows of this V matrix.

So we've shown our claim and so now just like we did when we were looking at kernel ridge regression we are going to boil our optimization problem down to instead of directly estimating the weight vector w we're going to estimate this parameter or this um weights on the samples alpha. Okay, so I feel like I've been throwing the word Word's weight vector around a little bit more than is clear. So I just want to be clear that when we talk about W hat SVM or even What ridge or le squares, this is going to be a vector in our um feature space.

So either D-dimensional or P-dimensional depending on whether we have a kernel or not, but it's a a weight on our features. So at the beginning of the course, we talked about trying to predict whether a photo is of someone smiling or not. And so we have different facial features. And now we're saying, well, some of those facial features are going to be more important to that prediction than others. So we're waiting applying weights to different features.

But the other weight vector that we're working with now in kernel ridge regression and in the support vector machine, this weight vector is in Rn. So it's a weight on each of the different samples. And what we're saying here is that our predictor of a new label for a new training or for a new feature vector is going to be a weighted sum of the um labels of my training samples and we're trying to figure out what those weights should be.

And so we're going to derive an expression for that analogous to how we derived an expression for it in the context of kernel bridge regression. So again, two different weight vectors weighing different things. The W's are weighing features. The alphas are weighing samples. Okay. So now what we're going to do is instead of finding an expression for W hat SVM, we're going to say let's find an expression for alpha for the weights on samples.

Okay. So unfortunately this is um not something that we can do in closed form the way we could with kernel ridge regression. And in particular we're going to say that alpha hat is going to correspond to solving this optimization problem that we have on the previous board. So it is the argument alpha that minimizes the sum from i = 1 to n of 1 - y i sum j = 1 to n alpha j f x i transpose v xj J plus plus the two norm sum from I = 1 to N of alpha J V of XJ.

And now I'm going to do a little bit more work on the regularizer here. And we'll see why in a second. >> [clears throat] >> So the first part measuring the data fit is going to be the same. [clears throat] Oops, I had a lambda out front. And so now what I want to do is I want to note that within here I'm computing a bunch of different inner products. And so I can rewrite this two norm squared as the sum from i= 1 to n sum j = 1 to n alpha i alpha j * v of x i transpose v of xj.

And the reason that I've written it out this way is because now we can see that this objective function only really depends on inner products of fees of x's and never explicitly just the fees. So just like we did with kernel ridge regression, we can say this inner product here is the kernel between x i and xj. And here we've got the kernel function between x i and xj. And so we do just like we could with kernel ridge regression approach finding the alphas using only the kernels or the underlying kernel matrix instead of ever explicitly computing f of any feature vector x.

All right. Now unfortunately when we look at uh well maybe I'll just write this out more explicitly. So our final alpha corresponds to the argument that minimizes over all alpha sum i = 1 to n 1 - y i sum over j alpha j k x i xj plus lambda sum over i sum over J alpha I alpha J kernel X I XJ Now when we were working with kernel ridge regression where we use squared error here we were able to derive a nice closed form expression for the alphas here unfortunately we cannot the way that we find the alphas is using numerical optimization schemes and in fact in the second half of today we're going to start talking about different schemes like gradient descent.

You can use gradient descent on this, but it's not nearly as efficient as other more sophisticated optimization methods that are beyond the scope of this class. But there are existing software packages for solving this optimization problem. But this is what's happening under the hood when we use support vector machines. we are solving this optimization problem in order to get this alpha hat and specifically the alpha hat for SVMs.

And then just like we did with kernel ridge regression once we've got the alphas we can make predictions for new samples um in order to um get good classification performance. Okay. So let's talk a little bit more or sorry are there any questions before Yeah. >> XJ >> um I just was trying to talk and write at the same time and wasn't being uh there was no reason to switch it. So I've got XI first now every time. That said, I can't off the top of my head think of a single kernel function where it's not symmetric, where the order of the x i and the xj matters.

Yeah. Okay. Okay, so we've talked a lot about how we compute the support vector machine, but I think I also want to talk about um why it's called a support vector machine and what's actually happening here. So in particular typically when we solve this optimization the alpha hat SVM that we der that we end up with is sparse and by that I mean most of the alpha js are equal to zero and there's only a small number that are non zero and so if we recall All that our weight vector W hat SVM is equal to the sum J = 1 to N alpha J V of XJ.

If this is the form of our weight vector and most of the alpha js are equal to zero then what it means is that this w hat svm is equal to a weighted sum of a small number of these highdimensional feature vectors. Okay, so we've said all along it's a weighted sum of all n of them, but most of those weights are zero. There's only a small number that are non zero. And so what are they? So let's make a picture where we're doing classification in two dimensions.

So I've got feature vector one and feature I'm sorry, not feature vector, feature one and feature two. And let me put in some samples. So, I've got some negative samples here in the lower left and some positive samples up here. And now I try to derive um a decision boundary by computing this alpha hat SVM and the corresponding W hat SVM. And in this space, what I would end up with is a decision boundary that looks like this.

It's separating my positive from my negative examples. And just like before, on one side, W hat SVM transpose X, that's going to be greater than zero. And so we would predict for any point in here that the corresponding label is positive and then on the other side of the line everything's negative. But in addition to this decision boundary, we can think about the following. We can think about drawing a kind of tube around the decision boundary and trying to make it as wide as possible until we start touching training samples.

So in this example, oops. Okay, it should be the same width everywhere. I've got this tube here like I've drawn with the dashed lines. within that tube. There's lots of different decision boundaries I could have drawn, right? I could like just take this boundary here and I could angle it a little bit and I would still have perfect classification on all of my training samples. So there's many different weight vectors that would give me zero classification error.

I correctly label all the samples, but the SVM is choosing the one weight vector that makes this tube as big as possible. So to contrast it in orange here, right? Imagine that I considered a different decision boundary that looks like this. That's not enough color contrast. And unfortunately the colors are even less visible on um the videos. Okay. So in green here I've got another decision candidate decision boundary that I among all the ones that I'm searching over.

So this green decision boundary is perfectly classifying my positive and negative samples. But if I think about trying to draw this tube around it, that tube has to be a lot narrower. It's a much skinnier tube. And so the idea behind the SPM is that if I consider all the different classifiers that have equally good performance on my training samples, I want to choose the one that has the most padding or the biggest tube around it.

And this is to basically try to maximally separate the data. And the idea is maybe pretty intuitive because in this case where I've got the green skinny tube, this sample right here, if it had moved just a little bit, it might have been pushed over the boundary. Whereas with the yellow decision boundary, the one corresponding to the SVM, I would have to move it a lot more before it gets mclassified. And so this SVM classifier that has the biggest possible tube is going to be the one where in order to start misclassifying points I would have to perturb them the most.

And so this is giving me um hopefully better generalization performance. Okay. So the technical term for this is not tube but rather margin. And so in here, I'm going to call this region here the margin. And so what we're doing with the SPM is we are trying to maximize that margin. In addition, I said earlier that this alpha hat SVM is sparse. So remember, alpha hat is giving us a weight on each one of the training samples.

So in this example with the yellow SPM classifier, which are the samples that have nonzero weight, those are the samples that are right there on the margin. These three here. So these are the support vectors. These are the feature vectors that tell me where that margin is located or where that decision boundary is and those are the ones that are going to get nonzero weights in this alpha vector. Everything else is going to get zero weight.

So for this point here for instance the alpha j is equal to zero and for this point here the alpha j is not equal to zero. And so when we talk about support vector machines mathematically, it's exactly like I described before. We're using hinge loss. We're using squared norm regularization. We solve the objective function that I described earlier. But what's happening is that the solution to that optimization problem is the decision boundary that maximizes this margin and the support vectors are the training feature vectors that have the nonzero alpha weights and those are the ones that are defining the boundaries of this margin.

So in the lecture notes posted online there are some illustrations that are more complex than this one here showing much larger numbers of features and also instead of showing linear decision boundaries they're showing curved decision boundaries that we would get if we used a kernel. And so you can take a look at that and hopefully build up some additional intuition about this notion of a margin and how the classifiers defer dep when you um vary different parameters or ask or you know if you vary what kernel you're using or if you vary uh this parameter lambda and it gives you a lot more yeah understanding.

Are there any questions? >> So for the like for the margin they are derived by shifting the decision boundary until they simple. >> Okay, the question is are we basically shifting the decision boundary? So I would I would frame it like this. In our first board here, we said that the support vector machine corresponds to whatever vector W minimizes this objective. So we can think about searching over all possible weight vectors, which is equivalent to searching over all possible decision boundaries.

And I'm saying through that search during that search we might consider this green decision boundary but it is not going to minimize the objective function that I described. The one that minimizes the objective function. The one that I've drawn here in yellow is the one that maximizes this margin. So um >> I mean like the margin is like the margin is like just shifting the decision boundary. >> The margin is not shifting the decision boundary for any candidate decision boundary.

We could think about how big that margin is and we are choosing the decision boundary that maximizes that margin. But like on the graph the margins are all parallel to the decision. Can the margins curve or >> um okay can the margins be curved? So in this case so here um the in this drawing my f function f ofx is simply equal to x. I'm x I'm using a linear kernel. So I have linear decision boundaries and this margin that I'm drawing like you said is parallel to the um uh decision boundary and straight lines.

If I were to use a different fee corresponding to a kernel function then my decision boundary might be curved and my margin would be curved in the original feature space. But if I were to plot things in my highdimensional feature space in this V space then I would still have linear decision boundaries there and straight line parallel margins there. >> Yes. >> The support vectors do they have hinge loss of zero? >> Do the support vectors have hinge loss of zero?

Yes, that's right. And in fact the vectors though that are correctly classified and are not right on the margin they also would have hinge loss of zero. So in this case my um data is separable. I can draw a decision boundary that perfectly separates the positive and the negative examples. And so I can achieve and they're separated by by some margin and so I can achieve zero hinge loss. So this notion of a margin is a little bit more complex when we have non-separable data but I'm not going to go into that uh today but that is something that's discussed in um our our course textbooks. >> Yes.

So basically I want to ask about like uh for this example it's very simple but I mean like in real life data like I don't think it is like very possible that you can have like multiple data points on the margin like if you are finding the one which is closest to the decision boundary maybe there will be only one so in real life is it most likely that all positive will only be one data points on the as the support score support vector and also like does the margin have to be uh symmetry uh like on the this boundary or they can be not quite symmetry on the positive side and negative side.

Okay, so the first part of that question was this is a very simple example. Wouldn't it be the case in general that I might only have one or two samples on this line on the margin? Um and the answer is no because I'm only drawing this in two dimensions but in general we're in much higher dimensions and so you do have more decision bound or I'm sorry more feature vectors that have nonzero weight and that basically are support vectors.

Um, so it only you only have a small number in this case and it looks a little contrived because we're only drawing this in two dimensions, but in higher dimensions you would have many more support vectors because you need more points to define uh a linear separator in higher dimensions. The second question was, is this margin always symmetric or could it be that it's hitting a couple of support vectors on one side and not or one on one side and zero on the other side?

And the answer is no. That's not possible because if I had a decision boundary, let's just say that was like parallel to my yellow decision boundary but closer to the blue points than the red points. Like the mar when I measure the margin, I'm looking both above and below the decision boundary. And so by pushing the decision boundary closer to the blue points, I'm making that margin smaller. And so by putting it sort of equidistant from the red and the blue lines then I'm maximizing the size of that margin.

So I'm always having points on you know both sides of the decision boundary if you will. >> Can I please clarify? I mean like currently like when we are finding a margin is that we are somehow like to minimize uh the distance from each data points to the decision boundary >> maximize. Oh uh but we are act like the margin the length itself is actually depend on the data point that is closest to the >> okay maybe I misheard you but you I thought what you said is that what we're trying to do is minimize the distance between our training feature vectors in the decision boundary and I'm saying no when they're correctly classified we want them to be far from the decision boundary we don't want to draw our decision boundary say where this dashed line is so that some of our samples are right on the decision boundary.

We want because well imagine for instance that these are um that these feature vectors correspond to you know pixels in an image. You don't want it to be where if you just have a little bit of graininess in your photograph all of a sudden you change your prediction of whether someone's smiling or not. You want your predictions to be robust to small perturbations. And so by trying to make sure that your decision boundary not only correctly classifies as many samples as possible but also is as far as possible from any of the training samples, you're providing yourself with that robustness to small perturbations. >> But like for example, if there's a plus like if there's a data point uh within the current margin. >> Yeah. >> The margin that will like will the margin be shorter just because of this one data point? >> Yeah.

Yeah. If my data were if my samples were closer together, then I would have a smaller margin. >> But it still seems like that just one data point could affect our prediction. >> Absolutely. >> And the rest are not affecting. >> That's right. If you and that's maybe illustrated with this example, right? These samples out here are having very little effect on where the decision boundary is, right? because I don't want to like change the angle of my decision boundary based on a point that's way out here nowhere close to the decision boundary because no matter how I rotate this decision boundary here this point is going to remain corre correctly classified.

So if I'm really just trying to make sure that I'm correctly classifying as many points as possible and maximizing the margin or making sure that my prediction is robust to small perturbations, then I should not be paying attention to points way out here because I can perturb them quite a bit and their prediction is not going to the prediction associated with them will not change. Like that was the one of the failings of least squares is that you could have points that are way out here that were having that were correctly classified and we were like changing where the decision boundary was located based on them in a way that could cause mclassifications close to the decision boundary.

So that that was like a big part of last lecture like that was actually something we want to avoid. And so one of the benefits of the support vector machine is that we no longer have that feature. These points that are nowhere close to the decision boundary are not really affecting, you know, exactly what the angle or rotation of that boundary is. We're really just looking at stuff that is closest to the decision boundary.