Lecture 11 Fall 2025: PageRank and Ridge Regression transcript

All right, welcome back everybody. So um today we're going to continue with our discussion on ways in which the singular value decomposition and regular and relatedly um decompositions are showing up in various machine learning context. And to start we're going to talk about um page rank which is a method for determining the importance of different web pages um say in the internet so that when you search for uh a topic the ordering of the pages that are returned to you is prioritizing pages that are more important in some sense.

So what do we mean by important? So, what we're going to do is imagine that we are surfing the internet by just randomly clicking links. So, I'm at some website and I just choose one of the links on that website at random and I click on it. Then there's a whole bunch of links on that website. I choose one of them at random and I click on it and I keep repeating this process. So if I keep on doing this forever then in some sense we will visit more important websites more frequently.

Right? So if I have in my internet a huge number of sites that all link to Amazon, then as I do my random surfing, then I will hit Amazon more and more often. And so in particular, if we do this long enough, then eventually we will hit some sort of steady state. And in this steady state um you're going to have um some new variable pi now where pi i for my i website is going to be the probability that we are at website i at any given time.

Okay, so we start off by just doing this random surfing. And if we do this random surfing for an infinite amount of time, then at some point we will just on average be hitting site one with probability pi 1 and site 2 with probability pi 2 etc. And so then we can think of these probabilities as being a measure of this importance notion that we've talked about and we can use that to rank different websites that perhaps match a search term or something.

So let's think about um an example of this. Okay. So, we are going to create a little miniature internet here with four different sites. One, two, three, and four. And then we are going to think about what network I'm sorry, what links are in this site. So in particular if we think about which sites are linking to page one um we are going to have sites two three and four all link to site one and then if we think about who's linking to sites two we have link or sites three and four pointing to site two.

If we think about who's linking to site three, it's only site one. And if we think about who is linking to site four, it is sites one and three. Okay, so this is a graphical representation of our miniature internet indicating which nodes are connected to which other nodes. And so these are our hyperlinks and these are our websites. And so now what we can do is we can represent the structure of this network using a matrix.

So in particular we are going to let M be uh the adjacency matrix. for the network. And in particular, if we were to look at the J's entry of this matrix, it's either going to be one or zero. And it's going to be one if site J links to site I and zero otherwise. So for our little example now we're going to form a matrix and we're going to say all right for the first row which sites are linking to site one and that's everybody sites 2 three and four and then if we look and we say who is linking to site two we have sites three and four.

If we look and we see who is linking to site three, it is only site one. And if we say who is linking to site four, it is sites one and three. Like this. Okay. So this is our adjacency matrix. If you've got this graphical description of your network, then you can figure out what the adjacency matrix is. And once you've got the adjacency matrix, you can figure out what that network structure is. So they this is just simply a matrix representation of exactly that representation on the board.

Next what we are going to do is we are going to um divide each column by its sum in order to get a normalized form of this matrix. So we're going to call that new matrix A. So if we look at the first column of M, its sum is two. And so the first column of A is going to be 0 0 1/2. For the second column, we'll just have 1 0 0. For the third column, we have a third, a third, 0, and a third. And for the fourth column, we have 1/2, 1/2, 0, and zero.

Okay, so same information again we've just done a particular normalization here and this normalization is going to turn out to be extremely helpful to us. Okay, so in particular what we are going to do is we are going to let our vector pi be equal to the vector of all of the different probabilities for all the different nodes in our network. So we're going to have pi 1, pi 2 all the way to pi n if I've got n n n n n n n n n n n n n n n n n n n n nodes in the network.

And I'm going to put a little transpose here because I'm thinking about this as a column vector. So this is the vector of probabilities or importances that ultimately I'm trying to calculate and I'm going to use these adjacency matrices in order to do it. So in particular, we could imagine having a pi k that corresponds to the um how often we or how frequently we've visited sites after doing this process of random surfing k different times.

Oops. Okay, so this top one is the steady state that we are going after that we ultimately want to calculate. And when I have this k superscript, what we're saying is these are sort of like our our frequencies of visiting the different sites after k um hops or after k clicking on k different links. And so now what we're interested in is what happens if I keep up doing this random surfing forever. So what happens as K goes to infinity?

So in particular this pi k is going to approach this vector pi that we actually want to compute. But what I mean when I'm asking this question about what happens as k goes to infinity is how is this adjacency matrix that we've been talking about going to affect it? So if I'm at these different websites, each one with some probability, and then I were to choose one of the links at random, then what are the probabilities that I'm going to be at any individual website in the next step?

So my vector of probabilities or frequencies at the k + one step is going to correspond to taking this vector at the kith step and multiplying it by this matrix a uh normalized adjacency matrix. So what I'm doing here is I'm saying okay at time k I've got some probability that I'm at each of the different websites. A is telling me something about the probability of going to each one of the different websites from there.

Right? So, if I'm at website four over here, then there's only two places I can go from there, either to site one or to site two. And since I'm choosing links randomly, there's a 50/50 chance of me going to one or the other. And so when I write this equation here, what I'm reflecting is the fact that I've got some probability of being at each one of the different websites and then some probability of clicking each of the links at those different websites.

And that's going to update my probability vector. And so then as K goes to infinity, what I'm going to have when I talk about this steady state is that this vector pi is equal to this adjacency matrix A * pi. So my problem now is the following. Given this matrix A, what is pi? what is this vector of probabilities? And we don't want to figure that out by actually doing this experiment of randomly surfing the internet forever.

That's computationally intense. And it turns out that just using a little bit of math, we can actually figure out what pi is without doing this random surfing. So in particular, when you look at this equation here, what does this look like to you? What does this remind you of that we've talked about in this class? Right? This is an igen value equation. So recall that we have we could have l a scalar lambda and a vector v and they are an igen value vector pair. for a matrix A, if A * the IGEN vector is equal to lambda* the IGEN vector.

And so with this equation that we've got here in terms of pi, this is telling us that pi is an igen vector of a and the corresponding value lambda would be equal to one. Okay, so let's flush this out a little bit more. So in particular we did this normalization for A. So a in this context is what's called um a marov matrix. All of the entries are non- negative and the columns are all summing to one like vectors of probabilities.

And marov matrices have an important property where the leading oops value um lambda is equal to one and I'll say lambda 1 here and all of the igen remaining igen values are smaller. So if we looked at all the different igen values of a, lambda 1 is going to be equal to one and it's going to be bigger than lambda 2 and lambda 3 and any other values that we might have. So not only is pi one of the igen vectors of a but in fact is the the leading igen vector of a the vector corresponding to the largest igen value which in this case is equal to one and so now all we need to do is to calculate what that igen vector is.

All right. So to do this, you could use a full just decomposition of the matrix A. For something like ranking all of the sites on the internet where there could the number of sites could be in the millions or billions, doing a full decomposition can be very slow. So what we want to do is to just compute that first vector in order to be as efficient as we can be. So I'm first going to show you a generic um method for computing IGEN values and I'm sorry I en vectors and then I'm going to talk about a specialization of that to this page rank setting when we have a markoff matrix.

Okay. Okay, so for the generic power iteration method, we're going to have some pi 1 be an initial guess for pi. So we start off with some initial guess and then we are going to iterate as follows. So 4 k = um 2 3 4 etc. What we are going to do is we are going to take our current guess I guess we are starting at one pi k and then we are going to multiply it by the matrix for which we want to compute values a maybe I'll do it like this just to be a minus one and then in most power iteration methods we normalize this because we are looking for igen vectors with norm norm one typically.

So we would divide by a * pi k minus one it's two norm and so this normalized vector is what we are going to call pi k and then finally sorry this is a little messy but if my estimate pi k and estimate pi k minus one if it stops changing. Um, if we are no longer making any progress, we say we're converged and we stop. But that's it. It's a very simple method where we're just continually in every iteration applying the matrix A in order to update our vector of probabilities.

Very powerful and very effective. Okay. Now at the same time this in when we think about page rank this might feel a little bit weird because what we are doing with this um normalization here is ensuring that the final vector that we get has a norm a two norm that's equal to one but what I told you earlier is that in the context of page rank we want to interpret pi as being a vector of probabilities, right? Hopefully that will add up to one like most probabilities do.

And so we would actually do something a little bit different in the context of page rank to account for the fact that we're dealing with vectors of probabilities and marov matrices. And so what does this look like? So with Oh, okay. Um, so for page rank, let's initialize with a vector pi where all of the entries add up to one. And then what we're going to do is try to ensure that that is true for every iteration. So we want this to be a vector of probabilities so that if I were to look at the sum of all of its entries from j = 1 to n of pi j and I'm doing this at say my kth iteration that that is equal to one.

And now what I want to note uh if um if my vector is a bunch of numbers that add up to one that are all non- negative Then if I just look at pi k + 1 where I compute the product of the matrix a times pi k and I don't do any additional normalization then I will have that the sum of the entries of my new mat uh vector pi k + 1 also add up to one. So if I start off initially with a vector of probabilities that add up to one and at every iteration I don't do any additional normalization.

I just take my vector and multiply by a where a is a marov matrix. Then at each iteration I will keep I will still have a vector of probabilities that add up to one. And we can see this very clearly by just using the way that we specified this marov matrix. So in particular let's look at the sum from j= 1 to n of pi k + 1 j. So now what I'm going to do is I'm going to put in here that this pi k + 1 corresponds to taking the sum from i = 1 to n of a j i times my previous estimate pi k and its i entry.

And then I'm going to sum up um the results of those operations. So each of these sums in yellow is giving me pi j k. Now what I can do is I can simply change the order of my sums here. So, I'm going to pull out the sum from i = 1 to n. And I'm going to have in parentheses my sum from j = 1 to n [snorts] of a j i and that gets multiplied by pi i k. So, I'm just changing the order of my sums here. And I'm noting that this sum over j's doesn't really depend on the values of the pies.

But now if I look and see what's in these parentheses here, what do I know about that sum? >> Oh, sum to one. Yes. Yes. Exactly. This has to be equal to one because this is the sum of column I in that matrix. And when we form that matrix A, we said we're going to normalize it so that every column sums to one. And so then what we're left with here is simply the sum from I = 1 to N of pi I K. So whatever my sum was at the kth iteration is going to be what my sum is at the J iteration.

And so if I I'm sorry, at the k + 1 iteration. And so if I initialize with a vector that sums to one, a vector of probabilities, then all I need to do is at every iteration take that vector and multiply by a no additional normalization and at every iteration I will get a vector of probabilities that sums to one. So this is a special way that we can do power iterations in the context of page rank when we have um um marov matrices.

And so for example a common choice would be to set my first estimate to simply be a vector of ones. So a vector that's n by one of ones and then I multiply that by 1 / n. So I'm just saying I'm going to have uniform probability or uniform weight on every site in my network when I start off. And then I continue to iterate using these unnormalized power iterations with a marov matrix in order to get this final vector of weights.

Yes. So when we initialize the the pi, we must like have every term to like every term in pi to have a value because if we initialize pi maybe to be the canonical factor then like only one term would have like multip like multiple with a and all the others would just. So the question is do we have to be careful about the initialization because what if we started off with an initial pi vector where some weight sites had no weight.

Um we can get around that. I think uh I I I think that's not an issue because if you have no initial weight on site one for instance but other sites do link to it you will still visit that site even if it's not in that initial vector. But your question is getting at a bigger problem which is imagine that I had a network for instance where I've got two different subn networks that are not connected to one another. Right?

So if I start and I just do these power iterations, I'll only visit the network that's connected and I'll never visit the network that's disconnected from it. So there is sort of a fundamental issue with the way I've set this up because I have implicitly assumed that I can get to any site eventually as long as I hop around long enough. And that's not always the case. For instance, if we have these disconnected networks.

So to resolve that issue, we introduce a damping factor. And in particular, what we're going to do is um have this stamping factor alpha, which is just a scaler that's somewhere between 0 and one. And typically for page rank, alpha is 0.85. Seems to work well empirically. And then what we do is the following. We're going to change the way we do our random surfing. So, we're going to basically flip a po a coin where probability of it coming up heads is alpha and the probability of it coming up tails is 1 minus alpha.

And then based on that coin flip, we're going to do the following. So with probability, we are just going to follow a link from wherever whatever page we're currently at. So if ALO is equal to one, this would be exactly the method that I described to you before. Oh, I thought it was the microphone, but someone's drilling. Okay, so with probability 1 minus alpha, we're just going to go to a random website. So, in the context of our little toy example here, right, we start off at some site and we keep doing random surfing, but 15% of the time our coin is going to come up tails and we're just going to choose a random site.

It might be in that same network, but it might be in a different subn network. And so, we're going to allow ourselves to hop around totally at random, in this case, 15% of the time. Okay, so algorithmically that makes sense. Can we still use power iterations and iiggen decompositions? And the answer is yes. So in particular, we can define a matrix G for Google which is equal to I forgot. Yeah. Alpha times our matrix M plus 1 - alpha times a normalized ones matrix.

So we're just I'm going to write this as 1 n byn. So this just means a matrix of ones that's n by n by n. And then I'm going to multiply that by the fraction 1 / n so that every column of this adds up to one. Okay. So now I've got a new matrix that is representing the way that I am traversing the network with this new way of surfing where with probability alpha I'm going to follow a link using this matrix M and with probability 1 minus alpha I am going to um just hop around randomly and I apologize I think here I want the matrix A.

I know. And so now what we seek is a vector of importance is pi. That's going to be the leading igen vector of my matrix G. So I can still use exactly the same concepts. I'm just introducing this little damping factor to account for the fact that this adjacency matrix might represent um disconnected components of my network. Are there any questions? Yeah. So yeah, if you really wanted to like build a um search engine, you would have to handle special cases like what if you get to a website that doesn't have any links.

I mean I guess it formally does fit within this framework um in the sense that then you would just go to a random web page. Um but yeah, I mean I think there are a number of ways in which the original algorithm can break down. You could get stuck in a loop where you just have sites that just link only to each other or you could have disconnected networks or you could have random pages that don't link to anywhere else.

And so this damping factor is designed to handle those edge cases. Yeah. >> Also you might have said this but how does it decide which Oh yeah, it's still just a random link and it's uniformly at random. So it's not giving preference to any link over any other link. Yeah. Any other questions? Yeah. >> I think that should be Jing P with the Oh, you're just saying here that should be K plus one. Is that what you're saying?

Okay. Yes. Thank you very much. All right. So in the lecture notes that will be posted online, I go into a more detailed explanation of why power iterations work, why this approach is going to lead you to um actual en vectors. Um and so I do want to encourage you to look carefully at that explanation. Um it's a very kind of stepbystep and I think uh easy to follow explanation. But unless there are any other questions about page rank, I want to move on to discussing ridge regression.

Okay, so rich regression is an extremely fundamental and important concept. In addition, if you've played around in the past with neural networks and you've used weight decay, it's intimately related to ridge regression. So, we're going to learn some core ideas and concepts here. And we're going to focus on them in the context of lease squares because that's where we are in the class right now. But a lot of the concepts that I'm introducing here and why they're important translate to other settings including neural networks.

And so um uh hopefully this will be very broadly useful even as we initialize our discussion with a more narrow focus. Okay. So as we have before we are going to um be given training samples X I and Yi where the XI's are our feature vectors. They are P-dimensional. Our y i are just scalers and we are going to have n different training samples just like we've been doing with leash squares. And as before, we could have our matrix of features x where we could have x1 transpose as the first row, x2 transpose as the second row, xnpose as the nth row.

So this matrix now is n by p. So recall that if X has P linearly independent columns then we can find a unique le squares weight vector W hat le squares which was equal to XRPOSE X inverse XRpose Y. And we said if it didn't have p linearly independent columns then this matrix here xrpose x was not full rank and we could not compute its inverse. And so in order to make this work we had to have the number of training samples be greater than the number of features and the features be linearly independent.

But there are many settings where those assumptions cannot be met. And so let's just think a little bit about what this looks like in the context of the singular value decomposition and then ridge regression is going to allow us to sidestep some of these constraints that we have been having to deal with in the context of le squares. Okay. So, as a warmup, we're going to let x have a singular value decomposition. Use sigma vranspose.

So now what I can do is I can write my least square solution W hat ls in terms of these matrices. So w hat squares is going to be v sigma transpose uranspose u sigma vranspose inverse time v sigma transpose uranspose * y. So I'm just using the exact same formula, but I'm plugging in my SVD matrix. And now I'm going to start simplifying. So what's uranspose u identity right? So that immediately goes away. And now I'm going to refer to sigma transpose time sigma.

I'm just going to call that for shortand sigma squar. So now what I have is v sigma squar vtranspose inverse time v sigranspose uranspose y. Okay. Now let's think about this thing that we're trying to invert here. So when I'm trying to invert a product of matrices like this, if each of the different factors are invertible, then what I can do is similarly to what we do with the transpose, I can invert each of the factors and then change the order.

So I can write this as vtranspose inverse sigma squar inverse v inverse v sigma transpose uranspose y. So now I can do some additional simplifications. What's v inverse * v? Identity. >> Identity. Great. And also what's vranspose inverse? Okay. So just recall that um for the SVD vranspose V is equal to VRpose is equal to the identity matrix. So what this tells us then is that VRpose is equal to V inverse. And so in the context of the left side of the board here, if I have vranspose inverse, then this is v inverse inverse, which is just v.

Okay, so this thing here is now just v. And so going up here, I can now write my least squares weight vector as simply being um v time sigma and I'm going to write sigma squar inverse as sigma to the -2 time sigma transpose uranspose y. So now first of all let's remember that the rank of a matrix is equal to the number of nonzero singular values. So when we look at this from the perspective of the SVD, we can see that this only really works if there are no zeros in the diagonal of sigma.

Right? If I've got any zerovalued singular values, I'm not going to be able to compute this sigma inverse. Right? So let me just flush that out a little bit. Sigma to the -2 is going to be a diagonal matrix. I'm going to have 1 / sigma 1^ 2 1 / sigma 2^ 2 all the way to 1 / sigma p^ squ and everything else in the matrix is zero. So I can only really calculate this if none of these sigas are equal to zero. Right? As soon as one of them's equal to zero, then this blows up and it's not defined.

And so when we required before that xrpose x was invertible, it's like saying all of those singular values had to be greater than zero. But once we do this then if we were to look at sigma to the -2 times sigma transpose. So let's just remember sigma to the -2 that's going to be p by p and sigma transpose is going to be p by n. And so we are going to have a matrix that looks like this. So we're going to have in the first diagonal the sigma 1 squared in the numerator I sorry in the denominator times a sigma 1 from that sigma transpose matrix.

So we have sigma 1 over sigma 1^ 2 or more simply 1 over sigma 1 and then we've got 1 over sigma 2 all the way to 1 over sigma p and then however many extra zeros are there to make it the right size. And so if we think about what's happening with this least square solution, we're using our SVD basis matrices U and V and we are simply uh so we take Y, we rotate it according to this U basis matrix. Then we just multiply by a diagonal matrix corresponding to one over all the singular values.

And then we rotate rotate back into kind of weight space using this V matrix. So from here hopefully it's clear all of these singular values have to be greater than zero for this to make any sense. But also if some of the singular values are super close to zero, let's say 10 the minus 6, right? One over a million. Then when we compute this matrix in the middle here, all of a sudden we're going to have some entries that are on the order of a million.

So even if none of the singular values are zero, these squares can still lead us astray. And I'm going to show you a very specific example of that in a little bit. But ridge regression is designed to bypass this challenge to bypass the issue that some of the sigas might be zero. So we can't compute one over the sigas at all and some of them might just be not zero but extremely close to zero. We're computing one over sigma gives us enormous numbers that can cause real problems with generalization.

Okay. So with ridge regression, we're going to do something different than le squares. So I'm going to write w hat r for ridge. And this is going to be the argument w that minimizes the sum of squared errors y - xw just like we did in least squares plus another term going to have lambda * the 2 norm of w for some value of lambda that's greater than zero. Let's just say for the sake of argument like 0.1 or 0.01 1. This is something that a user would choose.

It's a tuning parameter or a hyperparameter and we'll talk more about it a little bit later. For now, imagine someone has told you a good value of lambda to use. So what we're doing here is we are saying we want to have a vector W that is a good predictor of the labels of all of our training samples but also where the sum of the squares of the weights are not blowing up. We don't want to have any weights that are on the order of a million if we can avoid it.

Okay. So now let's think about first of all what the solution to this minimization problem looks like and then we'll talk about how it relates to what we discussed with the SVD with le squares. Okay. So to solve this optimization problem there are a couple of different techniques that we could use. So one is we could um set gradients to zero. So in particular I am going to call this whole thing my loss function which is a function of w.

And now what I want to know is what is the gradient of that loss with respect to w. So we talked about that gradient before for the first term here for least squares and there it looked like um y - x w time xrpose uh * 2. So that's what we calculated times -2. Yeah, times -2. So this is what we calculated when we did it uh for just le squares. And then we do something analogous here. So we have -2 lambda * w. So we just have a little extra term on our gradient corresponding to this extra term in our loss function.

And uh sorry, not negative, positive. And just to be clear, because I might say it and I want to be explicit, I'm going to call this a regularizer or sometimes people will call it a regularization function. And so in this context, what we're doing is we're saying we want to promote weight vectors that are more regular than others. And by regular in this context we mean that the sums of the squares of the entries are small when possible.

Okay. So our gradient has an extra term in it corresponding to this regularization component of our loss function. And so now what we can do is set this equal to zero which gives us that negative um positive2 xrpose y is going to be equal to positive2 xrpose x w + 2 lambda w. And what I'm going to do to help with my next step is I'm going to just insert a little identity matrix there. The identity matrix doesn't change anything, but it is a nice square matrix that's the same size as xrpose x.

And that's going to help me simplify things. So, first of all, I'm just going to cancel out all my twos. They're not doing anything for me. And then I'm going to simplify the right hand side of my equation here where what I want to do is I want to pull out the w and have everything that gets multiplied by w on the left part here in parenthesis. So I'm going to have xrpose x plus lambda* an identity. And so now if I want to solve for W, I get that W hat with riged regression just corresponds to XRPOSEX plus lambda identity inverse times XRPOSE Y.

So in the special case where lambda is equal to zero then this looks exactly like le squares and this looks exactly like the le squares weight vector. It's only when lambda is greater than zero that we're doing something different here. And the key point that I'm going to illustrate to you is that there are going to be times when xrpose x is not invertible where we cannot do these squares like I mentioned but xtranspose x plus lambda ident identity is always invertible.

So I can always compute this ridge regression estimate. So ridge regression is going to work is going to be possible even when least squares is not possible and it's going to help us avoid overfitting and I'll describe how that works as well. Are there any questions so far? Okay, so just like before um there is another way that you can compute this ridge regression estimate and I think it might be just useful to walk through it really quickly.

So the other way we could do it is just massage it to look like le squares. So in particular I could take my loss function and I could write it as my squared error y - xw 2 norm^ 2 plus lambda but now instead of just writing w I can write this as 0 minus identity w it's exactly the same but now what I can do is I can rewrite this in a way that will let me use standard least squares. So in particular, this is exactly the same as compute as concatenating my Y vector and my zero vector and subtracting from it my X matrix concatenated with my lambda identity matrix time W uh square root of lambda.

Yes. Square root of lambda 2 norm squ. So what I can do is I can call this y tilda and I can call this x tilda. So that what this is is simply the two norm squared of y tilda minus x tilda w. And so then I can compute from here that my W hat for ridge regression would correspond to X tilda transpose X tilda inverse X tilda transpose Y tilda and then I can just plug in my definitions of X tilda and Y tilda to get the same expression as we had over on the left.

Okay. So, nothing we're doing here is a big shift in terms of the mathematics and the linear algebra from what we've already been doing. The shift is coming from what's happening with the singular values and what that means for generalization and bypassing some of the limitations of le squares. Okay, so in particular we said that W hat ridge is going to look like xrpose x plus lambda identity inverse xrpose y. And now what I'm going to do just like we did with le squares is rewrite this using the singular value decomposition.

So I'm going to have v sigma squar vranspose plus lambda identity inverse vranspose sigma transpose or I'm sorry I think that was a v v sigma transpose uranspose y okay so we're just using the same techniques as we used before when we started thinking about le squares in the context of the svd only Now we've got this little extra lambda identity in here. Now remember with the SVD we can write this I matrix as VVRpose.

And so I can rewrite this as v sigma squar vranspose plus v lambda i vranspose inverse v sigma transpose uranspose y. And once I've written it like this, I haven't really changed anything, but now I can group the two terms inside of my parentheses here to rewrite this as v sigma^ 2 + lambda identity vranspose inverse v sigma transpose urpose y. And now I can do the same steps as we did with le squares when I'm taking this inverse.

So that I get v sigma^ 2 + lambda identity inverse sigma transpose uranspose y. Okay. So this here is my vector of ridge regression weights in terms of my um ridge regression penalty factor lambda and in terms of the SVD matrices of my feature matrix X. So if you remember when we were talking about le squares, we said we would run into trouble if sigma had not had some zero valued singular values because this product sigma to the -2 * sigma transpose looked like 1 over sigma 1 1 over sigma 2 etc.

Soon as one of those is zero things blow up. But now over here when we think about what we're actually inverting we're inverting sigma squar plus lambda identity lambda is greater than zero. So all the diagonal entries of this matrix are going to be greater than zero. So let me just be a little bit more explicit. If we look at sigma squar plus lambda identity um inverse then what we get is in this top entry 1 over sigma 1^ squar + lambda and then we have 1 over sigma 2^ 2 + lambda all the way down to 1 over sigma p ^ 2 plus lambda.

And so since lambda is greater than zero, no matter how small these singular values are, even if they're equal to zero, I'm never actually dividing by zero here. And so when I look at sigma squar um plus lambda identity inverse times sigma transpose the thing that's showing up here in the middle of my ridge regression estimator. What I'm getting is a matrix that looks like sigma 1 over sigma 1 squared plus lambda sigma 2 over sigma 2^ 2 + lambda all the way down to sigma p over sigma p^ 2 plus lambda and then this might be a different size so we might have some additional zero valued columns to tack on.

So never do we have to worry about dividing by zero in this expression for ridge regression. So the role of when we talked about ridge regression what we said was we started off by saying well we want to ensure that whatever weight vector we choose does not have huge values if we can avoid it. We want to penalize vectors W that have really giant factors and if there are many different W's that give reasonably good predictions on our training data then we prefer to choose the one that has the smallest norm.

So we had that sort of handwavy explanation of what's happening here. And now what we have through the singular value decomposition is another understanding of what's happening. So basically what's happening is we are tempering the singular values that show up in this expression. Um so if we were to think about the least squares expression, some of the singular values could be close to zero and we would have um and so if we didn't have lambda here, we could be dividing by zero or dividing by extremely small numbers.

But now because of the lambda, we're never dividing by zero. And in fact the thing that we divide by is never going to be smaller than lambda. Okay. So, um, another way of saying this, and I just want to write it out explicitly because it's a super important point. XRPOSE X may not be invertible. But xrpose x plus lambda identity for some lambda that's greater than zero is always invertible. And so we can always compute the ridge regression solution even if we don't have linearly independent features, even if we've got more features than we have samples.

All the things that we were worried about before we can handle now because of this ridge regression penalty. Okay. So now I want to talk about um ridge regression and overfitting. Um so let's imagine that I get a bunch of points a bunch of training samples. So my horizontal axis is X, vertical axis are my labels Y. And now I'm going to plot them. And they look something like this. And now imagine that I try two different ways to fit these samples by using the same kind of polomial fitting idea that we talked about earlier in the quarter where we formed a Vandermond matrix in order to do le squares.

So if I let my polomial order be really high, I let myself have really um big polomial coefficients for really high order polomials, then I could maybe even fit this data exactly. But it can just be extremely maybe I'll just be a little bit more exaggerated here, right? If I'm like constraining myself to polinomials like it can just be exaggerated and based on these orange dots you might not think that this is the most likely or reasonable predictor of what's happening say when x is equal to zero right every single training sample here is up here with positive y's and because I've fit this high order polomial and tried to match my training data exactly then my predictor is saying oh you should when x is zero predict a label of say -10.

And so what you might prefer conceptually is a smooth lower order polomial that's close to fitting the data that doesn't perfectly fit the data but we might expect to be able to perform better and give more reasonable estimates on new samples later on when we deploy our model. And so if I were to force myself to use high order polomials and only do least squares and I try to fit my data as close as I can, I risk running into this green scenario where I have something that's really fit to the training data very accurately but may not perform well on my test data.

Whereas with ridge regression, I am promoting solutions that are more regular or smoother in this case. um that hopefully are going to give me better performance on my test data and better generalization. Okay, so this is a very handwavy claim, but we can actually see it in a very concrete setting. So what we're going to contrast is the following. So with lease squares we have sigma to the -2 * sigma transpose that shows up within our le squares estimator.

And we said that looks like 1 / sigma 1 over sigma 2 all the way to 1 over sigma p. And then if we were to do ridge, we would have sigma squar + lambda identity inverse time sigma transpose. And that looks like sigma 1 over sigma 1^ 2 + lambda. Sigma 2 over sigma 2^ 2 + lambda all the way to sigma p over sigma p^2 + lambda. Okay. Now let's imagine that the way my labels Y are generated is by taking this X that corresponds to my training features and multiplying by some true weight vector W star. but then just adding a little bit of noise or error to those labels.

So there is a true weight vector that generated my labels, but all those labels have just been corrupted by a little bit of error or measurement noise. Okay, we also are going to imagine that um X has some small singular values. So for instance, let's imagine that sigma p is not equal to zero. So we've said all right, le squares is a valid approach when none of the singular values are equal to zero. But let's imagine that sigma p is like 10 the minus 6.

Okay, so we're still within the realm of what we said is allowable for le squares. And now we're going to do is we're going to examine in this setting what happens if we do le squares and how that's different from what happens if we do ridge. Okay. Now over here before I erase I'm going to jump back a little bit and just mention this regularizer that I'm describing here one times the sum of the squares of all of my weights or all my parameters.

This in the neural network community is called weight decay. So everything when we talk about ridge regression, we're really talking about this weight decay regularization plus le squares. When people talk more generally about weight decay, they might not be using a le squares loss function explicitly. They might be using something else, but the regularizer is still the sum of the squares of all the weights or the parameters we're trying to learn.

Okay, so just a little vocabulary. Okay. So first of all I want to say that with ridge when we look at these diagonal terms let's just choose the e one. So we've got sigma i over sigma i^ 2 + lambda. So we can think about what that value will be in a couple of different cases of interest. So we might be interested in settings where the singular values are large maybe much larger than lambda. So in that case this is going to look close to maybe let's put our approximation here 1 over sigma i.

So when the sigma i's are big when we've got large singular values then the lambda is going to play very small role and this is going to look a lot like the corresponding diagonal value that we have with le squares. But when sigma i is close to zero, then we would have something that looks like 0 over 0 + lambda, we're going to get something that's close to zero. So what this is telling us is happening is whenever we've got large singular values, the lambda is not going to play a huge role.

We're going to be behaving like le squares would behave. And wherever we have small singular values, we're going to avoid having anything blow up. And in fact, we'll just say that this ratio is going to be close to zero. Okay, so that's the effect of it. Um, and I'm afraid I've lost a page. Ah, okay. So going back to our example with a little bit of measurement noise. If we were to look at W hat le squares, we've got xrpose x inverse xrpose and then normally I would write y here, but instead what I'm going to write is xr or I'm sorry x war plus this noise epsilon.

And so now I can rewrite this. I can have xrpose x inverse xrpose x war plus xrpose x inverse xrpose epsilon. So here I've got xrpose x inverse * xrpose x. Those cancel out and so what I have is w star. This is good. We really want um our le squares estimate to be as close as possible to w. But then we've added on to this this thing here xtranspose x inverse xtranspose epsilon. And if we think about what's happening here in terms of the SVD, right, what we're going to get is this V sigma to the -2 sigma transpose uranspose epsilon.

And so when one of the singular values is close to zero, say sigma p is 10us 6, then this is going to have an entry that's close to 10^ the 6 close to a million. So if we think about what's happening here, we're taking our noise, we're rotating it into this u space, but that doesn't change how big it is. It's just a rotation. Then we're multiplying by a million and then rotating again. So what we have is the true thing that we care about plus our noise that's been amplified potentially by a factor of a million.

And so what you see is honestly garbage in many settings because this is so small compared to our measurement noise amplified by a factor of a million. Okay. So then that means that we've got a very noisy inaccurate le squares estimate. And if we try to make predictions on new data this is really going to dominate and give us bad predictions on new data. In contrast, this will only take a minute with ridge. We have that what ridge is equal to xtranspose x plus lambda identity inverse xrpose.

And now again I'm going to put in xw star plus my epsilon. And so I'm going to get xtranspose x + lambda identity inverse xrpose x war plus xrpose x lambda identity inverse xtranspose epsilon. So when I look at this now for the first term the thing that I'm multiplying by xrpose x is no longer exactly xtranspose x inverse it's been perturbed a little bit by this lambda but if lambda is small then this will these two factors will be close to cancelling themselves out or each other out and so this will be not exactly but it'll be close to w star.

So we've got a little bit of error now that we're introducing through this lambda here. It's not going to be exactly lambda star. But we're going to make up for that small error by this being much better because now when we think about what's happening here, this is equal to we said v sigma squar + lambda identity inverse sigma transpose uranspose epsilon. So now we're taking our noise rotating into the U space like we talked about before, but now we are no longer multiplying by a million, right?

Because we're no longer dividing anything by 10us 6. The lambda is tempering that. And so we're not going to take whatever that noise is and multiply it by this factor of a million and instead we'll be mod multiplying it by something that's much smaller because of the presence of that lambda. And so this will um not blow up the same way. Um and so what we will have is a slightly erroneous estimate of W star plus some noise that's not too huge.

And overall the combination of those two things is much closer to W star than what we got when we were just doing these squares over here over somewhere. Um I lost it here than what we got over here where we didn't have that sort of bias on W star. We didn't have any error in that first term but the e second term was so huge that we lost sight of how good the first term was. Okay, we'll continue to talk about ridge regression on Thursday.

Thank you very much and have a good couple of days.