Rethinking Attention with Performers (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper nlp natural language processing natural language understanding data science transformer attention attention mechanism transformers attention is all you need gpus tpu linformer reformer explanation imagenet64 kernels gaussian kernel softmax softmax kernel approximation random features random positive features random fourier features google favor machine translation
#ai #research #attention

Transformers have huge memory and compute requirements because they construct an Attention matrix, which grows quadratically in the size of the input. The Performer is a model that uses random positive orthogonal features to construct an unbiased estimator to the Attention matrix and obtains an arbitrarily good approximation in linear time! The method generalizes beyond attention and opens the door to the next generation of deep learning architectures.

OUTLINE:
0:00 - Intro & Outline
6:15 - Quadratic Bottleneck in Attention Mechanisms
10:00 - Decomposing the Attention Matrix
15:30 - Approximating the Softmax Kernel
24:45 - Different Choices, Different Kernels
28:00 - Why the Naive Approach does not work!
31:30 - Better Approximation via Positive Features
36:55 - Positive Features are Infinitely Better
40:10 - Orthogonal Features are Even Better
43:25 - Experiments
49:20 - Broader Impact Statement
50:00 - Causal Attention via Prefix Sums
52:10 - Code
53:50 - Final Remarks & Conclusion

Paper: https://arxiv.org/abs/2009.14794
Code: https://github.com/google-research/google-research/tree/master/performer
Blog: https://ai.googleblog.com/2020/10/rethinking-attention-with-performers.html

Kernels on ML Street Talk: https://www.youtube.com/watch?v=y_RjsDHl5Y4
My Video on Linformer: https://www.youtube.com/watch?v=-_2AF9Lhweo
My Video on Reformer: https://www.youtube.com/watch?v=i4H0kjxrias
My Video on Attention: https://www.youtube.com/watch?v=iDulhoQ2pro

Abstract:
We introduce Performers, Transformer architectures which can estimate regular (softmax) full-rank-attention Transformers with provable accuracy, but using only linear (as opposed to quadratic) space and time complexity, without relying on any priors such as sparsity or low-rankness. To approximate softmax attention-kernels, Performers use a novel Fast Attention Via positive Orthogonal Random features approach (FAVOR+), which may be of independent interest for scalable kernel methods. FAVOR+ can be also used to efficiently model kernelizable attention mechanisms beyond softmax. This representational power is crucial to accurately compare softmax with other kernels for the first time on large-scale tasks, beyond the reach of regular Transformers, and investigate optimal attention-kernels. Performers are linear architectures fully compatible with regular Transformers and with strong theoretical guarantees: unbiased or nearly-unbiased estimation of the attention matrix, uniform convergence and low estimation variance. We tested Performers on a rich set of tasks stretching from pixel-prediction through text models to protein sequence modeling. We demonstrate competitive results with other examined efficient sparse and dense attention methods, showcasing effectiveness of the novel attention-learning paradigm leveraged by Performers.

Authors: Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, Adrian Weller


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
 Hi there, today we'll look at rethinking attention with performers by researchers of Google, the University of Cambridge, DeepMind and the Alan Turing Institute. This paper is yet another paper in the quest to make transformers more performant and what better name to give to a technique than the performer. So the performer, performers are a new kind of class of models. They try to approximate the transformer. If you don't know what a transformer is, I've done like a ton of videos on transformers, on attention mechanisms, and you can, there's more than enough material to look that up. Today we'll talk about performers. And the performers, as I already said, they approximate transformers. And they do so without running into the classic transformer bottleneck, which is that the attention matrix in the transformer is, has space and compute requirements that are quadratic in the size of the input and that limits how much input you can put into the model. So it kind of limits how long of text you can input if you work with text or how big your images are that you can work with. This is all kind of bad at when you use transformers. So the performers get around this by this technique they call fast attention via positive orthogonal random features abbreviated favor plus they use this favor plus to get around it and what's interesting is that the favor pluff, I'll just call it favor this fast attention, it is potentially useful beyond transformers. So it's apparently been here developed in the realm of the transformers, but they say, which may be of independent interest for scalable kernel methods. You'll see what they do is they approximate the attention matrix by decomposing it, but they do it in a special way. And they do it in the in the way if you know what random Fourier features are, maybe you can kind of think, think ahead a little bit, if not, we'll get into it for sure. I think honestly, this might be one of the enabling one of the next mini breakthroughs in deep learning, not big breakthrough, but kind of mini breakthrough. I remember a time when we used sigmoid and tan h nonlinearities, believe it or not, you young kids at the beginning of deep learning, not the beginning of deep learning, but before deep learning really took off, it was the sensible thing to use softmax and tan h nonlinearities everywhere in your neural networks. Because well, first of all, they were like differentiable. So that was cool. And then, you know, it was sort of how nature does it with the step function in, like it was an approximation to the step function in the true neuron and so on. And it was just kind of well motivated. So people thought that must be the way to go. But then, of course, turned out that relu's are much easier, much more stable, give much better results, and so on, don't saturate all these cool things. This here is kind of the it feels like the same thing, because right now, we're doing this softmax thing in attention. And it's very important because it normalizes the attention matrix, right? It gives you kind of this thing that comes out is kind of a distribution over the inputs and so on. So it's well motivated. And you may be able to see, but also as the sigmoid is, it's kind of has this exponential thing in there. And the favor algorithm is going to approximate this softmax thing, but it can be used to approximate much more. So maybe, you know, we're going to find that if we swap out these, the nonlinearity in there, we might be able to build much better transformers, or whatever the model will be called performers, I guess they already do this here with relu's in this very paper. So the performer is going to be fully compatible with regular transformer, and with strong theoretical guarantees, unbiased or nearly unbiased estimation of the attention matrix uniform convergence and low estimation variance. So the difference of the performer here is going to be that there have been methods before that decompose the attention matrix into low rank matrices. But those either don't work, or they kind of rely on on priors, like the you're assuming that your attention matrix has a certain structure, if it doesn't, it sort of fails. This method here is going to be an unbiased estimator. And it's going to sort of converge to the attention matrix if you add more of these random features. Okay, they this is fed here like provably not relying on any priors fully compatible with regular transformers, which means that you can take a transformer checkpoint and sort of plug it into this framework. And then you just have to fine tune a little bit to sort of use the checkpoint of a regular transformer, which is pretty cool, right. So we'll go through the paper. It's quite a heavy paper. It's quite a math heavy paper. We won't go through all of it. I just kind of want you to get the idea of what these performers do, what the reasoning behind it is, and how you might be able to kind of work with them or extend them where it's going from here. As always, if you like content like this, don't hesitate to share it out and tell your friends about it. All right. So the problem with attention or the problem with transformers is like I've done this a million times and you can go look it up. But if you want to map a sequence of layer L into a sequence or a set or whatnot of layer L plus one, and you need to compute these attention weights, right. So the attention weights are going to be from each token here to each token in the next layer, you're going to compute one of these weights. All right. So there is this matrix is called A, the attention matrix, and A is going to be of size L by L. And that is a problem if you have long sequences, right, you can already see this. So the way that this A comes to be is that conceptually, the upper layer, like it's all the same layer, but conceptually, the upper layer emits something that are called queries and the lower layer emits something that are called keys and values. Now the keys and the queries, they go together into matrices. So it multiply the keys and the queries. Then you run this through and this is the problem you run this through a softmax nonlinearity to basically get a distribution and then you multiply it by the values. So the query key matrix, this attention matrix, it will tell you how to aggregate the values. All right. If it weren't for the softmax, so you can you can think if if these if these the dimensions of the queries and keys and values, let's call it small d, then the dimensionality here will be something like here you'd have L by D, here it have D by L for the transposed. And then here you'd have L by D. So because you have to do the softmax, you have to compute this first, which gives you this L by L, which is the terrible thing. However, if you could, if you could, if somehow decompose the softmax operation, you could first do keys and values, which will give you a D by D matrix. And then you could multiply it by the Q matrix, right, which would be much, much, much more easy if D is smaller than L. Certainly wouldn't grow quadratically in L, it would just grow linearly in in space and time. So here this is formulated out the attention mechanism right here. The attention mechanism is made of queries, keys and values. And it's given by this formula right here. Now there is a bit of a technicality I wasn't exactly correct in what a is. So here, they, they say, they, I called this thing here a, okay, they are very specific what they mean by a, by a, they simply mean the exponential function of the normalized queries times keys. And then to get the actual softmax, you have to normalize by here. So D, which is so you see, the inverse is made here, D is constructed from a and normalize as a, but the normalization is of secondary importance. The important part here is that this exponential cannot be easily decomposed, right? It's not like you can decompose the inner multiplication into two exponentials or something, otherwise the problem would be solved. So what is this paper doing? It's exactly what I just said was impossible. So you have this matrix a right here, and you multiplied by V. Yes, again, forget about the normalization by now. It will decompose a into the query, the Q prime and K prime. Now they are called prime because they are not the queries and the keys, because we've just said the queries and the keys, they go into the exponential. So it's going to be that K, sorry, Q prime times K prime transposed is going to be approximately equal to exponential function of Q times K, maybe normalized by square root of D. But you can see that this here isn't decomposable, and yet they decompose it. And the question is how, because there have been papers before that try to decompose the attention matrix. I think Lin former maybe, and there is also the reformer, which uses LSH and so on. So there have been a number of tricks, but they all don't perform as well, which this paper also shows empirically. And they all rely on certain assumptions of the attention matrix. And they all are not unbiased estimators in general, this paper is going to be an unbiased estimator. And they do this via sort of a kernel framework. So what they they first of all, they make this problem more general, they say we have our attention matrix A, the ijth entry is going to be the query i, the key j, and some kernel function of that. In our case, this is going to be the right X of query times key, like this, sorry, the other way around. Query transpose, transpose, query times key, the inner product of that. However, you can think of any sort of kernel function. So yeah, if I'm not going to try to explain more details into kernels, we had a fantastic machine learning street talk. So if you don't know about this, this is our podcast, machine learning street talk, where Alex Stanlik explained kernels in great detail, and with very, very precise language, and very understandable as well. So what I'm going to say is that they allow you to do things like this. So you can think of kernels as kind of connecting two things, they allow you, they represent an inner product in some other space. So the kernel function of two inputs right here will be equal to some inner product of the two inputs when pulled through this function phi right here. And that's what we're going to use. Now usually, usually when you learn about kernels, you do it in this way. You say, we would like to compute in this very high dimensional space, but we can't, we can't do inner products, we can't map this function phi explicitly. So we're going to instead use this kernel right here, this kernel function. And that's going to be equal. If you pick the right kernel function for the particular phi, in this paper, we're going to do it the other way around, because we say, well, this thing here is this is the softmax function. And that's just a beast, right? We can't possibly compute that. However, if we could find out what inner product that corresponds to, what other space, we could just go to that other space and perform an inner product. And this thing over here is linear, right? This is a linear function. This here is the nonlinear function. This is our softmax. So you can see that by going in this way, by finding what is the higher or the phi function for the softmax kernel, we can construct all of this attention business in a linear fashion. And that's what this paper does. What it allows you to do is it allows you to find these q and k, q prime and k prime matrices such that as over here, right, this is the kernel function. And this here is linear. And then you can simply first multiply k by v, or k prime by v, and then you can multiply q by k, and that will alleviate you of having this giant attention matrix. So how do they do it? If you again, if you know about random Fourier features, this is going to be very much or very similar thing right here. They're not going to explicitly construct the high dimensional space such that this is exactly equal, but they're going to construct an approximation. And the approximation, you can make arbitrarily good. And you do that via the following you say, so here you see this is how do I have to map something into this other dimensional space, where this whole softmax business is just a linear operation. So what you would do ultimately is you would take your queries, you would map it through this phi, okay, and you would take your keys, and you would also map it through this phi. And this will give you query prime, and this will give you key prime, right. So and then in the higher down in the higher lower whatever dimensional space, you would take the inner product. And the inner product between the two is going to approximately be as if you had multiple so the inner product is going to be approximately as if you had taken the original q and k, multiply them and put them through a softmax. How do we do it? So here we define what the function needs to look like, sit such that this holds the function again, they go very general here, the function in general is going to look like the following. So you have one function here that's called h, that is a function of your input, and it's in front, it's a deterministic function of your input. And you also have a normalization factor. So this is kind of it's kind of a factor in front of it. You see that here comes a vector. So this is a vector, right, we are mapping this to a some dimensional space. And this is the vector. Now it's a bit you have to pay a bit of attention. So inside this vector, you have l different sub vectors, they're all concatenated after each other. Okay, so you have CC here, this, where the F, this is f1, and then f2, f3, f4, and so on until fl. Okay, so you have all these sub vectors. It doesn't matter ultimately, you just concatenate them all. But it's important to just keep in mind, within each of these vectors, within each of these sub vectors, you always have the same repeated term, you have this w times your x, so the inner product between w and x, you can see there's w1 through wm or omega, I think it's an omega. And again, in the in each sub vector, you have this repeated. So what are these omegas, first of all, the omegas are random vectors drawn for from some distribution. Now in practicality, this is going to be a normal distribution like this one here, an isotropic normal distribution. So and the the other part here is what are the F's. So the F's f1 through fl are going to be functions, deterministic functions. So in a an example they gave right here, f1 is the sine function, f2 is the cosine function. And then you have to specify h and h in this particular example is one, but it can be a function of x here, here, it's just the identity. Sorry, not the identity, the constant function one. So let's break this a little down. So we have x, and x is going to be a vector x, as I said, x is going to be like one of the queries here, or one of the one of the keys here, one one of them, right, one column or one row, however you conceptualize it, and we wonder how do we want to map so x is going to be some vector. Okay, then this is an ugly vector. Let's draw it like this. x is a vector. Then what we're going to do is we're going to take a bunch of omegas. Now it's important that the omegas are random. So they come from this isotropic normal distribution, but they're going to remain the same throughout the algorithm. So this is a method to resample them, but just conceptualize that at the beginning of the algorithm, you choose these omegas and then you fix them. So the omegas are going to be also vectors, which are random, just a bunch of random vectors. Let's take three. What you're going to do is you're going to compute the inner product between your x and each of the omegas. So inner product in your x and each of the omegas. So this gives you omega 1x, omega 2x, omega 3x. The inner product, this is going to be these, this is going to be numbers. And then you're going to have a collection of functions. So these are going to be functions, maybe function one is going maybe here, the sine function function two is going to be the cosine function. Now you're going to take each to make a table. You're going to take each of these products you computed and put them through each of the functions. So this is going to be sine of omega 1x, cosine of omega 1x, sine of omega 2x and so on. And then you're going to take this table and you're going to flatten it to a big vector. So sine omega 1x, cosine or no sine first, the ordering data doesn't matter as long as you always do it the same omega 2x, and so on right until you have here cosine of omega 3x. So that's the vector they're constructing. And these are those random features. Okay, so this here is going to be the vector that you're constructing. What you do is basically geometrically your x is like somewhere here. And it's a bit hard to draw in low dimensional space because you don't get the intuition. But this is if this is your x, you're going to choose a bunch of these omegas, these omegas are going to be randomly sampled from a uniform Gaussian. So this is omega 1, maybe omega 2, omega 3, omega 4. And you're going to compute the inner product between between any of the two. Okay, so you're going to be essentially computing the projections onto each other or the angle however you want to conceptualize it, the angle of this to each of the two of the omegas. And then you're going to make a features out of these angles, right? So this will sort of tell you how your vector stands to each of these random features. Now the reason I say it's difficult in low dimension is because now I have more omegas than the dimensionality, which is two right here. And this makes no sense, right? As soon as I have two vectors that are not collinear in two dimensional space, I can if I project x onto them, like like this, sorry, like if I project x onto both of them, I already have x fully represented, right? There's no need to have more of them. However, if you are in super duper high dimensional space, and you don't you don't have as many features, then you get some interesting approximation properties, namely, so this was an example, right? We don't always have the sine and the cosine here. This is purely an example, you can only have one function, you see like this f one, you don't need two functions, you can have one, you can have many. Okay. And you can choose how many omegas you sample, that is a parameter. So yeah, you have a couple of choices, I want to make it clear the choice of h, so the choice of h and f, they go hand in hand, the choice of h and the F's determine what the phi function is. Okay. So the choice of h f determine which kernel function this phi function corresponds to, if you construct it like this. So by choosing the correct functions, you tell the function which kernel you would like to approximate. And then by sampling the omegas, the more omegas you sample, the more accurately you approximate that kernel, and then you can give some approximation guarantees. As they say, so the softmax kernel is given by this thing here, which we've already seen. Okay. And now how do we approximate the softmax kernel? And they show that right here, softmax kernel is approximated by this thing right here. So it's a bit of a ugly formula, and it contains this Gaussian kernel, the Gauss kernel. So they say, if we choose h equals to one, so just a constant factor, and this f1 and f2 to the sine and cosine, and in if we choose d, the distribution to be a normal distribution isotropic around the mean, this is the Gaussian kernel. And then we simply have to choose h differently, this factor in front to make it into the softmax kernel, so as long as we put this factor in front, you can see that this here represents an inner product, right? So you have to kind of think of decomposition. So if you put, you can see f1, the sine, f2, the cosine, which is this makes it the Gaussian kernel, and then this factor in front of it here, two for h, this makes it now the softmax kernel. So if we choose h and f like this, then when we map our queries and keys through, if we map our queries and keys through the phi function, and then make the inner product between them, okay, like here, that will approximate depending on how many omegas we've sampled better or worse, they approximate the result as if we had multiplied them first, and then put them through the softmax function. All right. So this you can see how this becomes much easier, because we can independently put them through the phi, okay. And then it's just a linear operation, which allows us to do our trick where we multiply k and v first, and then multiply by q instead of the other way around, which we're forced to do when we apply the softmax. This was a long, long way to get here. But I hope you're with this. And this is, this is pretty straightforward, actually, so far. Now renormalization, we can take care of that easily. But there is a problem. And this is they argue, this hasn't been proposed so far, because it doesn't work like this. So even though you approximate this kernel fairly well, it's it's a bad approximation. And they say here, there is however, a caveat here, the attention module from one constructs for each token, a convex combination of value vectors with coefficients given as corresponding green renormalized kernel scores. That is why kernels producing non negative scores are used. Applying random feature maps with potentially negative dimension values leads to unstable behaviors, especially when kernel scores close to zero, which is the case for lots of entries of a corresponding to not relevant tokens are approximated by estimators with large variants in such regions. This results in abnormal behaviors, eg negative diagonal value renormalizers, and consequently either completely prevents training or leads to sub optimal models. So what they're saying is that when you use softmax, you always always get positive values, right? So if I have a bunch of vectors, or a bunch of numbers, this is, you know, positive number, negative number, very positive number, negative number, and I run it through a softmax, I will get out a distribution right, like this, or really big, sorry, that softmax will scale that up, I will get out a positive district like a kind of a histogram. And now I'm trying to approximate this by this formula right here. And you can see these are these are vectors, which gives me sine and cosine coefficients, and I linearly multiply two vectors together, which definitely means I can get negative entries and so on. So the renormalization then has to somehow maybe take care of that. And it says especially, especially around zero, when the original softmax matrix would have values close to zero, this approximation is really bad and has high variance. And they also argue, a lot of attention vectors are close to zero, because we know that attention is sort of sparsify, just by the fact of what how the softmax works, it exaggerates the largest inner products, and it really dampens the low inner products. Okay. Actually, I might not even have done this correctly here. If it's, if it's very negative, I'm not sure. In any case, they say that's why this doesn't work, because it has such high variance, it's a good approximation, but has such high variance in the wrong places, they really around zero where most values are. So they call this these s, the SM the softmax approximation with m sampled features trig, because it uses the sine and cosine functions. And now they're trying to remedy this. And for that, they propose a different decomposition. So a different approximation to the softmax kernel. And they say we can also decompose the softmax or approximate the softmax kernel with the following formula. And I look, I, I'm not going to, they have a proof for this. But this is the formula. You sample again, you sample these things. And then you perform this inner, this is the inner product that approximates the softmax kernel. Okay. And this is further, you can reduce this to this thing right here. So it's a deterministic matrix right here, this which is given by that. And it's this cos h. So cos h is the hyperbolic tangent. This can be this is so cos h of x is e to the x plus e to the minus x divided by two. Okay, so this function approximates the softmax. And that's just something you'll have to take from their proof. However, you can now see that this can be fairly easily represented as an inner product, you already see it here, right? This you simply, this is the part that comes from x, and this is the part that comes from y. If you want to note this in our in our notation earlier, again, we use the distribution that we sampled the omegas from is going to be a normal distribution. And our functions are going to be this h function is the pre factor, it's simply going to be the made up of the norm of x and put through the exponential function. And then we have two options actually, right here. I don't even know why they put the first one. But the second option makes more sense. And there's a bit of a more of a factor right here. So you have two functions, there is x of u and negative x and x of negative u, as the two function you remember, this is where we had sine and cosine before. Now we have x u and negative x, sorry, x of negative u. And we can quickly check that this gives us the same thing. So this h, these h functions, if we inner product them, that's going to be to give us the this, what is that even lambda? Is that a big lambda matrix right here? And our vector, let's just say we sample one single omega, right? So we have our x, we sample one single omega. So x is going to give us a vector with two sub vectors, right? Since we have two functions, each sub vector is of length one. So the first is going to be e to the omega x, and the second entry is going to be e to the negative omega x. If we put in y through the same or as instead of x and y, you can think of queries and keys, that's going to be y e to the negative omega y. If we now take the inner product, that is going to give us and I'm resolving the exponentials already right here. So that's going to give us e to the e to the w x plus y. And here is going to give us plus e to the w or sorry, the negative w x plus y. And that's the you know, there is a normalization factor. That's why the square root of two is here, right? So that comes in somewhere here to give us this normalization factor. So this is exactly the hyperbolic cosine of omega times z and z is x plus y that they say it somewhere. Yeah. Okay. So if we choose f1 and f2 to be this x, u and x negative u, then we get if we perform the inner product, we get out exactly this formula number seven right here. So this is this. And that is an approximation of the softmax kernel of the softmax function. It's just a different approximation than before. Okay. And the cool thing about this approximation is that the approximation itself only ever has positive values. So these vectors here, you can see the x, the vectors here, and there's of course a four a factor in front of this right here, which is going to be also an exponential. These are all exponential. So these are all going to be positive features, which is very, very nice. And they also show this theoretically. So here, this kind of funky graphic shows this. This is the ratio of the approximation mistake. Okay, the ratio of the approximation mistake of the of the original approximation that we discussed and this new positive approximation that we just built right now. And you can see that in parts here, it's fairly similar. So this, I believe, so R is the ratio. So it's fairly flat right here. But there are parts where it just shoots up, right? And in fact, they can prove that you can see this also right here. So the error of the trig approximation that shoots up while the positive approximation just stays flat or flatter in these regions. They can in fact prove that the the error of the Yeah, so you see the error. If the softmax values go to zero, so that's the problematic regions, the error of the trigonomic approximation can go to infinity while the error of the positive approximation goes to zero. Okay, they have a number of theoretical results in here. I think that's one of the main ones, the fact that the this approximation succeeds where the other approximation fails. Really quickly, they also have this variant here, where they don't build a two vector or a vector of two sub vectors, but just one with just the exponential function. And that is the same thing. Because of course, if you sample w, you're going to have sorry, omega, if you sample omega, you're going to have omega as much as negative omega, I believe and and thereby in expectation, you're going to get this hyperbolic cosine again, I think that's the reason why but this lower this lower construction here gives you the hyperbolic cosine. Okay, so pretty cool. We simply use this approximation, we run our queries, right? This your queries and our keys through this. And again, we ideally use more omegas than just one, maybe a bunch. The more we use the better we obtain a linear function that approximates the softmax function. The more we sample, the more it approximated, it's unbiased, and so on. And have a bunch of variants of it. So variant where you normalize the omegas, which gives you the regularized softmax kernel, which is not a softmax anymore, but it's a regularized softmax. And they can approximate this in pretty much the same way. Except instead of a normal distribution, you use a uniform distribution right here. And they have a bunch of other things, namely, one other improvement is that so far, we've simply sampled these W's, okay, we sampled the W's from a normal distribution like this here. They say we can improve even further. Namely, we can strictly improve with this gives us an estimator with strictly lower variance if we make sure that the W's we sample are exactly orthogonal. So they're already approximately orthogonal if we sample them from a high dimensional space. But if we make sure that they are exactly orthogonal, sorry, then they are giving us an even better approximation. And you can do that by this procedure called the Gram-Schmidt orthogonalization or Gram-Schmidt renormalization procedure. It's a pretty easy procedure. And it doesn't mess with your unbiasedness. Whenever D is an isotropic distribution, isotropic just means the same in every direction. So like a standard Gaussian would fulfill or a uniform would fulfill this thing as long as it's centered. I think maybe even if it's not centered, depends on how you renormalize. Okay, this is irrelevant. But if you make them exactly orthogonal, say this leads to the first theoretical results showing that orthogonal random features can be applied to reduce the variance of the softmax or Gaussian kernel estimators for any dimensionality D rather than just asymptotically for large enough D as it is the case for previous methods. And leads to the first exponentially small bounds on large deviations probabilities that are strictly smaller than for non-orthogonal methods. So you're going to end up with a thing that's strictly smaller, so bounds that are strictly smaller than if you don't use orthogonality. The only thing it requires is that m is smaller or equal to D. So the number of omega u sample is going to be smaller equal to the dimensionality that the original space operates in, which they say this will be the case in all our experiments. Okay, and again, these are exponentially small bounds, which is pretty cool. I guess for you, the end user, it matters that this works. And if you use all of their tricks with the positivity and the orthogonality. So by the way, this here is where they show that CDD or orthogonal MSE, the mean squared error is smaller than the original one minus some thing. And as long as the something of course is greater than zero, you're going to have something that's smaller. Okay, then they prove a bunch of other things again about this kind of this regularized, sorry, not regularized. I forget it's the where you divide by the norm. In any case, they implement this in jacks. Oh, great. Wow, cool. I okay, I have no opinion on jacks. But they have the code released and I'll of course link to it. And here you can clearly see so this is a log log plot, where you have l the size of the input and the number of seconds that it takes to go forward and backward over here in the model. And you can see the x here. The x is the baseline where you simply bypass the attention matrix, you simply take the identity function and just return the value matrix. And you can see that the performance the performers, they scale fairly well with that baseline. And in fact, they scale at the same slope, which is the important part right here, you can really see that this is linear slope where the transformers which are the dashed lines, they all curve upwards, which of course is that that quadratic requirement. The same in the backward pass, I don't know if they continue curving. I think it's also a straight line in the log log plot. But the slope is two instead of one, like the linear like the linear models. Again, the comparison is only important between the baseline and the lines that you're looking at. If they have the same slope, they scale the same as you get higher. Look at it. This is log L, right? So this is these these are now two to the 18th tokens. And I believe this is done on one GPU. Yes, so an out of memory error on a V 100 GPU. And this is pretty good. This is pretty good news for everyone who wants to run the performers in in kind of a low resource environment low risk with low resource. I mean, like a deep learning GPU instead of 1000 TPUs, which is pretty cool. They also show the that their method is better than the kind of so the orthogonality is better than the ID features. And then of course, the positive ID features are better than these original trigonometric decomposition. And they show that this thing that you can take a transformer checkpoint, and you plug it into the performer. And you simply have to fine tune a little bit to get it to the performance that the transformer was at, right? This is I believe this is the original training curve of the transformer. So you know, it's not a fair comparison, because the performer starts from the checkpoint already. At least that's how I interpret it. It's not clearly written and they say, okay, over here, this trig thing works. This is the original approximation, this even works. However, if we do that on a bit more challenging, more longer sequences, data, data set, then you can see that the trig softmax, it just it just whacks out. That's this thing here. And you actually need better these positive approximations. And that compared to the Linformer here, which is pretty cool. So the Linformer, another, I've made a video about it, if you want to know about it, but they also do random projections of the attention matrix. But you can see that the Linformer plateaus along with the performers, if you don't redraw the random features. So if you want in the performer, if you do it at the right time, you redraw these random features, these omegas, you have to have to see where you can you can't just arbitrarily redraw them between computation steps. But at the end of like a computation step, you can redraw for the next computation step. And if you do that, and the even better with the regularized or the the normalized features, you get to the same level of performance that a standard transformer would get. But of course, without the quadratic requirements. And okay, lastly, as I said, they've already they've already swapped out the they swapped out this nonlinearity by a relu. So here they construct performer relu, taking f equals relu in equation five, you remember what f was, f was the sine and cosine when we had the first approximation and f was the x x of u and x of minus u, the second one. And as I said, the big improvement in deep learning came when we swapped sigmoids for relus. And here they've already they're already trying swapping now this because they say, well, so we have a method that we can basically plug in anything we want. So they plug in relu because it's you know, worked well. And this again, it works pretty well. So they compare again also with the reformer here with the Lin former, as you can see, and of course, they beat everything now, whether or not this method is going to be the next thing, like the thing that everyone uses is to be we don't know. It's fairly possible. It's pretty cool. And it appears to be theoretically solidly grounded, but you never know from the experiments of the single paper, the broader impact statement, much respect, they just use it to tell you how awesome their paper is. Like there's no mention on on on any kind of ethical impact, which I believe like I'm all for these kinds of broader impact statements, like just kind of okay, research on transformers is going to be better because now people have access to it. It's backward compatible. That's pretty cool. It's applicable to biology and medicine because we can take longer sequences. It's all like, yeah, I like these kinds of broader impact statement. The last thing here is that you might be so the only problem is if you want to do this causal attention that if you want to do like a generative model, like a GPT sort of model, you have to do a bit of a trick. And that is because your attention matrix isn't the full attention matrix. So you can't just decompose it. It's this lower triangular matrix right here. But since you have linear decomposition of this thing, you can do these kind of prefix sums, namely, you can compute simply so you you you can compute the key one times value one, and then you can compute key two times value two plus key one times value one. And you compute key three value three plus key two value two plus key one, sorry, value one, and so on. You compute these things. And these are all these are all the big where the L goes away, right? So we do that first. And then we simply have to come along and we take q q one, multiply by q one, v one, we take q two, multiply by this and this q three will multiply by this, this and this. And you see, that's how you get your causal attention. So you simply keep track of these prefix sums right here. And then when the next q comes along, simply multiplied by all of the things that are above it in the prefix sum, that's how you get your triangular matrix. So even that is solved, a thing that I believe the Lin former wasn't able to do with its particular decomposition, I might be I might be wrong here. All right, they have a bunch of experiments on protein analysis, and so on, which of course, wasn't possible, I guess before because it was so so heavy. They also have like image net 64, as you can see right here, which is an impossible data set for a classic transformer. As I said, they have code code is in jacks, which is like this is it's ugly code. Let's be honest, but it's code. So that's fairly cool. And I want to point out the right at the bottom here is actually where the stuff happens. So you can see that. Just quickly, you have here keys and queries are, where is it? Exactly. So queries and keys are going to be constructed right here. So query prime and key prime are going to be pulled through this feature creator, which implements these these kernels. So these can either as we said, these x or the relu's or the sine cosine, whatnot, then you're going to multiply the queries and the keys, which gives you yet this W matrix. And all that we need to do now is normalize it. Okay, so we re normalize by constructing this denominator right here. And then there's a whole block for the unit directionality, which you can imagine is pretty ugly, but the renormalization we constructed, we reciprocal means we take the inverse multiplied by the W and return the result, this should be translatable into your favorite whatnot pytorch or TensorFlow, maybe it's already been done, I haven't researched that particular thing. In any case, I invite you to check out the paper, the code, play around with the functions used here, as long as you, you know, use fun, you don't even you don't need to know, like these papers, they always know which kind of kernels their functions correspond to. But you know, in SVM, people just went, went nuts, I just plug in some functions, see what happens. Probably nothing good, but it's possible. Alright, so that was it for the performer. I hope you gained something from this kind of an understanding of how it works. And I wish you the best. Bye bye.
 Hi there, today we'll look at rethinking attention with performers by researchers of Google,
 the University of Cambridge, DeepMind and the Alan Turing Institute.
 This paper is yet another paper in the quest to make transformers more performant and what
 better name to give to a technique than the performer.
 So the performer, performers are a new kind of class of models.
 They try to approximate the transformer.
 If you don't know what a transformer is, I've done like a ton of videos on transformers,
 on attention mechanisms, and you can, there's more than enough material to look that up.
 Today we'll talk about performers.
 And the performers, as I already said, they approximate transformers.
 And they do so without running into the classic transformer bottleneck, which is that the
 attention matrix in the transformer is, has space and compute requirements that are quadratic
 in the size of the input and that limits how much input you can put into the model.
 So it kind of limits how long of text you can input if you work with text or how big
 your images are that you can work with.
 This is all kind of bad at when you use transformers.
 So the performers get around this by this technique they call fast attention via positive
 orthogonal random features abbreviated favor plus they use this favor plus to get around
 it and what's interesting is that the favor pluff, I'll just call it favor this fast attention,
 it is potentially useful beyond transformers.
 So it's apparently been here developed in the realm of the transformers, but they say,
 which may be of independent interest for scalable kernel methods.
 You'll see what they do is they approximate the attention matrix by decomposing it, but
 they do it in a special way.
 And they do it in the in the way if you know what random Fourier features are, maybe you
 can kind of think, think ahead a little bit, if not, we'll get into it for sure.
 I think honestly, this might be one of the enabling one of the next mini breakthroughs
 in deep learning, not big breakthrough, but kind of mini breakthrough.
 I remember a time when we used sigmoid and tan h nonlinearities, believe it or not, you
 young kids at the beginning of deep learning, not the beginning of deep learning, but before
 deep learning really took off, it was the sensible thing to use softmax and tan h nonlinearities
 everywhere in your neural networks.
 Because well, first of all, they were like differentiable.
 So that was cool.
 And then, you know, it was sort of how nature does it with the step function in, like it
 was an approximation to the step function in the true neuron and so on.
 And it was just kind of well motivated.
 So people thought that must be the way to go.
 But then, of course, turned out that relu's are much easier, much more stable, give much
 better results, and so on, don't saturate all these cool things.
 This here is kind of the it feels like the same thing, because right now, we're doing
 this softmax thing in attention.
 And it's very important because it normalizes the attention matrix, right?
 It gives you kind of this thing that comes out is kind of a distribution over the inputs
 and so on.
 So it's well motivated.
 And you may be able to see, but also as the sigmoid is, it's kind of has this exponential
 thing in there.
 And the favor algorithm is going to approximate this softmax thing, but it can be used to
 approximate much more.
 So maybe, you know, we're going to find that if we swap out these, the nonlinearity in
 there, we might be able to build much better transformers, or whatever the model will be
 called performers, I guess they already do this here with relu's in this very paper.
 So the performer is going to be fully compatible with regular transformer, and with strong
 theoretical guarantees, unbiased or nearly unbiased estimation of the attention matrix
 uniform convergence and low estimation variance.
 So the difference of the performer here is going to be that there have been methods before
 that decompose the attention matrix into low rank matrices.
 But those either don't work, or they kind of rely on on priors, like the you're assuming
 that your attention matrix has a certain structure, if it doesn't, it sort of fails.
 This method here is going to be an unbiased estimator.
 And it's going to sort of converge to the attention matrix if you add more of these
 random features.
 Okay, they this is fed here like provably not relying on any priors fully compatible
 with regular transformers, which means that you can take a transformer checkpoint and
 sort of plug it into this framework.
 And then you just have to fine tune a little bit to sort of use the checkpoint of a regular
 transformer, which is pretty cool, right.
 So we'll go through the paper.
 It's quite a heavy paper.
 It's quite a math heavy paper.
 We won't go through all of it.
 I just kind of want you to get the idea of what these performers do, what the reasoning
 behind it is, and how you might be able to kind of work with them or extend them where
 it's going from here.
 As always, if you like content like this, don't hesitate to share it out and tell your
 friends about it.
 All right.
 So the problem with attention or the problem with transformers is like I've done this a
 million times and you can go look it up.
 But if you want to map a sequence of layer L into a sequence or a set or whatnot of layer
 L plus one, and you need to compute these attention weights, right.
 So the attention weights are going to be from each token here to each token in the next
 layer, you're going to compute one of these weights.
 All right.
 So there is this matrix is called A, the attention matrix, and A is going to be of size L by
 L. And that is a problem if you have long sequences, right, you can already see this.
 So the way that this A comes to be is that conceptually, the upper layer, like it's all
 the same layer, but conceptually, the upper layer emits something that are called queries
 and the lower layer emits something that are called keys and values.
 Now the keys and the queries, they go together into matrices.
 So it multiply the keys and the queries.
 Then you run this through and this is the problem you run this through a softmax nonlinearity
 to basically get a distribution and then you multiply it by the values.
 So the query key matrix, this attention matrix, it will tell you how to aggregate the values.
 All right.
 If it weren't for the softmax, so you can you can think if if these if these the dimensions
 of the queries and keys and values, let's call it small d, then the dimensionality here
 will be something like here you'd have L by D, here it have D by L for the transposed.
 And then here you'd have L by D. So because you have to do the softmax, you have to compute
 this first, which gives you this L by L, which is the terrible thing.
 However, if you could, if you could, if somehow decompose the softmax operation, you could
 first do keys and values, which will give you a D by D matrix.
 And then you could multiply it by the Q matrix, right, which would be much, much, much more
 easy if D is smaller than L. Certainly wouldn't grow quadratically in L, it would just grow
 linearly in in space and time.
 So here this is formulated out the attention mechanism right here.
 The attention mechanism is made of queries, keys and values.
 And it's given by this formula right here.
 Now there is a bit of a technicality I wasn't exactly correct in what a is.
 So here, they, they say, they, I called this thing here a, okay, they are very specific
 what they mean by a, by a, they simply mean the exponential function of the normalized
 queries times keys.
 And then to get the actual softmax, you have to normalize by here.
 So D, which is so you see, the inverse is made here, D is constructed from a and normalize
 as a, but the normalization is of secondary importance.
 The important part here is that this exponential cannot be easily decomposed, right?
 It's not like you can decompose the inner multiplication into two exponentials or something,
 otherwise the problem would be solved.
 So what is this paper doing?
 It's exactly what I just said was impossible.
 So you have this matrix a right here, and you multiplied by V. Yes, again, forget about
 the normalization by now.
 It will decompose a into the query, the Q prime and K prime.
 Now they are called prime because they are not the queries and the keys, because we've
 just said the queries and the keys, they go into the exponential.
 So it's going to be that K, sorry, Q prime times K prime transposed is going to be approximately
 equal to exponential function of Q times K, maybe normalized by square root of D. But
 you can see that this here isn't decomposable, and yet they decompose it.
 And the question is how, because there have been papers before that try to decompose the
 attention matrix.
 I think Lin former maybe, and there is also the reformer, which uses LSH and so on.
 So there have been a number of tricks, but they all don't perform as well, which this
 paper also shows empirically.
 And they all rely on certain assumptions of the attention matrix.
 And they all are not unbiased estimators in general, this paper is going to be an unbiased
 estimator.
 And they do this via sort of a kernel framework.
 So what they they first of all, they make this problem more general, they say we have
 our attention matrix A, the ijth entry is going to be the query i, the key j, and some
 kernel function of that.
 In our case, this is going to be the right X of query times key, like this, sorry, the
 other way around.
 Query transpose, transpose, query times key, the inner product of that.
 However, you can think of any sort of kernel function.
 So yeah, if I'm not going to try to explain more details into kernels, we had a fantastic
 machine learning street talk.
 So if you don't know about this, this is our podcast, machine learning street talk, where
 Alex Stanlik explained kernels in great detail, and with very, very precise language, and
 very understandable as well.
 So what I'm going to say is that they allow you to do things like this.
 So you can think of kernels as kind of connecting two things, they allow you, they represent
 an inner product in some other space.
 So the kernel function of two inputs right here will be equal to some inner product of
 the two inputs when pulled through this function phi right here.
 And that's what we're going to use.
 Now usually, usually when you learn about kernels, you do it in this way.
 You say, we would like to compute in this very high dimensional space, but we can't,
 we can't do inner products, we can't map this function phi explicitly.
 So we're going to instead use this kernel right here, this kernel function.
 And that's going to be equal.
 If you pick the right kernel function for the particular phi, in this paper, we're going
 to do it the other way around, because we say, well, this thing here is this is the
 softmax function.
 And that's just a beast, right?
 We can't possibly compute that.
 However, if we could find out what inner product that corresponds to, what other space, we
 could just go to that other space and perform an inner product.
 And this thing over here is linear, right?
 This is a linear function.
 This here is the nonlinear function.
 This is our softmax.
 So you can see that by going in this way, by finding what is the higher or the phi function
 for the softmax kernel, we can construct all of this attention business in a linear fashion.
 And that's what this paper does.
 What it allows you to do is it allows you to find these q and k, q prime and k prime
 matrices such that as over here, right, this is the kernel function.
 And this here is linear.
 And then you can simply first multiply k by v, or k prime by v, and then you can multiply
 q by k, and that will alleviate you of having this giant attention matrix.
 So how do they do it?
 If you again, if you know about random Fourier features, this is going to be very much or
 very similar thing right here.
 They're not going to explicitly construct the high dimensional space such that this
 is exactly equal, but they're going to construct an approximation.
 And the approximation, you can make arbitrarily good.
 And you do that via the following you say, so here you see this is how do I have to map
 something into this other dimensional space, where this whole softmax business is just
 a linear operation.
 So what you would do ultimately is you would take your queries, you would map it through
 this phi, okay, and you would take your keys, and you would also map it through this phi.
 And this will give you query prime, and this will give you key prime, right.
 So and then in the higher down in the higher lower whatever dimensional space, you would
 take the inner product.
 And the inner product between the two is going to approximately be as if you had multiple
 so the inner product is going to be approximately as if you had taken the original q and k,
 multiply them and put them through a softmax.
 How do we do it?
 So here we define what the function needs to look like, sit such that this holds the
 function again, they go very general here, the function in general is going to look like
 the following.
 So you have one function here that's called h, that is a function of your input, and it's
 in front, it's a deterministic function of your input.
 And you also have a normalization factor.
 So this is kind of it's kind of a factor in front of it.
 You see that here comes a vector.
 So this is a vector, right, we are mapping this to a some dimensional space.
 And this is the vector.
 Now it's a bit you have to pay a bit of attention.
 So inside this vector, you have l different sub vectors, they're all concatenated after
 each other.
 Okay, so you have CC here, this, where the F, this is f1, and then f2, f3, f4, and so
 on until fl.
 Okay, so you have all these sub vectors.
 It doesn't matter ultimately, you just concatenate them all.
 But it's important to just keep in mind, within each of these vectors, within each of these
 sub vectors, you always have the same repeated term, you have this w times your x, so the
 inner product between w and x, you can see there's w1 through wm or omega, I think it's
 an omega.
 And again, in the in each sub vector, you have this repeated.
 So what are these omegas, first of all, the omegas are random vectors drawn for from some
 distribution.
 Now in practicality, this is going to be a normal distribution like this one here, an
 isotropic normal distribution.
 So and the the other part here is what are the F's.
 So the F's f1 through fl are going to be functions, deterministic functions.
 So in a an example they gave right here, f1 is the sine function, f2 is the cosine function.
 And then you have to specify h and h in this particular example is one, but it can be a
 function of x here, here, it's just the identity.
 Sorry, not the identity, the constant function one.
 So let's break this a little down.
 So we have x, and x is going to be a vector x, as I said, x is going to be like one of
 the queries here, or one of the one of the keys here, one one of them, right, one column
 or one row, however you conceptualize it, and we wonder how do we want to map so x is
 going to be some vector.
 Okay, then this is an ugly vector.
 Let's draw it like this.
 x is a vector.
 Then what we're going to do is we're going to take a bunch of omegas.
 Now it's important that the omegas are random.
 So they come from this isotropic normal distribution, but they're going to remain the same throughout
 the algorithm.
 So this is a method to resample them, but just conceptualize that at the beginning of
 the algorithm, you choose these omegas and then you fix them.
 So the omegas are going to be also vectors, which are random, just a bunch of random vectors.
 Let's take three.
 What you're going to do is you're going to compute the inner product between your x and
 each of the omegas.
 So inner product in your x and each of the omegas.
 So this gives you omega 1x, omega 2x, omega 3x.
 The inner product, this is going to be these, this is going to be numbers.
 And then you're going to have a collection of functions.
 So these are going to be functions, maybe function one is going maybe here, the sine
 function function two is going to be the cosine function.
 Now you're going to take each to make a table.
 You're going to take each of these products you computed and put them through each of
 the functions.
 So this is going to be sine of omega 1x, cosine of omega 1x, sine of omega 2x and so on.
 And then you're going to take this table and you're going to flatten it to a big vector.
 So sine omega 1x, cosine or no sine first, the ordering data doesn't matter as long as
 you always do it the same omega 2x, and so on right until you have here cosine of omega
 3x.
 So that's the vector they're constructing.
 And these are those random features.
 Okay, so this here is going to be the vector that you're constructing.
 What you do is basically geometrically your x is like somewhere here.
 And it's a bit hard to draw in low dimensional space because you don't get the intuition.
 But this is if this is your x, you're going to choose a bunch of these omegas, these omegas
 are going to be randomly sampled from a uniform Gaussian.
 So this is omega 1, maybe omega 2, omega 3, omega 4.
 And you're going to compute the inner product between between any of the two.
 Okay, so you're going to be essentially computing the projections onto each other or the angle
 however you want to conceptualize it, the angle of this to each of the two of the omegas.
 And then you're going to make a features out of these angles, right?
 So this will sort of tell you how your vector stands to each of these random features.
 Now the reason I say it's difficult in low dimension is because now I have more omegas
 than the dimensionality, which is two right here.
 And this makes no sense, right?
 As soon as I have two vectors that are not collinear in two dimensional space, I can
 if I project x onto them, like like this, sorry, like if I project x onto both of them,
 I already have x fully represented, right?
 There's no need to have more of them.
 However, if you are in super duper high dimensional space, and you don't you don't have as many
 features, then you get some interesting approximation properties, namely, so this was an example,
 right?
 We don't always have the sine and the cosine here.
 This is purely an example, you can only have one function, you see like this f one, you
 don't need two functions, you can have one, you can have many.
 Okay.
 And you can choose how many omegas you sample, that is a parameter.
 So yeah, you have a couple of choices, I want to make it clear the choice of h, so the choice
 of h and f, they go hand in hand, the choice of h and the F's determine what the phi function
 is.
 Okay.
 So the choice of h f determine which kernel function this phi function corresponds to,
 if you construct it like this.
 So by choosing the correct functions, you tell the function which kernel you would like
 to approximate.
 And then by sampling the omegas, the more omegas you sample, the more accurately you
 approximate that kernel, and then you can give some approximation guarantees.
 As they say, so the softmax kernel is given by this thing here, which we've already seen.
 Okay.
 And now how do we approximate the softmax kernel?
 And they show that right here, softmax kernel is approximated by this thing right here.
 So it's a bit of a ugly formula, and it contains this Gaussian kernel, the Gauss kernel.
 So they say, if we choose h equals to one, so just a constant factor, and this f1 and
 f2 to the sine and cosine, and in if we choose d, the distribution to be a normal distribution
 isotropic around the mean, this is the Gaussian kernel.
 And then we simply have to choose h differently, this factor in front to make it into the softmax
 kernel, so as long as we put this factor in front, you can see that this here represents
 an inner product, right?
 So you have to kind of think of decomposition.
 So if you put, you can see f1, the sine, f2, the cosine, which is this makes it the Gaussian
 kernel, and then this factor in front of it here, two for h, this makes it now the softmax
 kernel.
 So if we choose h and f like this, then when we map our queries and keys through, if we
 map our queries and keys through the phi function, and then make the inner product between them,
 okay, like here, that will approximate depending on how many omegas we've sampled better or
 worse, they approximate the result as if we had multiplied them first, and then put them
 through the softmax function.
 All right.
 So this you can see how this becomes much easier, because we can independently put them
 through the phi, okay.
 And then it's just a linear operation, which allows us to do our trick where we multiply
 k and v first, and then multiply by q instead of the other way around, which we're forced
 to do when we apply the softmax.
 This was a long, long way to get here.
 But I hope you're with this.
 And this is, this is pretty straightforward, actually, so far.
 Now renormalization, we can take care of that easily.
 But there is a problem.
 And this is they argue, this hasn't been proposed so far, because it doesn't work like this.
 So even though you approximate this kernel fairly well, it's it's a bad approximation.
 And they say here, there is however, a caveat here, the attention module from one constructs
 for each token, a convex combination of value vectors with coefficients given as corresponding
 green renormalized kernel scores.
 That is why kernels producing non negative scores are used.
 Applying random feature maps with potentially negative dimension values leads to unstable
 behaviors, especially when kernel scores close to zero, which is the case for lots of entries
 of a corresponding to not relevant tokens are approximated by estimators with large
 variants in such regions.
 This results in abnormal behaviors, eg negative diagonal value renormalizers, and consequently
 either completely prevents training or leads to sub optimal models.
 So what they're saying is that when you use softmax, you always always get positive values,
 right?
 So if I have a bunch of vectors, or a bunch of numbers, this is, you know, positive number,
 negative number, very positive number, negative number, and I run it through a softmax, I
 will get out a distribution right, like this, or really big, sorry, that softmax will scale
 that up, I will get out a positive district like a kind of a histogram.
 And now I'm trying to approximate this by this formula right here.
 And you can see these are these are vectors, which gives me sine and cosine coefficients,
 and I linearly multiply two vectors together, which definitely means I can get negative
 entries and so on.
 So the renormalization then has to somehow maybe take care of that.
 And it says especially, especially around zero, when the original softmax matrix would
 have values close to zero, this approximation is really bad and has high variance.
 And they also argue, a lot of attention vectors are close to zero, because we know that attention
 is sort of sparsify, just by the fact of what how the softmax works, it exaggerates the
 largest inner products, and it really dampens the low inner products.
 Okay.
 Actually, I might not even have done this correctly here.
 If it's, if it's very negative, I'm not sure.
 In any case, they say that's why this doesn't work, because it has such high variance, it's
 a good approximation, but has such high variance in the wrong places, they really around zero
 where most values are.
 So they call this these s, the SM the softmax approximation with m sampled features trig,
 because it uses the sine and cosine functions.
 And now they're trying to remedy this.
 And for that, they propose a different decomposition.
 So a different approximation to the softmax kernel.
 And they say we can also decompose the softmax or approximate the softmax kernel with the
 following formula.
 And I look, I, I'm not going to, they have a proof for this.
 But this is the formula.
 You sample again, you sample these things.
 And then you perform this inner, this is the inner product that approximates the softmax
 kernel.
 Okay.
 And this is further, you can reduce this to this thing right here.
 So it's a deterministic matrix right here, this which is given by that.
 And it's this cos h.
 So cos h is the hyperbolic tangent.
 This can be this is so cos h of x is e to the x plus e to the minus x divided by two.
 Okay, so this function approximates the softmax.
 And that's just something you'll have to take from their proof.
 However, you can now see that this can be fairly easily represented as an inner product,
 you already see it here, right?
 This you simply, this is the part that comes from x, and this is the part that comes from
 y.
 If you want to note this in our in our notation earlier, again, we use the distribution that
 we sampled the omegas from is going to be a normal distribution.
 And our functions are going to be this h function is the pre factor, it's simply going to be
 the made up of the norm of x and put through the exponential function.
 And then we have two options actually, right here.
 I don't even know why they put the first one.
 But the second option makes more sense.
 And there's a bit of a more of a factor right here.
 So you have two functions, there is x of u and negative x and x of negative u, as the
 two function you remember, this is where we had sine and cosine before.
 Now we have x u and negative x, sorry, x of negative u.
 And we can quickly check that this gives us the same thing.
 So this h, these h functions, if we inner product them, that's going to be to give us
 the this, what is that even lambda?
 Is that a big lambda matrix right here?
 And our vector, let's just say we sample one single omega, right?
 So we have our x, we sample one single omega.
 So x is going to give us a vector with two sub vectors, right?
 Since we have two functions, each sub vector is of length one.
 So the first is going to be e to the omega x, and the second entry is going to be e to
 the negative omega x.
 If we put in y through the same or as instead of x and y, you can think of queries and keys,
 that's going to be y e to the negative omega y.
 If we now take the inner product, that is going to give us and I'm resolving the exponentials
 already right here.
 So that's going to give us e to the e to the w x plus y.
 And here is going to give us plus e to the w or sorry, the negative w x plus y.
 And that's the you know, there is a normalization factor.
 That's why the square root of two is here, right?
 So that comes in somewhere here to give us this normalization factor.
 So this is exactly the hyperbolic cosine of omega times z and z is x plus y that they
 say it somewhere.
 Yeah.
 Okay.
 So if we choose f1 and f2 to be this x, u and x negative u, then we get if we perform
 the inner product, we get out exactly this formula number seven right here.
 So this is this.
 And that is an approximation of the softmax kernel of the softmax function.
 It's just a different approximation than before.
 Okay.
 And the cool thing about this approximation is that the approximation itself only ever
 has positive values.
 So these vectors here, you can see the x, the vectors here, and there's of course a
 four a factor in front of this right here, which is going to be also an exponential.
 These are all exponential.
 So these are all going to be positive features, which is very, very nice.
 And they also show this theoretically.
 So here, this kind of funky graphic shows this.
 This is the ratio of the approximation mistake.
 Okay, the ratio of the approximation mistake of the of the original approximation that
 we discussed and this new positive approximation that we just built right now.
 And you can see that in parts here, it's fairly similar.
 So this, I believe, so R is the ratio.
 So it's fairly flat right here.
 But there are parts where it just shoots up, right?
 And in fact, they can prove that you can see this also right here.
 So the error of the trig approximation that shoots up while the positive approximation
 just stays flat or flatter in these regions.
 They can in fact prove that the the error of the Yeah, so you see the error.
 If the softmax values go to zero, so that's the problematic regions, the error of the
 trigonomic approximation can go to infinity while the error of the positive approximation
 goes to zero.
 Okay, they have a number of theoretical results in here.
 I think that's one of the main ones, the fact that the this approximation succeeds where
 the other approximation fails.
 Really quickly, they also have this variant here, where they don't build a two vector
 or a vector of two sub vectors, but just one with just the exponential function.
 And that is the same thing.
 Because of course, if you sample w, you're going to have sorry, omega, if you sample
 omega, you're going to have omega as much as negative omega, I believe and and thereby
 in expectation, you're going to get this hyperbolic cosine again, I think that's the reason why
 but this lower this lower construction here gives you the hyperbolic cosine.
 Okay, so pretty cool.
 We simply use this approximation, we run our queries, right?
 This your queries and our keys through this.
 And again, we ideally use more omegas than just one, maybe a bunch.
 The more we use the better we obtain a linear function that approximates the softmax function.
 The more we sample, the more it approximated, it's unbiased, and so on.
 And have a bunch of variants of it.
 So variant where you normalize the omegas, which gives you the regularized softmax kernel,
 which is not a softmax anymore, but it's a regularized softmax.
 And they can approximate this in pretty much the same way.
 Except instead of a normal distribution, you use a uniform distribution right here.
 And they have a bunch of other things, namely, one other improvement is that so far, we've
 simply sampled these W's, okay, we sampled the W's from a normal distribution like this
 here.
 They say we can improve even further.
 Namely, we can strictly improve with this gives us an estimator with strictly lower
 variance if we make sure that the W's we sample are exactly orthogonal.
 So they're already approximately orthogonal if we sample them from a high dimensional
 space.
 But if we make sure that they are exactly orthogonal, sorry, then they are giving us
 an even better approximation.
 And you can do that by this procedure called the Gram-Schmidt orthogonalization or Gram-Schmidt
 renormalization procedure.
 It's a pretty easy procedure.
 And it doesn't mess with your unbiasedness.
 Whenever D is an isotropic distribution, isotropic just means the same in every direction.
 So like a standard Gaussian would fulfill or a uniform would fulfill this thing as long
 as it's centered.
 I think maybe even if it's not centered, depends on how you renormalize.
 Okay, this is irrelevant.
 But if you make them exactly orthogonal, say this leads to the first theoretical results
 showing that orthogonal random features can be applied to reduce the variance of the softmax
 or Gaussian kernel estimators for any dimensionality D rather than just asymptotically for large
 enough D as it is the case for previous methods.
 And leads to the first exponentially small bounds on large deviations probabilities that
 are strictly smaller than for non-orthogonal methods.
 So you're going to end up with a thing that's strictly smaller, so bounds that are strictly
 smaller than if you don't use orthogonality.
 The only thing it requires is that m is smaller or equal to D. So the number of omega u sample
 is going to be smaller equal to the dimensionality that the original space operates in, which
 they say this will be the case in all our experiments.
 Okay, and again, these are exponentially small bounds, which is pretty cool.
 I guess for you, the end user, it matters that this works.
 And if you use all of their tricks with the positivity and the orthogonality.
 So by the way, this here is where they show that CDD or orthogonal MSE, the mean squared
 error is smaller than the original one minus some thing.
 And as long as the something of course is greater than zero, you're going to have something
 that's smaller.
 Okay, then they prove a bunch of other things again about this kind of this regularized,
 sorry, not regularized.
 I forget it's the where you divide by the norm.
 In any case, they implement this in jacks.
 Oh, great.
 Wow, cool.
 I okay, I have no opinion on jacks.
 But they have the code released and I'll of course link to it.
 And here you can clearly see so this is a log log plot, where you have l the size of
 the input and the number of seconds that it takes to go forward and backward over here
 in the model.
 And you can see the x here.
 The x is the baseline where you simply bypass the attention matrix, you simply take the
 identity function and just return the value matrix.
 And you can see that the performance the performers, they scale fairly well with that baseline.
 And in fact, they scale at the same slope, which is the important part right here, you
 can really see that this is linear slope where the transformers which are the dashed lines,
 they all curve upwards, which of course is that that quadratic requirement.
 The same in the backward pass, I don't know if they continue curving.
 I think it's also a straight line in the log log plot.
 But the slope is two instead of one, like the linear like the linear models.
 Again, the comparison is only important between the baseline and the lines that you're looking
 at.
 If they have the same slope, they scale the same as you get higher.
 Look at it.
 This is log L, right?
 So this is these these are now two to the 18th tokens.
 And I believe this is done on one GPU.
 Yes, so an out of memory error on a V 100 GPU.
 And this is pretty good.
 This is pretty good news for everyone who wants to run the performers in in kind of
 a low resource environment low risk with low resource.
 I mean, like a deep learning GPU instead of 1000 TPUs, which is pretty cool.
 They also show the that their method is better than the kind of so the orthogonality is better
 than the ID features.
 And then of course, the positive ID features are better than these original trigonometric
 decomposition.
 And they show that this thing that you can take a transformer checkpoint, and you plug
 it into the performer.
 And you simply have to fine tune a little bit to get it to the performance that the
 transformer was at, right?
 This is I believe this is the original training curve of the transformer.
 So you know, it's not a fair comparison, because the performer starts from the checkpoint
 already.
 At least that's how I interpret it.
 It's not clearly written and they say, okay, over here, this trig thing works.
 This is the original approximation, this even works.
 However, if we do that on a bit more challenging, more longer sequences, data, data set, then
 you can see that the trig softmax, it just it just whacks out.
 That's this thing here.
 And you actually need better these positive approximations.
 And that compared to the Linformer here, which is pretty cool.
 So the Linformer, another, I've made a video about it, if you want to know about it, but
 they also do random projections of the attention matrix.
 But you can see that the Linformer plateaus along with the performers, if you don't redraw
 the random features.
 So if you want in the performer, if you do it at the right time, you redraw these random
 features, these omegas, you have to have to see where you can you can't just arbitrarily
 redraw them between computation steps.
 But at the end of like a computation step, you can redraw for the next computation step.
 And if you do that, and the even better with the regularized or the the normalized features,
 you get to the same level of performance that a standard transformer would get.
 But of course, without the quadratic requirements.
 And okay, lastly, as I said, they've already they've already swapped out the
 they swapped out this nonlinearity by a relu.
 So here they construct performer relu, taking f equals relu in equation five, you remember
 what f was, f was the sine and cosine when we had the first approximation and f was the
 x x of u and x of minus u, the second one.
 And as I said, the big improvement in deep learning came when we swapped sigmoids for
 relus.
 And here they've already they're already trying swapping now this because they say, well,
 so we have a method that we can basically plug in anything we want.
 So they plug in relu because it's you know, worked well.
 And this again, it works pretty well.
 So they compare again also with the reformer here with the Lin former, as you can see,
 and of course, they beat everything now, whether or not this method is going to be the next
 thing, like the thing that everyone uses is to be we don't know.
 It's fairly possible.
 It's pretty cool.
 And it appears to be theoretically solidly grounded, but you never know from the experiments
 of the single paper, the broader impact statement, much respect, they just use it to tell you
 how awesome their paper is.
 Like there's no mention on on on any kind of ethical impact, which I believe like I'm
 all for these kinds of broader impact statements, like just kind of okay, research on transformers
 is going to be better because now people have access to it.
 It's backward compatible.
 That's pretty cool.
 It's applicable to biology and medicine because we can take longer sequences.
 It's all like, yeah, I like these kinds of broader impact statement.
 The last thing here is that you might be so the only problem is if you want to do this
 causal attention that if you want to do like a generative model, like a GPT sort of model,
 you have to do a bit of a trick.
 And that is because your attention matrix isn't the full attention matrix.
 So you can't just decompose it.
 It's this lower triangular matrix right here.
 But since you have linear decomposition of this thing, you can do these kind of prefix
 sums, namely, you can compute simply so you you you can compute the key one times value
 one, and then you can compute key two times value two plus key one times value one.
 And you compute key three value three plus key two value two plus key one, sorry, value
 one, and so on.
 You compute these things.
 And these are all these are all the big where the L goes away, right?
 So we do that first.
 And then we simply have to come along and we take q q one, multiply by q one, v one,
 we take q two, multiply by this and this q three will multiply by this, this and this.
 And you see, that's how you get your causal attention.
 So you simply keep track of these prefix sums right here.
 And then when the next q comes along, simply multiplied by all of the things that are above
 it in the prefix sum, that's how you get your triangular matrix.
 So even that is solved, a thing that I believe the Lin former wasn't able to do with its
 particular decomposition, I might be I might be wrong here.
 All right, they have a bunch of experiments on protein analysis, and so on, which of course,
 wasn't possible, I guess before because it was so so heavy.
 They also have like image net 64, as you can see right here, which is an impossible data
 set for a classic transformer.
 As I said, they have code code is in jacks, which is like this is it's ugly code.
 Let's be honest, but it's code.
 So that's fairly cool.
 And I want to point out the right at the bottom here is actually where the stuff happens.
 So you can see that.
 Just quickly, you have here keys and queries are, where is it?
 Exactly.
 So queries and keys are going to be constructed right here.
 So query prime and key prime are going to be pulled through this feature creator, which
 implements these these kernels.
 So these can either as we said, these x or the relu's or the sine cosine, whatnot, then
 you're going to multiply the queries and the keys, which gives you yet this W matrix.
 And all that we need to do now is normalize it.
 Okay, so we re normalize by constructing this denominator right here.
 And then there's a whole block for the unit directionality, which you can imagine is pretty
 ugly, but the renormalization we constructed, we reciprocal means we take the inverse multiplied
 by the W and return the result, this should be translatable into your favorite whatnot
 pytorch or TensorFlow, maybe it's already been done, I haven't researched that particular
 thing.
 In any case, I invite you to check out the paper, the code, play around with the functions
 used here, as long as you, you know, use fun, you don't even you don't need to know, like
 these papers, they always know which kind of kernels their functions correspond to.
 But you know, in SVM, people just went, went nuts, I just plug in some functions, see what
 happens.
 Probably nothing good, but it's possible.
 Alright, so that was it for the performer.
 I hope you gained something from this kind of an understanding of how it works.
 And I wish you the best.
 Bye bye.