LambdaNetworks: Modeling long-range Interactions without Attention (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper attention attention mechanism lambda lambdaresnet residual networks local attention quadratic memory transformer transformers keys values queries architecture input size iclr lambdanet lambdanets lambdaresnets efficientnet tradeoff routing linear function functional programming
#ai #research #attention

Transformers, having already captured NLP, have recently started to take over the field of Computer Vision. So far, the size of images as input has been challenging, as the Transformers' Attention Mechanism's memory requirements grows quadratic in its input size. LambdaNetworks offer a way around this requirement and capture long-range interactions without the need to build expensive attention maps. They reach a new state-of-the-art in ImageNet and compare favorably to both Transformers and CNNs in terms of efficiency.

OUTLINE:
0:00 - Introduction & Overview
6:25 - Attention Mechanism Memory Requirements
9:30 - Lambda Layers vs Attention Layers
17:10 - How Lambda Layers Work
31:50 - Attention Re-Appears in Lambda Layers
40:20 - Positional Encodings
51:30 - Extensions and Experimental Comparisons
58:00 - Code

Paper: https://openreview.net/forum?id=xTJEN-ggl1b
Lucidrains' Code: https://github.com/lucidrains/lambda-networks

Abstract:
We present a general framework for capturing long-range interactions between an input and structured contextual information (e.g. a pixel surrounded by other pixels). Our method, called the lambda layer, captures such interactions by transforming available contexts into linear functions,  termed lambdas,  and applying these linear functions to each input separately.  Lambda layers are versatile and may be implemented to model content and position-based interactions in global, local or masked contexts.  As they bypass the need for expensive attention maps, lambda layers can routinely be applied to inputs of length in the thousands, en-abling their applications to long sequences or high-resolution images. The resulting neural network architectures, LambdaNetworks, are computationally efficient and simple to implement using direct calls to operations available in modern neural network libraries.  Experiments on ImageNet classification and COCO object detection  and  instance  segmentation  demonstrate  that  LambdaNetworks  significantly  outperform  their  convolutional  and  attentional  counterparts  while  being more computationally efficient. Finally, we introduce LambdaResNets, a family of LambdaNetworks, that considerably improve the speed-accuracy tradeoff of image classification models. LambdaResNets reach state-of-the-art accuracies on ImageNet while being ∼4.5x faster than the popular EfficientNets on modern machine learning accelerators.

Authors: Anonymous

Links:
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/

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
 Another day, another state-of-the-art result in machine learning land on ImageNet. This time coming from a thing called Lambda ResNets. As you can see here, it outperforms EfficientNets and ResNets right here, not only in terms of top one accuracy, but also in terms of the trade-off between accuracy and training time. Here it says Lambda ResNets are about 4.5 times faster than EfficientNets and substantially improve the speed accuracy trade-off of image classification models across different scales. So this is something new that we have not seen in recent times. In recent times we've seen like transformers take over image classification and so on, but it came either with downsampling the image like this 16 by 16 patches and so on, or just throwing massive amounts of data at it or massive amounts of compute. This paper here promises that they have something that's more efficient and it can reach good accuracy or for the same efficiency can reach better accuracy. So today we're going to look at this paper, Lambda Networks Modeling Long Range Interactions Without Attention by Anonymous Authors. It's under review at ICLR 2021. I'm not going to de-anonymize this paper. Well mostly because this one is a bit harder and would require a bit of research, but also because I think I've made my point. I remain that double blind reviewing isn't really what it's set out to be in the ideal case. But let's actually look at this paper because the paper itself is quite hard to understand. And I still don't know if I understand it correctly, but we'll just go through it and I will talk about what I understand and then we, I guess we can have a discussion. Before a discussion, always leave a comment if you want, join our Discord. There are many, many competent people there that have opinions, way better opinions than I do. So, all right. So they say we present a general framework for capturing long range interactions between an input and structured contextual information, e.g. a pixel surrounded by other pixels. Another method called the Lambda layer captures such interactions by transforming available contexts into linear function termed Lambdas and applying these linear functions to each input separately. Lambda layers are versatile and may be implemented to model content and position based interactions in global, local or mass contexts. So as you read this, there are a number of things right here that we are going to blatantly disregard while reading this paper. So first of all, they present a general framework, like let's like screw, screw the general framework. They're going to apply this to image classification. We'll look at it in the context of well, first of sequence classification, and then of image classification, because it comes out of the kind of transformer area. So then the transformers classically have been applied to sequence or set classifications. So we're going to look at it in that framework, like general framework, blah, blah, blah, right. Okay, so for capturing long range interactions between an input and structured contextual information, e.g. a pixel surrounded by other pixels, okay, so when you hear again, this long range interactions immediately, you should think of something like a transformer like an attention mechanism that that's exactly what they're going for here. And they're trying to frame this into this this like lambda layer, the fact that we build a linear function termed lambdas from lambda calculus, and we apply these linear functions to each input separately. Now, anytime you multiply a matrix by a vector, that's what you're doing. But the framing here is, and we'll see why the framing is like this. But it sort of makes it it introduces a new terminology. Lambda layers are versatile, yada, yada, yada, yada. And the tricky part or the important part here is, as they bypass the need for expensive attention maps, lambda layers can routinely be applied to inputs of length in the 1000th, enabling their applications to long sequences or high resolution images. The resulting neural network architectures, the lambda networks are computationally efficient and simple to implement using direct calls to operations available in modern neural network libraries. Okay, so they have a bunch of things here, they now get into the framework of okay, it's kind of like attention, but we do not need these expensive attention maps. And they're going to show why they do not need the attention maps that an attention layer would compute. And we will look at what what's the trade off here, like there's always a trade off. The attention is kind of a very, very general computational framework. It's super general, it's like dynamic routing of information. And they don't do that. So we're going to see where the trade off is. And the what they gain is, of course, if they don't need to compute these expensive attention maps, which know that the limiting factor is memory in transformers. It's also a bit time, but we can just let it run for longer. But memory, we can't really just wait long. And then we get more memory, we have the memory that we have. So since they don't have that they can take inputs and links of the 1000s, you know, they can apply these things to high resolution images. And we're going to see that applying these things to high resolution images, that is, let's say, that is shaky. Let me just say, they can't do that without going to what's called local attention. And what I mean by this is so attention mechanisms, extremely briefly, extremely briefly, if you have a sequence, and you transform it into another sequence, that's what an attention mechanism is for. The attention mechanism looks at a looks at from each top part here, it emits a query queue. Wow, that's a big thing. Each top part emits a query queue. Each bottom thing emits a key K, and then it builds what's called an attention map. So an attention map, in this case, is just a matrix, a in this case, a five by five matrix. And this matrix specifies how each of the inputs is routed to the outputs. So this five by five matrix, as you can see, pretty clearly, if I make the sequence here longer than this, like one of the axes is going to get longer. And if I make this sequence longer, the other axis is going to get longer. And normally, or in what's called self attention, these sequences are the same sequence. So you'll have the sequence paying attention to itself. And if you have an image, what that means in an image is that so the image is already a matrix, but it's a it's kind of a collection of pixels, what you would do is you would see the image as a collection of as a sequence of pixels, and then each pixel needs to attend to each other pixel. So you can see pretty easily if the image is like something like 200 by 200, that's what 40,000. So you'd have a your matrix up here would be 40,000 by 40,000, which is impossible, right? That's the trouble here. Now people have gotten around this by doing what's called local attention. And local attention means like, well, you know, you pixel, you don't need to pay attention to all of the other pixels, you actually only need to pay attention to the pixels in your neighborhood, which is sort of, it's a convolution, right? A convolution is usually this but local attention is a dynamic convolution. So usually in a convolution, you have a fixed convolutional kernel, local attention is simply a dynamic convolutional kernel, like global attention is a dynamic feed forward layer, instead of a fixed feed forward layer, local attention is a dynamic convolution instead of a fixed convolution. They are going to do something similar here to process for high resolution images, they are going to restrict their context to a local kind of local field of view around the pixel that they're interested in. So just so you don't get super hyped by by the by the abstract right here. So we'll go into what these lambda layers do. And I'm going to jump a whole bunch of things in the paper, just so we get to the kind of the meat of the thing. So they say, look at these images, and we just we just set this right. So usually you have a, you have for each pixel, you wonder how should I transform this to the next layer. So you imagine your neural network as having layer, layer, layer, layer, layer. And in each time you can imagine you have this image, and you want to transform it into like an intermediate representation that's still, it still looks like an image, maybe has different number of channels and so on. But and maybe it's a different resolution. But still, you want to kind of forward propagate this image into its intermediate representations. And the question is, for each location in the image, so for each pixel, how should I transform that particular location into its next intermediate representation? That's what a neural network does. In this, in this framework, what we want to do is we want to look at this pixel, and then say, okay, well, we can't just look at the pixel itself, we somehow need to look at all the other pixels. So we know how to transform it, because it's going to be a really boring neural network if we just look at each pixel individually. So we are going to look at all the other pixels in the picture. As we said, it we're going to pay attention to all the other pixels. And that determines how we should transform the current pixel into the next representation. That would be what they call a global context or global attention in the attention framework. However, as we already said, here, what we're going to do is we're simply around, we're simply going to restrict how far the pixel can look at the other pixels, what they call the local context. So the pixels, they're going to be transformed into what's called queries, like in the attention framework, the context is, it can be something else. But usually, it's going to be the same as the input. So the input is this picture. And the context is also going to be the picture. But now, we are going to additionally for each location restrict the context around that location. So what local attention would do, local attention would build for each pixel an attention map. And the attention map, as we said, it is going to define how the pixel should pay attention to all the surrounding pixels. So you can see right here, this is the attention map for this one pixel. So you can imagine that if I were to construct an attention map for all the pixels in the image, now it's going to be every pixel is going to have an attention map like this telling it how it should aggregate all the pixels around itself. And you can easily see that if we make the context as large as the image itself, that is going to give us each context map is going to be as large as the image. And we need that for each pixel. So we're going to end up with if this is if this is height and this is width, we're going to end up with height squared width squared memory requirements. So the difference in the lambda layers is that the lambda layers, what they do is they take the context, and they're going to abstract this into a matrix, they're going to summarize the context first without looking at the query, okay, they're going to take the context and make it into this lower dimensional linear function, you can see from the picture that what they're trying to make sure that you see is that the left thing is basically restricted to be of the size that the it's pixel by pixel. While on the right side, you have you're going to have some freedom over how you want to construct that matrix. And they are going to abstract the context into a function. And then they're simply going to multiply this by the query. So the whole operation here is going to be a linear function, as opposed to the attention operation, which is you look at the interactions between queries and keys, and then you take a softmax over that, which makes it into a nonlinear function, this is going to be a linear function. Okay, so, but the rhetoric around this, you can already see they say we abstract the context into a linear function, and then we apply that linear function to each query separately. The problem right here is that there is one context per query, right? As soon as you go to the next pixel, like right here, your context is going to be is going to be shifted. So it's not like if you had the global context, right, if you had the global context, you could simply compute this context function once, and then apply it to each to each pixel individually, that's going to be, that would be the gain in, let's say time. But here, not so much. So they're the trade offs that they make in space immediately result in the in the breakdown of their narrative, at least, I feel like this. Now, how can you understand this just from here before we go into the formula? Again, I would say we go back to kind of the sequence narrative, okay, so the sequence narrative is the following, we want to transform the sequence into its next layer representation. In attention, we take a look here and we look at how does this pay attention to each of the inputs right here, depending on what the inputs are, right, we depending on what these queries and depending on what the keys are here. So that's going to be really important. What we do here instead, in the lambda network is we're going to take the context, which is this thing, and now we're dealing with a global context because we don't. So we are closer to the terminology, and we're going to summarize it, we're going to just summarize this into a function. So and the function is represented by a matrix and the matrix dimensions, we can even choose how big this matrix is, right? We're just going to summarize the context without looking at the queries and then the queries without looking at the individual part of the context, like we don't do that. We simply take the queries and pull them through this function to get the next higher level representation, right, we take, we take the query, put it through the same function, get the higher level representation. So the context is summarized into one single linear function that transforms all queries the same. And it's not exactly what they do, like they have positional encodings and so on. But in essence, that's what they are, that's what they are advertising in the first place. Alright, so let's dive into the formula, the formulas are fairly, fairly complex, I had a while until I until I grasped all of this. So this is the first half, you can see right here that this is the first half. And then how you get from here to the outputs, that's another set of equations right here. Okay. It's again, as I said, it's it's fairly complex. And that's not all like there and there, then there is translation, equivariants, then there is the convolutional lambda, and so on, and the analysis. But let's break this down and see where the lambda layer is different and how it works. So we start out with the input and the context, right, that is that is here. These are the inputs to the lambda layer, x and c. Now, keep in first of all, okay, let's let's build up a little diagram over here, we have x and we have c coming in, and we'll annotate them with their respective sizes. So x is n by d, and c is m by d. So that's n by d, and m by d. Now, keep in mind, okay, that x and c are often the same thing. First of all, right, or similar if c is restricted and so on. But keep keep that in mind. So x and c are often the same thing, n here is what would be referred to as the input size, input size, right. And if n is equal to m, if x is equal to c, then the problem is going to be whenever there is a term m by n, then that is going to be quadratic in the input size, and that is going to blow up. So in terms of in when if this is an image, and this here is going to be whatever 225 by 225, that's the image resolution. That's that's n, right? n is this. We're not talking d is going to be the channels. So n itself is going to be this giant number. So you can see that n by m is going to be that squared. So whenever there is a term like this, that's going to be a problem. So in attention, what do we do in attention, let's make a little thing here in attention, we have x and we have c. This is n by d, this is m by d. In attention, what we're going to do is we're going to transform x by means of w q, but this is these are learnable parameters, the w, w q is d by k. So it transforms the inputs into queries and the queries are going to be n one query per input, by the key dimension, which is often which is a parameter you can choose, then we're going to transform the context by means of w k, which is also d by k into the keys, which are now m by k, sorry, and we're going to transform the c into w also into values. And the values, I mean, there would be an additional parameter of the value dimension, but very often, since the output dimension is going to be d again, we'll just say this is m by d. Sorry, no, this is, let's call that d by d, which makes the values m by d. Okay, so these are now your standard attention parameters, let's say. So you are going to take the queries and the keys and you're going to multiply them together to get the attention map. Okay, you can see if you multiply those two things together. So query, you do query times key transposed, you get n by m, and you're going to softmax this, let's do it like a little sigma, so which is going to be the normalized by m, and you're going to take the values and calculate the outputs y from this and the outputs y are going to be n by d. All right, so you can see that the nonlinearity is right here. Okay, so the nonlinearity determines how do you aggregate the context which is transformed into the values linearly, how do you aggregate the context to the output that's determined by the nonlinearity, it's determined by this attention map. And most notably, you have this n by m parameter right here. This is a matrix you have to construct, you can't get around it because you have to apply nonlinearity to it can decompose it. And that's the problem. So now, it's about to get complicated. Really easy. First of all, we take the inputs, and we're going to again, apply a WQ, that's d by k to get the queries. Okay, the queries are going to be n by k so far, so good. So we got these, we got the query, as you can see right here, it's d by k. And the queries are constructed like this. Now there's a there's a mistake here. Authors, anonymous authors, if you're looking, this is wrong. Yes, this should be something like n by k. Okay, not even you. So you here is like an inter dimension parameter, this, we're just going to scrap this, this is equal to one for our purposes. You can, you know, you can you can do all the things with the with the u equal to more stuff, but we're just going to leave it at one if that's okay. So yeah, scrap this. Alright, so we got we got our queries and you can see keys and values just the same. So we're going to transform the context into keys and values just the same as in attention. Let's quickly go over here and do that. Here we're going to transform this using WK, which is d by k, and we're going to transform it as well using WV, which is D. Now, they're going to say D by V, but we'll just always say D by D. They are going to relax that later on and so on. But yeah, D by D. So this gives you keys and this gives you values and sorry, m by k, and now m by D. And now the the difference is is happening. We're getting to the positional embeddings in a minute. So now what we're going to do is we're going to apply a softmax to the keys, just the keys. Okay, so we're going to take the keys and we're going to do a softmax operation along m. So we'll maybe say along which dimension here is along m along the m dimension. Okay, so which gives us the key m by k. Now this is a little bit weird. Why would we apply the softmax to like an individual thing? And we're going to see in a minute what that does. But for now, this simply create, we create a key matrix. The key matrix is m by k. And then we're going to apply a softmax over the m dimension. And that means that means we now have k attention maps. We have k different attention maps over m inputs. All right, and every time you make a softmax, you basically make a distribution. And that defines how you aggregate information. And so we have k different distributions as here, you can see our attention map was we had n different attention maps of size m. And now we have k different attention maps of size m. This is going to be the difference, right? Here, it's not that attention vanishes in this model. It's that the attention shifts where it is. And you're going to see that quickly. When you look at here, this content contribution and position contribution is where we're going to now multiply the keys by the values. And yeah, the position we're going to look in a minute. But we're now going to multiply the keys by the value. So the queries are nowhere to be found. And if we go down here, you can see that we multiply the keys by the values and then contract over m. So this is this is a a multiplication right here. So we're going to take the values, whoopsie, the values and the keys, and we're going to contract over m. So in this case, we'll simply do whatever key key like key transposed times V, maybe. Yeah, that makes sense. Or the other way around. No, that that sounds sounds about right. Which gives us what what do they call it? I think they call it lambda. They call it lambda C. Now we have to pay attention. The C up here is going to be this is not a dimension. This is just the name of this is lambda C, which is going to be of size k by D. Okay. Do we get this right? This is going to be of size. Yes, k by V in this case, but k by D in our case and contracting over m. So here you see that it's kind of a it's kind of a tricky trick in here. So this whole thing is sort of by itself. And it does kind of an attention to itself. It's the context summarizes itself. And you can see at the end, there is no more m. So m, there is there's no more m, m is vanished from this. So we have summarized the context in in and abstracted the m before we ever had a chance to let it interact with the end. And this is exactly where the this differs from attention. So the last step here is going to be that we're going to take this this lambda C, and we're going to take the queries. And we're going to multiply those together. So this is simply a linear function right here. This is a linear function, we're doing q times lambda C. And that is going to give us our output y. Okay, and y is going to be n by D. So each of the inputs have this is each of the inputs next layer representation. So each of the inputs next layer representation is simply a linear function of its query. And its context, and the context is a summary of the context. So what you don't have is fine grained interaction between position, a transformer can say, well, I am this pixel here. And I am green. And you are this pixel there. And you are red. I am going to pay x amount of attention to you. This is no law and you this pixel here you are yellow, I'm going to pay more attention to you. You can't do that. The pixels in the context, they will go among themselves, they will decide, okay, you're red, I'm yellow, and so on. How much attention should anyone be able to pay to the two of us, they will put that into a summary vector, basically. And then the query can only look at that summary vector and decide what it wants to do with it. In essence, I have a multiple frameworks of how you can understand this. Notably, what you can understand this as is the whole blue part here, what it does is it kind of constructs a vector space, okay, it constructs a vector space of k dimensions, you can see here, this k is going to be very important. So it constructs a vector space of k, not of k dimensions. But it comes, yeah, like a subspace of k dimensions in the D dimensional vector space. Okay, is usually pretty small. So we're going to have this k subspace of k vectors in the D dimensional space that is constructed, and all the queries can do is they can select a point in that, okay. The meaning here is that the context, no, let's go a step back and talk about this softmax operation. So it might be a bit weird to apply the softmax just to like a single matrix of keys. But that's not exactly what's happening. So in the attention, what you'll have is you'll have a softmax over the queries times the keys, right. And the both are computed, the queries are computed from the input and the keys are computed from the input. And the question is, how, how should they how should information be aggregated from the values that's determined by the two things, okay. Now, in this case, you might say, well, it's just the keys that decide, so there is no interaction. But there is. If you write the keys out what the keys are, the keys are the context times this matrix WK. Okay, and what this is now, you can see this as the analog to the one before. So this here is the input that's kind of like the query matrix, except the query matrix is a linear transformation of the input. But it's sort of like it comes to the input. But this here is now no longer like the key matrix from above, this here is actually fixed. So the keys in this world are fixed. How you can imagine that is each layer constructs a sort of like a pseudo sequence, a pseudo sequence of K of K different of size K. And what it first does is it kind of summarizes the input sequence, it will draw it will draw it like I drew this before. So instead of transforming this sequence into this sequence, what it does is it constructs a pseudo sequence of let's say length three intermediate, and this pseudo sequence, this intermediate sequence always, always, always has the same queries. Now, okay, you have to swap the two actually. This this is kind of like the keys. This is like the queries. Okay, so this pseudo sequence always has the same queries. And the the this this sequence down here is now going to send information to that pseudo sequence. So this pseudo sequence always aggregates information in the same way, independent of what the input is. And after and after, so that's how it aggregates the output. So no longer transforms this into this upper sequence right here. And then, of course, it does in the second step, but this now is just linear. So this here, this part here is attention. And then this part here is linear, this is kind of reminiscent of the Lin former and so on that that kind of concept that project the sizes, the intermediate sizes of the sequences down. It's just done in a different way is that the attention is shifted to this first part here and is sort of fixed. I don't even want to call it attention. Because it's kind of like fixed, the queries are always the same, they are learned a bit like, if you remember the DETR paper where we have learned queries. So what does this mean? It means something like you each layer learns these different dimensions that it could that it can aggregate in the in the context. So this could be like color. So it says this context, what what kind of what what, or this particular context element, what kind of a color does it have? It could be it could be higher level features, it could be like, is there is there give me the give me if there is a corner, if this is an image, there's a corner, or if this is a sequence, tell me whether or not like what kind of word it is, tell me it's it's grammatical meaning, I don't know, even though it's grammatical meaning, or its label, like whether it's a noun or a verb. And here, you kind of get what I mean that there it constructs this space of properties of the context elements. And each, each query can then come and basically decide how important each query from up here can decide how important each of these is. So this these blue arrows here refer directly to the pseudo sequence, which is of length k. And then the query simply selects a point in this and aggregates information in that. Okay. I don't know if that's if that's entirely clear. But the point is that the attention operation is now shifted to instead of transforming a sequence into its higher representation, it's transforming it into kind of an intermediary pseudo sequence that has nothing to do with the with the queries in question is just dependent on the context. Then the projection to the next level representation where the queries actually come in is simply a linear operation constructs this kind of subspace that has these axes. And then it in this subspace, it's just a linear operation to get to the next layer. Okay, so summarize the context using attention. So the trick here is you don't summarize the context into a vector, you actually summarize the context into a bunch of vectors. So the context can say my color is green. My my corner reness over the whole like, I got lots of corners. And each of these each of these properties is a vector, as you can see here. And then so maybe it's better characterized as a list, a list of size k. And each entry in this list has a particular meaning like color, and each one is a vector. So the context will be summarized into a collection of k vectors. Like this, okay, so each context can have a different collection of k vectors, but still it's k. And then the query, the query can decide how it wants to aggregate how important is color to me. It's like five, five important color. And then sees like, oh, you're you're green. Okay, cool. How important is corner reness to me? Eight. Okay, cool. The important part is what the query cannot do is it cannot go look, it cannot look at what the color is and then decide how important it is. That's what makes it different from attention. So in attention, the query can see and it's like, oh, you're green. Well, that's not that important to me. The query must decide, ah, okay, I myself am a red pixel, I'm going to pay five attention to the color of other pixels. If I am yellow, I'm going to pay seven attention, but it can't look at the other pixels, because they're all summarized, right? It can't go look at all the other pixels, it can only look at the summary, decide how important is that. So enough ranting from me, there is a second part to this, which is the position encoding. So they have noticed probably they've tried it like this. And this just doesn't doesn't work. And it shows in their ablations, what's actually important is the additional positional encodings. And that's what they have right here. So the what they have now is these encodings E and E, as you can see, right here, E is already indexed by n and m. So E is going to be an n by m by k tensor. You see the inputs are n by d, and m by d, and E is going to be n by m by k. Now these are positional encodings. So what they do is they are a fixed set of learn parameters kind of like positional encodings in a transformer, but in a transformer, it would simply be like m by k, right? That's what it would be because you just put the positional encodings onto the context or on the input. In that case, it would be n by k. Here we have an n by m by k. So these are actually learned attention weights kind of. So these are going to be a matrix that is n by m and is going to be a k dimensional vector for each. So each n by m pair has a vector associated with it and embedding. This kind of destroys the whole notion of this summarizing the context first, right? Because now we're building up basically a learned attention map, a learned attention map. The advantage here is that this thing is learned, this thing is not computed, it is learned per layer, and it cannot be kind of changed from example to example. So that's the difference between the attention map. So the stuff that is computed dynamically is not dependent on n by m. And the stuff that is n by m is not computed dynamically. And that has the big advantage that if I have a batch size in front, then these things here are all going to be adding the batch size n by d by b, n by d by b, while this thing no b, okay? So this thing is fixed. And all you have to do is you have to hold n by m once in memory. And you don't have to hold it, you don't have to grow it with the batch size. And since we are reducing n and m anyway, because or m at least, because we are only paying attention to local context, that's going to be feasible. You can see that you can't get around the fact that you have to have these attention maps. And therefore, you probably in this framework can't get around to the fact that you have to have some sort of local restriction. Because if it weren't for that, this thing right here, there is no n by m, never ever an n by m, and therefore, you don't have this giant blow up, the attention mechanism is over m by k, as you can see here. And as long as you can keep k small, that could actually work with a global context. Okay, not with the position embedding. And it doesn't work without the position embeddings. And they are not position embeddings, they are attention embeddings. Okay, let's or interaction embeddings, to call them position embeddings would be a little bit a little bit. I mean, they say it's a positional bedding for their relation n to m. It's important to note that these, again, are not computed from the input, they are simply fixed, they're simply say, if a pixel is on the top left, and the other pixels on the bottom right, then they are, their relation is given by this vector right here. Okay, so for each pair of pixel, there is an entry in this matrix. Now how do we use those? Kinda similar, we just start down here, we multiply them with the value. And you can see that you will and you contract over m in subsequent equation. Where is it? Right here, you contract over m, which gives you this thing right here, which you can see there is nothing here, now there is an n here. So what you'll get naturally is one positional embedding per input. So yeah, as I said, it sort of destroys this this notion of first summarizing the context, because now it's, it's on again. So you're going to take the values and this thing, and you're going to compute from this, this lambda p positional lambda, which is of size, and you can see it, it's n by k by d. And you're going to take, you're going to take the queries, it's going to get complicated. So you're going to take the queries over here. And you're going to compute the output y p, which is going to be n by d. Yes, this is n, this is n, you're going to do it once per, and then you're going to add the y's together. So this is a plus for the final y. So you can see these are two completely linear, this is y c, the content y, two completely linearly separable pathways, one comes from these positional encodings, and one comes from these from the context. And the positional encodings are actually more important in the experiments. If they leave those away, nothing works. If they leave this summarizing away, then stuff pretty much works still. So you know, it's fair to say that the power here comes from the positional encodings. And that, again, a bit, it's a bit counter to their to their narrative, because I feel that the whole point of the lambda layers is to do this stuff right here. And this here is something that you need to make it work. But in any case, what you do is you take, you take these positional encodings and you multiply them by the values. So what this does is this here, this is a special object, this lambda p, as you can see, it creates n times k times d tensor. And this is it's a big tensor. So what does it do for each of the n pieces in the input? For each of the n pieces in the input, it creates a one of these lists, right, one of these k sized lists, k sized lists of the vectors, as we've seen before, but it does so differently for each position. Okay. So for each position, it creates a different table. And the queue again indexes into this table, but into, you know, at the position where it is. So if you take the query from a particular position in the output, it's going to look to its table, aggregated according to what it's interested in. So the positional encodings basically say, if you if if if this element in the context, if you are the first element in the sequence, then you have to aggregate information according to this particular scheme. But if you're the second element, you have to aggregate information according to this particular scheme. So again, it can't look at the contents of what these particular things are, it can only kind of define a linear operation. However, it can kind of look at the contents of the query, because usually x and c are the same. So by incorporating v in here, m being equal to n, most often, it can actually do that. And again, we see in the results that most of the information actually goes through this path. The good thing, again, is that so here you have n by m, but you don't have a B, you don't have a batch size. Here the batch size appears because there is actually a batch size, right, there is a batch size here. And then the batch size would appear right here. But at the moment the batch size appears, the n by m term falls away. So there is no m right here, you contract over m as you introduce the batch size. So again, there is nowhere an n by m tensor to be held as you add that that is scaled by the batch size. So there is again, this this kind of performance increase. But you can already see here you have we had these nice construction where all the whole context constructs this table of vectors, and then the query aggregates it. And here we construct a separate table for each element in the input. And then the query, according to its position, aggregates that and it simply adds those two aggregations together, most of the performance comes from the bottom right here, which you can sort of see this as if you know if you have like y equals w x plus b, you can sort of see the w here as these tables right here, because they actually depend on what the x is, in this case, the position of the x and the b is just something that comes on top to every single position that that there is. Okay, this is a giant mess. But that's about how it works. And I hope you didn't you didn't completely you didn't get completely lost in this. So they have a whole bunch of extensions, as I said, so they have translation equivalence, then because they build their positional encodings as relative encodings, which makes it very easy to then build this lambda convolution. So you can actually implement this operation here as a convolutional operation to get this positional lambda. And their whole point is kind of that if I do local attention, right, if I do local attention, what I need to do is I kind of if I do local attention, then this thing only pays attention to these three, and this thing only pays attention to these three kind of like a convolution. But because it's an attention for each of these things, I need to build my attention map, I need to build my attention map. And that kind of if I want to batch this, if I want to do this at once, I need to sort of if this is my interaction matrix, it kind of looks like this, this downward descending stairs or something like this. And that is not well supported in current frameworks. And that makes it a lot like really slow. They say, look, even though we use the same amount of let's say memory, as local attention or time, sorry time, we can implement it using these primitives, and they are much faster. So they are they are going to outperform local attention in that sense. They do compare here in terms of time and space to an attention layer. Now, they split this into content interactions, which is that first pathway and position interactions like this here, this is absolutely irrelevant because it's smaller than the position interaction and the position interactions give the performance. So you can see clearly that there is in space we have B times n times m, h is the number of heads, we don't care much about that right now. So B times n times for the attention layer, which is the problem. And here you see you have n times m here, but no B. And you have B times n, but no M. So that is kind of the the gain right here, as long as you can keep the K small, right, this intermediate sequence, which makes sense, right, this attention goes to this intermediate sequence. So as long as you can keep that intermediate sequence small and fixed, you don't have a problem with this quadratic memory, at least you have a problem right here, but that's not modulated by the batch size. In terms of time, it's still you can see there is a B times n times m, you still have that time complexity, because after all, you need to do these multiplications and contracts just the same. So not much of a difference in terms of time. The time argument is more like they can implement it using convolutional operators rather than the this kind of striding attention maps. They also do this in multi query, multi like multi head and so on. And you can see right here that it outperforms outperforms other systems, including like systems with self attention, especially in terms of if you see the memory, if you do global self attention, it uses a lot of memory. In fact, like an out of memory error on their machine axial self attention, these are all kind of limits to self attention, local self attention, which comes closest to what they do. But then what you suffer is a massive drop in performance, whereas their lambda layer right here. It has a lot of performance. And you can see the performance gain, right? This is k, I believe k is equal to 16. In this example, if they go k to eight, and we know that the attention interaction in the lambda networks is not n by m, but actually m by k. So if you have k, you can already see there is a massive jump in the number of examples you can throughput through the network. Okay, so that kind of gives evidence to what we are what what my hypothesis is is going on right here. Okay, lastly, I've already shown you this table as it outperforms kind of the efficient nets. And this is a special version of lambda networks, the lambda res nets, where they take a res nets and they only they only replace a part of the resnet. So if you look at the table down here, these are the different architectures where they could replace things in the resnet, for example, the resnet 50 right here. So this is all convolutions. This is kind of the baseline and you can see that it's like 7200 samples per second. If you replace everything by a lambda layer, you're down to like 1160 examples per second. Interestingly, if you replace the first layer by a lambda layer, you are also the performance drops enormously. And that is because of course, the the sizes of the of the of the images get smaller and smaller. So your your n gets smaller and smaller as you go up the layers. As you can see right here, if you only replace the last layer by a lambda layer, then you can gain all back almost all of that performance and interestingly still outperform the complete convolutional layer. And it also has less parameters, you can see the 25 instead of the 18. Alright so that was my rant on this paper. Again, I hope this wasn't too convoluted. There's a lot more to this paper. I want to kind of quickly shout out LucidRains and made a made a I got to show you. This is hilarious. He implemented this so. Yes, thank you. Implemented this as the paper came out. And of course, well, we don't know if Phil Wang is the author of this paper. We don't know maybe maybe not. Chances are not but still cool that he goes ahead and implements these things. I especially I love the conciseness using the INOPs right here. So there are as you can see, like this is it. That's it. That's all. The use of INOPs right here to like do this rearrange and INSOM operations, which are much more concise than the reshape, squeeze, unsqueeze whatnot. So that's pretty cool. And the coolest thing is lambda actual Greek letters in the code. Thank you, Python. So yeah, I invite you to check out this implementation. I'll of course link it. Tell me what you think of the paper and I'll see you next time. Bye bye.
 Another day, another state-of-the-art result in machine learning land on ImageNet.
 This time coming from a thing called Lambda ResNets.
 As you can see here, it outperforms EfficientNets and ResNets right here, not only in terms
 of top one accuracy, but also in terms of the trade-off between accuracy and training
 time.
 Here it says Lambda ResNets are about 4.5 times faster than EfficientNets and substantially
 improve the speed accuracy trade-off of image classification models across different scales.
 So this is something new that we have not seen in recent times.
 In recent times we've seen like transformers take over image classification and so on,
 but it came either with downsampling the image like this 16 by 16 patches and so on, or just
 throwing massive amounts of data at it or massive amounts of compute.
 This paper here promises that they have something that's more efficient and it can reach good
 accuracy or for the same efficiency can reach better accuracy.
 So today we're going to look at this paper, Lambda Networks Modeling Long Range Interactions
 Without Attention by Anonymous Authors.
 It's under review at ICLR 2021.
 I'm not going to de-anonymize this paper.
 Well mostly because this one is a bit harder and would require a bit of research, but also
 because I think I've made my point.
 I remain that double blind reviewing isn't really what it's set out to be in the ideal
 case.
 But let's actually look at this paper because the paper itself is quite hard to understand.
 And I still don't know if I understand it correctly, but we'll just go through it and
 I will talk about what I understand and then we, I guess we can have a discussion.
 Before a discussion, always leave a comment if you want, join our Discord.
 There are many, many competent people there that have opinions, way better opinions than
 I do.
 So, all right.
 So they say we present a general framework for capturing long range interactions between
 an input and structured contextual information, e.g. a pixel surrounded by other pixels.
 Another method called the Lambda layer captures such interactions by transforming available
 contexts into linear function termed Lambdas and applying these linear functions to each
 input separately.
 Lambda layers are versatile and may be implemented to model content and position based interactions
 in global, local or mass contexts.
 So as you read this, there are a number of things right here that we are going to blatantly
 disregard while reading this paper.
 So first of all, they present a general framework, like let's like screw, screw the general framework.
 They're going to apply this to image classification.
 We'll look at it in the context of well, first of sequence classification, and then of image
 classification, because it comes out of the kind of transformer area.
 So then the transformers classically have been applied to sequence or set classifications.
 So we're going to look at it in that framework, like general framework, blah, blah, blah,
 right.
 Okay, so for capturing long range interactions between an input and structured contextual
 information, e.g. a pixel surrounded by other pixels, okay, so when you hear again, this
 long range interactions immediately, you should think of something like a transformer like
 an attention mechanism that that's exactly what they're going for here.
 And they're trying to frame this into this this like lambda layer, the fact that we build
 a linear function termed lambdas from lambda calculus, and we apply these linear functions
 to each input separately.
 Now, anytime you multiply a matrix by a vector, that's what you're doing.
 But the framing here is, and we'll see why the framing is like this.
 But it sort of makes it it introduces a new terminology.
 Lambda layers are versatile, yada, yada, yada, yada.
 And the tricky part or the important part here is, as they bypass the need for expensive
 attention maps, lambda layers can routinely be applied to inputs of length in the 1000th,
 enabling their applications to long sequences or high resolution images.
 The resulting neural network architectures, the lambda networks are computationally efficient
 and simple to implement using direct calls to operations available in modern neural network
 libraries.
 Okay, so they have a bunch of things here, they now get into the framework of okay, it's
 kind of like attention, but we do not need these expensive attention maps.
 And they're going to show why they do not need the attention maps that an attention
 layer would compute.
 And we will look at what what's the trade off here, like there's always a trade off.
 The attention is kind of a very, very general computational framework.
 It's super general, it's like dynamic routing of information.
 And they don't do that.
 So we're going to see where the trade off is.
 And the what they gain is, of course, if they don't need to compute these expensive attention
 maps, which know that the limiting factor is memory in transformers.
 It's also a bit time, but we can just let it run for longer.
 But memory, we can't really just wait long.
 And then we get more memory, we have the memory that we have.
 So since they don't have that they can take inputs and links of the 1000s, you know, they
 can apply these things to high resolution images.
 And we're going to see that applying these things to high resolution images, that is,
 let's say, that is shaky.
 Let me just say, they can't do that without going to what's called local attention.
 And what I mean by this is so attention mechanisms, extremely briefly, extremely briefly, if you
 have a sequence, and you transform it into another sequence, that's what an attention
 mechanism is for.
 The attention mechanism looks at a looks at from each top part here, it emits a query
 queue.
 Wow, that's a big thing.
 Each top part emits a query queue.
 Each bottom thing emits a key K, and then it builds what's called an attention map.
 So an attention map, in this case, is just a matrix, a in this case, a five by five matrix.
 And this matrix specifies how each of the inputs is routed to the outputs.
 So this five by five matrix, as you can see, pretty clearly, if I make the sequence here
 longer than this, like one of the axes is going to get longer.
 And if I make this sequence longer, the other axis is going to get longer.
 And normally, or in what's called self attention, these sequences are the same sequence.
 So you'll have the sequence paying attention to itself.
 And if you have an image, what that means in an image is that so the image is already
 a matrix, but it's a it's kind of a collection of pixels, what you would do is you would
 see the image as a collection of as a sequence of pixels, and then each pixel needs to attend
 to each other pixel.
 So you can see pretty easily if the image is like something like 200 by 200, that's
 what 40,000.
 So you'd have a your matrix up here would be 40,000 by 40,000, which is impossible,
 right?
 That's the trouble here.
 Now people have gotten around this by doing what's called local attention.
 And local attention means like, well, you know, you pixel, you don't need to pay attention
 to all of the other pixels, you actually only need to pay attention to the pixels in your
 neighborhood, which is sort of, it's a convolution, right?
 A convolution is usually this but local attention is a dynamic convolution.
 So usually in a convolution, you have a fixed convolutional kernel, local attention is simply
 a dynamic convolutional kernel, like global attention is a dynamic feed forward layer,
 instead of a fixed feed forward layer, local attention is a dynamic convolution instead
 of a fixed convolution.
 They are going to do something similar here to process for high resolution images, they
 are going to restrict their context to a local kind of local field of view around the pixel
 that they're interested in.
 So just so you don't get super hyped by by the by the abstract right here.
 So we'll go into what these lambda layers do.
 And I'm going to jump a whole bunch of things in the paper, just so we get to the kind of
 the meat of the thing.
 So they say, look at these images, and we just we just set this right.
 So usually you have a, you have for each pixel, you wonder how should I transform this to
 the next layer.
 So you imagine your neural network as having layer, layer, layer, layer, layer.
 And in each time you can imagine you have this image, and you want to transform it into
 like an intermediate representation that's still, it still looks like an image, maybe
 has different number of channels and so on.
 But and maybe it's a different resolution.
 But still, you want to kind of forward propagate this image into its intermediate representations.
 And the question is, for each location in the image, so for each pixel, how should I
 transform that particular location into its next intermediate representation?
 That's what a neural network does.
 In this, in this framework, what we want to do is we want to look at this pixel, and then
 say, okay, well, we can't just look at the pixel itself, we somehow need to look at all
 the other pixels.
 So we know how to transform it, because it's going to be a really boring neural network
 if we just look at each pixel individually.
 So we are going to look at all the other pixels in the picture.
 As we said, it we're going to pay attention to all the other pixels.
 And that determines how we should transform the current pixel into the next representation.
 That would be what they call a global context or global attention in the attention framework.
 However, as we already said, here, what we're going to do is we're simply around, we're
 simply going to restrict how far the pixel can look at the other pixels, what they call
 the local context.
 So the pixels, they're going to be transformed into what's called queries, like in the attention
 framework, the context is, it can be something else.
 But usually, it's going to be the same as the input.
 So the input is this picture.
 And the context is also going to be the picture.
 But now, we are going to additionally for each location restrict the context around
 that location.
 So what local attention would do, local attention would build for each pixel an attention map.
 And the attention map, as we said, it is going to define how the pixel should pay attention
 to all the surrounding pixels.
 So you can see right here, this is the attention map for this one pixel.
 So you can imagine that if I were to construct an attention map for all the pixels in the
 image, now it's going to be every pixel is going to have an attention map like this telling
 it how it should aggregate all the pixels around itself.
 And you can easily see that if we make the context as large as the image itself, that
 is going to give us each context map is going to be as large as the image.
 And we need that for each pixel.
 So we're going to end up with if this is if this is height and this is width, we're going
 to end up with height squared width squared memory requirements.
 So the difference in the lambda layers is that the lambda layers, what they do is they
 take the context, and they're going to abstract this into a matrix, they're going to summarize
 the context first without looking at the query, okay, they're going to take the context and
 make it into this lower dimensional linear function, you can see from the picture that
 what they're trying to make sure that you see is that the left thing is basically restricted
 to be of the size that the it's pixel by pixel.
 While on the right side, you have you're going to have some freedom over how you want to
 construct that matrix.
 And they are going to abstract the context into a function.
 And then they're simply going to multiply this by the query.
 So the whole operation here is going to be a linear function, as opposed to the attention
 operation, which is you look at the interactions between queries and keys, and then you take
 a softmax over that, which makes it into a nonlinear function, this is going to be a
 linear function.
 Okay, so, but the rhetoric around this, you can already see they say we abstract the context
 into a linear function, and then we apply that linear function to each query separately.
 The problem right here is that there is one context per query, right?
 As soon as you go to the next pixel, like right here, your context is going to be is
 going to be shifted.
 So it's not like if you had the global context, right, if you had the global context, you
 could simply compute this context function once, and then apply it to each to each pixel
 individually, that's going to be, that would be the gain in, let's say time.
 But here, not so much.
 So they're the trade offs that they make in space immediately result in the in the breakdown
 of their narrative, at least, I feel like this.
 Now, how can you understand this just from here before we go into the formula?
 Again, I would say we go back to kind of the sequence narrative, okay, so the sequence
 narrative is the following, we want to transform the sequence into its next layer representation.
 In attention, we take a look here and we look at how does this pay attention to each of
 the inputs right here, depending on what the inputs are, right, we depending on what these
 queries and depending on what the keys are here.
 So that's going to be really important.
 What we do here instead, in the lambda network is we're going to take the context, which
 is this thing, and now we're dealing with a global context because we don't.
 So we are closer to the terminology, and we're going to summarize it, we're going to just
 summarize this into a function.
 So and the function is represented by a matrix and the matrix dimensions, we can even choose
 how big this matrix is, right?
 We're just going to summarize the context without looking at the queries and then the
 queries without looking at the individual part of the context, like we don't do that.
 We simply take the queries and pull them through this function to get the next higher level
 representation, right, we take, we take the query, put it through the same function, get
 the higher level representation.
 So the context is summarized into one single linear function that transforms all queries
 the same.
 And it's not exactly what they do, like they have positional encodings and so on.
 But in essence, that's what they are, that's what they are advertising in the first place.
 Alright, so let's dive into the formula, the formulas are fairly, fairly complex, I had
 a while until I until I grasped all of this.
 So this is the first half, you can see right here that this is the first half.
 And then how you get from here to the outputs, that's another set of equations right here.
 Okay.
 It's again, as I said, it's it's fairly complex.
 And that's not all like there and there, then there is translation, equivariants, then there
 is the convolutional lambda, and so on, and the analysis.
 But let's break this down and see where the lambda layer is different and how it works.
 So we start out with the input and the context, right, that is that is here.
 These are the inputs to the lambda layer, x and c.
 Now, keep in first of all, okay, let's let's build up a little diagram over here, we have
 x and we have c coming in, and we'll annotate them with their respective sizes.
 So x is n by d, and c is m by d.
 So that's n by d, and m by d.
 Now, keep in mind, okay, that x and c are often the same thing.
 First of all, right, or similar if c is restricted and so on.
 But keep keep that in mind.
 So x and c are often the same thing, n here is what would be referred to as the input
 size, input size, right.
 And if n is equal to m, if x is equal to c, then the problem is going to be whenever there
 is a term m by n, then that is going to be quadratic in the input size, and that is going
 to blow up.
 So in terms of in when if this is an image, and this here is going to be whatever 225
 by 225, that's the image resolution.
 That's that's n, right?
 n is this.
 We're not talking d is going to be the channels.
 So n itself is going to be this giant number.
 So you can see that n by m is going to be that squared.
 So whenever there is a term like this, that's going to be a problem.
 So in attention, what do we do in attention, let's make a little thing here in attention,
 we have x and we have c.
 This is n by d, this is m by d.
 In attention, what we're going to do is we're going to transform x by means of w q, but
 this is these are learnable parameters, the w, w q is d by k.
 So it transforms the inputs into queries and the queries are going to be n one query per
 input, by the key dimension, which is often which is a parameter you can choose, then
 we're going to transform the context by means of w k, which is also d by k into the keys,
 which are now m by k, sorry, and we're going to transform the c into w also into values.
 And the values, I mean, there would be an additional parameter of the value dimension,
 but very often, since the output dimension is going to be d again, we'll just say this
 is m by d.
 Sorry, no, this is, let's call that d by d, which makes the values m by d.
 Okay, so these are now your standard attention parameters, let's say.
 So you are going to take the queries and the keys and you're going to multiply them together
 to get the attention map.
 Okay, you can see if you multiply those two things together.
 So query, you do query times key transposed, you get n by m, and you're going to softmax
 this, let's do it like a little sigma, so which is going to be the normalized by m,
 and you're going to take the values and calculate the outputs y from this and the outputs y
 are going to be n by d.
 All right, so you can see that the nonlinearity is right here.
 Okay, so the nonlinearity determines how do you aggregate the context which is transformed
 into the values linearly, how do you aggregate the context to the output that's determined
 by the nonlinearity, it's determined by this attention map.
 And most notably, you have this n by m parameter right here.
 This is a matrix you have to construct, you can't get around it because you have to apply
 nonlinearity to it can decompose it.
 And that's the problem.
 So now, it's about to get complicated.
 Really easy.
 First of all, we take the inputs, and we're going to again, apply a WQ, that's d by k
 to get the queries.
 Okay, the queries are going to be n by k so far, so good.
 So we got these, we got the query, as you can see right here, it's d by k.
 And the queries are constructed like this.
 Now there's a there's a mistake here.
 Authors, anonymous authors, if you're looking, this is wrong.
 Yes, this should be something like n by k.
 Okay, not even you.
 So you here is like an inter dimension parameter, this, we're just going to scrap this, this
 is equal to one for our purposes.
 You can, you know, you can you can do all the things with the with the u equal to more
 stuff, but we're just going to leave it at one if that's okay.
 So yeah, scrap this.
 Alright, so we got we got our queries and you can see keys and values just the same.
 So we're going to transform the context into keys and values just the same as in attention.
 Let's quickly go over here and do that.
 Here we're going to transform this using WK, which is d by k, and we're going to transform
 it as well using WV, which is D. Now, they're going to say D by V, but we'll just always
 say D by D. They are going to relax that later on and so on.
 But yeah, D by D. So this gives you keys and this gives you values and sorry, m by k, and
 now m by D. And now the the difference is is happening.
 We're getting to the positional embeddings in a minute.
 So now what we're going to do is we're going to apply a softmax to the keys, just the keys.
 Okay, so we're going to take the keys and we're going to do a softmax operation along
 m.
 So we'll maybe say along which dimension here is along m along the m dimension.
 Okay, so which gives us the key m by k.
 Now this is a little bit weird.
 Why would we apply the softmax to like an individual thing?
 And we're going to see in a minute what that does.
 But for now, this simply create, we create a key matrix.
 The key matrix is m by k.
 And then we're going to apply a softmax over the m dimension.
 And that means that means we now have k attention maps.
 We have k different attention maps over m inputs.
 All right, and every time you make a softmax, you basically make a distribution.
 And that defines how you aggregate information.
 And so we have k different distributions as here, you can see our attention map was we
 had n different attention maps of size m.
 And now we have k different attention maps of size m.
 This is going to be the difference, right?
 Here, it's not that attention vanishes in this model.
 It's that the attention shifts where it is.
 And you're going to see that quickly.
 When you look at here, this content contribution and position contribution is where we're going
 to now multiply the keys by the values.
 And yeah, the position we're going to look in a minute.
 But we're now going to multiply the keys by the value.
 So the queries are nowhere to be found.
 And if we go down here, you can see that we multiply the keys by the values and then contract
 over m.
 So this is this is a a multiplication right here.
 So we're going to take the values, whoopsie, the values and the keys, and we're going to
 contract over m.
 So in this case, we'll simply do whatever key key like key transposed times V, maybe.
 Yeah, that makes sense.
 Or the other way around.
 No, that that sounds sounds about right.
 Which gives us what what do they call it?
 I think they call it lambda.
 They call it lambda C.
 Now we have to pay attention.
 The C up here is going to be this is not a dimension.
 This is just the name of this is lambda C, which is going to be of size k by D. Okay.
 Do we get this right?
 This is going to be of size.
 Yes, k by V in this case, but k by D in our case and contracting over m.
 So here you see that it's kind of a it's kind of a tricky trick in here.
 So this whole thing is sort of by itself.
 And it does kind of an attention to itself.
 It's the context summarizes itself.
 And you can see at the end, there is no more m.
 So m, there is there's no more m, m is vanished from this.
 So we have summarized the context in in and abstracted the m before we ever had a chance
 to let it interact with the end.
 And this is exactly where the this differs from attention.
 So the last step here is going to be that we're going to take this this lambda C, and
 we're going to take the queries.
 And we're going to multiply those together.
 So this is simply a linear function right here.
 This is a linear function, we're doing q times lambda C.
 And that is going to give us our output y.
 Okay, and y is going to be n by D. So each of the inputs have this is each of the inputs
 next layer representation.
 So each of the inputs next layer representation is simply a linear function of its query.
 And its context, and the context is a summary of the context.
 So what you don't have is fine grained interaction between position, a transformer can say, well,
 I am this pixel here.
 And I am green.
 And you are this pixel there.
 And you are red.
 I am going to pay x amount of attention to you.
 This is no law and you this pixel here you are yellow, I'm going to pay more attention
 to you.
 You can't do that.
 The pixels in the context, they will go among themselves, they will decide, okay, you're
 red, I'm yellow, and so on.
 How much attention should anyone be able to pay to the two of us, they will put that into
 a summary vector, basically.
 And then the query can only look at that summary vector and decide what it wants to do with
 it.
 In essence, I have a multiple frameworks of how you can understand this.
 Notably, what you can understand this as is the whole blue part here, what it does is
 it kind of constructs a vector space, okay, it constructs a vector space of k dimensions,
 you can see here, this k is going to be very important.
 So it constructs a vector space of k, not of k dimensions.
 But it comes, yeah, like a subspace of k dimensions in the D dimensional vector space.
 Okay, is usually pretty small.
 So we're going to have this k subspace of k vectors in the D dimensional space that
 is constructed, and all the queries can do is they can select a point in that, okay.
 The meaning here is that the context, no, let's go a step back and talk about this softmax
 operation.
 So it might be a bit weird to apply the softmax just to like a single matrix of keys.
 But that's not exactly what's happening.
 So in the attention, what you'll have is you'll have a softmax over the queries times the
 keys, right.
 And the both are computed, the queries are computed from the input and the keys are computed
 from the input.
 And the question is, how, how should they how should information be aggregated from
 the values that's determined by the two things, okay.
 Now, in this case, you might say, well, it's just the keys that decide, so there is no
 interaction.
 But there is.
 If you write the keys out what the keys are, the keys are the context times this matrix
 WK.
 Okay, and what this is now, you can see this as the analog to the one before.
 So this here is the input that's kind of like the query matrix, except the query matrix
 is a linear transformation of the input.
 But it's sort of like it comes to the input.
 But this here is now no longer like the key matrix from above, this here is actually fixed.
 So the keys in this world are fixed.
 How you can imagine that is each layer constructs a sort of like a pseudo sequence, a pseudo
 sequence of K of K different of size K. And what it first does is it kind of summarizes
 the input sequence, it will draw it will draw it like I drew this before.
 So instead of transforming this sequence into this sequence, what it does is it constructs
 a pseudo sequence of let's say length three intermediate, and this pseudo sequence, this
 intermediate sequence always, always, always has the same queries.
 Now, okay, you have to swap the two actually.
 This this is kind of like the keys.
 This is like the queries.
 Okay, so this pseudo sequence always has the same queries.
 And the the this this sequence down here is now going to send information to that pseudo
 sequence.
 So this pseudo sequence always aggregates information in the same way, independent of
 what the input is.
 And after and after, so that's how it aggregates the output.
 So no longer transforms this into this upper sequence right here.
 And then, of course, it does in the second step, but this now is just linear.
 So this here, this part here is attention.
 And then this part here is linear, this is kind of reminiscent of the Lin former and
 so on that that kind of concept that project the sizes, the intermediate sizes of the sequences
 down.
 It's just done in a different way is that the attention is shifted to this first part
 here and is sort of fixed.
 I don't even want to call it attention.
 Because it's kind of like fixed, the queries are always the same, they are learned a bit
 like, if you remember the DETR paper where we have learned queries.
 So what does this mean?
 It means something like you each layer learns these different dimensions that it could that
 it can aggregate in the in the context.
 So this could be like color.
 So it says this context, what what kind of what what, or this particular context element,
 what kind of a color does it have?
 It could be it could be higher level features, it could be like, is there is there give me
 the give me if there is a corner, if this is an image, there's a corner, or if this
 is a sequence, tell me whether or not like what kind of word it is, tell me it's it's
 grammatical meaning, I don't know, even though it's grammatical meaning, or its label, like
 whether it's a noun or a verb.
 And here, you kind of get what I mean that there it constructs this space of properties
 of the context elements.
 And each, each query can then come and basically decide how important each query from up here
 can decide how important each of these is.
 So this these blue arrows here refer directly to the pseudo sequence, which is of length
 k.
 And then the query simply selects a point in this and aggregates information in that.
 Okay.
 I don't know if that's if that's entirely clear.
 But the point is that the attention operation is now shifted to instead of transforming
 a sequence into its higher representation, it's transforming it into kind of an intermediary
 pseudo sequence that has nothing to do with the with the queries in question is just dependent
 on the context.
 Then the projection to the next level representation where the queries actually come in is simply
 a linear operation constructs this kind of subspace that has these axes.
 And then it in this subspace, it's just a linear operation to get to the next layer.
 Okay, so summarize the context using attention.
 So the trick here is you don't summarize the context into a vector, you actually summarize
 the context into a bunch of vectors.
 So the context can say my color is green.
 My my corner reness over the whole like, I got lots of corners.
 And each of these each of these properties is a vector, as you can see here.
 And then so maybe it's better characterized as a list, a list of size k.
 And each entry in this list has a particular meaning like color, and each one is a vector.
 So the context will be summarized into a collection of k vectors.
 Like this, okay, so each context can have a different collection of k vectors, but still
 it's k.
 And then the query, the query can decide how it wants to aggregate how important is color
 to me.
 It's like five, five important color.
 And then sees like, oh, you're you're green.
 Okay, cool.
 How important is corner reness to me?
 Eight.
 Okay, cool.
 The important part is what the query cannot do is it cannot go look, it cannot look at
 what the color is and then decide how important it is.
 That's what makes it different from attention.
 So in attention, the query can see and it's like, oh, you're green.
 Well, that's not that important to me.
 The query must decide, ah, okay, I myself am a red pixel, I'm going to pay five attention
 to the color of other pixels.
 If I am yellow, I'm going to pay seven attention, but it can't look at the other pixels, because
 they're all summarized, right?
 It can't go look at all the other pixels, it can only look at the summary, decide how
 important is that.
 So enough ranting from me, there is a second part to this, which is the position encoding.
 So they have noticed probably they've tried it like this.
 And this just doesn't doesn't work.
 And it shows in their ablations, what's actually important is the additional positional encodings.
 And that's what they have right here.
 So the what they have now is these encodings E and E, as you can see, right here, E is
 already indexed by n and m.
 So E is going to be an n by m by k tensor.
 You see the inputs are n by d, and m by d, and E is going to be n by m by k.
 Now these are positional encodings.
 So what they do is they are a fixed set of learn parameters kind of like positional encodings
 in a transformer, but in a transformer, it would simply be like m by k, right?
 That's what it would be because you just put the positional encodings onto the context
 or on the input.
 In that case, it would be n by k.
 Here we have an n by m by k.
 So these are actually learned attention weights kind of.
 So these are going to be a matrix that is n by m and is going to be a k dimensional
 vector for each.
 So each n by m pair has a vector associated with it and embedding.
 This kind of destroys the whole notion of this summarizing the context first, right?
 Because now we're building up basically a learned attention map, a learned attention
 map.
 The advantage here is that this thing is learned, this thing is not computed, it is learned
 per layer, and it cannot be kind of changed from example to example.
 So that's the difference between the attention map.
 So the stuff that is computed dynamically is not dependent on n by m.
 And the stuff that is n by m is not computed dynamically.
 And that has the big advantage that if I have a batch size in front, then these things here
 are all going to be adding the batch size n by d by b, n by d by b, while this thing
 no b, okay?
 So this thing is fixed.
 And all you have to do is you have to hold n by m once in memory.
 And you don't have to hold it, you don't have to grow it with the batch size.
 And since we are reducing n and m anyway, because or m at least, because we are only
 paying attention to local context, that's going to be feasible.
 You can see that you can't get around the fact that you have to have these attention
 maps.
 And therefore, you probably in this framework can't get around to the fact that you have
 to have some sort of local restriction.
 Because if it weren't for that, this thing right here, there is no n by m, never ever
 an n by m, and therefore, you don't have this giant blow up, the attention mechanism is
 over m by k, as you can see here.
 And as long as you can keep k small, that could actually work with a global context.
 Okay, not with the position embedding.
 And it doesn't work without the position embeddings.
 And they are not position embeddings, they are attention embeddings.
 Okay, let's or interaction embeddings, to call them position embeddings would be a little
 bit a little bit.
 I mean, they say it's a positional bedding for their relation n to m.
 It's important to note that these, again, are not computed from the input, they are
 simply fixed, they're simply say, if a pixel is on the top left, and the other pixels on
 the bottom right, then they are, their relation is given by this vector right here.
 Okay, so for each pair of pixel, there is an entry in this matrix.
 Now how do we use those?
 Kinda similar, we just start down here, we multiply them with the value.
 And you can see that you will and you contract over m in subsequent equation.
 Where is it?
 Right here, you contract over m, which gives you this thing right here, which you can see
 there is nothing here, now there is an n here.
 So what you'll get naturally is one positional embedding per input.
 So yeah, as I said, it sort of destroys this this notion of first summarizing the context,
 because now it's, it's on again.
 So you're going to take the values and this thing, and you're going to compute from this,
 this lambda p positional lambda, which is of size, and you can see it, it's n by k by
 d.
 And you're going to take, you're going to take the queries, it's going to get complicated.
 So you're going to take the queries over here.
 And you're going to compute the output y p, which is going to be n by d.
 Yes, this is n, this is n, you're going to do it once per, and then you're going to add
 the y's together.
 So this is a plus for the final y.
 So you can see these are two completely linear, this is y c, the content y, two completely
 linearly separable pathways, one comes from these positional encodings, and one comes
 from these from the context.
 And the positional encodings are actually more important in the experiments.
 If they leave those away, nothing works.
 If they leave this summarizing away, then stuff pretty much works still.
 So you know, it's fair to say that the power here comes from the positional encodings.
 And that, again, a bit, it's a bit counter to their to their narrative, because I feel
 that the whole point of the lambda layers is to do this stuff right here.
 And this here is something that you need to make it work.
 But in any case, what you do is you take, you take these positional encodings and you
 multiply them by the values.
 So what this does is this here, this is a special object, this lambda p, as you can
 see, it creates n times k times d tensor.
 And this is it's a big tensor.
 So what does it do for each of the n pieces in the input?
 For each of the n pieces in the input, it creates a one of these lists, right, one of
 these k sized lists, k sized lists of the vectors, as we've seen before, but it does
 so differently for each position.
 Okay.
 So for each position, it creates a different table.
 And the queue again indexes into this table, but into, you know, at the position where
 it is.
 So if you take the query from a particular position in the output, it's going to look
 to its table, aggregated according to what it's interested in.
 So the positional encodings basically say, if you if if if this element in the context,
 if you are the first element in the sequence, then you have to aggregate information according
 to this particular scheme.
 But if you're the second element, you have to aggregate information according to this
 particular scheme.
 So again, it can't look at the contents of what these particular things are, it can only
 kind of define a linear operation.
 However, it can kind of look at the contents of the query, because usually x and c are
 the same.
 So by incorporating v in here, m being equal to n, most often, it can actually do that.
 And again, we see in the results that most of the information actually goes through this
 path.
 The good thing, again, is that so here you have n by m, but you don't have a B, you don't
 have a batch size.
 Here the batch size appears because there is actually a batch size, right, there is
 a batch size here.
 And then the batch size would appear right here.
 But at the moment the batch size appears, the n by m term falls away.
 So there is no m right here, you contract over m as you introduce the batch size.
 So again, there is nowhere an n by m tensor to be held as you add that that is scaled
 by the batch size.
 So there is again, this this kind of performance increase.
 But you can already see here you have we had these nice construction where all the whole
 context constructs this table of vectors, and then the query aggregates it.
 And here we construct a separate table for each element in the input.
 And then the query, according to its position, aggregates that and it simply adds those two
 aggregations together, most of the performance comes from the bottom right here, which you
 can sort of see this as if you know if you have like y equals w x plus b, you can sort
 of see the w here as these tables right here, because they actually depend on what the x
 is, in this case, the position of the x and the b is just something that comes on top
 to every single position that that there is.
 Okay, this is a giant mess.
 But that's about how it works.
 And I hope you didn't you didn't completely you didn't get completely lost in this.
 So they have a whole bunch of extensions, as I said, so they have translation equivalence,
 then because they build their positional encodings as relative encodings, which makes it very
 easy to then build this lambda convolution.
 So you can actually implement this operation here as a convolutional operation to get this
 positional lambda.
 And their whole point is kind of that if I do local attention, right, if I do local attention,
 what I need to do is I kind of if I do local attention, then this thing only pays attention
 to these three, and this thing only pays attention to these three kind of like a convolution.
 But because it's an attention for each of these things, I need to build my attention
 map, I need to build my attention map.
 And that kind of if I want to batch this, if I want to do this at once, I need to sort
 of if this is my interaction matrix, it kind of looks like this, this downward descending
 stairs or something like this.
 And that is not well supported in current frameworks.
 And that makes it a lot like really slow.
 They say, look, even though we use the same amount of let's say memory, as local attention
 or time, sorry time, we can implement it using these primitives, and they are much faster.
 So they are they are going to outperform local attention in that sense.
 They do compare here in terms of time and space to an attention layer.
 Now, they split this into content interactions, which is that first pathway and position interactions
 like this here, this is absolutely irrelevant because it's smaller than the position interaction
 and the position interactions give the performance.
 So you can see clearly that there is in space we have B times n times m, h is the number
 of heads, we don't care much about that right now.
 So B times n times for the attention layer, which is the problem.
 And here you see you have n times m here, but no B. And you have B times n, but no M.
 So that is kind of the the gain right here, as long as you can keep the K small, right,
 this intermediate sequence, which makes sense, right, this attention goes to this intermediate
 sequence.
 So as long as you can keep that intermediate sequence small and fixed, you don't have a
 problem with this quadratic memory, at least you have a problem right here, but that's
 not modulated by the batch size.
 In terms of time, it's still you can see there is a B times n times m, you still have that
 time complexity, because after all, you need to do these multiplications and contracts
 just the same.
 So not much of a difference in terms of time.
 The time argument is more like they can implement it using convolutional operators rather than
 the this kind of striding attention maps.
 They also do this in multi query, multi like multi head and so on.
 And you can see right here that it outperforms outperforms other systems, including like
 systems with self attention, especially in terms of if you see the memory, if you do
 global self attention, it uses a lot of memory.
 In fact, like an out of memory error on their machine axial self attention, these are all
 kind of limits to self attention, local self attention, which comes closest to what they
 do.
 But then what you suffer is a massive drop in performance, whereas their lambda layer
 right here.
 It has a lot of performance.
 And you can see the performance gain, right?
 This is k, I believe k is equal to 16.
 In this example, if they go k to eight, and we know that the attention interaction in
 the lambda networks is not n by m, but actually m by k.
 So if you have k, you can already see there is a massive jump in the number of examples
 you can throughput through the network.
 Okay, so that kind of gives evidence to what we are what what my hypothesis is is going
 on right here.
 Okay, lastly, I've already shown you this table as it outperforms kind of the efficient
 nets.
 And this is a special version of lambda networks, the lambda res nets, where they take a res
 nets and they only they only replace a part of the resnet.
 So if you look at the table down here, these are the different architectures where they
 could replace things in the resnet, for example, the resnet 50 right here.
 So this is all convolutions.
 This is kind of the baseline and you can see that it's like 7200 samples per second.
 If you replace everything by a lambda layer, you're down to like 1160 examples per second.
 Interestingly, if you replace the first layer by a lambda layer, you are also the performance
 drops enormously.
 And that is because of course, the the sizes of the of the of the images get smaller and
 smaller.
 So your your n gets smaller and smaller as you go up the layers.
 As you can see right here, if you only replace the last layer by a lambda layer, then you
 can gain all back almost all of that performance and interestingly still outperform the complete
 convolutional layer.
 And it also has less parameters, you can see the 25 instead of the 18.
 Alright so that was my rant on this paper.
 Again, I hope this wasn't too convoluted.
 There's a lot more to this paper.
 I want to kind of quickly shout out LucidRains and made a made a I got to show you.
 This is hilarious.
 He implemented this so.
 Yes, thank you.
 Implemented this as the paper came out.
 And of course, well, we don't know if Phil Wang is the author of this paper.
 We don't know maybe maybe not.
 Chances are not but still cool that he goes ahead and implements these things.
 I especially I love the conciseness using the INOPs right here.
 So there are as you can see, like this is it.
 That's it.
 That's all.
 The use of INOPs right here to like do this rearrange and INSOM operations, which are
 much more concise than the reshape, squeeze, unsqueeze whatnot.
 So that's pretty cool.
 And the coolest thing is lambda actual Greek letters in the code.
 Thank you, Python.
 So yeah, I invite you to check out this implementation.
 I'll of course link it.
 Tell me what you think of the paper and I'll see you next time.
 Bye bye.