Lecture 12 Fall 2025: Pseudoinverse and Kernel Ridge Regression transcript

All right, welcome back everybody. So last time we started talking about ridge regression and with ridge regression we had an estimator that looked as follows. So we said that the ridge regression set of weights that we would use would correspond to minimizing over all possible weight vectors the sum of the squared error between our predictions and our observed training labels plus some parameter lambda times the two norm or the sum of the squared weights of W and we also said that we could write the solution to this optimization problem as being xrpose x + lambda * identity inverse xtranspose * y.

So what we didn't talk about is where this quantity lambda comes into play. So we talked about its role. We talked about its impact on the singular values of X and how it affected what this matrix inverse looked like, but we didn't really specify how you would choose it. And so that's something that I want to touch on um right now. So in particular if we take all of our available I'm just going to call it training data to start but all of our data then generally what we would do is we would split it into three pieces.

So in particular I would take the first I don't know maybe 70% or so and I would call this my training data and then I would take another 15% or so and this would be validation data and then my final 15% or so would maybe be my test data. So all of this is coming from my original collection of data that I'm using to do my machine learning with. So what's happening here is with the training data I am um going to fit each possible model to the data to the training data.

Oh, you know what? This is a little bit hard to read. Let me just put it up here. So when I'm using the training data, I want to fit candidate models with the validation data. I'm trying to figure out which model is best. And then finally with my test data, I'm trying to estimate how well whatever model I think is best will work on new data. So in the context of ridge regression for instance when I say oh I'm using the training data to fit candidate models and the validation data to say which model is best I'm really thinking here about different models corresponding to different values of lambda.

So what I'm doing with the validation data is I'm saying I'm going to use it to select a good value of lambda in the context of ridge regression. And with the training data what I'm doing is I am going to fit my w and I'll just put lambda in parenthesis here to indicate that I'm going for different values of lambda. I'm going to get different values of this ridge regression weight vector. So for each value of lambda, I can use my training data to find a weight vector.

And then with the validation data, I can use it to decide which value of lambda I think is the best. So let's map that out a little bit more precisely. Okay, so we're going to have our training set, which is going to be a bunch of Xi, Yi pairs for i= 1 to let's say M. And then for my validation set, I'm going to also have x i yi pairs, but now it's for i equals, let's just say m + 1 all the way to um n. [snorts] So now what I would do is the following.

I'm going to have a whole collection of different lambdas. I could call them lambda 1, lambda 2, all the way to lambda, I don't know, L. Just got a discrete set of possible lambdas that I want to consider. And so for each one of them I am going to use my M training samples to find this W hat for that particular lambda. So I'm going to get a whole bunch of W hat Rs corresponding to different lambdas and each of them is only going to be computed using my M different training samples.

Then I'm going to measure the loss um on my n minus m validation samples. So specifically, I might say that the loss on my validation samples for a given lambda could equal to the sum from i is equal to m + 1 all the way to n of y i minus x i transpose w lambda squared. So I'm just looking at the sum of squared errors on my validation data set and when I am using ridge parameter lambda then I'm computing the loss associated with that parameter lambda and then finally I would choose the lambda with the smallest l sublambda.

Now, in practice, when I'm doing this, I don't always know what the right range of lambdas is. If I see that I'm getting the smallest loss with the biggest lambda or the smallest lambda, I always feel a little nervous. I think, oh, well, maybe if I had gone even smaller or even bigger, I could have done even better with my loss. So I try to make sure that my grid is such or the selection of lambdas that I'm considering is wide enough so that I'm actually choosing something somewhere in the middle and not on the edge just to make sure that I didn't narrow my search to artificially.

And then in the context of the training and validation and test split finally when I'm done when I have chosen my lambda so let's just call that lambda lambda star the one that gives us the smallest loss on our validation set once I have that then I can estimate my um loss on the final test data for this W hat R for lambda star. So I'm not touching my testing data until the very end when I've selected all the parameters in this case lambda and weights um for my method.

So you could even imagine you know somebody holding this back. You don't get to look at it at all until you've done everything you can to figure out what the best possible method is and then you just test and see how well it's working. This is how for instance a kegle competition would run. If you are looking at that test data before this stage, say using it to rethink what the best possible lambda is, then you run the risk that this test error will be artificially low because you've used it to make decisions.

So that when you actually deploy your method in the wild, you're getting higher errors than you anticipated. So it's very important to keep this separate until the very very end. Are there any questions? Yeah. >> Wait, if the validation is going up to samples, where do you find test? >> Oh, okay. Let me just say NV for validation here. And then my test data would be x i y i for i equ= n validation + one all the way to n. >> Yeah.

Any other questions? >> Yeah. >> Is that just like squares? >> [snorts] >> Yeah, this is just the squared error. And I'm using squared error in this description here because that's also the loss that we've been using for ridge regression. Um, but in general, you can use a variety of different things here. For instance, if we were doing classification, we said that we might train a classifier, find a set of weights by minimizing squared errors.

But of course, what we actually care about is how many mistakes we make. We didn't use that number of mistakes loss because it's not clear how to optimize it. But when we're only looking at that loss on a discrete set of parameters, we can do it. And so in some cases, people will have a different measure of loss that they consider during validation than they do during training because we're really typically in validation only considering a discrete set of options.

So we don't have to worry about whether it's differentiable or convex or anything like that. So you've got a little bit of flexibility here. This is a design choice. >> I'm just wondering why it would be like the smallest value when your figures are like progression function was it at least minimizing the squares but also return right. So when we did the ridge regression we were saying if somebody gives you a lambda then what's the right weight vector so what I've been doing here is I've been writing lambda in there.

So for every different lambda you give me I would give you a different weight vector coming out of bridge regression. And so now what we're talking about is saying how do I choose which lambda I want to use and that's what this process on the middle board is about. I'm just wondering if the left side of the ar is the same as the function. >> Oh I see. So you're saying here when we are doing training we are minimizing this this overall function and semantics or nomenclature varies from paper to paper.

Um some people would call this a regularized loss because I have a loss plus a regularizer. So they would distinguish they would call this squared error the loss and this something different. Other people would just call this whole combined function that we're minimizing the loss. So they would use loss in a way that encapsulates regularization just varies from paper to paper and person to person. But you are right that during training I'm talking about minimizing this sum whereas in what I mapped out on the middle board here we are only looking at the sum of the squared errors.

So I'm not considering the regularization here. Yeah. Any other questions? Okay. So then with that I want to switch gears and talk about a setting where we don't necessarily have a regularization parameter but we still have to deal with the fact that le squares will not work. So I want to talk in particular about an alternative to ridge regression that specifically um is of interest when um some of our singular values are equal to zero.

So when some of the singular values are equal to zero, we said one of the ramifications of that is that there are many different weight vectors that we could find that perfectly um predict our labels. So the question is if I've got many different weight vectors and they all give me perfect predictions of the labels or maybe even not perfect but just equally good then I have no way of distinguishing among them. Right?

So how do I choose which of these different weight vectors I want to use? Right? So we said with le squares we're just going to totally sidestep that but now we're going to look at an alternative approach. And so specifically we are going to define the pseudo inverse of a matrix. Um and I'm going to start by defining it for diagonal matrices. sigma um and we're going to denote that as sigma with a plus sign superscript.

So this is not transpose. This is pseudo inverse. And if we look at the one of the diagonal entries of that pseudo inverse, sorry, I'm going to do it like this. I compute the pseudo inverse and then I look at the diagonal entry. Then it is going to be 1 over the original singular value. if that singular value is greater than zero. But if the singular value is just equal to zero, then instead of trying to divide by zero, I'm just going to say in this pseudo inverse matrix that the corresponding diagonal entry will just be exactly zero.

So in other words, it corresponds to It's taking the transpose of sigma and inverting the non zero diagonal entries. which I think I didn't fully specify. So, let me give you an example that's a little bit more concrete here. So let's look at the special case where P the number of features that I'm trying to learn from or use as predictors is greater than N um the number of training samples and X has n linearly independent rows.

So before we were talking about settings where the number of samples was greater than the number of features and X had n or had p linearly independent columns and in that case we could do these squares. So now we're going to consider the setting where we actually have lots of features and all of the different training samples all of the different yeah all the different feature vectors for the different training samples are linearly independent.

So pictorially our matrix X here is now short and fat. It is N by P. And if we think about its singular value decomposition, u is N by N and sigma is N by P and V is going to be P by P. And so now if we were to think about the um pseudo inverse of sigma then first of all let's think about what sigma looks like. It's going to have entries sigma 1 sigma 2 all the way down to sigma n and then the remaining n minus p columns will all be equal to zero.

And so now if we were to compute the pseudo inverse of that then what I will have is something that's p by n. So I'm going to have 1 over sigma 1 over sigma 2 all the way to 1 over sigma n and then all zeros. So this is my pseudo inverse. And so now what I can do is I can use this pseudo inverse to form a predictor. So specifically I'm going to say that my pseudo inverse predictor W hat is going to correspond to taking this V matrix times sigma pseudo inverse uranspose those times y.

So I want to say a couple of things here. So first of all um I want to emphasize a point that is going to be helpful to us later in today's class which is that this pseudo inverse here is equivalent to writing sigma transpose times sigma sigma transpose inverse. So I've got an explicit formula for this pseudo inverse. In addition, I can show that what I'm writing here, this pseudo inverse predictor, I can write explicitly in terms of x.

This would be xrpose * xxrpose inverse * y. So we can define the pseudo inverse of a general matrix x using the pseudo inverse of its singular value matrix as I've described. I also want to compare this with le squares. So with le squares, we had a weight vector that we derived to be v times um sigma um um transpose sigma inverse sigma transpose uranspose y. And we can also compare with ridge where we had widge was equal to v times sigpose sigma plus lambda identity inverse sigranspose uranspose time y.

So now we've got three different expressions for three different weight vectors that we can use to fit our training data. So one thing I want to emphasize when we look at these is that they all have a very similar form. All of them start with this v matrix. All of them end with uranspose y. And the thing that's really distinguishing them in the middle is what we're doing with the singular value matrices. So with the pseudo inverse, we are only inverting the nonzero singular values.

With le squares, we end up inverting all of the singular values, which is why we can't use it everywhere because sometimes singular values are equal to zero. And when we try to invert them, we get major problems. As we talked about last class and with rich regression, we are adding a little bit to all of the singular values that we invert. So when they are zero, we don't have um huge blowups. We don't have we're not dividing by zero anymore.

And so these are three different ways of handling the singular values of X in order to get good predictions of weight vectors that can then help us make good predictions of labels on new test data. Are there any questions so far? Yeah. uh just to make sure that that equivalence is true the the sigma transpose sigma sigma transpose inverse that's true of every in every case not just the special case so um I think this particular equation here is for this special case where I have p greater than n and n linearly independent rows so when I've got n linearly independent then this matrix sigma sigma transpose is invertible.

But in general it might not be. And so um I think that the form of that pseudo inverse can look different depending on the setting. And personally I find it most intuitive in general to think about it like this to think about inverting the nonzero singular values and taking the transpose. Um, and I can do that for a matrix of any or for for a singular value matrix regardless of the dimension, how many rows it has versus how many columns and whether or not uh and regardless of how many singular values are zero versus non zero.

So this I can always do. >> Yeah. When can we use this person like predtor like can we use it like for [clears throat] like is that like just a new method or can we use it for ridge regression? >> So the pseudo inverse predictor is not ridge regression because the ridge regression explicitly has this lambda parameter in here that's not equal to zero. So it is doing something different. At the same time, it is conceptually very similar in the sense that um in both the pseudo inverse setting and the ridge regression setting, we potentially have more than one weight vector that could be equally good fits to our training data.

And we are through these choices deciding which weight vectors we are going to give preference to. Um, so I'm going to talk a little bit more about the pseudo inverse in a second, but with the ridge regression, we are explicitly saying that we want this balance between squared error and the sum of the weights in the weight vector. So that is conceptually very similar to what the pseudo inverse is doing, but they are not the same thing. >> Yes. pseudo inverse. >> Oh, for the pseudo inverse here the subscript is I I just indicating it's the E diagonal entry.

Yeah. >> Yes. >> So we can use the pseudo inverse um predictor in general settings. But it won't always have this particular form because xx xranspose is not always invertible. But we can always take the svd of x compute the pseudo inverse of sigma and have this predictor. So this is very so yeah just to be clear this here is very general and this is specific to when xx transpose is invertible or x has n linearly independent rows.

Does that make sense? Yeah. Great question. Yes. >> Perfect. >> Right. We are going to talk about that right now. So what exactly is it doing? So the claim is the following. So let's consider the case when X has n linearly independent rows and in that setting we have that the choice this of this pseudo inverse predictor W hat I'm just going to say W hat um equaling U sigma pseudo inverse I'm sorry V sigma pseudo inverse uranspose y um has the smallest norm.

So the two nororm of w hat is going to be as small the smallest possible norm of any w satisfying our training labels y equaling x * w. So in this setting where I can fit my data, my training data perfectly, where there are many different weight vectors that can perfectly predict my training labels of all of those weight vectors that give me perfect predictions, the pseudo inverse is going to give me the one that has the smallest sum of squared weights.

Okay, so let's actually see how to show that. If we just consider any weight vector W, I can write that the norm of that W that I choose is equal to the norm of W minus W hat plus W hat like that. Okay. Now I'm going to split this up and I'm going to say this is equal to W - W hat 2 norm^ 2 + 2 W - W hat transpose W plus the two norm of W So once I've written the norm of any vector w this way in terms of the norm of my pseudo inverse then I can start to think about my machine learning context.

So let's assume that this W is giving us a perfect fit to our training labels and so it's just as good as W hat. Okay, so we are interested now in knowing well what's special about W hat compared to W. Both of them are equally good predictors of the training labels. And my argument or my claim was that W hat is going to have a smaller norm than W that it's got the smallest possible norm. So this assumption means that if I were to look at the product of X wus w hat, then that has to be equal to zero, right?

Because XW and XW hat, they have the same value. So if I subtract them from each other, then I just get zero. And so if I think about this middle term here inside my expression above [snorts] then what I get is that w - w hat transpose w I can write that as w - w hat transpose. And now I'm going to plug in my expression for w in this context we're going to use the version written in terms of x is xrpose xxtranspose inverse time y.

But now what I have here, if I just group this ww hatpose with the xrpose, I know that that has to be equal to zero because that's what I have up above. So in other words this is equal to x w - what transpose time xxrpose inverse y and this whole thing here is zero. And so this whole thing is zero which tells us that that whole thing is zero. So if we put that together then what we have up here is that the two norm of W is going to be equal to the norm of W - W hat plus the norm of W hat.

So when I look at this, I know that all norms they correspond to like links of vectors, they have to be non- negative. So if w and w hat are different, if they're not equal to one another, then this norm is greater than zero. And so this tells us that the norm of W has to be greater than the norm of W hat. So just some very simple algebra is showing us that when we compute this pseudo inverse predictor then any other predictor that we might find W which also gives us a perfect prediction of the training labels would have to have a bigger norm or in other words the pseudo inverse predictor is going to have the smallest norm among all predictors that perfectly predict my data.

Yes. >> How is that initial assumption different than just saying W= W >> Oh, right here. >> Yeah. >> So, that's a great question. Um, so I actually was going to work through a simple little example right now that I think will get at that. So in this example, x is going to be 1 0 and then 0.1 and then 0 1 0. So I've got two rows and those rows are linearly independent just like in our setting. And our y vector of labels is going to be one and zero.

So now there are actually multiple different W's that could fit this, right? So possible W's, we could have 1 0 0. So if I were to assign weight one to the first feature and zero to the other features, then I will get a perfect predictor of Y. But there's other W's that I could also consider. For instance, I could have zero zero 10. So I could say instead of giving weight one to that first feature, I could give weight 10 to the last feature.

That's going to also give me a perfect prediction of the labels. Or I could do any combination of those. I could do 1,000, 0, and 10,000. Uh I think I think999, right? And so I have multiple different ways that I can combine these two different features and get exact predictions of why. And so for all of these W's, they all have the same XW and that XW is equal to Y. So assuming that the XW's are equal is not the same as assuming that the W's are equal.

And so that's why we have to make that distinction in the proof. And what we're saying here is among all these different candidates, this weight vector here has the minimum norm. So it's a choice, right? We're saying that there's infinitely many possible W's that could perfectly predict our training data. And we as machine learning designers have to make a decision about which of the infinitely many W's we prefer. And minimum norm is one particular choice that you can make.

Um, but you know, depending on your context, you might say it's a little bit silly that I've got two features that are both really predictive of why and I'm artificially choosing one versus the other just because the raw values or or the normalization is different. And that's a fair criticism. So there are many different ways that people address this, different kinds of regularizers besides ridge regression um that you can use to disambiguate between candidate models that all fit your data well.

But the minimum norm is one that's been around for a long time and is extremely relevant in many different settings and worth knowing about. Yeah, >> sorry I kind of said up for a second, but uh we want to choose a weight vector with the minimum norm right to avoid really large weights because that that causes overfitting, right? Is there a situation where we want really large weights, >> right? Question is often we like to pref um to avoid having large weights to help avoid overfitting.

Um are there settings where we really want large weights? Nothing's coming to mind at the moment. What I do see a lot are things where people will say I want um so alternatives to this would be to say I want sparse weights. So here let's just talk about alternative regularizers. So one would be to say let's minimize the norm or relatedly try to make uh well yeah minimize the norm. We could also say make whatever w hat we choose sparse.

So we want to have as many zero elements as we can. So we'd be saying instead of sharing the weights among lots of different features, I just want to choose a small number of features that are good predictors. That's another possibility. Um sometimes people will say make W hat smooth in some sense. So maybe there's some ordering to my features like for instance they correspond to pixels in an image or something where somehow I think the weight for one feature should be related to the weight of another feature.

And so what I might do then is I might say um that I want the i element and the i + 1 element to be closer if possible. I guess I'm just saying absolute value. So again, these are just all design decisions that would depend on the context of your problem. Um, and depending on that context, any of these can make a lot of sense. And of course, there's hundreds of other regularizers out there. Um, but these are some of the ones that I see most often.

Yes. So is the uh conceptually can we think of the uh non-inverability of uh that xrpose x and the factors multiple possible uh outcomes as like linked and with bridge regression because we're favoring an outcome that also solves non-invertibility and vice versa. >> Yes. So in this setting this particular X we have um you know P features and they are linearly dependent and so as we've talked about before XRPOSEX is not invertible and there is um also no unique least squares solution.

Right? So there's multiple different wave vectors here that give me the same sum of squared errors which is zero. So there's no unique le square solution and that's intimately related to the fact that xrpose x is not invertible. The reason it's not invertible or yeah the way way to think about it not being invertible is that there is no unique solution here um and this is because my P features are linearly dependent.

So these are the settings in which we need to use some sort of regularization or impose some sort of structure on W to help us choose among possible weight vectors that all look equally good more or less in terms of prediction on the training data. Yeah, >> this might be too much of a digress. >> Okay, so what's the difference between a sparse W hat and just minimizing the weights? Um, this is subtle. Um, but I'm not going to have a great example off the top of my head, but I could imagine having a W hat where my entries are um um I don't know, let's just say one and then 0.01 and 002.

So in this setting with this vector, these two entries here are not really contributing a lot to the norm. Um and yet I'm giving the corresponding features some weight. And so um if I try to promote sparsity, what I'm doing actually or the way that people do this most often is they try to try to make or minimize the L1 norm of W or the sum over I of the absolute values of the weights as opposed to the squares of the weights.

So those are different. And when I try to minimize this L1 norm as opposed to minimizing the uklidian norm that we typically are working with in this class, then I'm trying to say, you know what, if I can get almost as good or equally good predictions from a weight vector where I've only put weight on one feature, then in some settings that I would really prefer um for a variety of reasons. One of which is interpretability.

If I want to say, hey, I only I want to know which features I really should care about for predicting labels, then this can highlight a small number of features that are highly predictive in a way that we might not get if we just try to find a minimum norm solution. >> Yeah. >> What is that expression? Is that like wus w? >> Oh, sorry. I guess I don't need the vectors here. I just mean if I've got a um a weight vector and I'm looking at the E entry and the next entry two neighboring entries in the vector then this smoothness condition would be like saying that they have similar values. >> Yes. >> Sorry. >> I mean like doesn't like sparse mean like as many zero elements as possible?

So like even the elements have similar values that's not like the same as spars. Uh yeah, these are two different bullets. Sorry if that's not obvious. So one possibility is to minimize the norm like we've been talking about or use ridge regression which is closely related. Another pos separate possibility is to try to make W sparse. And a third possibility is to make it smooth. So you're totally right. They're not the same. >> Yeah.

So like what's the meaning of like taking that concept of like having >> okay um so the first question was is there a good geometric interpretation of the pseudo inverse? It's a great question. I'm not sure. I need to think about that a little bit. Um, yeah, I'm not sure. But in terms of thinking about I I think the second part you were saying, how do we think about minimum norm versus sparcity? Is that right? >> Okay.

So, here's one way that I could look at it. Um imagine that I've got my space of possible weights. So now um P is equal to 2. So my weight vectors have entries W1 and W2. And then I can say in this setting where there are many weight vectors that all fit um my training data um so I'm going to draw a line here like this. So for every point on this line, XW is equal to Y. Okay, so these are all possible weight vectors that fit my training data.

And now my job is to choose among them, right? All right, so there are a couple of ways I could do this. one is I could say I want to have the minimum norm. So now I can think about the space of all weights that have equal norm. And so maybe I'll do it like this. So this red circle, every W on this circle has the same two norm. It's all they're all the same distance from the origin. And so when I look for a minimum norm solution, what I'm going to choose is this one here.

So this would be my W hat. I'm going to write MN for minimum norm here. And alternatively, I could say I want to think about all of the weight vectors that have the same L1 norm or the same amount of sparity. And that is going to look so that well it's not exactly sparity but the L1 norm that turns out to be a diamond. So now every W on the diamond has the same L1 norm or the same sum of absolute values. And so if I say among all of the possible weights that fit my training data, I want to choose the one that has the minimum L1 norm. then I would choose this one.

So this would be my W hat. Uh let's call it sparse because that's how I've been referring to it. So depending on the norm that I choose, I may be choosing or preferring different weight vectors that fit my data. Does that answer your question? >> Okay. I I Yeah, it takes a little bit of thought. It's not quite as um easy to grasp for me at least as like the least squares geometric picture that we drew. Yeah. Um I'll come back to I want to make sure you hear others too.

Yeah. >> Um can I think sparse um w is related to truncated SVD where some of the singular values we set set them to be zero. So like some features are not used. So with the um truncated SVD, we took some singular values and we would set them equal to zero. Um and in general, we would set the smallest ones equal to zero. If I think about the pseudo inverse, I'm taking the smallest singular values. Maybe you could think about it as inverting them and then truncating some of the biggest ones after inversion, but it's a little bit different.

Yeah. Yes. >> So for sparse, do we mean as zero like as many zero as possible or do we mean the least like L1? just like here for the like white white uh white diamond if we just want as many zeros as possible then we can take the point that's like a >> that's right so I did not yeah so so we could say conceptually that what we would like to promote is sparsity as many zeros as possible but then when it comes to developing algorithms where we can actually solve the optimization problem explicitly trying to give us sparity turns out to be computationally hard.

And so as a proxy, we will try to minimize the L1 norm. It's totally analogous to what we were talking about with matrix completion where we might like to minimize the rank of a matrix, but computationally that's hard. And so instead we might try to minimize the nuclear norm of the trace norm. So same here we might care about sparity on a conceptual level and yet when it comes to practical algorithms working with the L1 norm is much easier and under certain such certain conditions that we're not going to be able to go through in this class.

You can prove that minimizing the L1 norm is equivalent to maximizing sparity but again beyond the scope of this class. Yeah, >> actually I want to like ask a question about like previously we've actually learned a lot a lot of techniques on how to make linear dependent columns to be the find the basis which is linear independent like why do we have like different features which are linearly dependent but we are not for example just drop off some of the ones who are like making it dependent like why we bother to use a new technique instead of just making it independent find a basis and then use the previous one that you >> So that's a fantastic question and for the recording the question is if I've got P features and they're linearly dependent why am I going through all this rigomearroll why don't I just do PCA find a basis for the features and work in that basis space and um that is a totally valid way to go um one reason is interpretability So here my features mean something very concrete and when I learn weights on those features I know how to interpret it.

This is telling me if I want to have a good prediction of y then I should just look at the first feature and I can ignore the other two features. I can interpret this weight vector that way. But if I were to instead first learn a basis, well this isn't a great example because the basis would give the same result. But in general the basis is going to be a linear combination of all the features. And so if I learn a basis and then my predictor says oh you should put a weight of five on your first basis vector which represents some combination of all your features then that gives you good prediction but is not necessarily interpretable in the same way right it's not telling you which of your raw features are important.

So it really is context dependent. There are definitely settings where just doing some dimensionality reduction, finding a basis for my features is perfectly legitimate and a great way to go. And then there are other settings where we really do care about interpretation and these alternative techniques that we're describing are a better way to go. Yeah. Okay. Really excellent questions everyone. Thank you so much. So the next thing we're going to do is transition to um kernel regression and this is going to lead us directly to the support vector machines which before neural networks became a big thing were the workhorse of a lot of machine learning.

So this is extremely important conceptually. It's going to teach us a lot of important ideas um that are still in use today. So recall that what we've been working with is predictors of the form yhat is um is equal to just a weighted sum of my features. So in my toy example here, let's just say I've got two features. So my yhat might be some w um uh one x1 + w2 x2 + w3. And I can write this as wpose x where in this case my x is equal to x1 x2 and then I've tacked on a little one at the end here.

Okay. So this is sort of the linear prediction setting we've been working in. But we've noted before that they that what we might prefer is something like this. a let's say quadratic predictor where y hat is say w1 x1 w2 x2 w3 time um and then I could have an addition x1 2ar w x1 2ar and w5 x1 x2 and w6 x2 2^2, right? So there are settings where this would be a mechanism for getting much higher accuracy. And so what we would like is to figure out a way to make this systematic.

So first of all, let me provide a motivating example. So imagine that when we plot our training data and we look at our two coordinates, we see something like this. So we see all of our x1 s or I'm sorry, all of our positive samples in a little disc here. And then when we look at all of our negative [clears throat] samples, they lie in a ring. Okay? So we as humans can look at this and immediately recognize that there's a very simple way to differentiate the red and the blue samples.

If I restrict myself to a linear classifier, there's no linear classifier here that's going to work well. No matter where I put that line, I'm going to be making errors. And so by allowing ourselves to have quadratic predictors, then what we can do is learn decision boundaries that can perfectly separate our data. And the way to think about it is like this. So I'm going to redraw this data, but instead of drawing it in two dimensions like I just did, I'm going to add a third axis.

So, I've got x1, x2, and then my third axis here is going to be um x1 squared + x2^2. Okay, so one of the or yeah a combination of some of the features in this quadratic expression. So now if I plot my data, my training data in this setting, then I get all of my red dots here by the origin. And I've got my blue ring up here cuz they're farther from the origin. This is like a circle that's on its edge. I know it's hard to tell from the drawing.

And so once I've mapped everything into this 3D space, it's very clear that there's a nice linear predictor in this new space. So what we're talking about is saying, hey, we've spent all this time on le squares, minimum norm, pseudo inverse, ridge regression, etc. But it only is for these linear predictors. And there's lots of settings like this where we want nonlinear decision boundaries. And the point I want to make is that there are times where we can just augment our features like I've done here.

So that in this new feature space, I can just use all of the linear prediction tools that we've been learning about all quarter and get very accurate and powerful predictors. Okay. So in general then what we are going to do is we are going to let we're going to define a function f that will input a feature vector x and output a new feature vector that's going to look like in this case uh x1 x2 I guess one x1 x1 2ar x1 x2 and x2^2 and so now what I'm saying is that I want to have my y hat my prediction be equal to the inner product of this f ofx and some weight vector so I'm still now after doing this mapping with fee doing linear prediction I'm just doing it with the feature vectors instead of my original X feature vectors.

Everything clear so far? Okay. Very simple concept, extremely powerful. So when we talk about using kernels, what we're trying to do is to formalize and generalize this concept. So you might be thinking well what is there new to learn here I can just define one of these fee functions and then proceed with le squares or ridge or whatever else but the problem is that if x is in let's say uh each feature vector is in p dimensions um and we say that our new feature vector f ofx is in dimensions then um d is typically way bigger than p.

So for instance if we had quadratic polomials the way I described on the previous board then d is on the order of um p^2 and if we were to have fifth degree polomials then we have d is on the order of p to the 5th and if we think about p the number of features being say in the hundreds or thousands then taking these to huge powers is going to create just enormous feature vectors and then we run the risk of overfitting and some of the other challenges that we've talked about as well as computational challenges.

And so with kernel methods, we are going to um basically let us make predictions of the form yhat is equal to the inner product of x or f ofx and some weight vector W. Um, and we are going to do this in a way that helps us avoid overfitting and with manageable computation. Okay. So in particular what we are going to do is we are going to do um the first thing we're going to do is we are going to do ridge regression using these V of X feature vectors.

And typically when we talk about these sphere of x's, we'll refer to them as being in the high dimensional feature space because often the dimension in this fe after this fee mapping is much much bigger than our original dimension. So we think about fe as mapping our original features to some new highdimensional feature space. Okay, so now I want to think about what happens with ridge regression um and add a little bit of nuance that we didn't see last time, but which is going to be really helpful now as we start thinking about kernel methods.

So first if we recall ridge regression again we said that our wave vector W hat R looked like v sigma um transpose sigma plus lambda identity inverse sigma transpose uranspose y and I want to focus on what's happening with these singular value matrices and so in particular the point that I want to make is that this is equivalent to we just haven't written it this way before um sigma Sigma transpose sigma sigma transpose plus lambda identity inverse.

Okay, I can write it either way and they are the same thing. I'm using the fact that the sigas are um a a diagonal matrices. So I'm not going to show this in every case but for example when n is less than p when we've got huge number of features compared to the number of training samples which wi which can happen easily once we start mapping to these highdimensional feature spaces then our sigma which is n by p. So it's going to be short and fat is going to have sigma 1 through sigma n and then everything else is zero.

And so now if I look at sigma transpose sigma, I'm going to get something that is p by p. And so I will have sigma 1 through sigma n and then I will have a whole bunch of zeros for the rest of this diagonal matrix. And so then if I were to from here compute Sigma transpose sigma plus lambda identity inverse sigma transpose. Then what I would get would be um sigma 1 over sigma 1^ 2 + lambda all the way to let me get this right.

Yeah, sorry. Apologize. This is sigma, right? Okay, this goes up to sigma n, but this is p by p. And so now here I've got something that is p by p times something that's p byn. So the product is going to be p byn. And so I'm going to have something that's taller and thinner and I'm going to have it be all the way to sigma n over sigma n^ 2 + lambda and everything else down here is zeros. Okay. Now if I look at the equivalent thing that I mentioned here then I am going to first look at sigma sigma transpose plus the lambda times the identity and what I'm going to get now is that this is going to be n by n and so I will have sigma 1^ 2 + lambda all the way to sigma n^ 2 + lambda in a diagonal matrix.

And if I compute sigma transpose time sigma sigma transpose plus lambda identity, I end up getting exactly what I showed you before. Sigma 1 over sigma 1^ 2 + lambda all the way down to sigma n over sigma n^2 + lambda. And everything else here is just going to be zero. And the dimensions line up because this is n by n and this is p by n. And so my product here is p byn. So it's exactly the same. Okay. So key point here is that now I'm just going to write this expression using this alternative way of formulating ridge regression.

And that's going to be very helpful as we start thinking about how we can use different kernel methods. Okay. So when we look at our ridge regression estimate, we've got V sigma transpose and then I'm going to leave a little space. Then I've got sigma sigma transpose plus lambda identity inverse and then I've got uranspose y. And now what I'm going to do is insert in the middle of that a uranspose u. And I can do that because I know that this is identity.

But this is helpful because now I can say hey this first product here this is just exactly the same as xrpose and everything else including the y. I'm going to just call alpha. Okay. So I'm saying now that I can write my ridge regression estimate as xrpose times this vector alpha. And this is important because it tells us that W hat R is equal to a weighted sum of the columns of XRPOSE, which is the same as a weighted sum of my different um XI's.

And the alphas tell me the weights. So this alpha vector is going to be an n-dimensional vector. So alpha is telling me how much weight to give to each one of my training samples. And then I'm going to write my weight vector for ridge regression as a weighted sum of those training samples. So here are the training samples and here are the weights assigned to each one of them. And I've got this formula here that tells me exactly how to compute those weights using my training labels and the singular vectors and singular values associated with X.

So now we can say that we want to compute ridge regression in our feature space. So specifically we are going to define a new matrix capital V which is simply V of my first training vector transpose and then V of my second training vector transpose all the way to FE of my nth training vector transpose. So this matrix is n by d. It's got the same number of rows as x did but way more columns. And now what we're going to do is we are going to say that our ridge regression estimate is going to be the arg min over w of y minus capital v * a weight vector 2 norm^ 2 plus lambda * the sum of the squares of all the weights.

So now this is framed in a way that we know how to solve. We've spent a couple of weeks talking about this now, maybe one week. So, we can m maybe two days. But now we have tools for approaching this. But what we're going to see next week is that we can use what I described here. The fact that this weight vector is a weighted sum of the samples to get an alternative expression for this ridge thing that like I said is going to allow us to compute things very efficiently.

So in particular what's going to happen in many practical scenarios is that this fee matrix the number of rows D is going to be enormous. We are going to want to not even have to compute this V matrix at all. So we have to say all right this is ideally what we would like to compute. How can we compute it in a way that totally avoids computing this matrix and uses the information that we have derived about ridge regression in order to make that computation feasible.

So that's what we will talk about in detail next week.