Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention (AI Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper machine learning explained transformers explained nystrom nystromformer nystromer nystrom approximation self attention attention mechanism attention is all you need transformer linear transformer linformer linear attention machine learning tutorial quadratic attention matrix approximation low rank landmark points landmarks matrix reconstruction fast attention
#transformer #nystromer #nystromformer

The Nyströmformer (or Nystromformer, Nyströmer, Nystromer), is a new drop-in replacement for approximating the Self-Attention matrix in Transformers with linear memory and time requirements. Most importantly, it uses the Nystrom-Method to subselect (or segment mean) queries and keys as so-called landmarks and uses those to reconstruct the inherently low-rank attention matrix. This is relevant for many areas of Machine Learning, especially Natural Language processing, where it enables longer sequences of text to be processed at once.

OUTLINE:
0:00 - Intro & Overview
2:30 - The Quadratic Memory Bottleneck in Self-Attention
7:20 - The Softmax Operation in Attention
11:15 - Nyström-Approximation
14:00 - Getting Around the Softmax Problem
18:05 - Intuition for Landmark Method
28:05 - Full Algorithm
30:20 - Theoretical Guarantees
35:55 - Avoiding the Large Attention Matrix
36:55 - Subsampling Keys vs Negative Sampling
43:15 - Experimental Results
47:00 - Conclusion & Comments

Paper: https://arxiv.org/abs/2102.03902
Code: https://github.com/mlpen/Nystromformer
Appendix: https://github.com/mlpen/Nystromformer/blob/main/doc/Nystromformer_Supplement.pdf
LRA Results: https://twitter.com/tanmingxing/status/1359301186734620675
Twitter lucidrains w/ author: https://twitter.com/lucidrains/status/1359597104075661312
Twitter lucidrains w/ _clashluke: https://twitter.com/_clashluke/status/1359483460851802115

Abstract:
Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences -- a topic being actively studied in the community. To address this limitation, we propose Nyströmformer -- a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with O(n) complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard Transformer. Our code is at this https URL.

Authors: Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, Vikas Singh

Links:
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/
BiliBili: https://space.bilibili.com/1824646584

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there, today we're talking about a Nyström former, a Nyström based algorithm for approximating self-attention by Jung-Yang Hsiung, Chang-Peng Cheng, Rudrazes Chakraborty, Mingxin Tan, Glenn Fung, Yin Li and Vika Singh. So this paper, yet another paper that proposes an approximation to the self-attention mechanism, to the self-attention matrix in transformer models. This time it's based on the Nyström matrix approximation. That's why the model is called Nyström former. And why it is not called the Nyströmmer, I don't know. Like, you had the chance. So I'm officially renaming this to the Nyströmmer. Okay. That's the title now. That's the model now, the Nyströmmer. By the way, if you're not in any language that has this sign or this sign, it's called an O. So O, you go O, but O. Well, it's hard to explain. In any case, as I said, this is an approximation to the self-attention matrix. The Nyströmmer method basically takes a subset of rows and columns, sorry, of keys and queries in this case, and approximates the full matrix by just using this subset. And we're going to look at how this works. But the promise is that you can scale transformers to much longer sequences without having the classic attention bottleneck that you'd have in transformers. And the results so far show are pretty good for this model. No results in single papers. You know how I feel about those. But we'll check it out. We'll go through it. If you have comments, let me know in the comments. And don't hesitate to share the video out if you like content like this. All right, let's dive in. So there is a long discussion here about transformers and this this kind of bottleneck, this quadratic memory bottleneck. And if you don't know what I'm talking about, you can go watch the video on attention is all you need or any of the transformer videos. The paper really starts down here with the introduction of self-attention. So here we're dealing with self-attention. There is also something like cross attention, like when you have an encoder and the decoder and you need to pass information from the encoder to the decoder that is not self-attention, that is called something like cross attention. Or I don't actually even know what it's called. This model, this paper deals with self-attention, though I know that LucidRains and ClashLuke on Twitter had a nice conversation about how you could do this also for cross attention. I'll link to it. Check both of these people out. Yeah. Alright, so self-attention. You have your inputs, your input signal. This is one attention layer, right? It's usually multi-head attention, but here we'll just have one head. So you have your attention layer, which takes an input X. So your X is usually some kind of a sequence and you want to transform it into another sequence. We've been here a bunch of times already and you want to know, it's probably an equally long sequence, you want to know which information do you need to pass where. So maybe this thing needs to inform those two and this thing needs to inform those three and this thing just needs to inform that one and so on. So you sort of want to transform a sequence into another sequence in the next higher layer and yeah, you want to kind of send information around so that every sequence element knows about every other relevant sequence element. The way you do this is by attention. So what you do is you construct these query key and value matrices of the attention mechanism simply by linear projection. So you can see that the X here is an input to all of them. What you do next is you this is the crucial operation, you multiply the queries by the keys. So essentially what you do is you express the keys are as our vectors and basically every sequence element is advertising what it has to offer. So the keys are vectors, something like this. Every sequence element expresses a key. The key is an encoding of what kind of information the sequence element contains. And then every sequence element also expresses a query and the query I usually draw up here. And that is what kind of information would this sequence element like to gather from its surroundings, right? And then you do the inner product, you multiply each query by each key and you can see already like this element here is probably going to receive information from this and from this because the inner product is very high between the query that this expresses and the keys that these express and so on. So you can see that you need to multiply each query by each key. That's exactly this operation over here. Query times keys. And that gives you a quadratic complexity in time and memory basically. So you have usually your query matrix and your query matrix is number of sequence elements. So your query matrix is number of sequence elements times the number of dimensions. So you have some kind of d dimensionality for your queries. And here n is the sequence length, right? So you have one query per sequence element. And row here is one query. And then you have the keys and the keys and usually write the keys as a transposed matrix are exactly the same. So they are number of sequence elements times some kind of dimensionality, inner dimensionality. Now I'm on purpose, I'm already drawing the dimensionality smaller than the number of sequence elements because that's usually the case. So the especially if you have multi head attention, the dimensionality can be lower or is often lower than the number of sequence elements and right here. And then you perform this product. And what you end up with is as we said, this n by n matrix. So this is an n by n matrix. And one element in this matrix is going to be the product, of course, of the corresponding query and key. Now the we'll get to the rank in just a second. The second notable operation here is this softmax operation. So after you've put queries and keys together, you want to perform a softmax and that is a row wise softmax, it says it down here, a row wise softmax, which means that in order to really so this is this is this year is simply queries times keys, this is not the self attention matrix yet. What you need to do is you need to put it through a softmax. And in the softmax, it's the same matrix except it's normalized by row, right? So the softmax is something like the softmax of x is something like at position i, like e to the x i divided by sum over j e to the x j. So you exponentiate every element and then you normalize by the whole row. So this is the normalization over the whole row. It's sort of like the softmax at the end of a classifier, where you just have a bunch of logits at the end of a classifier. So if this is your zero line, you have a bunch of logits one says, ah, this is class is kind of likely, this one's not, this one's super likely, but it's just a bunch of numbers, right? Your neural networks can give you a bunch of numbers. And then through the softmax, you transform that into a proper histogram, where, you know, this one is the highest probability, this one a bit more, and these two are just really low probabilities. So the same softmax operation goes for here, because ultimately, you want to know from which point do you send information where, and that is going to be a histogram, that is going to be a distribution over. So the this any sequence element sees the input, then as a distribution over where it should gather input from and how it should weigh it when it aggregates it. People have tried this without the softmax. And it just turns out that it doesn't work as well, I guess in the future, someone might come up with something that doesn't require normalization. But you know, it is what it is right now. Okay, so you need to normalize this. And you can see that in order to normalize, you actually need the whole row. So you need the whole row to pass it through the softmax. And that is sort of the bottleneck. If we could, if we were, if we didn't have the softmax right here, a lot of techniques would apply a lot of linear algebra techniques to decompose this big matrix, because if you know a little bit about matrices, then you can immediately see that if this D here, if the dimensionality is smaller than n, then this big matrix here will have a rank that's lower than n, like it will have rank at most D. And that means that you can decompose it into smaller parts, you can do a lot of tricks to not have to deal with actually n by n, things. However, the softmax operation requires you to consider these whole rows at a time. And you can't really decompose it because it's a nonlinear operation. And that's why so far, people have struggled approximating this. Now there are other techniques like the performer and the linformer and the longform, actually the longformer is just local attention. But there are other techniques, and I've made videos about most of them. So what does this paper do? They find they tackle the problem again of approximating this big matrix. So here is what they suggest. They say, look, what you can do, you can consider any matrix as sort of this collection of sub matrices. And if you look at this collection over here, it simply means that you want to divide your matrix into four sectors. So you have sector one here is A, and then this is B. And then for some reason, this is F. And then this is C. I don't know why it's F. We'll just go with the flow right here. So you can consider any matrix like this, and the goal here isn't going to be to actually do matrices that are just evenly distributed. The goal is going to be matrices that are distributed where maybe something like this. So A is super small, B and F are kind of long, tall and wide. And C is a big block, and our goal is to leave C away, to simply store A, B and F and calculate with A, B and F and then leave C. And so you can see if we can do that, that is going to be an advantage. So the Nystrom method does exactly that. It leaves away this C right here, leaves it away and replaces it by this quantity right here. So if we have A in the top left, and then F and B on the off diagonals, then we can reconstruct C. And this seems like magic. We can reconstruct C by F A inverse B. And you can see it over here how you would calculate something like this. You can immediately see that you don't run into this everything with everything bottleneck because this right now is simply N by M, and M is the size of A. And this is M by M, and this here is M by N. So unless you actually construct the full matrix, you don't need to worry about this N by N complexity because you can just calculate with the smaller matrices. So there are two things right here. If you... We'll go into why this might work in a second, but there are two things. So the first thing is that I have just said that you can do all kinds of linear algebra tricks. However, in order to calculate the softmax, you need to construct the full matrix, right? That's what we said, you need to construct the N by N in order to calculate. Actually, you just need to construct the entire row. But still, you need the full thing in order to calculate the softmax. This linear algebra trick won't get us around it by itself. And they actually say this, they say, look, if we do this, and they... This is the first kind of try at this. If we do this, we would simply, if we want to approximate the softmax matrix, we would have to have the softmax matrix first in order to then select the sub matrices from it. So we would need to calculate the full rows in order to normalize them in the softmax operation before we can do these sub matrices, which would, you know, defeat the purpose, it would defeat the purpose of the whole thing. So their plan, ultimately, is going to be, you know, when it's, it's something like this, it is here you have your X, you construct by means of keys, queries, values, you construct your sorry, by means of keys and queries, you construct your matrix. Let's call it you can Oh, sorry, you construct your matrix S by no, let's call that what we call it, you construct, let's call it keys, queries, queries, keys. You construct this, then you construct the softmax matrix, and then you approximate it. Okay, that is the naive way, let's just say and then the nice term method comes in here. And you can see that you still need to calculate the full matrix before you can approximate it. So defeats the purpose. What they're going to do is simply they're going to say, Well, can't we first approximate sort of the the the queries and keys, I'm just going to make it like this, can we just approximate this somehow? And then do the and then from that calculates the softmax approximation. And the nice term method will actually come in somewhere here. That's where I'm not really convinced because what they're ultimately end up doing is they simply end up doing the approximation inside the softmax, then applying the softmax to each of the approximation, and then calculate with these approximation. Like this, it's not really valid. It's like saying here are two operators that you really can't interchange, like you first need to construct this n by n matrix. And only then can you apply the softmax and they're just saying, Well, we're going to exchange the operators anyway. Yeah, so this this that's where the approximation is, you exchange the operation of the softmax and of the sub sampling that is necessary for the nice term approximation, this selecting rows and columns. And they do have some proofs that this converges to the true softmax matrix. But just be aware that this is where the approximation actually happens in the exchange of operations. So this is the first thing. The second thing is, why? Why does this even work? Why does the softmax at this nice term approximation even work? And here is an intuition. Okay, so intuition number one. We've already said this is low rank, this is a low rank matrix. And what does it mean to be low rank? It means that it means that the entries in the matrix are not necessarily independent from each other. So they don't carry n by n bits, let's say of information right here, or n by n floats. Even though the matrix is n by n large, you can actually describe it with less information. That's what it means to be low rank. And so it is conceivable, right, that we can just leave away some entries of the matrix and recover them from the rest, because we already know that we don't need the full numbers the full n by n numbers to describe this matrix. So if we somehow had a handle on the exact information we needed to describe it, we could leave away big chunks. Now we might not have that. So okay, so what does the nice term method do in this particular case? Now let's leave away this softmax problem for for just a second and focus on what it does. As we said, we had our queries and our keys as these kind of tall and long matrices, right? So the rows here are queries, and the columns here are keys, and we're about to do this outer product. Now we don't we don't want to do this outer product. But if we did, we would get again this n by n matrix. Now the nice term method here selects three matrices out of this. So first of all, what it does is it determines the so called landmarks. And the landmarks are a subset of queries and a subset of keys that are special, they're called landmarks. Now actually, in this paper, they calculate the landmarks by averaging over queries and keys. But for easiness, we'll simply say we'll select a subset. So right now, we're going to select actually, let's just select one query, and one key as a landmark. Okay, so these are special in some way, right? We'll see how they're special in a second. So what we're going to do is we're going to construct, first of all, we're going to construct two matrices right here, we're going to construct the query tilde times the keys. And we're going to construct the queries times the key tilde. Now the tilde, these are just the landmarks. So here you see that we're going to calculate our attention matrices. But instead of calculating the full attention between all queries and all keys, we're simply calculate the landmark query attention into all the keys, right? These are all. And we're going to calculate the attention of the landmark keys into all the queries. So we've now drastically reduced because instead of having, you know, all of the queries and all keys, we'll simply have all keys with one query and one key with all queries. So what does this give us? What can we accurately represent with these things? Well, if we have one query with all the keys, we can accurately represent this first row of the matrix right here. Because this wiggly line, I hope you can see that because you simply take the landmark query and you calculate its attention or its product, its inner product with all of the keys, which is exactly this first matrix right here, we can also faithfully represent the first column. We can represent the first column accurately by, well, I am terrible today. Because we have the first key and all the queries, its inner product with all the queries. What we cannot accurately represent is we cannot accurately represent any entry down here in this big C matrix that we choose to leave away. If we only calculate these two matrices, we don't have any entries here. Okay, nada, no. So what do we do if we actually want to know what an entry here is? Well, let's look what an entry here represents. An entry here is the interaction between query, let's say that's query, query five and key four. Okay, the key number four and query number five, we wonder how do they relate to each other? How, what's their inner product? How much are they attracted to each other? Whatever you want to call it. And we don't know. What we can do is we can ask, so query five and key four, what's their inner product? And we can say, well, we don't know. What we do know, however, is how does query five interact with key number one? Okay, so key number one and query number one are the keys and queries that we actually do have. So we do have the entry like this entry right here for query five and key number one, we have check we can calculate this. And we can also calculate another thing, namely, so this we can calculate here. And we can calculate how does key number four interact with query number one. Okay, we can also calculate that. So how does key query number one interact with key number four? Check, we can do that. And now, what we simply need to do is we need to know how does key one and query one interact. You see, we have made kind of a trip. So instead of saying how does query five interact with key four, we've asked how does query five interact with key one, then we need to know how does key one interact with query one. And from that, how does query one interact with key four, and via kind of a way around here, we have determined the interaction between query five and key four, at least in approximate. So I hope you can see that instead of going directly from here to here, as we wanted, like we wonder how much how much you know, wait, how here is a box, this is a box. I want to lift it onto this shelf. And I wonder how much force do I need to lift it onto this shelf? Now what I can do, I can do this, or I can ask, well, here are a bunch of other shelves. How much force do I need to lift it onto this, and then onto this, and then onto this, it's not going to be exactly the same, because you know, I every single time I need to put it down and pick it up again. So there is a bit of inaccuracy, but I'm going to get a pretty good idea. And that's the approximation. So instead of query five, key four, we're going to do query five, key one, query one, key four, and now since this is multiplicative, you can already see that here, technically, you know, I would have I would have this twice sort of because you can see the two columns, the column and the row are overlapping in the top left corner. So what I actually need to do is I need to divide by the interaction query one, sorry, query one, and key one. Okay, this is a one. And now I have the correct approximation. Well, is there even such a thing as a correct approximation? That's a philosophical question. In any case, that's how the Nystrom method works. So instead of calculating the entries directly, it goes this three step way, it says, well, I don't have the entry. So let me check what my the query I'm interested in does with the landmark keys. And then I check, well, what does the what do how do the landmark keys interact with the landmark queries? And then I check how do the landmark queries interact with the key that I'm interested in. And from that, I should be able to determine about how does the query I'm interested in interact with the key I'm interested in. And that now is the Nystrom approximation. So the third matrix we actually need right here is we are going to need the queries times the keys of the landmark, and we're going to invert that. So it's either a pure inverse, or actually what they do here, a pseudo inverse, just in case it is not invertible in itself. So with these three matrices, we can sort of reconstruct the whole matrix under the assumption that this is low rank, right? Which it often is. Okay, you can see that's exactly what they do. So the Nystrom approximation is going to be and this is probably too pixelish, but it's going to be the this. Oh, now the query, the interaction of all keys, sorry, all queries with the subset of keys, then the interaction just between the landmarks, and then the interaction between the landmark. Oh, no, this is query, the landmark queries and all the keys. Well, you get the idea. And as I said, they simply switch away the operators. So what they do is they calculate each of these inner matrices right here, you can see queries with landmark keys, landmark queries with keys, and landmark queries with landmark keys. And then after they calculate this, they do the softmax. And after they do the softmax, they multiply them together to get the Nystrom approximation. It's not valid because you need to do the softmax after right. Or before you even select the landmarks, one of the two so you you can choose to Nystrom approximate the query times key matrix by itself, but then you need to count you need to reconstruct before you do the softmax. Or you construct the full queries by keys, do the softmax and then approximate. And then yeah, you can decompose that but again, you need the full matrix and do the softmax. So this here is sort of an in between. And we're simply going to hope that this gives us the good matrix. Now, of course, they don't hope they actually in the supplementary material, they show the approximation. So here, this lemma, I just think it's it's so funny, because what they say is, well, the following simple result states that the Galerkin discretization of the keys and the queries with the same set of quadrature and landmark points induces the same Nystrom matrix, in particular, the same n by n Nystrom approximation s, this result agrees with the discussion in the lemma is given the input data set q and k and the corresponding landmark point set query tilde and k tilde using 1717 is what we've discussed. So 17 is you have the softmax here, then this is these this inverse in the middle, and they have a way of doing this pseudo inverse on kind of GPU. And then this is the other the landmark queries with the keys. The Nystrom approximate self attention converges to the true self attention if there exists landmark points q tilde and k tilde such that and now check this out such that the landmark is equal to the query landmark queries equal to the query and the landmark key is equal to the key for all hi and j. So essentially, so they frame it as it suggests that if the landmark points overlap sufficiently with the original data points, the approximation to self attention will be good. Well, the lemma actually says, if you choose the original data points as your queries and as your landmarks, then the approximation will be good. And I agree, like if you choose every single query, every single key as your landmarks, your approximation will be good because it won't be an approximation, it will actually just be the matrix approximating. However, in the supplementary material, which is astonishingly difficult to find, like it's on GitHub, they do show the actual magnitude of the approximation. So you can see here and here down here, they actually do have bounds on how bad this approximation is. And it doesn't seem too bad. And yeah, so the bounds are in terms of the l infinity norm, so you can make use of the fact that the softmax never goes over one and things like this. Right, so there is a bit of math behind it. I just thought it was it was funny because, you know, at the end of the day, you do switch to operators that are kind of not so you can't really switch them. And yeah, but it appears to work. So I have also if the authors are watching, if the authors are watching, there is a mistake. Where is the mistake? Where you discuss so they discuss how they do the pseudo inverse? Yeah, right here. The say their algorithm converges to the inverse to this inverse, this is the query tilde key tilde. Yep. And I think here where we say let ASP approximated by z star, there should be an inverse right here. Probably. Alright, so I hope you got how they do this approximation. All right, so they select the landmark queries and the landmark keys, they then softmax the products between landmarks and non landmarks like this. So all of these three matrices are much smaller than the original matrix, they softmax those individually, and then they calculate them together in order to recover the full attention matrix. Of course, they never do this explicitly because now, if you have three separate matrices, and the reason and it's just a linear operation, like this thing right here, then you can actually you can work with them individually, you never have to go up into the full n by n dimensions. And they do show this explicitly down here. So you can see that you have this kind of convoluted path, but ultimately, you have your input x, you construct queries, keys and values. Then you select the landmark points and they select as I said, the landmark points by segment means, so they actually average out landmark points. Sorry, they average out queries and keys to get the landmarks, which I think is smarter than just selecting a subset. I don't know, actually, but it seems okay. Then they calculate this inner matrix that they need to invert right here. This is m by m. They also calculate these two long and tall matrices, then they calculate this thing right here, which is n by m. Now if they were to calculate it together with this, it would give them back an n by n, they don't do it. However, they first calculate the product together with the values, which is ultimately what you want in order to reduce this dimensionality n right here. And then once they calculate that they go into, they only have an n by d matrix. They also add a skip connection down here to apparently stabilize training or make it faster. They do say it works without this is reminds me of the lambda layers or lambda. I don't know what it was called. But is a similar reasoning, you never go to n by n because if all of this are linear algebra operations, you can, it is valid at this point to kind of switch the order and do things such that you never have to go up to the full matrix. So the here is where they calculate the means. So you can see that the landmarks are constructed by averaging out a bunch of queries and keys. And a last thing I wanted to mention about this is maybe an intuition of why switching the softmax and the order of operation here, the thing I said is not valid, why this might actually be valid. So assume why do you need why do you need the full matrix for the softmax, because we said you have this row here, and you need to normalize over the whole row, it's valid, right? Because ultimately, you want the distribution to come out. So you need to normalize over everything in the distribution. Otherwise it won't be a valid distribution. Now you can see that this is pretty easy for one of these two, right? If we have this thing right here, if we have the queries, the landmark queries and all the keys, that will give us a matrix like this. Okay, so this is a different this is a different matrix now than the key matrix. This is simply the landmark queries. And I think I've drawn this, if we just have one landmark, let's actually have more one than one landmark, because I want to make my point. So here is landmark query one, landmark query two, and landmark query three, right? These are the subset of queries we selected, or they are the averages of queries, however you want to do it. And here is key one, sorry, key two, and so on with all the keys. Now we calculate this, do we have a problem here with the softmax? No, we don't, because the softmax goes over the row. And in this matrix, at least we can, you know, we have the whole row, so we can normalize across the row, not a problem. This gives us a valid distribution for these particular queries. Where we do get a problem is when we have this matrix, this matrix is the tall matrix, and the tall matrix is all the queries with the landmark keys. So here is query one, query two, and so on. And here is landmark key one, landmark key two, and landmark key three. Now we have a problem, because if we want to normalize by row, we're missing a whole bunch of keys. Now why could this still work? Now it could still work, because as we said, these things here, they're actually the means of all the keys. So this is the mean of the first third of the keys, this is the mean of the second third of all the keys, and so on. So that might be one reason, but another reason comes from word embeddings. So if you know word embeddings, then you know that if I want to train word embeddings, what I do is I say like, a cat sat on the mat. And if I want to train word embeddings in one particular word to vec, what I do is I take a particular word, like this word here, sat, the word sat, and I try to predict the surrounding words. So I try to predict the word cat from sat. Now in order to predict this correctly, I need to know how often cat appears in cat appears around sat as compared to every other word in the vocabulary. So I need to know the connection like that the count, let's say C is the count function, I need to know how often does sat and cat appear together in this context, sorry, in context. And I need to divide it by everything else that the word sat could, here x, by everything else that the word sat could appear with, right, by every other possible context. Now that is not possible usually. So what we do is we do this thing called negative sampling. And in negative sampling, we simply say something like, I'm just going to get a bunch of other contexts that I randomly sample from the data set. And I'm going to normalize this by these randomly sampled data points. So I'm going to replace the whole of the denominator by a randomly sampled subset. And that's going to be good enough. And this is a lot of what contrastive methods do as well. So if I want to, let's say classify, we've seen this a lot, yeah, with with these contrastive methods, if I want to classify a data point x into, you know, wherever it needs to go, what I can do instead is I can simply say, well, I have a data point y right here. And I know x and y are somehow related to each other. So I want to make them close together. And I'm going to simply sample a bunch of other data points z1, z2, z3, z4. And I'm going to make those repel each other. And that's going to be my objective. So instead of comparing with the whole data set, I'm simply going to sub sample a set of negative samples randomly. And that's going to be my normalization in in the denominator. Maybe something like this is happening right here, right? By sub sampling a set of queries, and then simply normalizing over those, you do have actually an approximation of the whole distribution. So maybe it's not that bad what they do right here. Okay. So those are my thoughts on the Nystrom approximation. They do a bunch of experiments like they here compare matrices how they how they look. They do a complexity analysis. And naturally, what you'll have is instead of having the n squared complexity, you basically go down to an O of n complexity. You do have this m quantity quite a bit in here. But since m is way smaller than n, because you usually select just a small subset of landmarks, you get away you get away with just calling it O of n. They show how this relates to other transformers, especially the linformer and the longformer in terms of memory consumption. So here you can see as you scale up. So in 512 sequence length, the original transformer has 54 megabytes and the Nystromer the Nystromer has 35 in this case. If you select I think the 64 is you select 64 landmarks out of the 512. So it's not a big saving. But as you go up here, you see you can go up to a sequence length of 8000, where the original transformer will take 10 gigabytes of memory, whereas the Nystromer only takes 300 megabytes. So the scaling here is very smooth, it's quite linear, as you can see, and also the time required to calculate it gives you a big big speed up. And it's about the same order I would say here as maybe the the linformer, because the linformer also, it compresses down the sequence length through projection, if I remember correctly. However, they do compare to these other models in terms of and this I think is the an interesting result. And this is not in the paper yet, it just was tweeted by one of the authors. This is the result in the long range arena. So this is a sequence tasks where they are constructed such that long range dependencies in the text that you analyze are of importance. And you can see right here that the the standard transformer does, you know, okay, but it has this this big memory complexity. And the Nystromer is able to match that performance. Now we don't know yet if the Nystromer here has you know, what kind of settings it has, how much memory is really saved. But I assume that quite a bit of memory is saved. And it still retains that capability of doing these long range dependencies, as you can see right here, the other models that use the complexity of the attention matrix such as the performer, which uses random Fourier features, the Linformer, which projects down the sequence length, and the reformer, which if I remember correctly, uses locality sensitive hashing and isn't so that's n log n and not O of n, they all perform not as well. As always take experiments with a grain of salt right here, we don't know yet. So this axis isn't, you know, it's not centered at zero. So it looks more dramatic than it really is. However, it is it these are promising results. And also check out the appendix if you want to know a bit more about the math, because so in my opinion, you know, these kind of bounds right here, they should be in the paper because right now the paper just says, you know, if you use all the queries and keys as landmarks, then you're good. But you know, what does that give you? And yeah, I fully expect this graphic here also to be part of the paper. Because I think that's, that's the most important result of the paper. Yeah, there is more to the paper, but I don't want to drag this video on forever. Thanks for listening, if you have any sort of comments, if it was not understandable, I realized we've skipped over a bunch of things and I rambled a bit. Just let me know. And other than that, there is a link to the code right here. The code is super simple. It's just you know, what they describe in the algorithm. There is a link to the supplement. I'll leave this all in the description. And I'll see you next time. Bye bye.
 Hi there, today we're talking about a Nyström former, a Nyström based algorithm for approximating
 self-attention by Jung-Yang Hsiung, Chang-Peng Cheng, Rudrazes Chakraborty, Mingxin Tan,
 Glenn Fung, Yin Li and Vika Singh.
 So this paper, yet another paper that proposes an approximation to the self-attention mechanism,
 to the self-attention matrix in transformer models.
 This time it's based on the Nyström matrix approximation.
 That's why the model is called Nyström former.
 And why it is not called the Nyströmmer, I don't know.
 Like, you had the chance.
 So I'm officially renaming this to the Nyströmmer.
 Okay.
 That's the title now.
 That's the model now, the Nyströmmer.
 By the way, if you're not in any language that has this sign or this sign, it's called an
 O.
 So O, you go O, but O.
 Well, it's hard to explain.
 In any case, as I said, this is an approximation to the self-attention matrix.
 The Nyströmmer method basically takes a subset of rows and columns, sorry, of keys and queries
 in this case, and approximates the full matrix by just using this subset.
 And we're going to look at how this works.
 But the promise is that you can scale transformers to much longer sequences without having the
 classic attention bottleneck that you'd have in transformers.
 And the results so far show are pretty good for this model.
 No results in single papers.
 You know how I feel about those.
 But we'll check it out.
 We'll go through it.
 If you have comments, let me know in the comments.
 And don't hesitate to share the video out if you like content like this.
 All right, let's dive in.
 So there is a long discussion here about transformers and this this kind of bottleneck, this quadratic
 memory bottleneck.
 And if you don't know what I'm talking about, you can go watch the video on attention is
 all you need or any of the transformer videos.
 The paper really starts down here with the introduction of self-attention.
 So here we're dealing with self-attention.
 There is also something like cross attention, like when you have an encoder and the decoder
 and you need to pass information from the encoder to the decoder that is not self-attention,
 that is called something like cross attention.
 Or I don't actually even know what it's called.
 This model, this paper deals with self-attention, though I know that LucidRains and ClashLuke
 on Twitter had a nice conversation about how you could do this also for cross attention.
 I'll link to it.
 Check both of these people out.
 Yeah.
 Alright, so self-attention.
 You have your inputs, your input signal.
 This is one attention layer, right?
 It's usually multi-head attention, but here we'll just have one head.
 So you have your attention layer, which takes an input X.
 So your X is usually some kind of a sequence and you want to transform it into another
 sequence.
 We've been here a bunch of times already and you want to know, it's probably an equally
 long sequence, you want to know which information do you need to pass where.
 So maybe this thing needs to inform those two and this thing needs to inform those three
 and this thing just needs to inform that one and so on.
 So you sort of want to transform a sequence into another sequence in the next higher layer
 and yeah, you want to kind of send information around so that every sequence element knows
 about every other relevant sequence element.
 The way you do this is by attention.
 So what you do is you construct these query key and value matrices of the attention mechanism
 simply by linear projection.
 So you can see that the X here is an input to all of them.
 What you do next is you this is the crucial operation, you multiply the queries by the
 keys.
 So essentially what you do is you express the keys are as our vectors and basically
 every sequence element is advertising what it has to offer.
 So the keys are vectors, something like this.
 Every sequence element expresses a key.
 The key is an encoding of what kind of information the sequence element contains.
 And then every sequence element also expresses a query and the query I usually draw up here.
 And that is what kind of information would this sequence element like to gather from
 its surroundings, right?
 And then you do the inner product, you multiply each query by each key and you can see already
 like this element here is probably going to receive information from this and from this
 because the inner product is very high between the query that this expresses and the keys
 that these express and so on.
 So you can see that you need to multiply each query by each key.
 That's exactly this operation over here.
 Query times keys.
 And that gives you a quadratic complexity in time and memory basically.
 So you have usually your query matrix and your query matrix is number of sequence elements.
 So your query matrix is number of sequence elements times the number of dimensions.
 So you have some kind of d dimensionality for your queries.
 And here n is the sequence length, right?
 So you have one query per sequence element.
 And row here is one query.
 And then you have the keys and the keys and usually write the keys as a transposed matrix
 are exactly the same.
 So they are number of sequence elements times some kind of dimensionality, inner dimensionality.
 Now I'm on purpose, I'm already drawing the dimensionality smaller than the number of
 sequence elements because that's usually the case.
 So the especially if you have multi head attention, the dimensionality can be lower or is often
 lower than the number of sequence elements and right here.
 And then you perform this product.
 And what you end up with is as we said, this n by n matrix.
 So this is an n by n matrix.
 And one element in this matrix is going to be the product, of course, of the corresponding
 query and key.
 Now the we'll get to the rank in just a second.
 The second notable operation here is this softmax operation.
 So after you've put queries and keys together, you want to perform a softmax and that is
 a row wise softmax, it says it down here, a row wise softmax, which means that in order
 to really so this is this is this year is simply queries times keys, this is not the
 self attention matrix yet.
 What you need to do is you need to put it through a softmax.
 And in the softmax, it's the same matrix except it's normalized by row, right?
 So the softmax is something like the softmax of x is something like at position i, like
 e to the x i divided by sum over j e to the x j.
 So you exponentiate every element and then you normalize by the whole row.
 So this is the normalization over the whole row.
 It's sort of like the softmax at the end of a classifier, where you just have a bunch
 of logits at the end of a classifier.
 So if this is your zero line, you have a bunch of logits one says, ah, this is class is kind
 of likely, this one's not, this one's super likely, but it's just a bunch of numbers,
 right?
 Your neural networks can give you a bunch of numbers.
 And then through the softmax, you transform that into a proper histogram, where, you know,
 this one is the highest probability, this one a bit more, and these two are just really
 low probabilities.
 So the same softmax operation goes for here, because ultimately, you want to know from
 which point do you send information where, and that is going to be a histogram, that
 is going to be a distribution over.
 So the this any sequence element sees the input, then as a distribution over where it
 should gather input from and how it should weigh it when it aggregates it.
 People have tried this without the softmax.
 And it just turns out that it doesn't work as well, I guess in the future, someone might
 come up with something that doesn't require normalization.
 But you know, it is what it is right now.
 Okay, so you need to normalize this.
 And you can see that in order to normalize, you actually need the whole row.
 So you need the whole row to pass it through the softmax.
 And that is sort of the bottleneck.
 If we could, if we were, if we didn't have the softmax right here, a lot of techniques
 would apply a lot of linear algebra techniques to decompose this big matrix, because if you
 know a little bit about matrices, then you can immediately see that if this D here, if
 the dimensionality is smaller than n, then this big matrix here will have a rank that's
 lower than n, like it will have rank at most D. And that means that you can decompose it
 into smaller parts, you can do a lot of tricks to not have to deal with actually n by n,
 things.
 However, the softmax operation requires you to consider these whole rows at a time.
 And you can't really decompose it because it's a nonlinear operation.
 And that's why so far, people have struggled approximating this.
 Now there are other techniques like the performer and the linformer and the longform, actually
 the longformer is just local attention.
 But there are other techniques, and I've made videos about most of them.
 So what does this paper do?
 They find they tackle the problem again of approximating this big matrix.
 So here is what they suggest.
 They say, look, what you can do, you can consider any matrix as sort of this collection of sub
 matrices.
 And if you look at this collection over here, it simply means that you want to divide your
 matrix into four sectors.
 So you have sector one here is A, and then this is B. And then for some reason, this
 is F. And then this is C. I don't know why it's F. We'll just go with the flow right
 here.
 So you can consider any matrix like this, and the goal here isn't going to be to actually
 do matrices that are just evenly distributed.
 The goal is going to be matrices that are distributed where maybe something like this.
 So A is super small, B and F are kind of long, tall and wide.
 And C is a big block, and our goal is to leave C away, to simply store A, B and F and calculate
 with A, B and F and then leave C. And so you can see if we can do that, that is going to
 be an advantage.
 So the Nystrom method does exactly that.
 It leaves away this C right here, leaves it away and replaces it by this quantity right
 here.
 So if we have A in the top left, and then F and B on the off diagonals, then we can
 reconstruct C. And this seems like magic.
 We can reconstruct C by F A inverse B.
 And you can see it over here how you would calculate something like this.
 You can immediately see that you don't run into this everything with everything bottleneck
 because this right now is simply N by M, and M is the size of A. And this is M by M, and
 this here is M by N.
 So unless you actually construct the full matrix, you don't need to worry about this
 N by N complexity because you can just calculate with the smaller matrices.
 So there are two things right here.
 If you...
 We'll go into why this might work in a second, but there are two things.
 So the first thing is that I have just said that you can do all kinds of linear algebra
 tricks.
 However, in order to calculate the softmax, you need to construct the full matrix, right?
 That's what we said, you need to construct the N by N in order to calculate.
 Actually, you just need to construct the entire row.
 But still, you need the full thing in order to calculate the softmax.
 This linear algebra trick won't get us around it by itself.
 And they actually say this, they say, look, if we do this, and they...
 This is the first kind of try at this.
 If we do this, we would simply, if we want to approximate the softmax matrix, we would
 have to have the softmax matrix first in order to then select the sub matrices from it.
 So we would need to calculate the full rows in order to normalize them in the softmax
 operation before we can do these sub matrices, which would, you know, defeat the purpose,
 it would defeat the purpose of the whole thing.
 So their plan, ultimately, is going to be, you know, when it's, it's something like this,
 it is here you have your X, you construct by means of keys, queries, values, you construct
 your sorry, by means of keys and queries, you construct your matrix.
 Let's call it you can Oh, sorry, you construct your matrix S by no, let's call that what
 we call it, you construct, let's call it keys, queries, queries, keys.
 You construct this, then you construct the softmax matrix, and then you approximate it.
 Okay, that is the naive way, let's just say and then the nice term method comes in here.
 And you can see that you still need to calculate the full matrix before you can approximate
 it.
 So defeats the purpose.
 What they're going to do is simply they're going to say, Well, can't we first approximate
 sort of the the the queries and keys, I'm just going to make it like this, can we just
 approximate this somehow?
 And then do the and then from that calculates the softmax approximation.
 And the nice term method will actually come in somewhere here.
 That's where I'm not really convinced because what they're ultimately end up doing is they
 simply end up doing the approximation inside the softmax, then applying the softmax to
 each of the approximation, and then calculate with these approximation.
 Like this, it's not really valid.
 It's like saying here are two operators that you really can't interchange, like you first
 need to construct this n by n matrix.
 And only then can you apply the softmax and they're just saying, Well, we're going to
 exchange the operators anyway.
 Yeah, so this this that's where the approximation is, you exchange the operation of the softmax
 and of the sub sampling that is necessary for the nice term approximation, this selecting
 rows and columns.
 And they do have some proofs that this converges to the true softmax matrix.
 But just be aware that this is where the approximation actually happens in the exchange of operations.
 So this is the first thing.
 The second thing is, why?
 Why does this even work?
 Why does the softmax at this nice term approximation even work?
 And here is an intuition.
 Okay, so intuition number one.
 We've already said this is low rank, this is a low rank matrix.
 And what does it mean to be low rank?
 It means that it means that the entries in the matrix are not necessarily independent
 from each other.
 So they don't carry n by n bits, let's say of information right here, or n by n floats.
 Even though the matrix is n by n large, you can actually describe it with less information.
 That's what it means to be low rank.
 And so it is conceivable, right, that we can just leave away some entries of the matrix
 and recover them from the rest, because we already know that we don't need the full numbers
 the full n by n numbers to describe this matrix.
 So if we somehow had a handle on the exact information we needed to describe it, we could
 leave away big chunks.
 Now we might not have that.
 So okay, so what does the nice term method do in this particular case?
 Now let's leave away this softmax problem for for just a second and focus on what it
 does.
 As we said, we had our queries and our keys as these kind of tall and long matrices, right?
 So the rows here are queries, and the columns here are keys, and we're about to do this
 outer product.
 Now we don't we don't want to do this outer product.
 But if we did, we would get again this n by n matrix.
 Now the nice term method here selects three matrices out of this.
 So first of all, what it does is it determines the so called landmarks.
 And the landmarks are a subset of queries and a subset of keys that are special, they're
 called landmarks.
 Now actually, in this paper, they calculate the landmarks by averaging over queries and
 keys.
 But for easiness, we'll simply say we'll select a subset.
 So right now, we're going to select actually, let's just select one query, and one key as
 a landmark.
 Okay, so these are special in some way, right?
 We'll see how they're special in a second.
 So what we're going to do is we're going to construct, first of all, we're going to construct
 two matrices right here, we're going to construct the query tilde times the keys.
 And we're going to construct the queries times the key tilde.
 Now the tilde, these are just the landmarks.
 So here you see that we're going to calculate our attention matrices.
 But instead of calculating the full attention between all queries and all keys, we're simply
 calculate the landmark query attention into all the keys, right?
 These are all.
 And we're going to calculate the attention of the landmark keys into all the queries.
 So we've now drastically reduced because instead of having, you know, all of the queries and
 all keys, we'll simply have all keys with one query and one key with all queries.
 So what does this give us?
 What can we accurately represent with these things?
 Well, if we have one query with all the keys, we can accurately represent this first row
 of the matrix right here.
 Because this wiggly line, I hope you can see that because you simply take the landmark
 query and you calculate its attention or its product, its inner product with all of the
 keys, which is exactly this first matrix right here, we can also faithfully represent the
 first column.
 We can represent the first column accurately by, well, I am terrible today.
 Because we have the first key and all the queries, its inner product with all the queries.
 What we cannot accurately represent is we cannot accurately represent any entry down
 here in this big C matrix that we choose to leave away.
 If we only calculate these two matrices, we don't have any entries here.
 Okay, nada, no.
 So what do we do if we actually want to know what an entry here is?
 Well, let's look what an entry here represents.
 An entry here is the interaction between query, let's say that's query, query five and key
 four.
 Okay, the key number four and query number five, we wonder how do they relate to each
 other?
 How, what's their inner product?
 How much are they attracted to each other?
 Whatever you want to call it.
 And we don't know.
 What we can do is we can ask, so query five and key four, what's their inner product?
 And we can say, well, we don't know.
 What we do know, however, is how does query five interact with key number one?
 Okay, so key number one and query number one are the keys and queries that we actually
 do have.
 So we do have the entry like this entry right here for query five and key number one, we
 have check we can calculate this.
 And we can also calculate another thing, namely, so this we can calculate here.
 And we can calculate how does key number four interact with query number one.
 Okay, we can also calculate that.
 So how does key query number one interact with key number four?
 Check, we can do that.
 And now, what we simply need to do is we need to know how does key one and query one interact.
 You see, we have made kind of a trip.
 So instead of saying how does query five interact with key four, we've asked how does query
 five interact with key one, then we need to know how does key one interact with query
 one.
 And from that, how does query one interact with key four, and via kind of a way around
 here, we have determined the interaction between query five and key four, at least in approximate.
 So I hope you can see that instead of going directly from here to here, as we wanted,
 like we wonder how much how much you know, wait, how here is a box, this is a box.
 I want to lift it onto this shelf.
 And I wonder how much force do I need to lift it onto this shelf?
 Now what I can do, I can do this, or I can ask, well, here are a bunch of other shelves.
 How much force do I need to lift it onto this, and then onto this, and then onto this, it's
 not going to be exactly the same, because you know, I every single time I need to put
 it down and pick it up again.
 So there is a bit of inaccuracy, but I'm going to get a pretty good idea.
 And that's the approximation.
 So instead of query five, key four, we're going to do query five, key one, query one,
 key four, and now since this is multiplicative, you can already see that here, technically,
 you know, I would have I would have this twice sort of because you can see the two columns,
 the column and the row are overlapping in the top left corner.
 So what I actually need to do is I need to divide by the interaction query one, sorry,
 query one, and key one.
 Okay, this is a one.
 And now I have the correct approximation.
 Well, is there even such a thing as a correct approximation?
 That's a philosophical question.
 In any case, that's how the Nystrom method works.
 So instead of calculating the entries directly, it goes this three step way, it says, well,
 I don't have the entry.
 So let me check what my the query I'm interested in does with the landmark keys.
 And then I check, well, what does the what do how do the landmark keys interact with
 the landmark queries?
 And then I check how do the landmark queries interact with the key that I'm interested
 in.
 And from that, I should be able to determine about how does the query I'm interested in
 interact with the key I'm interested in.
 And that now is the Nystrom approximation.
 So the third matrix we actually need right here is we are going to need the queries times
 the keys of the landmark, and we're going to invert that.
 So it's either a pure inverse, or actually what they do here, a pseudo inverse, just
 in case it is not invertible in itself.
 So with these three matrices, we can sort of reconstruct the whole matrix under the
 assumption that this is low rank, right?
 Which it often is.
 Okay, you can see that's exactly what they do.
 So the Nystrom approximation is going to be and this is probably too pixelish, but
 it's going to be the this.
 Oh, now the query, the interaction of all keys, sorry, all queries with the subset of
 keys, then the interaction just between the landmarks, and then the interaction between
 the landmark.
 Oh, no, this is query, the landmark queries and all the keys.
 Well, you get the idea.
 And as I said, they simply switch away the operators.
 So what they do is they calculate each of these inner matrices right here, you can see
 queries with landmark keys, landmark queries with keys, and landmark queries with landmark
 keys.
 And then after they calculate this, they do the softmax.
 And after they do the softmax, they multiply them together to get the Nystrom approximation.
 It's not valid because you need to do the softmax after right.
 Or before you even select the landmarks, one of the two so you you can choose to Nystrom
 approximate the query times key matrix by itself, but then you need to count you need
 to reconstruct before you do the softmax.
 Or you construct the full queries by keys, do the softmax and then approximate.
 And then yeah, you can decompose that but again, you need the full matrix and do the
 softmax.
 So this here is sort of an in between.
 And we're simply going to hope that this gives us the good matrix.
 Now, of course, they don't hope they actually in the supplementary material, they show the
 approximation.
 So here, this lemma, I just think it's it's so funny, because what they say is, well,
 the following simple result states that the Galerkin discretization of the keys and the
 queries with the same set of quadrature and landmark points induces the same Nystrom matrix,
 in particular, the same n by n Nystrom approximation s, this result agrees with the discussion
 in the lemma is given the input data set q and k and the corresponding landmark point
 set query tilde and k tilde using 1717 is what we've discussed.
 So 17 is you have the softmax here, then this is these this inverse in the middle, and they
 have a way of doing this pseudo inverse on kind of GPU.
 And then this is the other the landmark queries with the keys.
 The Nystrom approximate self attention converges to the true self attention if there exists
 landmark points q tilde and k tilde such that and now check this out such that the landmark
 is equal to the query landmark queries equal to the query and the landmark key is equal
 to the key for all hi and j.
 So essentially, so they frame it as it suggests that if the landmark points overlap sufficiently
 with the original data points, the approximation to self attention will be good.
 Well, the lemma actually says, if you choose the original data points as your queries and
 as your landmarks, then the approximation will be good.
 And I agree, like if you choose every single query, every single key as your landmarks,
 your approximation will be good because it won't be an approximation, it will actually
 just be the matrix approximating.
 However, in the supplementary material, which is astonishingly difficult to find, like it's
 on GitHub, they do show the actual magnitude of the approximation.
 So you can see here and here down here, they actually do have bounds on how bad this approximation
 is.
 And it doesn't seem too bad.
 And yeah, so the bounds are in terms of the l infinity norm, so you can make use of the
 fact that the softmax never goes over one and things like this.
 Right, so there is a bit of math behind it.
 I just thought it was it was funny because, you know, at the end of the day, you do switch
 to operators that are kind of not so you can't really switch them.
 And yeah, but it appears to work.
 So I have also if the authors are watching, if the authors are watching, there is a mistake.
 Where is the mistake?
 Where you discuss so they discuss how they do the pseudo inverse?
 Yeah, right here.
 The say their algorithm converges to the inverse to this inverse, this is the query tilde key
 tilde.
 Yep.
 And I think here where we say let ASP approximated by z star, there should be an inverse right
 here.
 Probably.
 Alright, so I hope you got how they do this approximation.
 All right, so they select the landmark queries and the landmark keys, they then softmax the
 products between landmarks and non landmarks like this.
 So all of these three matrices are much smaller than the original matrix, they softmax those
 individually, and then they calculate them together in order to recover the full attention
 matrix.
 Of course, they never do this explicitly because now, if you have three separate matrices,
 and the reason and it's just a linear operation, like this thing right here, then you can actually
 you can work with them individually, you never have to go up into the full n by n dimensions.
 And they do show this explicitly down here.
 So you can see that you have this kind of convoluted path, but ultimately, you have
 your input x, you construct queries, keys and values.
 Then you select the landmark points and they select as I said, the landmark points by segment
 means, so they actually average out landmark points.
 Sorry, they average out queries and keys to get the landmarks, which I think is smarter
 than just selecting a subset.
 I don't know, actually, but it seems okay.
 Then they calculate this inner matrix that they need to invert right here.
 This is m by m.
 They also calculate these two long and tall matrices, then they calculate this thing right
 here, which is n by m.
 Now if they were to calculate it together with this, it would give them back an n by
 n, they don't do it.
 However, they first calculate the product together with the values, which is ultimately
 what you want in order to reduce this dimensionality n right here.
 And then once they calculate that they go into, they only have an n by d matrix.
 They also add a skip connection down here to apparently stabilize training or make it
 faster.
 They do say it works without this is reminds me of the lambda layers or lambda.
 I don't know what it was called.
 But is a similar reasoning, you never go to n by n because if all of this are linear algebra
 operations, you can, it is valid at this point to kind of switch the order and do things
 such that you never have to go up to the full matrix.
 So the here is where they calculate the means.
 So you can see that the landmarks are constructed by averaging out a bunch of queries and keys.
 And a last thing I wanted to mention about this is maybe an intuition of why switching
 the softmax and the order of operation here, the thing I said is not valid, why this might
 actually be valid.
 So assume why do you need why do you need the full matrix for the softmax, because we
 said you have this row here, and you need to normalize over the whole row, it's valid,
 right?
 Because ultimately, you want the distribution to come out.
 So you need to normalize over everything in the distribution.
 Otherwise it won't be a valid distribution.
 Now you can see that this is pretty easy for one of these two, right?
 If we have this thing right here, if we have the queries, the landmark queries and all
 the keys, that will give us a matrix like this.
 Okay, so this is a different this is a different matrix now than the key matrix.
 This is simply the landmark queries.
 And I think I've drawn this, if we just have one landmark, let's actually have more one
 than one landmark, because I want to make my point.
 So here is landmark query one, landmark query two, and landmark query three, right?
 These are the subset of queries we selected, or they are the averages of queries, however
 you want to do it.
 And here is key one, sorry, key two, and so on with all the keys.
 Now we calculate this, do we have a problem here with the softmax?
 No, we don't, because the softmax goes over the row.
 And in this matrix, at least we can, you know, we have the whole row, so we can normalize
 across the row, not a problem.
 This gives us a valid distribution for these particular queries.
 Where we do get a problem is when we have this matrix, this matrix is the tall matrix,
 and the tall matrix is all the queries with the landmark keys.
 So here is query one, query two, and so on.
 And here is landmark key one, landmark key two, and landmark key three.
 Now we have a problem, because if we want to normalize by row, we're missing a whole
 bunch of keys.
 Now why could this still work?
 Now it could still work, because as we said, these things here, they're actually the means
 of all the keys.
 So this is the mean of the first third of the keys, this is the mean of the second third
 of all the keys, and so on.
 So that might be one reason, but another reason comes from word embeddings.
 So if you know word embeddings, then you know that if I want to train word embeddings, what
 I do is I say like, a cat sat on the mat.
 And if I want to train word embeddings in one particular word to vec, what I do is I
 take a particular word, like this word here, sat, the word sat, and I try to predict the
 surrounding words.
 So I try to predict the word cat from sat.
 Now in order to predict this correctly, I need to know how often cat appears in cat
 appears around sat as compared to every other word in the vocabulary.
 So I need to know the connection like that the count, let's say C is the count function,
 I need to know how often does sat and cat appear together in this context, sorry, in
 context.
 And I need to divide it by everything else that the word sat could, here x, by everything
 else that the word sat could appear with, right, by every other possible context.
 Now that is not possible usually.
 So what we do is we do this thing called negative sampling.
 And in negative sampling, we simply say something like, I'm just going to get a bunch of other
 contexts that I randomly sample from the data set.
 And I'm going to normalize this by these randomly sampled data points.
 So I'm going to replace the whole of the denominator by a randomly sampled subset.
 And that's going to be good enough.
 And this is a lot of what contrastive methods do as well.
 So if I want to, let's say classify, we've seen this a lot, yeah, with with these contrastive
 methods, if I want to classify a data point x into, you know, wherever it needs to go,
 what I can do instead is I can simply say, well, I have a data point y right here.
 And I know x and y are somehow related to each other.
 So I want to make them close together.
 And I'm going to simply sample a bunch of other data points z1, z2, z3, z4.
 And I'm going to make those repel each other.
 And that's going to be my objective.
 So instead of comparing with the whole data set, I'm simply going to sub sample a set
 of negative samples randomly.
 And that's going to be my normalization in in the denominator.
 Maybe something like this is happening right here, right?
 By sub sampling a set of queries, and then simply normalizing over those, you do have
 actually an approximation of the whole distribution.
 So maybe it's not that bad what they do right here.
 Okay.
 So those are my thoughts on the Nystrom approximation.
 They do a bunch of experiments like they here compare matrices how they how they look.
 They do a complexity analysis.
 And naturally, what you'll have is instead of having the n squared complexity, you basically
 go down to an O of n complexity.
 You do have this m quantity quite a bit in here.
 But since m is way smaller than n, because you usually select just a small subset of
 landmarks, you get away you get away with just calling it O of n.
 They show how this relates to other transformers, especially the linformer and the longformer
 in terms of memory consumption.
 So here you can see as you scale up.
 So in 512 sequence length, the original transformer has 54 megabytes and the Nystromer the Nystromer
 has 35 in this case.
 If you select I think the 64 is you select 64 landmarks out of the 512.
 So it's not a big saving.
 But as you go up here, you see you can go up to a sequence length of 8000, where the
 original transformer will take 10 gigabytes of memory, whereas the Nystromer only takes
 300 megabytes.
 So the scaling here is very smooth, it's quite linear, as you can see, and also the time
 required to calculate it gives you a big big speed up.
 And it's about the same order I would say here as maybe the the linformer, because the
 linformer also, it compresses down the sequence length through projection, if I remember correctly.
 However, they do compare to these other models in terms of and this I think is the an interesting
 result.
 And this is not in the paper yet, it just was tweeted by one of the authors.
 This is the result in the long range arena.
 So this is a sequence tasks where they are constructed such that long range dependencies
 in the text that you analyze are of importance.
 And you can see right here that the the standard transformer does, you know, okay, but it has
 this this big memory complexity.
 And the Nystromer is able to match that performance.
 Now we don't know yet if the Nystromer here has you know, what kind of settings it has,
 how much memory is really saved.
 But I assume that quite a bit of memory is saved.
 And it still retains that capability of doing these long range dependencies, as you can
 see right here, the other models that
 use the complexity of the attention matrix such as the performer, which uses random Fourier
 features, the Linformer, which projects down the sequence length, and the reformer, which
 if I remember correctly, uses locality sensitive hashing and isn't so that's n log n and not
 O of n, they all perform not as well.
 As always take experiments with a grain of salt right here, we don't know yet.
 So this axis isn't, you know, it's not centered at zero.
 So it looks more dramatic than it really is.
 However, it is it these are promising results.
 And also check out the appendix if you want to know a bit more about the math, because
 so in my opinion, you know, these kind of bounds right here, they should be in the paper
 because right now the paper just says, you know, if you use all the queries and keys
 as landmarks, then you're good.
 But you know, what does that give you?
 And yeah, I fully expect this graphic here also to be part of the paper.
 Because I think that's, that's the most important result of the paper.
 Yeah, there is more to the paper, but I don't want to drag this video on forever.
 Thanks for listening, if you have any sort of comments, if it was not understandable,
 I realized we've skipped over a bunch of things and I rambled a bit.
 Just let me know.
 And other than that, there is a link to the code right here.
 The code is super simple.
 It's just you know, what they describe in the algorithm.
 There is a link to the supplement.
 I'll leave this all in the description.
 And I'll see you next time.
 Bye bye.