Linformer: Self-Attention with Linear Complexity (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper facebook linear quadratic transformer attention self-attention multi-head attention t2t vasvani bert devlin roberta glue language modeling perplexity dot product johnson lindenstrauss random projection
Transformers are notoriously resource-intensive because their self-attention mechanism requires a squared number of memory and computations in the length of the input sequence. The Linformer Model gets around that by using the fact that often, the actual information in the attention matrix is of lower rank and can be approximated.

OUTLINE:
0:00 - Intro & Overview
1:40 - The Complexity of Self-Attention
4:50 - Embedding Dimension & Multiple Heads
8:45 - Formal Attention
10:30 - Empirical Investigation into RoBERTa
20:00 - Theorem: Self-Attention is Low Rank
28:10 - Linear Self-Attention Method
36:15 - Theorem: Linear Self-Attention
44:10 - Language Modeling
46:40 - NLP Benchmarks
47:50 - Compute Time & Memory Gains
48:20 - Broader Impact Statement
49:55 - Conclusion

Paper: https://arxiv.org/abs/2006.04768

Abstract:
Large transformer models have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. However, training and deploying these models can be prohibitively costly for long sequences, as the standard self-attention mechanism of the Transformer uses O(n2) time and space with respect to sequence length. In this paper, we demonstrate that the self-attention mechanism can be approximated by a low-rank matrix. We further exploit this finding to propose a new self-attention mechanism, which reduces the overall self-attention complexity from O(n2) to O(n) in both time and space. The resulting linear transformer, the \textit{Linformer}, performs on par with standard Transformer models, while being much more memory- and time-efficient.

Authors: Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, Hao Ma

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
 Hi there! Today we're going to look at Linformer self-attention with linear complexity by Sinon Wang, Belinda Li, Madian Kabsa, Han Feng and Hao Ma of Facebook AI. So on a high level this paper observes that often the way we build transformers the self-attention matrix is low rank and can be approximated by first projecting the signal to a lower dimensional space and then performing these inner products that are responsible for attention in there. And thereby you save a lot of the complexity of multiplying full sequence length by full sequence length matrices but instead do these operations in the lower dimensional space. And they achieve a linear scaling of the transformer attention and we'll figure out how that is. As always if you like content like this consider subscribing, sharing, liking and commenting if you feel like it. Okay let's dive in. They say large transformer models have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. Okay so these, if you don't know what a transformer model is you can watch my video on the paper Attention is all you need. That was sort of the beginning of these transformers and it introduces the attention mechanism that we're going to look at today. If you don't know what an attention mechanism is you're not going to have a fun time in this paper. They say however training and deploying these models can be prohibitively costly for long sequences as the standard self attention mechanism of the transformer uses n squared time and space with respect to the sequence length. Now why is that? So really shortly to recap recap this the attention mechanism. These attention, these transformers they transform for basics let's say they transform one sequence into another. So here we have five tokens and the next layer will output five tokens. Okay so five tokens in five tokens out and the question is how do you route information between these five tokens from the first layer to produce the next layer. In a feed-forward network you would simply connect everything to everything and sort of learn the weights of these of these connections. That's not what we do here. In a convolutional network you would simply connect each node to its immediate neighbors like this. But this is also not what we do here. What we do here is we route the information according to the information itself. So according to the incoming information right here we route the information that goes out and we do that by expressing queries and keys. So this incoming information is transformed first of all into what are called keys. Now keys are simply vectors so each node is going to expose a vector right here and each node in the higher layer. Now these are produced by the same from the same information down here but I'm going to draw it conceptually on the higher layer. So each node here is going to expose a query which is sort of like calling the query is calling for what kind of information do you want from the lower layer and the key is sort of exposing what type of information this node contains right now. Now the information is simply routed by looking at the inner products of the keys and the queries. So this information right here would probably be routed to this node right here whereas this one would probably be routed here. This one would be routed here. In fact this is a soft assignment so it's not like a hard routing it's a soft routing. Everything is routed to everything with different weights but the majority goes to the place where the inner product is high and this one is again routed here. So you can see this is the attention mechanism. In order to do this we need to compute the inner product of every single one of these queries with every single one of these keys. And this if our sequence length here is of length n is going to require n squared operations. Now here is another parameter we need to pay attention. These vectors here they have a certain dimension and the certain dimension we're going to call D. The inner the embedding dimension of the vectors. Now in modern transformers you can think of n as something like maybe 512 tokens go into a transformer like this. And the hidden dimension here also is in the same order of magnitude. So you can also imagine this to be something like 512. Now if you think of these matrices if you multiply the keys by the queries however you want to let's do it like this then you have the keys are n by D and the queries are D by n. Now since n and D in this case are the same dimension this matrix is of rank 512. It doesn't have to be but it's a pretty good bet that it's of rank 512. Maybe it's approximately lower rank but now this isn't actually the modern way of transformers as such because usually what we have is multi-head attention which means that we're going to split this inner dimension right here. We're going to split these vectors into many many lower dimensional vectors and then have attention mechanism on these lower dimensional vectors. And that's such that you don't only have one attention mechanism you have multiple attention mechanisms so you can route different kinds of information with these multiple attention heads. Now sometimes you would split this you could split this in a modern transformer up to like 16 different heads but here we're going to let's say we're going to split this into four subvectors each of 128 dimensions. So we're going to split this up and now if this product here is only computed on these lower dimensional vectors so all of a sudden you no longer have n by D but you have like n by D over 4 and now this is 512 still but this now is 128 so the rank of this matrix is going to be 128. Mind it's still the thing that comes out is still a 512 by 512 matrix but it is of rank 128 and that means even though this matrix contains vectors that are of size 512 they could be they could be represented accurately by a matrix that's just 128 dimensions. Okay so these these 512 dimensions actually only contain information that is 128 dimensional in nature. It's just distributed over 512 dimensions but most of these are redundant. So in fact in these modern transformers these thing here this matrix here is low rank and therefore that's what this paper sort of exploits we could we could approximate this by 128 dimensions. Okay this is our starting point. They go on and they say in this paper we demonstrate that the self-attention mechanism can be approximated by a low rank matrix. We further exploit this finding to propose a new self-attention mechanism which reduces the overall self-attention complexity from n squared to n in both time and space. The resulting linear transformer the Lin former performs on par with standard transformer models while being much more memory and time efficient. Alright so let's dive into their thing. This is how they formulate the attention mechanism. So right here the attention has queries and keys as you can see here. Now these W matrices you can largely ignore. The W simply maps the queries to so this is these are simply d by d matrices that are a linear transformation of the queries. You can sort of overlook them for the arguments in this paper. So these are the keys and the queries we talked about. The values here this is the actual information that's being routed. So what we want to do is we want to compute this product between queries and keys right here and scale it appropriately. But ultimately this is this product. Then run this through a softmax operation. That means we normalize it such that it sums to one, the distribution sums to one. And then we want to route this information according to that distribution. So that's how they formulate an attention mechanism. Now notice something. This thing in here is what they call the matrix A and this is what I've demonstrated to be low rank. Now the actual thing that you would need to be low rank for their paper to hold is the matrix P which is different because this is after the softmax right. So if the matrix P is low rank then you have a legitimate claim of approximating this routing via a low rank matrix. However if P is not low rank you don't. Okay all right now the first thing they're going to show is that this is in fact low rank. So self-attention is low rank. And for that they make an empirical investigation into Roberta. So Roberta is a model that's based on BERT and I have made videos of both BERT and Roberta I believe. If sorry if you want to go look those up. But it is one of these transformer models and they take two data sets wiki103 and IMDB and they run them through this model and they look at this P matrix. So they look at how this information routing matrix is built and then they calculate the eigenvalues of that. So you calculate the eigenvalues and by looking at the eigenvalues you can look at the rank of a matrix broadly speaking. So if you list the eigenvalues in order of their size then a matrix that is sort of high dimensional has a high rank would have sort of a slope like this and that means as you go as you go to the next and next and next eigenvalue they drop like if you order a set of uniformly distributed numbers if you order them then it would look like this right so there is no particular dimension that's that's better than any or has much more information than any other. However if the matrix is approximately low rank you would look something like this and that would mean that most of the information is concentrated in very few dimensions and those are the ones with very high eigenvalues and most of the dimensions have no information. The thing you see here is simply the cumulative sum of these things so if you calculate the cumulative sum of this you'll get that over here. So if this is very high rank you would expect a curve that goes like this sort of slanted but not very. If this is very low rank you would expect a curve that goes very much into the corner right here and they show that the general shape here is such that there is this kind of a kink to it as you can see here. Now also notice that the axis here starts at 0.4 so actually this comes from down here somewhere and goes up and then goes like this. So they have a I feel they have a legitimate claim here that these matrices are approximately low rank and here they look at I don't actually know at which layer this is or if this is in all of the layers overall or something like this but they look at how this develops inside the layers so they look at the always the 128th eigenvalue and they discover that as they go deeper and deeper into the network this cumulative eigenvalue is higher and higher that means that network puts more and more information into fewer and fewer dimension in this routing as you go up the layers so it gets more and more skewed as you go up the layers it gets more and more into this corner right here so their claim appears to be more and more true. Now I have sort of thought about this a little and I've tried it out a bit myself and I invite you to just follow me here shortly. So right here I have a matrix that is just a random Gaussian matrix of size 512 by 512. If we look at the eigen spectrum of that so I have this function SVD it simply gives me the eigen spectrum of that then you can see that it sort of falls off uniformly and that will result in a in this cumulative sum of pretty much flat curve or slowly ascending curve like this. Now if we actually have a low rank matrix this would look different this would have this sort of typical kink in it and we can demonstrate that by making a lower dimensional matrix so let's just take let's just go 512 by 128 of this lower dimensional and and let's look at the MT now this only goes to 128 because we only get back 128 singular values so let's make a lower dimensional matrix that's actually 512 by 512 so if we do this this is sort of what they're doing in this this will construct a 512 by 512 matrix but that is only of rank 128 right and you can see that at the 128 singular or eigenvalue this snaps right at the at the one so it's sort of like what they what they have okay so we've seen the difference between a let's say higher rank matrix and the low rank matrix in this cumulative sum plot now I want to go back to the original matrix right here of course there the matrices they look at these routing matrices they're not Gaussian they're not sort of distributed with mean zero and the nice variance they are the result of a softmax operation and in particular that means they're all positive and that means that their mean is not zero so if you look at a data set and it's mean it's not zero and you calculate like the the eigenvalues or in this case the principal component you will find that the first one will be very strong because that must account for the fact that the mean is not at the center or the first few will be like this so it is sort of maybe we can replicate this right here so let's say we'll put M through let's first go with the absolute value of M okay not much of a change but you already see that this axis doesn't start at zero so let's go let's actually how do we do this xlim right xlim zero none so haha okay so the first one you simply have to imagine or I can do even something something more we can just put a zero in front here and that should do the trick no yes oh that's X I meant Y calm and dumb never mind this will work as well so you already get this sort of of kink and let's put it into the softmax so we'll put a softmax and that gives you also this kink now you might think that wait this is that this kink looks a lot smaller than the other kink so but if we simply modify let's modify the standard deviation of this random matrix and you can see that this spectrum immediately changes right because of the interaction now between the softmax and the standard deviation if I only were to change the standard deviation on the normal M matrix and we can actually try this right here that wouldn't do much that would still look pretty much the same it's just differently scaled but in the interaction with the softmax now this changes the spectrum dramatically and here as you know these these transformers have always sort of like layer normalization and so on so probably the standard deviation if we if if these are sort of Gaussian the standard deviation before the softmax would be a lot smaller so let's go something like this so smaller than one and can we run this please and you can see that this kink immediately appears now it's not it's it's it's not the same thing as this other as this here because this is a lot smoother as you can see right here but still I feel that this might not actually be a result of the you know the fact that this is an attention mechanism but it simply might be the result of that you apply a softmax now still that doesn't change the fact that it is approximately a lower rank matrix everything they say holds but yeah maybe maybe one should also look into why exactly that happens but in fact it is low rank okay it is approximately low rank they've demonstrated this and now they go to their first first theory below we provide a theoretical answer a theoretical analysis of the above spectrum results okay so the theoretical analysis theorem one is self-attention is low rank and we're going to go through this just glance at it for now they say for any of these query key values and these matrices which of course you can ignore for now for any column vector W of matrix V W and W here that's the information that needs to be routed there exists a low rank matrix P tilde so this P tilde here is going to be their low rank approximation of the P matrix you can see it's still n by n but it's going to be low rank in fact it's going to be of the order of the logarithm of the rank of the full matrix or well the full matrix of the rank that the full matrix could have as we have already seen the full matrix doesn't have full rank but yeah okay so if you use and this is the type of guarantee you get so what do we see here it basically means that this distance here is smaller than this and this here this is just the norm of one of these vectors projected times this error coefficient epsilon so all it says is that the distance on the left is smaller than something and that occurs with high probability okay so the entire guarantee here the entire formula just basically means that this thing is small this norm is small what's this norm this norm is the distance between these two things now what are these two things this is the information that we want to route and this is the routing matrix and that simply means that if I route my information using the P tilde this approximation then I won't be too far away as if I had routed my information using the original P matrix okay that's that's it that's what the theorem says the theorem says if I route my information using this approximation then I am not too far away as it had I routed my information using the original routing matrix that I don't say how they're going to construct they simply say there exists a low rank matrix like this and the proof of this and it's sort of worth looking at the proof of it it uses the Johnson Linden Strauss lemma this thing here or the JL for short and they're going to get this out of the JL now the Johnson Linden Strauss lemma in a classic sense says something like this if I have data in a high dimensional space here in a three dimensional space okay I have data distributed and I use a certain kind of projection matrix and there are a number so the the JL gives conditions on what these projections can be but for example a randomly sampled matrix with zero mean Gaussian entries and 1 over K standard deviation where K is the dimension you project into can do the trick so if I project my data in a certain way into a lower dimension here dimension 2 then the projected data is related to the original data by the fact that the distances between the points in the original space will not be distorted too much so the distances between these points are approximately preserved through this projection okay so that's that's the that's the Johnson Linden Strauss lemma now you'll notice here there is no reference to the fact that this data is or isn't low rank it's simply high dimensional data projected to lower dimension and the distances are approximately preserved and this theory here and I've looked at it for a while now they simply define okay they define this P matrix as this attention mechanism and here you can see the A matrix we've discussed before which is actually low rank but we don't know yet if the softmax is they write it as this form right here of the exponential of each entry of a divided by this diagonal right here so in the softmax of course you have the exponential of each entry divided by the sum of the entries and they write this simply as two matrices but ultimately this is a matrix right here and all they do is they take this P matrix and they apply the Johnson Linden Strauss lemma by having this projection matrix R and R is entries from this Gaussian as I said so this is the special type of projection that the JL addresses and then simply says if you pull if you this here is going to be your P tilde so if you project R in this manner and obtain P tilde and then you use P tilde instead of P then this this is going to be very close in fact you can reformulate the JL into different variants such that it gives you things like this things like saying that the distance between this projected version and this unprojected version is going to be a constant smaller than a constant time the norms of the unprojected version that is equivalent to saying that the distances are preserved now you can see right here nowhere in this theorem is the fact that this is self-attention and nowhere in the theorem appears the fact that this inner matrix A is low rank or even that this matrix A exists it's you can do this with any matrix P right the JL doesn't concern itself with the nature of this matrix P it says any matrix any sort of high dimensional data you can project to low dimensional data and this holds if you choose the projection correctly which they do right here so to claim that this theorem proves that self-attention is low rank to me is a bit it's a bit of a statement that is not warranted like this here should read something like the Johnson Lindenstrout's lemma exists or something like this it I'm not I'm not sure like convince me otherwise but yeah so they go with this so they say given the low rank property of the context mapping matrix P now again I disagree that this has been shown except empirically one straightforward idea is to use singularality composition to approximate P with a low rank matrix P low as follows so what you could do is you could simply learn these low rank matrices and approximate P through it or you can decompose P as such and then have these easier inner products in dimension K but they say however this approach requires performing an SVD decomposition in each self-attention matrix which adds additional complexity therefore we propose another approach for a low rank approximation that avoids this added complexity okay so they now come up with their model and their model goes as follows so here on the left you see a classic attention mechanism with their projections built in what they're proposing is they say let's project the matrix K using one of these random projections and then this attention routing if you route if you now multiply so you multiply K and Q right here K times Q and then you put it into the softmax and then you use it to route this W so they say if we build in this projection matrix that will project K to a lower dimension and then we won't have as expensive of inner products now the important part to see here is that if you think of this lower projection the first thing you think is that you project this inner this hidden dimension D right to a lower dimension and that's not the case here you actually project the N so in in a conceptual framework so you can see right here forget about this this is this W matrix in a conceptual framework you see here is this N by D matrix which are the keys so N is the sequence length and D is the dimensions and what you want to do is you want to project that by this matrix which is K by N so you want to reduce the sequence length you can see in this matrix right here why that might work because N is much larger than D and that means this matrix can be at most rank D right so you should not lose too much you should sort of be able to preserve the information if you project this N to a K where the K if the K is still larger than the D or approximately in the same order of magnitude you should be able to preserve that information if you do it in a smart way so conceptually if we have our five token sequence like here and the next layer produces five tokens again what we first do is we say we know we know that the information we want is not five dimensional it's actually two dimensional because okay let's say these this inner dimension D is is two as well so we have two dimensional vectors each thing exposes two dimensional vectors so we first project the sequence of length five to a sequence of length two and we simply do that in a random manner so we have a random Gaussian matrix that assigns weights to mix these five into these two and again because the JL works for any sort of data but in my argumentation if you you know think that this here is low rank it's of rank two then you shouldn't lose too much information by projecting it to a sequence length two and now we do this attention mechanism so now we expose the keys and now we expose the queries up here and now you can see instead of routing five things with five things you only have to route five things with two things and so instead of having O and squared you now have O N K if K K is the number right here okay so this is the idea you project the sequence length and it comes from the fact that the sequence length is much larger than the dimensionality and therefore you can sort of preserve the information if you project in a smart way they build this in this fashion right here so the attention mechanism now before we saw it was between the queries and the keys right here they built now this projection matrix here that projects the keys into a lower dimensional sequence and the now such that this will result in an N by K attention matrix we saw over here you don't need to route N by N things you need to route N by K so this this routing table in here is now N by K now the next layer as you can see here it actually needs to produce a sequence of length five again right so we always transform sequence of length five into sequence of length five but now we have we have this N corresponds to the sorry corresponds to the next layer and this K corresponds to the down projected sequence of the last layer and in order for that to fit we of course also need to down project the information that we're routing so if we don't project the routing table we also need to down project the information that we're routing that's we do this by a similar matrix F that is also sampled in this way in this special way and that gives us a K by D so we have projected the sequence to size K and if we multiply these two things again of course we'll get out an N by D matrix which is the signal for the next layer okay so an N by D signal comes in down here it's projected down to K sequence length it's and it's routed up again to N sequence length and you have again an N by D matrix here cool so that's how they do it and they build this into the transformer now as I understand it these projection matrices again they're not learned they are built up in this JL conscribed way they are not learned they are fixed once and then that's that's that at least that's how I understand it so there are no more learnable parameters okay so here they have a demonstration where they up the sequence length and you can see the batch size decreases but that's just to sort of keep the total amount of flops to be done the same you up the sequence length and down the batch size as the sequence length increases the standard transformers requirement in inference time goes up and this here as you can see this is not a linear scale it's a log scale log 2 so this goes up with the sequence length and it should go up quadratically right and you can also see that the Lin former keeps fairly constant for the same K now of course as you increase the K of the Lin former the inference time will go up because now it's dependent on N times K and not on N times N okay so let's look a bit further of how you have to choose that K up here in the first theorem we there was a already a hint to it in the first theorem you had to choose K by 5 log N and this is a problem so here you have log N that means it's not so O of N K is equal to O of N log N now that's not linear that's actually that's the same as the reformer but they want to get to a linear place and theorem 2 explains goes now to a linear shows how you can make self-attention linear okay they show again blah blah blah blah now you have to choose K at the minimum of these two things and you can see right here that one of them is independent of N so that means as N grows of course the minimum is no longer going to be this here the minimum is actually going to be the thing on the left and that is dependent on just D okay so you have D log D in here and that makes sense because in the very beginning we said hey D is actually much smaller than N and that means the information that is contained in these matrices is at most rank D so if we down project to K we should adjust K to what D is right if we adjust K to about the same thing as D we're guaranteed to not lose too much information so now we choose K according to D instead of according to N and therefore the computation is linear in N and N times K is like N times D to log D so it's linear in K and linear in D how do we get there so the first thing they do is they make these sort of Johnson-Lindenstrout statements again but now instead of the general statement they plug in their actual modified attention mechanism so here they have a bound on the distance between if I route my this is the information to be routed right if I route my information using the original softmax and this in here is the matrix A if the original tension mechanism I won't be too far away as if I were to route my information using this modified attention mechanism now the tricky part here mathematically I believe is that is is exactly the softmax what what I alluded to right so this softmax is the tricky part because if this weren't a softmax so if the softmax weren't here this would simply be a projection down and a projection up and the dilemma would almost apply as it is written right there you wouldn't have to actually do anything but the question is if this inside the softmax is is low rank can you make a claim that the entire softmax then is also low rank and it's not entirely clear because because oh yes we've done this so you can see right here that the softmax we have actually done the softmax of a low rank matrix so we have already seen the low rank matrix itself and how it immediately snaps to the to the upper axis after 128 now if we do the same thing for the softmax of that and we probably have to take away some of these dimensions the first few let's go with let's go to dimension 100 and look from there okay same thing okay that's pretty good I did not expect that hi there so this is Yannick from the future I've realized I've been an idiot in how I constructed these low rank matrices right here by multiplying MT by itself of course what's a better way to do it is to construct two independent 128 dimensional matrices like these two sub slices of M right here and then multiplying those together and looking at the SVD and you as you can see right here so the softmax of this is now not of this super low rank anymore it's still low rank but it's not not very it's not like hard low rank so if I just look at the matrix without the softmax then you can see it has a very peak that by at the 128 which gives us the indication it's actually 128 rank which we already knew but if we now introduce the softmax then you can see that this vanishes and it's no longer 128 dimensional and it's only approximately low rank as you can see all right back to Yannick in the past who is wholly surprised that the two that if you multiply MT by itself that that will give you back the the exact same thing all right so did we try this before maybe we did okay but the mathematical difficulty still remains and their main thing here is so they have a first first version where they pretty much plug it into the JL again and they they get out this K is the K needs to be by log n but they say this result does not utilize the low rank property of matrix A and the resultant K has a dependency on sequence length n and then in the appendix they finally go through the math to show that now if they choose E and F like this they can actually pull out this and show that the K is where you have it the decay is independent of n like this and I think the main the main step in this proof is the step B here where they say uses the fact that the exponential function is Lipschitz continuous in a compact region then we can choose a small enough Delta such that the as you can see here this now directly relates to this projection matrix within the exponential function to the projection matrix out of the exponential function so you can basically say that if I project first and then use the exponential function that's not too different than if I first use the exponential function and then project okay so that's the that's the sort of of of catch here now they only do this for the exponential function not the actual softmax as you can see here throughout they do it to the exponential function and also here in their statements the softmax isn't the exponential function the softmax is the exponential function divided by the sum of the exponential functions but I believe that this generalizes straightforwardly alright so for given choices of Delta and K they have shown that the Lin former in fact can do in a linear fashion what a transformer can do in a quadratic fashion and they are not too far off ok that's that's their point right here the results on these benchmarks sorry let's first go to the perplexities in language modeling so they show right here that they pretty much can keep up with the standard transformer as you can see here so with the standard transformer they can keep up here now think that this the the computation is n times K ok so something like this Lin former with K cost 256 will only so instead of n by n it's n times K it won't save you too much in that case but it's it's not too surprising that in fact you have the same performance because probably the standard transformer is distributed over more heads than two so the information necessarily has a lower dimensionality 10 to 56 one thing I want to draw attention to though here is that you can see that here it's not really done learning yet and as you can see the standard transformer sort of surpasses all of these models towards the end I wonder I wonder what happens I wouldn't be surprised if they end up sort of at the same place but I wonder if these diverge even more right here after that they also compare with a higher sequence length and the standard transformer outperforms the Lin former but of course the point here is that the Lin former is much much much faster and can keep up now also the scale here of the perplexity you see these are percentage points in perplexity but I can't actually tell if that matters or not I think I think in the original transformer paper the perplexities hovered between like three point something and five point something so this might actually be sort of significant differences and I'm not sure they investigate different methods of sharing these weights of these of these projections and they seems like they don't find real differences but I don't want to go into that because this video is already really long and then they look at what happens if they up the sequence length that they put into the Lin former and you can see that the Lin former can deal with higher sequence lengths and arrive at the same perplexities though again I don't know how much different that is and the scale here is larger than before but yeah so how does this fare on these benchmarks where you first train a transformer with pre training with language modeling and then you use it to do certain NLP tasks and here you can see that the Lin former is on par in some of these tasks with the original transformer but also you can see like a pattern where you can see pretty wild results in that you know sometimes the the Lin former here will be better than this but then also variants of the Lin former will be worse and they'll even be worse than this and sometimes they'll be better sometimes this Lin former is good and sometimes the original model is the best so this sort of points to you can make the general claim that the Lin former doesn't destroy your your gains but also it's not like a a better model it's simply a faster model that in some tasks can keep up with the original model and they show that of course this is the real deal here that as you go up in length the performance gains and also sorry this this way the performance gains and the memory gains that you get by the Lin former are dramatic of course the longer and you go and to the lower dimension you project the more these gains are but of course the more performance you're going to lose potentially hello again Yannick from the future just wanted to draw your attention on this beautiful broader impact statement in this paper saying our work focuses on making transformers more efficient everything cool potential positive in spec impacts of efficient transformers that's pretty cool it also has potential impact on training transformers on images since we can support very long sequences very cool furthermore there are positive environmental benefits very cool I mean these are all very cool things they say as such we see no immediate negative ethical or societal impacts of our work beyond what applies to the core building blocks of deep learning do better now this this honestly I agree with them right I completely agree with them that this is sort of a good thing you might trade off you know some accuracy might some make some approximations but you will get a much faster model and this model has any model can be used you know for things and and that they now have to pull out of there out of their but some way in in in over five steps of intermediate layers this could be used for bad it just seems ridiculous so good on them for defying the please also think about negative impacts right here all right back to back back to past Yannick all right this was the Lin former paper I hope this somewhat makes sense made sense to you I had to read it multiple times for it to make sense to me but ultimately it's all about the fact that you have these multiple heads and therefore your information is probably lower dimensional and you can abuse that and to just calculate in this lower dimension all right I'll see you next time bye bye
 Hi there! Today we're going to look at Linformer self-attention with linear
 complexity by Sinon Wang, Belinda Li, Madian Kabsa, Han Feng and Hao Ma of
 Facebook AI. So on a high level this paper observes that often the way we
 build transformers the self-attention matrix is low rank and can be
 approximated by first projecting the signal to a lower dimensional space and
 then performing these inner products that are responsible for attention in
 there. And thereby you save a lot of the complexity of multiplying full sequence
 length by full sequence length matrices but instead do these
 operations in the lower dimensional space. And they achieve a linear scaling
 of the transformer attention and we'll figure out how that is. As always if you
 like content like this consider subscribing, sharing, liking and
 commenting if you feel like it. Okay let's dive in. They say large transformer
 models have shown extraordinary success in achieving state-of-the-art results in
 many natural language processing applications. Okay so these, if you don't
 know what a transformer model is you can watch my video on the paper
 Attention is all you need. That was sort of the beginning of these
 transformers and it introduces the attention mechanism that we're going to
 look at today. If you don't know what an attention mechanism is you're not going
 to have a fun time in this paper. They say however training and deploying these
 models can be prohibitively costly for long sequences as the standard self
 attention mechanism of the transformer uses n squared time and space with
 respect to the sequence length. Now why is that? So really shortly to recap
 recap this the attention mechanism. These attention, these transformers they
 transform for basics let's say they transform one sequence into another. So
 here we have five tokens and the next layer will output five tokens. Okay so
 five tokens in five tokens out and the question is how do you route
 information between these five tokens from the first layer to produce the next
 layer. In a feed-forward network you would simply connect everything to
 everything and sort of learn the weights of these of these connections. That's not
 what we do here. In a convolutional network you would simply connect each
 node to its immediate neighbors like this. But this is also not what we do here.
 What we do here is we route the information according to the information
 itself. So according to the incoming information right here we route the
 information that goes out and we do that by expressing
 queries and keys. So this incoming information is transformed first of all
 into what are called keys. Now keys are simply vectors so each node is going to
 expose a vector right here and each node in the higher layer. Now these are
 produced by the same from the same information down here but I'm going to
 draw it conceptually on the higher layer. So each node here is going to expose a
 query which is sort of like calling the query is calling for what kind of
 information do you want from the lower layer and the key is sort of exposing
 what type of information this node contains right now. Now the information
 is simply routed by looking at the inner products of the keys and
 the queries. So this information right here would probably be routed to this
 node right here whereas this one would probably be routed here. This one would
 be routed here. In fact this is a soft assignment so it's not like a hard
 routing it's a soft routing. Everything is routed to everything with different
 weights but the majority goes to the place where the inner product is high
 and this one is again routed here. So you can see this is the attention
 mechanism. In order to do this we need to compute the inner product of every
 single one of these queries with every single one of these keys. And this if
 our sequence length here is of length n is going to require n squared
 operations. Now here is another parameter we need to pay attention.
 These vectors here they have a certain dimension and the certain dimension
 we're going to call D. The inner the embedding dimension of the vectors. Now
 in modern transformers you can think of n as something like maybe 512 tokens go
 into a transformer like this. And the hidden dimension here also is in the
 same order of magnitude. So you can also imagine this to be something like 512.
 Now if you think of these matrices if you multiply the keys by the queries
 however you want to let's do it like this then you have the keys are n by D and
 the queries are D by n. Now since n and D in this case are the same
 dimension this matrix is of rank 512. It doesn't have to be but it's
 a pretty good bet that it's of rank 512. Maybe it's approximately lower rank but
 now this isn't actually the modern way of transformers as such because usually
 what we have is multi-head attention which means that we're going to split
 this inner dimension right here. We're going to split these vectors into many
 many lower dimensional vectors and then have attention mechanism on these lower
 dimensional vectors. And that's such that you don't only have one attention
 mechanism you have multiple attention mechanisms so you can route different
 kinds of information with these multiple attention heads. Now sometimes you would
 split this you could split this in a modern transformer up to like 16
 different heads but here we're going to let's say we're going to split this into
 four subvectors each of 128 dimensions. So we're going to split this up
 and now if this product here is only computed on these lower
 dimensional vectors so all of a sudden you no longer have n by D but you have
 like n by D over 4 and now this is 512 still but this now is 128 so the rank of
 this matrix is going to be 128. Mind it's still the thing that comes out is
 still a 512 by 512 matrix but it is of rank 128 and that means even though this
 matrix contains vectors that are of size 512 they could be they could be
 represented accurately by a matrix that's just 128 dimensions. Okay so these
 these 512 dimensions actually only contain information that is 128
 dimensional in nature. It's just distributed over 512 dimensions but most
 of these are redundant. So in fact in these modern transformers these thing
 here this matrix here is low rank and therefore that's what this paper sort
 of exploits we could we could approximate this by 128 dimensions. Okay
 this is our starting point. They go on and they say in this paper we
 demonstrate that the self-attention mechanism can be approximated by a low
 rank matrix. We further exploit this finding to propose a new self-attention
 mechanism which reduces the overall self-attention complexity from n squared
 to n in both time and space. The resulting linear transformer the Lin
 former performs on par with standard transformer models while being much more
 memory and time efficient. Alright so let's dive into their thing. This is how
 they formulate the attention mechanism. So right here the attention has queries
 and keys as you can see here. Now these W matrices you can largely ignore. The W
 simply maps the queries to so this is these are simply d by d matrices that
 are a linear transformation of the queries. You can sort of overlook them
 for the arguments in this paper. So these are the keys and the queries we
 talked about. The values here this is the actual information that's being routed.
 So what we want to do is we want to compute this product between queries and
 keys right here and scale it appropriately. But ultimately this is
 this product. Then run this through a softmax operation. That means we
 normalize it such that it sums to one, the distribution sums to one. And then we
 want to route this information according to that distribution. So that's
 how they formulate an attention mechanism. Now notice something. This thing in here
 is what they call the matrix A and this is what I've demonstrated to be low rank.
 Now the actual thing that you would need to be low rank for their paper to hold
 is the matrix P which is different because this is after the softmax right.
 So if the matrix P is low rank then you have a legitimate claim of approximating
 this routing via a low rank matrix. However if P is not low rank you don't.
 Okay all right now the first thing they're going to show is that this is in
 fact low rank. So self-attention is low rank. And for that they make an
 empirical investigation into Roberta. So Roberta is a model that's based on BERT
 and I have made videos of both BERT and Roberta I believe. If sorry if you want
 to go look those up. But it is one of these transformer models and they take
 two data sets wiki103 and IMDB and they run them through this model and they
 look at this P matrix. So they look at how this information routing matrix is
 built and then they calculate the eigenvalues of that. So you calculate
 the eigenvalues and by looking at the eigenvalues you can look at the rank of
 a matrix broadly speaking. So if you list the eigenvalues in order of their size
 then a matrix that is sort of high dimensional has a high rank would have
 sort of a slope like this and that means as you go as you go to the next and
 next and next eigenvalue they drop like if you order a set of uniformly
 distributed numbers if you order them then it would look like this right so
 there is no particular dimension that's that's better than any or has much more
 information than any other. However if the matrix is approximately low rank you
 would look something like this and that would mean that most of the information
 is concentrated in very few dimensions and those are the ones with very high
 eigenvalues and most of the dimensions have no information. The thing you see
 here is simply the cumulative sum of these things so if you calculate the
 cumulative sum of this you'll get that over here. So if this is very high rank
 you would expect a curve that goes like this sort of slanted but not very. If
 this is very low rank you would expect a curve that goes very much into the
 corner right here and they show that the general shape here is such that there is
 this kind of a kink to it as you can see here. Now also notice that the axis here
 starts at 0.4 so actually this comes from down here somewhere and goes up and
 then goes like this. So they have a I feel they have a legitimate claim here
 that these matrices are approximately low rank and here they look at I don't
 actually know at which layer this is or if this is in all of the layers overall
 or something like this but they look at how this develops inside the layers so
 they look at the always the 128th eigenvalue and they discover that as
 they go deeper and deeper into the network this cumulative eigenvalue is
 higher and higher that means that network puts more and more information
 into fewer and fewer dimension in this routing as you go up the layers so it
 gets more and more skewed as you go up the layers it gets more and more into
 this corner right here so their claim appears to be more and more true. Now I
 have sort of thought about this a little and I've tried it out a bit myself and I
 invite you to just follow me here shortly. So right here I have a matrix
 that is just a random Gaussian matrix of size 512 by 512. If we look at the
 eigen spectrum of that so I have this function SVD it simply gives me the
 eigen spectrum of that then you can see that it sort of falls off uniformly and
 that will result in a in this cumulative sum of pretty much flat curve or slowly
 ascending curve like this. Now if we actually have a low rank matrix this
 would look different this would have this sort of typical kink in it and we
 can demonstrate that by making a lower dimensional matrix so let's just take
 let's just go 512 by 128 of this lower dimensional and and let's look at the MT
 now this only goes to 128 because we only get back 128 singular values so
 let's make a lower dimensional matrix that's actually 512 by 512 so if we do
 this this is sort of what they're doing in this this will construct a
 512 by 512 matrix but that is only of rank 128 right and you can see that at
 the 128 singular or eigenvalue this snaps right at the at the one so it's
 sort of like what they what they have okay so we've seen the difference between
 a let's say higher rank matrix and the low rank matrix in this cumulative sum
 plot now I want to go back to the original matrix right here of course
 there the matrices they look at these routing matrices they're not Gaussian
 they're not sort of distributed with mean zero and the nice variance they are
 the result of a softmax operation and in particular that means they're all
 positive and that means that their mean is not zero so if you look at a data
 set and it's mean it's not zero and you calculate like the the eigenvalues or in
 this case the principal component you will find that the first one will be
 very strong because that must account for the fact that the mean is not at the
 center or the first few will be like this so it is sort of maybe we can
 replicate this right here so let's say we'll put M through let's first go with
 the absolute value of M okay not much of a change but you already see that this
 axis doesn't start at zero so let's go let's actually how do we do this xlim
 right xlim zero none so haha okay so the first one you simply have to imagine or
 I can do even something something more we can just put a zero in front here and
 that should do the trick no yes oh that's X I meant Y calm and dumb never
 mind this will work as well so you already get this sort of of kink and
 let's put it into the softmax so we'll put a softmax and that gives you also
 this kink now you might think that wait this is that this kink looks a lot
 smaller than the other kink so but if we simply modify let's modify the standard
 deviation of this random matrix and you can see that this spectrum immediately
 changes right because of the interaction now between the softmax and the
 standard deviation if I only were to change the standard deviation on the
 normal M matrix and we can actually try this right here that wouldn't do much
 that would still look pretty much the same it's just differently scaled but in
 the interaction with the softmax now this changes the spectrum dramatically
 and here as you know these these transformers have always sort of like
 layer normalization and so on so probably the standard deviation if we
 if if these are sort of Gaussian the standard deviation before the softmax
 would be a lot smaller so let's go something like this so smaller than one
 and can we run this please and you can see that this kink immediately appears
 now it's not it's it's it's not the same thing as this other as this here because
 this is a lot smoother as you can see right here but still I feel that this
 might not actually be a result of the you know the fact that this is an
 attention mechanism but it simply might be the result of that you apply a softmax
 now still that doesn't change the fact that it is approximately a lower rank
 matrix everything they say holds but yeah maybe maybe one should also look
 into why exactly that happens but in fact it is low rank okay it is
 approximately low rank they've demonstrated this and now they go to
 their first first theory below we provide a theoretical answer a
 theoretical analysis of the above spectrum results okay so the theoretical
 analysis theorem one is self-attention is low rank and we're going to go
 through this just glance at it for now they say for any of these query key
 values and these matrices which of course you can ignore for now for any
 column vector W of matrix V W and W here that's the information that needs to be
 routed there exists a low rank matrix P tilde so this P tilde here is going to
 be their low rank approximation of the P matrix you can see it's still n by n but
 it's going to be low rank in fact it's going to be of the order of the
 logarithm of the rank of the full matrix or well the full matrix of the rank that
 the full matrix could have as we have already seen the full matrix doesn't
 have full rank but yeah okay so if you use and this is the type of guarantee
 you get so what do we see here it basically means that this distance here
 is smaller than this and this here this is just the norm of one of these vectors
 projected times this error coefficient epsilon so all it says is that the
 distance on the left is smaller than something and that occurs with high
 probability okay so the entire guarantee here the entire formula just basically
 means that this thing is small this norm is small what's this norm this norm is
 the distance between these two things now what are these two things this is
 the information that we want to route and this is the routing matrix and that
 simply means that if I route my information using the P tilde this
 approximation then I won't be too far away as if I had routed my information
 using the original P matrix okay that's that's it that's what the theorem says
 the theorem says if I route my information using this approximation
 then I am not too far away as it had I routed my information using the original
 routing matrix that I don't say how they're going to construct they simply
 say there exists a low rank matrix like this and the proof of this and it's sort
 of worth looking at the proof of it it uses the Johnson Linden Strauss lemma
 this thing here or the JL for short and they're going to get this out of the JL
 now the Johnson Linden Strauss lemma in a classic sense says something like this
 if I have data in a high dimensional space here in a three dimensional space
 okay I have data distributed and I use a certain kind of projection matrix and
 there are a number so the the JL gives conditions on what these projections can
 be but for example a randomly sampled matrix with zero mean Gaussian entries
 and 1 over K standard deviation where K is the dimension you project into can do
 the trick so if I project my data in a certain way into a lower dimension here
 dimension 2 then the projected data is related to the original data by the fact
 that the distances between the points in the original space will not be distorted
 too much so the distances between these points are approximately preserved
 through this projection okay so that's that's the that's the Johnson Linden
 Strauss lemma now you'll notice here there is no reference to the fact that
 this data is or isn't low rank it's simply high dimensional data projected
 to lower dimension and the distances are approximately preserved and this theory
 here and I've looked at it for a while now they simply define okay they define
 this P matrix as this attention mechanism and here you can see the A
 matrix we've discussed before which is actually low rank but we don't know yet
 if the softmax is they write it as this form right here of the exponential of
 each entry of a divided by this diagonal right here so in the softmax of course
 you have the exponential of each entry divided by the sum of the entries and
 they write this simply as two matrices but ultimately this is a matrix right
 here and all they do is they take this P matrix and they apply the Johnson
 Linden Strauss lemma by having this projection matrix R and R is entries
 from this Gaussian as I said so this is the special type of projection that the
 JL addresses and then simply says if you pull if you this here is going to be
 your P tilde so if you project R in this manner and obtain P tilde and then you
 use P tilde instead of P then this this is going to be very close in fact you
 can reformulate the JL into different variants such that it gives you things
 like this things like saying that the distance between this projected version
 and this unprojected version is going to be a constant smaller than a constant
 time the norms of the unprojected version that is equivalent to saying that
 the distances are preserved now you can see right here nowhere in this theorem
 is the fact that this is self-attention and nowhere in the theorem appears the
 fact that this inner matrix A is low rank or even that this matrix A exists
 it's you can do this with any matrix P right the JL doesn't concern itself with
 the nature of this matrix P it says any matrix any sort of high dimensional data
 you can project to low dimensional data and this holds if you choose the
 projection correctly which they do right here so to claim that this theorem
 proves that self-attention is low rank to me is a bit it's a bit of a statement
 that is not warranted like this here should read something like the Johnson
 Lindenstrout's lemma exists or something like this it I'm not I'm not sure like
 convince me otherwise but yeah so they go with this so they say given the low
 rank property of the context mapping matrix P now again I disagree that this
 has been shown except empirically one straightforward idea is to use
 singularality composition to approximate P with a low rank matrix P low as
 follows so what you could do is you could simply learn these low rank
 matrices and approximate P through it or you can decompose P as such and then
 have these easier inner products in dimension K but they say however this
 approach requires performing an SVD decomposition in each self-attention
 matrix which adds additional complexity therefore we propose another approach
 for a low rank approximation that avoids this added complexity okay so they now
 come up with their model and their model goes as follows so here on the left you
 see a classic attention mechanism with their projections built in what they're
 proposing is they say let's project the matrix K using one of these random
 projections and then this attention routing if you route if you now
 multiply so you multiply K and Q right here K times Q and then you put it into
 the softmax and then you use it to route this W so they say if we build in this
 projection matrix that will project K to a lower dimension and then we won't have
 as expensive of inner products now the important part to see here is that if
 you think of this lower projection the first thing you think is that you
 project this inner this hidden dimension D right to a lower dimension and that's
 not the case here you actually project the N so in in a conceptual framework so
 you can see right here forget about this this is this W matrix in a conceptual
 framework you see here is this N by D matrix which are the keys so N is the
 sequence length and D is the dimensions and what you want to do is you want to
 project that by this matrix which is K by N so you want to reduce the sequence
 length you can see in this matrix right here why that might work because N is
 much larger than D and that means this matrix can be at most rank D right so
 you should not lose too much you should sort of be able to preserve the
 information if you project this N to a K where the K if the K is still larger
 than the D or approximately in the same order of magnitude you should be able to
 preserve that information if you do it in a smart way so conceptually if we
 have our five token sequence like here and the next layer produces five tokens
 again what we first do is we say we know we know that the information we want is
 not five dimensional it's actually two dimensional because okay let's say these
 this inner dimension D is is two as well so we have two dimensional vectors each
 thing exposes two dimensional vectors so we first project the sequence of length
 five to a sequence of length two and we simply do that in a random manner so we
 have a random Gaussian matrix that assigns weights to mix these five into
 these two and again because the JL works for any sort of data but in my
 argumentation if you you know think that this here is low rank it's of rank two
 then you shouldn't lose too much information by projecting it to a
 sequence length two and now we do this attention mechanism so now we expose the
 keys and now we expose the queries up here and now you can see instead of
 routing five things with five things you only have to route five things with two
 things and so instead of having O and squared you now have O N K if K K is the
 number right here okay so this is the idea you project the sequence length and
 it comes from the fact that the sequence length is much larger than the
 dimensionality and therefore you can sort of preserve the information if you
 project in a smart way they build this in this fashion right here so the
 attention mechanism now before we saw it was between the queries and the keys
 right here they built now this projection matrix here that projects the
 keys into a lower dimensional sequence and the now such that this will result
 in an N by K attention matrix we saw over here you don't need to route N by
 N things you need to route N by K so this this routing table in here is now N
 by K now the next layer as you can see here it actually needs to produce a
 sequence of length five again right so we always transform sequence of length
 five into sequence of length five but now we have we have this N corresponds
 to the sorry corresponds to the next layer and this K corresponds to the
 down projected sequence of the last layer and in order for that to fit we of
 course also need to down project the information that we're routing so if we
 don't project the routing table we also need to down project the information
 that we're routing that's we do this by a similar matrix F that is also sampled
 in this way in this special way and that gives us a K by D so we have projected
 the sequence to size K and if we multiply these two things again of
 course we'll get out an N by D matrix which is the signal for the next layer
 okay so an N by D signal comes in down here it's projected down to K sequence
 length it's and it's routed up again to N sequence length and you have again an
 N by D matrix here cool so that's how they do it and they build this into the
 transformer now as I understand it these projection matrices again they're not
 learned they are built up in this JL conscribed way they are not
 learned they are fixed once and then that's that's that at least that's how I
 understand it so there are no more learnable parameters okay so here they
 have a demonstration where they up the sequence length and you can see the
 batch size decreases but that's just to sort of keep the total amount of flops
 to be done the same you up the sequence length and down the batch size as the
 sequence length increases the standard transformers requirement in inference
 time goes up and this here as you can see this is not a linear scale it's a
 log scale log 2 so this goes up with the sequence length and it should go up
 quadratically right and you can also see that the Lin former keeps fairly
 constant for the same K now of course as you increase the K of the Lin former
 the inference time will go up because now it's dependent on N times K and not
 on N times N okay so let's look a bit further of how you have to choose that
 K up here in the first theorem we there was a already a hint to it in the first
 theorem you had to choose K by 5 log N and this is a problem so here you have
 log N that means it's not so O of N K is equal to O of N log N now that's not
 linear that's actually that's the same as the reformer but they want to get
 to a linear place and theorem 2 explains goes now to a linear shows how you can
 make self-attention linear okay they show again blah blah blah blah now you
 have to choose K at the minimum of these two things and you can see right here
 that one of them is independent of N so that means as N grows of course the
 minimum is no longer going to be this here the minimum is actually going to
 be the thing on the left and that is dependent on just D okay so you have D
 log D in here and that makes sense because in the very beginning we said
 hey D is actually much smaller than N and that means the information that is
 contained in these matrices is at most rank D so if we down project to K we
 should adjust K to what D is right if we adjust K to about the same thing as D
 we're guaranteed to not lose too much information so now we choose K
 according to D instead of according to N and therefore the computation is linear
 in N and N times K is like N times D to log D so it's linear in K and linear in
 D how do we get there so the first thing they do is they make these sort of
 Johnson-Lindenstrout statements again but now instead of the general statement
 they plug in their actual modified attention mechanism so here they have a
 bound on the distance between if I route my this is the information to be routed
 right if I route my information using the original softmax and this in here
 is the matrix A if the original tension mechanism I won't be too far away as if
 I were to route my information using this modified attention mechanism now
 the tricky part here mathematically I believe is that is is exactly the softmax
 what what I alluded to right so this softmax is the tricky part because if
 this weren't a softmax so if the softmax weren't here this would simply be a
 projection down and a projection up and the dilemma would almost apply as it is
 written right there you wouldn't have to actually do anything but the question is
 if this inside the softmax is is low rank can you make a claim that the
 entire softmax then is also low rank and it's not entirely clear because because
 oh yes we've done this so you can see right here that the softmax we have
 actually done the softmax of a low rank matrix so we have already seen the low
 rank matrix itself and how it immediately snaps to the to the upper
 axis after 128 now if we do the same thing for the softmax of that and we
 probably have to take away some of these dimensions the first few let's go with
 let's go to dimension 100 and look from there okay same thing okay that's pretty
 good I did not expect that hi there so this is Yannick from the future I've
 realized I've been an idiot in how I constructed these low rank matrices
 right here by multiplying MT by itself of course what's a better way to do it
 is to construct two independent 128 dimensional matrices like these two
 sub slices of M right here and then multiplying those together and looking
 at the SVD and you as you can see right here so the softmax of this is now not
 of this super low rank anymore it's still low rank but it's not not very it's
 not like hard low rank so if I just look at the matrix without the softmax then
 you can see it has a very peak that by at the 128 which gives us the indication
 it's actually 128 rank which we already knew but if we now introduce the softmax
 then you can see that this vanishes and it's no longer 128 dimensional and it's
 only approximately low rank as you can see all right back to Yannick in the
 past who is wholly surprised that the two that if you multiply MT by itself
 that that will give you back the the exact same thing all right so did we try
 this before maybe we did okay but the mathematical difficulty still remains
 and their main thing here is so they have a first first version where they
 pretty much plug it into the JL again and they they get out this K is the K
 needs to be by log n but they say this result does not utilize the low rank
 property of matrix A and the resultant K has a dependency on sequence length n
 and then in the appendix they finally go through the math to show that now if
 they choose E and F like this they can actually pull out this and show that
 the K is where you have it the decay is independent of n like this and I think
 the main the main step in this proof is the step B here where they say uses the
 fact that the exponential function is Lipschitz continuous in a compact
 region then we can choose a small enough Delta such that the as you can see here
 this now directly relates to this projection matrix within the exponential
 function to the projection matrix out of the exponential function so you can
 basically say that if I project first and then use the exponential function
 that's not too different than if I first use the exponential function and then
 project okay so that's the that's the sort of of of catch here now they only
 do this for the exponential function not the actual softmax as you can see here
 throughout they do it to the exponential function and also here in their
 statements the softmax isn't the exponential function the softmax is the
 exponential function divided by the sum of the exponential functions but I
 believe that this generalizes straightforwardly
 alright so for given choices of Delta and K they have shown that the Lin
 former in fact can do in a linear fashion what a transformer can do in a
 quadratic fashion and they are not too far off
 ok that's that's their point right here the results on these benchmarks
 sorry let's first go to the perplexities in language modeling so they show right
 here that they pretty much can keep up with the standard transformer as you can
 see here so with the standard transformer they can keep up here now
 think that this the the computation is n times K ok so something like this Lin
 former with K cost 256 will only so instead of n by n it's n times K it
 won't save you too much in that case but it's it's not too surprising that in
 fact you have the same performance because probably the standard transformer
 is distributed over more heads than two so the information necessarily has a
 lower dimensionality 10 to 56 one thing I want to draw attention to though here
 is that you can see that here it's not really done learning yet and as you can
 see the standard transformer sort of surpasses all of these models towards
 the end I wonder I wonder what happens I wouldn't be surprised if they end up
 sort of at the same place but I wonder if these diverge even more right here
 after that they also compare with a higher sequence length and the standard
 transformer outperforms the Lin former but of course the point here is that the
 Lin former is much much much faster and can keep up now also the scale here of
 the perplexity you see these are percentage points in perplexity but I
 can't actually tell if that matters or not I think I think in the original
 transformer paper the perplexities hovered between like three point
 something and five point something so this might actually be sort of
 significant differences and I'm not sure they investigate different methods of
 sharing these weights of these of these projections and they seems like they
 don't find real differences but I don't want to go into that because this video
 is already really long and then they look at what happens if they up the
 sequence length that they put into the Lin former and you can see that the Lin
 former can deal with higher sequence lengths and arrive at the same
 perplexities though again I don't know how much different that is and
 the scale here is larger than before but yeah so how does this fare on these
 benchmarks where you first train a transformer with pre training with
 language modeling and then you use it to do certain NLP tasks and here you can
 see that the Lin former is on par in some of these tasks with the original
 transformer but also you can see like a pattern where you can see pretty wild
 results in that you know sometimes the the Lin former here will be better than
 this but then also variants of the Lin former will be worse and they'll even be
 worse than this and sometimes they'll be better sometimes this Lin former is good
 and sometimes the original model is the best so this sort of points to you can
 make the general claim that the Lin former doesn't destroy your your gains
 but also it's not like a a better model it's simply a faster model that in some
 tasks can keep up with the original model and they show that of course this
 is the real deal here that as you go up in length the performance gains and also
 sorry this this way the performance gains and the memory gains that you get
 by the Lin former are dramatic of course the longer and you go and to the lower
 dimension you project the more these gains are but of course the more
 performance you're going to lose potentially hello again Yannick from the
 future just wanted to draw your attention on this beautiful broader
 impact statement in this paper saying our work focuses on making transformers
 more efficient everything cool potential positive in spec impacts of efficient
 transformers that's pretty cool it also has potential impact on training
 transformers on images since we can support very long sequences very cool
 furthermore there are positive environmental benefits very cool I mean
 these are all very cool things they say as such we see no immediate negative
 ethical or societal impacts of our work beyond what applies to the core building
 blocks of deep learning do better now this this honestly I agree with them
 right I completely agree with them that this is sort of a good thing you might
 trade off you know some accuracy might some make some approximations but you
 will get a much faster model and this model has any model can be used you
 know for things and and that they now have to pull out of there out of their
 but some way in in in over five steps of intermediate layers this could be used
 for bad it just seems ridiculous so good on them for defying the please also
 think about negative impacts right here all right back to back back to past
 Yannick all right this was the Lin former paper I hope this somewhat makes
 sense made sense to you I had to read it multiple times for it to make sense to
 me but ultimately it's all about the fact that you have these multiple heads
 and therefore your information is probably lower dimensional and you can
 abuse that and to just calculate in this lower dimension all right I'll see you
 next time bye bye