This is a game changer! (AlphaTensor by DeepMind explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper deepmind deep mind deepmind alphatensor alpha tensor deepmind math google deep mind google deepmind matrix multiplication ai matrix multiplication matrix multiplication reinforcement learning alphazero alpha zero alphazero math deep learning tutorial introduction to deep learning what is deep learning alphatensor explained alpha tensor explained
#alphatensor #deepmind #ai 

Matrix multiplication is the most used mathematical operation in all of science and engineering. Speeding this up has massive consequences. Thus, over the years, this operation has become more and more optimized. A fascinating discovery was made when it was shown that one actually needs less than N^3 multiplication operations to multiply to NxN matrices. DeepMind goes a step further and creates AlphaTensor, a Deep Reinforcement Learning algorithm that plays a single-player game, TensorGame, in order to find even more optimized algorithms for matrix multiplication. And it turns out, there exists a plethora of undiscovered matrix multiplication algorithms, which not only will make everything from computers to smart toasters faster, but also bring new insights into fundamental math and complexity theory.

Sponsor: Assembly AI
Link: https://www.assemblyai.com/?utm_source=youtube&utm_medium=social&utm_campaign=yannic_sentiment

OUTLINE:
0:00 - Intro
1:50 - Sponsor: Assembly AI (link in description)
3:25 - What even is Matrix Multiplication?
6:10 - A very astounding fact
8:45 - Trading multiplications for additions
12:35 - Matrix Multiplication as a Tensor
17:30 - Tensor Decompositions
20:30 - A formal way of finding multiplication algorithms
31:00 - How to formulate this as a game?
39:30 - A brief primer on AlphaZero / MCTS
45:40 - The Results
48:15 - Optimizing for different hardware
52:40 - Expanding fundamental math
53:45 - Summary & Final Comments

Paper: https://www.nature.com/articles/s41586-022-05172-4
Title: Discovering faster matrix multiplication algorithms with reinforcement learning

Abstract:
Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems—from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. Here we report a deep reinforcement learning approach based on AlphaZero1 for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. AlphaTensor discovered algorithms that outperform the state-of-the-art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago2. We further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. Our results highlight AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.

Authors: Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis & Pushmeet Kohli

Links:
Homepage: https://ykilcher.com
Merch: https://ykilcher.com/merch
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://ykilcher.com/discord
LinkedIn: https://www.linkedin.com/in/ykilcher

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
 Hello there, today DeepMind published a new paper called Alpha Tensor. This is a system that speeds up matrix multiplications of all things. Now I know it sounds a bit boring to speed up matrix multiplications that's like not as flashy as some of the other things DeepMind has done. But since matrix multiplications are at the foundation of pretty much all of science, a speed up of 10%, 20% or even 1% in this domain is huge and can make the whole world better off. And this is really cool because it also shows how DeepMind took their ideas, their original ideas from something like AlphaGo and pulled them through all the way to now where they have real applications in science. And that's cool. And it's a bit a validation of this idea because a lot of people said initially when DeepMind focused that much on games and things like this that it's just for press, it's just flashy and to a certain degree it is. But definitely it is also applicable because you can frame a lot of things as games, not just Atari and chess and Go. In fact, matrix multiplication, as we'll see, can be framed as a single player game, essentially, called tensor game. And then you can apply much the same techniques to it as you do solving chess or solving Go. So we're going to look at this paper, as I said, this was published by DeepMind, it was published in the Journal of Nature. And yeah, it's a big deal. I think it's a big deal. And yeah, let's dive in. We're going to look at what the problem actually is, how it works, and what the actual results are. So this video is sponsored by assembly AI assembly AI does real time and batch audio transcription of audio and video files powered by the latest advances in artificial intelligence. So if you are a developer or work for a company that's looking to get more out of your audio or video data through transcription and audio intelligence, assembly AI is the best place to go. Not only do they have a user interface where you can just upload stuff, but they do have a very powerful API, but transcription isn't all they do. Once your audio is described, they actually post process it in many different optional ways. So they can do things like speaker classification or annotations of various forms inside of your audio. One feature I'd like to particularly highlight today is the sentiment analysis. Now we're all familiar with sentiment analysis. But have you ever done it on a piece of transcribed audio, not only can you infer it from the text, but you can actually infer it from the tones of voices, the breaks people take and much more. In order to use this feature with assembly AI simply provide the sentiment analysis equals true in your request and assembly AI will do the rest for you, you'll get the result as a neat JSON output and you can take it from there. So if you're interested, head on over to assembly AI use the link in the description to let them know that I sent you there are the single API to transcribe and understand audio, they do so in batch and in real time via web socket, they accept all kinds of audio and video formats and they do so in over 15 languages. Give it a try and thank you very much to assembly AI for sponsoring this video. And now let's get into the video. So the paper is called discovering faster matrix multiplication algorithms with reinforcement learning. As I already said, if you don't if you don't know what matrix multiplication is, we not not go too much into this here. Suffice to say a matrix is just kind of like a a bunch of numbers. And there's a specific way of multiplying these bunch of numbers with a bunch of other numbers and you get a bunch of other numbers. So essentially a matrix is a square box of numbers, and we have ways of multiplying them. And that's all of science there. There you go. So what's the the actual deal? So if we go through it, and I'm going to make this a tiny bit bigger right here. So if we have a matrix like a one, how they call it a two, a three, a four, and we multiply that by a matrix B, B one, B two, B three, B four, right, the classic algorithm of doing matrix matrix multiplication goes something like this, if I want to have this, the entry up here, then I look at the row, I take that row of this matrix, I look at the column, I take the column of this matrix, I compute the inner product. So that's kind of like a one, b one, plus a two, b two, right? That's the that's the thing. And I do it for every single component right here. So a one, b one plus a two, no, b three, b three is that you see I already fail. So I do that. And then I compute this one by using this row and this column, and so on. And you can see there's a bunch of stuff coming together, mainly additions and multiplications. So we have an addition right here. And we have the multiplications obviously in between the components. Now it just turns out that on our hardware that we use in silicon, addition is much, much faster than multiplication. So the bulk of the time that a processor is going to spend on doing matrix multiplications is actually doing the individual multiplications between the numbers, the additions are not the issue. The question is, how many multiplications do we need in order to to multiply two matrices? Now it's sort of the classic algorithm. If I have matrices of size n by n, then I'm going to need about O n to the to the third, I think, multiplications of achieving that. So I need to do every row with every column. And each of those inner products is again of size n, right? So those are those are my the square is everything with everything. And then inside of each of these of the inner products, I again have n multiplications. Now what is already astounding is that because you would think this is right, I need this I need to do all of these multiplications to compute all of these numbers, like I have no choice if I want to compute these numbers somewhere there needs to be a multiplication between this number and this number and this number. Oh, sorry, this and you see I'm terrible at this. So between this number and this number, and between this number and this number, and that's naturally two multiplications, I can't get around it. And so I need to compute two multiplications for each of the four entries right here. That's two to the third, that's eight. Okay, and I can tell you it's faster than that. There is a way of doing it faster. In fact, it's displayed right here. So you can see I hope you can see it's not all too big. But if you compute this term right here, m one, m one is a, a one plus a four times b one plus b four. So I would first go let me have to have another color. Yes, I would first go and add those two numbers. And then I would add those two numbers, no multiplication yet. And then I would simply multiply the addition of the two numbers. That's just one multiplication between two numbers, right, not an inner product or anything. So that's, that's a term that I'll call m one. And then I do this a bunch of other times, you can see here, it gets kind of tricky, you subtract, subtraction is essentially addition as well. So it's really cheap, but each of these terms right here is just one scalar multiplication. And then from these intermediate terms, I can compute down here, you can see again, only additions, the final product. And if you calculate this all out, you'll actually see, yes, it actually works. It works out. We can try to follow one of these things. And oh, yeah, the catch is there's only seven, there's only seven, one of these multiplications. And that seems like magic, right? It seems like it shouldn't be it shouldn't be possible. But I'm going to convince you that it is with a simple example. In fact, you already know this, if you for example, take the following. So take a squared minus b squared. This is very common formula in sort of high school algebra. So that is a times a minus b times b, two multiplications, right? One multiplication here, one multiplication here. Now I can rewrite this as you know, to a plus b times a minus b. And look at that. There's now just one multiplication. Like that's literally it. But you might say, well, it's still the same thing. Yes, what you're doing is you're trading off addition or multiplication. In fact, when you calculate this out, as you know, this is a squared plus a b minus a b minus b squared. And then these terms here cancel out. So in fact, hidden in all of this are one, two, three, four multiplications. However, by clever arrangement, it's actually the two multiplications that we started with out here. So by cleverly arranging things, right, you and then later, so this would be the intermediate term one, I guess they call that m1, this would be the intermediate term m2, by cleverly arranging these intermediate terms, so that later multiplying them actually cancels out some of the terms, you can have it such that one scalar multiplication with more additions than you would usually do, in fact, results in the same result as four or respectively two multiplications if you cross out the canceling terms, but with fewer additions. And that's exactly what we want. So you know this here already, and the same principle carries over to the matrix world. In fact, when you look at one of these entries, we can quickly look at one. Let's look at c2 right here. So c2 is m3 plus m5. But what's m3? m3 is this one right here plus m5. Well you already see what's c2, c2 is here. So that's this row times this column. So we need an a1 plus a1 b2 in there somehow. So a1 is here times b2, that's this term. And we also need an a2 b4. Well a2 and b4, b4 and a2, that's here. Now all we need is that the other terms cancel. Well there is a b4 times a1. And look, there is an a1 times b4 with a minus sign. They cancel. So that's the general principle of why it is possible, the seemingly impossible task of speeding up matrix multiplication, why it is possible. And again, the speed up isn't because of some math magic. The speed up is because we only care about the number of multiplications, because our hardware is bounded by the number of multiplications, and because we can trade off multiplications for additions. We don't make speed appear out of nothing. We simply customize it more to our hardware. So how do we now formulate this as some sort of game? It seems to be that the game is to find these formulas right here, to find this algorithm. This is an algorithm. This is valid for any multiplications of two by two matrices. Any of these you can multiply like this, it'll give you the correct result independent of the actual coefficients. But how do we set up a system that could find this right here? If you as a human were to find this, you'd be like, well, let me try. But it turns out there's a neat formalization of finding these algorithms as a tensor decomposition. So for that, you have to look at the tensor right here. Now I don't know if you can see this, the rendering of the PDF here is a bit small, but I'm going to try to keep it zoomed in like that. This is a three dimensional tensors. You might say, wait, I thought we were dealing with two dimensional matrices. Well, yes. But the problem of finding the algorithm of multiplying two dimensional matrices can actually be phrased. Or let me say, let me other than that, let me say the multiplication of two dimensional matrices can be phrased as a three dimensional tensor. And then finding the algorithm is a decomposition problem of that tensor. So let me show you what I mean. Here you have that tensor, you have the matrix A unrolled here into its components, you see A1, A2, A3, A4, you have the matrix B unrolled in this dimension into its components. And in the last dimension, so this is in the last dimension, this dimension here, you have the resulting matrix unrolled. This is a matrix, this right here, it only has components zero or one, there's no other numbers in it, there's just either a zero or a one. Now, the ones you can see here colored in solid blocks. And whenever there's a one in this tensor, it means that that's, that's a step you have to do. So ideally, there should be a one for every entry in the C dimension right here. So you can see C1, how do we do it? We go look, aha, okay, this block here is the entry for C1. Now what do we need to do? We look at the other dimensions. So this corresponds to B1 and A1, right? A, this is this dimension, B1 is this dimension. So this block being solid, it means in order to get C1, we need to multiply A1 and B1. Now that's not enough, there's also going to be another entry for C1, namely, as you can see down here, this is also on the dimension of on the axis that corresponds to C1. And it in turn corresponds again to A1, this dimension, but B3. So we have to multiply A1 by B3 also to get C1. And if you look C1, it's this times this right now. So A1 times B1. No it's A2. I might be confused here. Or is the drawing confused? It should be A2 multiplied by B3. Oh, yes, of course, obviously, sorry. Yeah, this is A2. This slice here is A2. I was dumb. So it's a three dimensional tensor. I'm not used to these kind of higher level mathematical stuff that scares me. But you can see using this tensor, we can fill in the blocks that we know corresponds to matrix matrix multiplication entries. This is just a classic algorithm, right? I'm doing nothing fancy here. I'm just applying the high school matrix multiplication algorithm saying like, okay, what do I need to get for this? I need to get these two plus these two. And for every multiplication here, I make one entry into this tensor. So at the location that I want to see one is the result. I'm going to make one entry here for the first multiplication. I want to make one entry here for the second multiplication, and I'll get a tensor. Now it turns out it turns out that a low rank decomposition of this tensor will exactly give me an algorithm to perform this multiplication. In fact, any decomposition of this tensor will do that. So I can decompose a tensor, I can decompose a matrix, but also a tensor into individual components. Now, for a matrix, you may know, for example, that if I have a matrix A, I can, I can write it as a sum of outer products of vectors ui, vi, right? There's various and sorry, outer product. So every component here is going to be some sort of a vector multiplied by some sort of other vector. So the outer product will give me a matrix, but the matrix is of rank one. And then I add many of these matrices, and I'll give me the original matrix, I can do that with any matrix, right? You might know some special cases of these decompositions, for example, spectral decomposition usually extracts also some sort of a scalar right here, and then makes these two orthogonal. So there are various ways of how to do this. But in our case, any decomposition of this matrix will give us an algorithm. And it's going to be a valid algorithm because it's a valid decomposition of the it's a valid decomposition of the tensor. Or if I apply that algorithm, I will get the correct matrix multiplication. Here on the right hand side, you can see one such decomposition that corresponds to this algorithm right here. There can be various different algorithms all with either the same or more or less steps, which correspond to various ways of decomposing that tensor. So the tensor specifically, you can see here matrices u, v and w. And specifically, the decomposition goes as the matrix, how do we call that? Maybe M, no T, they call it T. So specifically, that matrix T is going to be decomposed into individual parts of vectors ui, outer product with vi, outer product with wi. Again, I can do this in any case, these are going to be rank one, three dimensional tensors. If I if I do that right, one vector, one vector, and one vector gives me a rank one three dimensional tensor. If I add many of these, I'll get more rank more tensor. And if that addition results in this tensor right here, that means I have found a decomposition of that tensor. And this also directly corresponds to an algorithm. Let's look at that how that works. So if assume that I have such a decomposition, what I can do is I can take the first vector here, and the first vector here. And that will give me kind of the components that I need to compute. So the first vector here, you can see corresponds to a one plus a four, so I have to take a one and a four, the two entries with the ones. And then of the B matrix, I have to take B one and B four, this thing right here. And I have to build these things, I have to multiply them, multiply them, multiply that those and that will become m one. And that will result in m one, m one, I'll remember for later. So m one. Similarly, the second columns will become m two, m three, and so on. And then later, I'll go and look at my matrix W. And now I'm going to look at the rows of the matrix W. And this row tells me which one of the m terms I need to combine together. So one, well, that's actually good, better visible, one m one plus one m four minus one m five plus one m seven. That's exactly this row right here, we're just going to give me c one as an entry. So if I have a decomposition, I can just read off the algorithm. And just to understand like a tiny bit more what's happening right here, I also thought we'd look at the same entry we did before. So let's look at c two. How do I get c two? Well, I need m three now. No, I was wanted to do something different. I wanted to let's stay at the c one. And let's look at what that actually does, like how this how this outer product even looks, right? Because I still can see that maybe some people have a hard time visualizing what's happening. So I just told you how to do the algorithm. But I also showed you, well, there's this decomposition right here. And technically, that first column of all of these vectors should correspond to the first entry in that decomposition. But how does that look? Well, if I take u and v, and I built the outer product, essentially, what I have to do is I have to take u and let's put u into the column here, just into the row, let's transpose you and I outer product it with v. So I need to take one time u then zero time u in the next column, then zero times u in the next column, and then one time u in the last column. That's this. And now I want the outer product with w here. Okay, I go into the third dimension. So I take one time that slice that I just computed. That's my front, then zero times zero times that's like 00000000000. And you can like it's a cube, you fill in the back yourself. And then I take it one time again. So 1001001 and so on. So that's going to be a cube with ones at the corners. Ones and everything else is zero. So this cube with ones at the corners and everything else is zero is rank one is a rank one 3d tensor because it can be decomposed into the outer product of three vectors. Not every 3d tensor is can do that only rank one 3d tensors. And now, if we if we go through all of these columns right here, we do all of that and we add all of these cubes that we're going to get together, then we get back to this thing right here, which means that again, it's a valid decomposition. And you can already see here, two of the corners are actually correct. So this corner right here. Yes, we just we just made it right. This corner right here is already done. It's this corner here. That we already we have it right. And the corner down here, we have it to here. So if the all of this is correct, right, then it should be that in none of the other columns, we're going to modify these corners again. So let's quickly check that for the top left corner here. So the 111 entry, that's this, this, and this. So none of these things. So these should be these are 111 here, which gives us that result. So in no other column, should we get an entry here, there's always going to be one zero somewhere. And you can see right, there's a zero here. In fact, here too, there's one here and here. There's one here. There's one here, one here, and two here. So good, right? This, this is the only place where that's modified. So that corner is the direct is this corner in the final result. However, if we look at another corner, for example, this one here, well, this one is zero in the final tensor. But here we have it as a one. So our hypothesis is that in some of the other columns, this must be kind of reverted, right? Much like this component right here is reverted later. Or you know, however you want to want to watch it, this needs to be canceled out somewhere. So let's go and find out where it is canceled out. So currently, this is a one. Why is it a one? Well, it's a one because a one is here, a one is here, right? Because we're in other corner now, and a one is here. So dimension one, dimension four, dimension one here, our hypothesis is that this is going to be somewhere later subtracted again. Well, okay, there's a zero here, zero here. So that's not nothing. We have one minus one and one here. So three candidates. There's as I know, we're in the bottom row. There is a zero here. So not this column. There is a one and a one here. Okay, this already looks promising. Now there's a zero here. So it's not this column. So look at this column. There is a one boom, there is a one down here, you can't see it anymore, but it's there. And there is a negative one here. So this outer product of the last column is going to result in negative one as a as this corner of the cube, right? So in its cube, it's going to have a negative one here, instead of a one. And if we add those together, remember, we add those all together, because it's a tensor decomposition, we get zero at this place right here. And if we now go and look, okay, into c4, this is, yes, this is c4. At the last column, we should see that. No, wait. No, that's not something that's not something we can we can see right here. Sorry for that. In any case, I hope you can imagine a little bit in how that goes. So you build up these these, these things, these cubes, which are rank, which are low rank, but quite complex, right? And you then add them together. And the correct things need to cancel out such that you get back this thing right here, because this thing actually corresponds to the original matrix matrix multiplication. And if you find a correct decomposition, then that also corresponds to the multiplication. But the decomposition also gives you directly an algorithm to perform this multiplication a different one than the original tensor. And now it's only can you find a decomposition where this dimension right here is very low, right? And all find decompositions where this dimension is really high, because we can just consider the individual entries of the original tensor. And for each one of them, we construct such columns, right? So that it's one at exactly that place. However, if we do it in a smarter way, we can do with less columns, and thereby, our decomposition has a lower rank and thereby, we need less multiplications because each column corresponds to exactly one multiplication. That was long winded, but I hope you get a little bit of the idea of why it is even possible to speed up matrix matrix multiplication of how we represent a matrix matrix multiplication as a 3d tensor, and why a decomposition of that tensor gives us a new algorithm to perform the same thing. And then that the rank of the decomposition will is directly directly corresponding to the, to the number of multiplications we need. So the goal is to get a low number of terms in that decomposition. So what does now? How do you do this as a game? They formulate this as okay, this is all we probably talked about this, yada yada. And again, this is not this is not this has nothing to do with what numbers are in the matrix, right? The fact that there's zero and one here just corresponds to the algorithm itself. So we're working with the algorithm, we're not working with the numbers. Also you can see there's just zeros and ones and minus ones here. But this can be in fact, any decomposition, this can be negative 3.5 100,000 and so on. But for simplicity, and because of some symmetries, I assume, you can actually limit that in fact, they do limit it to negative two negative one, zero, one, and two, because of numerical stability. And because, well, I don't know, maybe maybe there's a super small smart algorithm with negative 3.7 as a as a coefficient. In any case, they now apply alpha zero to this. So they have a few special network architecture tricks where they exploit some properties of linear algebra. For example, they say, well, the if you change the basis of a linear operation, then it's it's kind of still the same problem. So it's you can you can change the basis of matrices, and it's still the essentially represents the same transformation. However, to this algorithm, this is like a new thing, because now that there's different numbers, right? So the algorithm looks different, because it's sort of a transformation of one another. Now, there's one class of research papers that say, we're going to build our neural network to be invariant to that. But there's an entirely other class and this one here falls under that with that says, well, great. So that's kind of like much more training data. If one training sample corresponds to like many, many, many, I can make many training samples out of one that's free data augmentation. So they use change of basis here, which is that fundamental property or a fundamental action in linear algebra to create more training data. They also say, well, look, while decomposing a 3d tensor is really hard. Constructing one is really easy. We just sample three vectors we add, we make the outer product, we do that a bunch of times we add those things together. And we have a three dimensional tensor that now you can try to decompose, right? So they can also create synthetic training data, all very smart tricks in order to feed their system with more data to train on. So the system is going to be trained on exactly providing these decompositions. We'll look at how in just a bit. The last thing I want to do is the neural network architecture that they analyze things with here, it's transformer based, who would have thought that? Now, interestingly, they say they generalize axial attention, they have a diagram of their architecture down here. And you don't need to know yet what they do with the architecture. But essentially, this is a reinforcement learning algorithm. So the input here is the current tensor and the history of tensors, which I find really interesting that they also consider the history of things. This goes into some sort of a torso or a body or whatnot, then outcomes some sort of embedding, this goes into a policy and a value head, you might be familiar with all of this. If you're familiar with reinforcement learning, the action space here. As you know, we've discussed, are to select three vectors, one of you one of V and one of W that so you select one of the columns of the thing we just saw, right, we saw there are u, v, and w, which should ultimately give you as the sum of outer products, this tau right here. And an action is you provide one of these columns of each of the entries. So one column at a time, this is an action, the next step in the game would be to determine this thing. The next step would be to determine the next column, the game is over, whenever the multiplication here is actually equal. So you can formulate that in a different way by saying, oh, sorry. You can formulate this in a different way by saying, well, the tau should be the sum of ui, outer product vi, outer product wi, right. So once I have u1, w1, and v1, I can subtract that, right. So this is step one of the game. Step two would be tau minus u1, outer product v1, outer product w1, one, not i, one, must be equal to the sum of i equals two to, you know, potentially infinity of ui. So once I have one, once I have an action, which is three vectors, I can subtract that from my original tensor, and then the goal is to find the next action to subtract from the original tensor. The game is over exactly then when this here is equal to zero, right. It can go negative in some entries, as you saw, but if all the entries of the tensor are zero, then the game is over. This is obviously a discrete problem. And it is in fact NP hard if the tensor is of an order higher than two. So this is not an easy task. And the action space is huge, right? You don't just emit one number, you don't you emit the three vectors, each with their respective entries. So that is a ginormous action space, actually much larger action space than something like chess or go. So that's why this problem is particularly difficult. This is a finer architecture, finer diagram of the architecture here of the torso. So what they do is they take the history here of the of the tensors that came along in the in the last time steps. And they projected down to this grid, you can see right here, this is s s by s by t s t being the number of steps or t s plus one, they projected down in various ways onto these grid layers, then they have linear layers projecting, not projecting linear layers, transforming this into some sort of C dimensional vector. And see here, you reduce the time dimension down to the C dimension. After that, you have these they call attentive modes. And at the end, some sort of output. Now the attentive modes, I hope that's this right here, policy head, duck, oh, no. The attentive modes are they say they, as I said, they generalize a form of axial attention. And then here, the way they do the actions in as in common in reinforcement learning, you take the embedding that comes out of the torso here. And this is kind of like an auto regressive language model, if you will, that outputs the next action. So here, you have no action at all. And then you output a policy and the policy is a distribution over your action space. There's also an output to the value head. And you do that. So here, next action, next action, and so on. The value head is simply you take that embedding from the policy head, shove it through some neural network, and you can train all of that end to end. Again, if you don't know alpha zero or reinforcement learning in general, I have many videos on that. So the gist is that you pair this network here, which we just saw is this one in kind of finer detail, you pair this with a so called Monte Carlo tree search. So in order to solve these games, you're in some sort of state, right? At the beginning, your matrix is full, you haven't subtracted anything, or your chess board is at the initial state. And then you consider different moves to do. And for each move that you could do, you then if you do it, you can consider more moves, right, or your opponent can consider more moves. And for each of those moves, again, you consider more moves. So this is a tree search algorithm. Now the alpha zero style Monte Carlo tree search works in a way that the policy and value head policy and value functions of your neural network, they will guide you through this tree search. So they will suggest to you nodes here that are more likely for you to be able to win the game again, winning in this case means getting a successful tensor decomposition. And some that are and say, well, now this one, you shouldn't even try, you shouldn't even explore that direction. So that saves you from considering all those possibilities, narrowing it down onto just a few that you then go explore further, and then you can ask your network again, well, if I were to go here, what would you do next? Well, I would maybe try this one or this one. Okay, and you only need to search those. And you iteratively train this such that once you actually play the game, and you do this, and you go down and at some point, you finish the game, either you reach the zero tensor, which means win reward of one, or you, you don't finish the game, which is a bad so very low reward. Then that feeds back into all of these things. So it feeds back training the neural network to make better predictions. In fact, the reward isn't just zero or one, they do give and I believe they describe it somewhere. They do give a negative one reward for every step that's being done. Nope. I don't exactly know where they describe that. But yes, there. So they say there's a negative reward of negative one for every step taken to encourage finding the shortest path. This is much better than just giving zero or one reward for one, this actually encourages a low D low rank decomposition. On the other hand, it also provides a denser reward signal. So you don't have to. It's not like you win, either win, because this problem is super difficult, right. And by to stumble by chance upon this would be not really, it would be like really lucky and the reward would be super sparse. So they say, well, you get a reward for every step taken a negative reward, so better take fewer steps. And then on top of that, they also pair a supervised reward from this synthetic demonstrations because in the synthetic data, not only can they generate data, they actually know the correct steps to do. So they can train the neural networks in a supervised fashion, they can say, hey, here is the situation. And we already know, because we made the problem, we already know what steps you should take. So that gets on top. Do they say that somewhere here? Maybe not. Somewhere they describe the loss in detail, where they say, well, our loss is this plus the supervised loss. In any case, that's how they do it. And the whole algorithm is essentially here. They start out with a game, which is one of the original tensors, they change the basis to make it to augment the data to make it into one never seen before. They do the Monte Carlo tree search, they determine the first step to do. So the tree search is just kind of imaginary, you kind of think ahead. Once you know what to do, you do the step, then you do the tree search again, and so on until you're at the end of the episode. That represents a played game. Whether you win or you lose, you take your reward and use that to train. So this is learning, you put that in your buffer of games, you also have your synthetic data right here. You sample these things, you train your neural network, either from a synthetic data point, or from one that you've already played in order to predict better what actions to do, which is the policy that's guiding you through the network, and also the value head, which is a function that estimates the value of each node in the network right here also helps to guide you. So the policy head, in fact, guides you to which path you want to go down. And then you don't always want to go down all the way. So at some point, you just cut off and you ask the value head, how much you think this state is worth. You aggregate that all on top. And you look at the top level of all your available actions, which one looks the most promising and that's what you go with. So that's MCTS AlphaZero style in a nutshell. The results, the results are pretty astounding in that you can see right here for small matrix matrix multiplications. They actually do find better algorithms. And you would think that something like multiplying four by four matrices would be kind of figured out by now. But no, the best known algorithm had a 49 multiplication decomposition. And now we have a 47 multiplication decomposition. Now this is modular. So as far as I understand, this is over a finite field. This is not real matrices. But I think for real, I'm actually not super sure. For real matrices, I believe the thing down here counts. So for example, multiplying three by four matrices to four by five matrices, previous best known rank 48, now 47. Again doesn't seem like much, but is. And as you go higher, this gets more drastic. Multiplying four by five to five by five matrices. There are four multiplications less in the algorithm that alpha tensor found. And seeing the diagram right here, as you go up in rank, so best rank known for given problems, and here improvement in rank, how much alpha tensor improves, see there's a clear diagonal line, and that is maybe a bit obvious because us humans, we can't really come up with, well, give me an 800 multiplication decomposition of some tensor. That's just kind of a bit above our league. So what we do is we kind of break it down in small problems and then just kind of recursively apply these strategies. And if you can consider a problem in its entirety, then obviously have a better chance of just you know, cancelling out some things somewhere at some point. Or are these just the symmetric up here? Okay, that could be as well. These are the symmetric and then these are finite versus modular, sorry, modular versus versus standard versus real. Good. The others can be real. I'm just going to stop talking now. Another cool thing you can do is you may have noticed nothing in the base algorithm actually says that, you know, low rank is the goal. That's simply us putting this into the reward, we say, well, for every step you do, you get a negative reward, or go the algorithm is encouraged to take as few steps as possible. However, we can just do something else. This is black box, right? There's nothing, the algorithm just gets this at the end, and it needs to learn this implicitly. So we can swap it out, we can say, actually, we're not that interested in lowest amount of steps, we're going to swap that out. Or in this case, we're going to add another reward on top of that. That says, well, we modify the reward, they say right here, we provide an additional reward at the terminal state, so you only get this additional reward after you actually found the correct solution. Otherwise, they would encourage the algorithm to not find correct solutions, but prioritize something else. So we give this reward. Once the algorithm has found the correct solution, we still retain the step reward. So it means it still needs to find that in as few steps as possible. However, equal to the negative of the runtime of the algorithm when benchmarked on a target hardware. So now they go and they take a V 100 GPU, or a TPU. And they say, you get additional reward if your algorithm is really fast on this particular hardware. Now the algorithm alpha or alpha tensor has no clue of what a V 100 is, or what happens in there is complete black box to it. I think they even have a diagram right here somewhere that says black box. So but still, through the power of reinforcement learning, the algorithm manages and says, well, there are a lot of a lot of algorithms with a low decomposition. A lot of them are kind of equivalent or thousands of algorithms that do, you know, do a decomposition of this tensor, which is another thing they mentioned in the paper, but I'll get to that in a bit. But I'm not going to search for one that is very fast on a particular hardware. And you can see right here, if we actually take an algorithm, we tell alpha tensor to optimize it for a TPU, then there is a significant speed up if we measure that on a TPU. Similarly, if we take one that's that we optimize, we tell alpha tensor to optimize for a GPU, right, and we get a significant speed up, not vice versa, though. You can really see the impact that this has, you can tell the algorithm to come up with a custom tailored solution. This is really cool. And I think it's you know, this must not stay with matrix matrix multiplication, right? You can think of compilers working in exactly this way. Right now, compilers have heuristics and rules of how they transform source code. But essentially, as long as you can prove that you're still doing the same, or I guess kind of the same, you can you could use these very same techniques in order to come up with a program with a with a sort of compile arrangement that optimizes for a particular hardware for a particular metric memory, speed cycles, whatnot. So there's so many applications of this, even beyond the many applications that matrix matrix multiplication already has. And if you thought, well, you know, in practice, we have much bigger tensors, even than, yeah, whatever 200 dimensional and so on. And these got there's got to be some limit to the algorithm at some point, because this seems compute intense than yes, however, even like something small, like this algorithm here, we can recursively apply it to get speed up even at higher dimensions. So that's pretty cool, too. It's not going to be the most optimal algorithm, but it's going to be a more optimal algorithm than we already have. So this will help at any size. Yeah, lastly, what I want to mention is briefly that they also say that it doesn't only help practically, it also helps a lot the mathematical view that we have of matrix decompositions, because it finds it finds like, for example, if you consider t four, which multiplies to four by four matrices, alpha tensor finds more than 14,000 non equivalent factorizations. So this means these are all different algorithms that you can use to find to to achieve the goal of multiplying four by four matrices to each other. And they're different. They're not just like symmetric transformations of each other. And that will, I think, yeah, that is a great benefit to mathematicians who care about complexity theory and things like this. All right, so that is about all I had to say about this paper. So to summarize, they built this, this game and the same agent, by the way, plays all of these games. So the same agent trains to multiply four by three matrices, five by five matrices, and so on. There's significant transfer learning happening. So they train one agent that does nothing else but start out with a problem like this, augment it a little bit, and then try to find a decomposition. It may be fail, it may succeed, it learns from it, it tries again, finds a decomposition. There's nothing that that that's a single player game. And if you get good at the game, you can find good decompositions, which correspond to algorithms to multiply two matrices. If you take very few steps in doing so, that means every step corresponds to one multiplication in the resulting algorithm. So if you're very good at it, your algorithms will have very few steps. And therefore, our hardware will be able to compute it more quickly because they have to do less of the expensive operation that is multiplication. All right, that was it for me. Let me know what you think. There's more to this paper. I invite you to read it. I hope I got the gist of it across. Bye bye.
 Hello there, today DeepMind published a new paper called Alpha Tensor.
 This is a system that speeds up matrix multiplications of all things.
 Now I know it sounds a bit boring to speed up matrix multiplications that's like not
 as flashy as some of the other things DeepMind has done.
 But since matrix multiplications are at the foundation of pretty much all of science,
 a speed up of 10%, 20% or even 1% in this domain is huge and can make the whole world
 better off.
 And this is really cool because it also shows how DeepMind took their ideas, their original
 ideas from something like AlphaGo and pulled them through all the way to now where they
 have real applications in science.
 And that's cool.
 And it's a bit a validation of this idea because a lot of people said initially when DeepMind
 focused that much on games and things like this that it's just for press, it's just
 flashy and to a certain degree it is.
 But definitely it is also applicable because you can frame a lot of things as games, not
 just Atari and chess and Go.
 In fact, matrix multiplication, as we'll see, can be framed as a single player game, essentially,
 called tensor game.
 And then you can apply much the same techniques to it as you do solving chess or solving Go.
 So we're going to look at this paper, as I said, this was published by DeepMind, it was
 published in the Journal of Nature.
 And yeah, it's a big deal.
 I think it's a big deal.
 And yeah, let's dive in.
 We're going to look at what the problem actually is, how it works, and what the actual results
 are.
 So this video is sponsored by assembly AI assembly AI does real time and batch audio transcription
 of audio and video files powered by the latest advances in artificial intelligence.
 So if you are a developer or work for a company that's looking to get more out of your audio
 or video data through transcription and audio intelligence, assembly AI is the best place
 to go.
 Not only do they have a user interface where you can just upload stuff, but they do have
 a very powerful API, but transcription isn't all they do.
 Once your audio is described, they actually post process it in many different optional
 ways.
 So they can do things like speaker classification or annotations of various forms inside of
 your audio.
 One feature I'd like to particularly highlight today is the sentiment analysis.
 Now we're all familiar with sentiment analysis.
 But have you ever done it on a piece of transcribed audio, not only can you infer it from the
 text, but you can actually infer it from the tones of voices, the breaks people take and
 much more.
 In order to use this feature with assembly AI simply provide the sentiment analysis equals
 true in your request and assembly AI will do the rest for you, you'll get the result
 as a neat JSON output and you can take it from there.
 So if you're interested, head on over to assembly AI use the link in the description to let
 them know that I sent you there are the single API to transcribe and understand audio, they
 do so in batch and in real time via web socket, they accept all kinds of audio and video formats
 and they do so in over 15 languages.
 Give it a try and thank you very much to assembly AI for sponsoring this video.
 And now let's get into the video.
 So the paper is called discovering faster matrix multiplication algorithms with reinforcement
 learning.
 As I already said, if you don't if you don't know what matrix multiplication is, we not
 not go too much into this here.
 Suffice to say a matrix is just kind of like a a bunch of numbers.
 And there's a specific way of multiplying these bunch of numbers with a bunch of other
 numbers and you get a bunch of other numbers.
 So essentially a matrix is a square box of numbers, and we have ways of multiplying them.
 And that's all of science there.
 There you go.
 So what's the the actual deal?
 So if we go through it, and I'm going to make this a tiny bit bigger right here.
 So if we have a matrix like a one, how they call it a two, a three, a four, and we multiply
 that by a matrix B, B one, B two, B three, B four, right, the classic algorithm of doing
 matrix matrix multiplication goes something like this, if I want to have this, the entry
 up here, then I look at the row, I take that row of this matrix, I look at the column,
 I take the column of this matrix, I compute the inner product.
 So that's kind of like a one, b one, plus a two, b two, right?
 That's the that's the thing.
 And I do it for every single component right here.
 So a one, b one plus a two, no, b three, b three is that you see I already fail.
 So I do that.
 And then I compute this one by using this row and this column, and so on.
 And you can see there's a bunch of stuff coming together, mainly additions and multiplications.
 So we have an addition right here.
 And we have the multiplications obviously in between the components.
 Now it just turns out that on our hardware that we use in silicon, addition is much,
 much faster than multiplication.
 So the bulk of the time that a processor is going to spend on doing matrix multiplications
 is actually doing the individual multiplications between the numbers, the additions are not
 the issue.
 The question is, how many multiplications do we need in order to to multiply two matrices?
 Now it's sort of the classic algorithm.
 If I have matrices of size n by n, then I'm going to need about O n to the to the third,
 I think, multiplications of achieving that.
 So I need to do every row with every column.
 And each of those inner products is again of size n, right?
 So those are those are my the square is everything with everything.
 And then inside of each of these of the inner products, I again have n multiplications.
 Now what is already astounding is that because you would think this is right, I need this
 I need to do all of these multiplications to compute all of these numbers, like I have
 no choice if I want to compute these numbers somewhere there needs to be a multiplication
 between this number and this number and this number.
 Oh, sorry, this and you see I'm terrible at this.
 So between this number and this number, and between this number and this number, and that's
 naturally two multiplications, I can't get around it.
 And so I need to compute two multiplications for each of the four entries right here.
 That's two to the third, that's eight.
 Okay, and I can tell you it's faster than that.
 There is a way of doing it faster.
 In fact, it's displayed right here.
 So you can see I hope you can see it's not all too big.
 But if you compute this term right here, m one, m one is a, a one plus a four times b
 one plus b four.
 So I would first go let me have to have another color.
 Yes, I would first go and add those two numbers.
 And then I would add those two numbers, no multiplication yet.
 And then I would simply multiply the addition of the two numbers.
 That's just one multiplication between two numbers, right, not an inner product or anything.
 So that's, that's a term that I'll call m one.
 And then I do this a bunch of other times, you can see here, it gets kind of tricky,
 you subtract, subtraction is essentially addition as well.
 So it's really cheap, but each of these terms right here is just one scalar multiplication.
 And then from these intermediate terms, I can compute down here, you can see again,
 only additions, the final product.
 And if you calculate this all out, you'll actually see, yes, it actually works.
 It works out.
 We can try to follow one of these things.
 And oh, yeah, the catch is there's only seven, there's only seven, one of these multiplications.
 And that seems like magic, right?
 It seems like it shouldn't be it shouldn't be possible.
 But I'm going to convince you that it is with a simple example.
 In fact, you already know this, if you for example, take the following.
 So take a squared minus b squared.
 This is very common formula in sort of high school algebra.
 So that is a times a minus b times b, two multiplications, right?
 One multiplication here, one multiplication here.
 Now I can rewrite this as you know, to a plus b times a minus b.
 And look at that.
 There's now just one multiplication.
 Like that's literally it.
 But you might say, well, it's still the same thing.
 Yes, what you're doing is you're trading off addition or multiplication.
 In fact, when you calculate this out, as you know, this is a squared plus a b minus a b
 minus b squared.
 And then these terms here cancel out.
 So in fact, hidden in all of this are one, two, three, four multiplications.
 However, by clever arrangement, it's actually the two multiplications that we started with
 out here.
 So by cleverly arranging things, right, you and then later, so this would be the intermediate
 term one, I guess they call that m1, this would be the intermediate term m2, by cleverly
 arranging these intermediate terms, so that later multiplying them actually cancels out
 some of the terms, you can have it such that one scalar multiplication with more additions
 than you would usually do, in fact, results in the same result as four or respectively
 two multiplications if you cross out the canceling terms, but with fewer additions.
 And that's exactly what we want.
 So you know this here already, and the same principle carries over to the matrix world.
 In fact, when you look at one of these entries, we can quickly look at one.
 Let's look at c2 right here.
 So c2 is m3 plus m5.
 But what's m3?
 m3 is this one right here plus m5.
 Well you already see what's c2, c2 is here.
 So that's this row times this column.
 So we need an a1 plus a1 b2 in there somehow.
 So a1 is here times b2, that's this term.
 And we also need an a2 b4.
 Well a2 and b4, b4 and a2, that's here.
 Now all we need is that the other terms cancel.
 Well there is a b4 times a1.
 And look, there is an a1 times b4 with a minus sign.
 They cancel.
 So that's the general principle of why it is possible, the seemingly impossible task
 of speeding up matrix multiplication, why it is possible.
 And again, the speed up isn't because of some math magic.
 The speed up is because we only care about the number of multiplications, because our
 hardware is bounded by the number of multiplications, and because we can trade off multiplications
 for additions.
 We don't make speed appear out of nothing.
 We simply customize it more to our hardware.
 So how do we now formulate this as some sort of game?
 It seems to be that the game is to find these formulas right here, to find this algorithm.
 This is an algorithm.
 This is valid for any multiplications of two by two matrices.
 Any of these you can multiply like this, it'll give you the correct result independent of
 the actual coefficients.
 But how do we set up a system that could find this right here?
 If you as a human were to find this, you'd be like, well, let me try.
 But it turns out there's a neat formalization of finding these algorithms as a tensor decomposition.
 So for that, you have to look at the tensor right here.
 Now I don't know if you can see this, the rendering of the PDF here is a bit small,
 but I'm going to try to keep it zoomed in like that.
 This is a three dimensional tensors.
 You might say, wait, I thought we were dealing with two dimensional matrices.
 Well, yes.
 But the problem of finding the algorithm of multiplying two dimensional matrices can actually
 be phrased.
 Or let me say, let me other than that, let me say the multiplication of two dimensional
 matrices can be phrased as a three dimensional tensor.
 And then finding the algorithm is a decomposition problem of that tensor.
 So let me show you what I mean.
 Here you have that tensor, you have the matrix A unrolled here into its components, you see
 A1, A2, A3, A4, you have the matrix B unrolled in this dimension into its components.
 And in the last dimension, so this is in the last dimension, this dimension here, you have
 the resulting matrix unrolled.
 This is a matrix, this right here, it only has components zero or one, there's no other
 numbers in it, there's just either a zero or a one.
 Now, the ones you can see here colored in solid blocks.
 And whenever there's a one in this tensor, it means that that's, that's a step you have
 to do.
 So ideally, there should be a one for every entry in the C dimension right here.
 So you can see C1, how do we do it?
 We go look, aha, okay, this block here is the entry for C1.
 Now what do we need to do?
 We look at the other dimensions.
 So this corresponds to B1 and A1, right?
 A, this is this dimension, B1 is this dimension.
 So this block being solid, it means in order to get C1, we need to multiply A1 and B1.
 Now that's not enough, there's also going to be another entry for C1, namely, as you
 can see down here, this is also on the dimension of on the axis that corresponds to C1.
 And it in turn corresponds again to A1, this dimension, but B3.
 So we have to multiply A1 by B3 also to get C1.
 And if you look C1, it's this times this right now.
 So A1 times B1.
 No it's A2.
 I might be confused here.
 Or is the drawing confused?
 It should be A2 multiplied by B3.
 Oh, yes, of course, obviously, sorry.
 Yeah, this is A2.
 This slice here is A2.
 I was dumb.
 So it's a three dimensional tensor.
 I'm not used to these kind of higher level mathematical stuff that scares me.
 But you can see using this tensor, we can fill in the blocks that we know corresponds
 to matrix matrix multiplication entries.
 This is just a classic algorithm, right?
 I'm doing nothing fancy here.
 I'm just applying the high school matrix multiplication algorithm saying like, okay, what do I need
 to get for this?
 I need to get these two plus these two.
 And for every multiplication here, I make one entry into this tensor.
 So at the location that I want to see one is the result.
 I'm going to make one entry here for the first multiplication.
 I want to make one entry here for the second multiplication, and I'll get a tensor.
 Now it turns out it turns out that a low rank decomposition of this tensor will exactly
 give me an algorithm to perform this multiplication.
 In fact, any decomposition of this tensor will do that.
 So I can decompose a tensor, I can decompose a matrix, but also a tensor into individual
 components.
 Now, for a matrix, you may know, for example, that if I have a matrix A, I can, I can write
 it as a sum of outer products of vectors ui, vi, right?
 There's various and sorry, outer product.
 So every component here is going to be some sort of a vector multiplied by some sort of
 other vector.
 So the outer product will give me a matrix, but the matrix is of rank one.
 And then I add many of these matrices, and I'll give me the original matrix, I can do
 that with any matrix, right?
 You might know some special cases of these decompositions, for example, spectral decomposition
 usually extracts also some sort of a scalar right here, and then makes these two orthogonal.
 So there are various ways of how to do this.
 But in our case, any decomposition of this matrix will give us an algorithm.
 And it's going to be a valid algorithm because it's a valid decomposition of the it's a
 valid decomposition of the tensor.
 Or if I apply that algorithm, I will get the correct matrix multiplication.
 Here on the right hand side, you can see one such decomposition that corresponds to this
 algorithm right here.
 There can be various different algorithms all with either the same or more or less steps,
 which correspond to various ways of decomposing that tensor.
 So the tensor specifically, you can see here matrices u, v and w.
 And specifically, the decomposition goes as the matrix, how do we call that?
 Maybe M, no T, they call it T. So specifically, that matrix T is going to be decomposed into
 individual parts of vectors ui, outer product with vi, outer product with wi.
 Again, I can do this in any case, these are going to be rank one, three dimensional tensors.
 If I if I do that right, one vector, one vector, and one vector gives me a rank one three dimensional
 tensor.
 If I add many of these, I'll get more rank more tensor.
 And if that addition results in this tensor right here, that means I have found a decomposition
 of that tensor.
 And this also directly corresponds to an algorithm.
 Let's look at that how that works.
 So if assume that I have such a decomposition, what I can do is I can take the first vector
 here, and the first vector here.
 And that will give me kind of the components that I need to compute.
 So the first vector here, you can see corresponds to a one plus a four, so I have to take a
 one and a four, the two entries with the ones.
 And then of the B matrix, I have to take B one and B four, this thing right here.
 And I have to build these things, I have to multiply them, multiply them, multiply that
 those and that will become m one.
 And that will result in m one, m one, I'll remember for later.
 So m one.
 Similarly, the second columns will become m two, m three, and so on.
 And then later, I'll go and look at my matrix W. And now I'm going to look at the rows of
 the matrix W.
 And this row tells me which one of the m terms I need to combine together.
 So one, well, that's actually good, better visible, one m one plus one m four minus one
 m five plus one m seven.
 That's exactly this row right here, we're just going to give me c one as an entry.
 So if I have a decomposition, I can just read off the algorithm.
 And just to understand like a tiny bit more what's happening right here, I also thought
 we'd look at the same entry we did before.
 So let's look at c two.
 How do I get c two?
 Well, I need m three now.
 No, I was wanted to do something different.
 I wanted to let's stay at the c one.
 And let's look at what that actually does, like how this how this outer product even
 looks, right?
 Because I still can see that maybe some people have a hard time visualizing what's happening.
 So I just told you how to do the algorithm.
 But I also showed you, well, there's this decomposition right here.
 And technically, that first column of all of these vectors should correspond to the
 first entry in that decomposition.
 But how does that look?
 Well, if I take u and v, and I built the outer product, essentially, what I have to do is
 I have to take u and let's put u into the column here, just into the row, let's transpose
 you and I outer product it with v. So I need to take one time u then zero time u in the
 next column, then zero times u in the next column, and then one time u in the last column.
 That's this.
 And now I want the outer product with w here.
 Okay, I go into the third dimension.
 So I take one time that slice that I just computed.
 That's my front, then zero times zero times that's like 00000000000.
 And you can like it's a cube, you fill in the back yourself.
 And then I take it one time again.
 So 1001001 and so on.
 So that's going to be a cube with ones at the corners.
 Ones and everything else is zero.
 So this cube with ones at the corners and everything else is zero is rank one is a rank
 one 3d tensor because it can be decomposed into the outer product of three vectors.
 Not every 3d tensor is can do that only rank one 3d tensors.
 And now, if we if we go through all of these columns right here, we do all of that and
 we add all of these cubes that we're going to get together, then we get back to this
 thing right here, which means that again, it's a valid decomposition.
 And you can already see here, two of the corners are actually correct.
 So this corner right here.
 Yes, we just we just made it right.
 This corner right here is already done.
 It's this corner here.
 That we already we have it right.
 And the corner down here, we have it to here.
 So if the all of this is correct, right, then it should be that in none of the other columns,
 we're going to modify these corners again.
 So let's quickly check that for the top left corner here.
 So the 111 entry, that's this, this, and this.
 So none of these things.
 So these should be these are 111 here, which gives us that result.
 So in no other column, should we get an entry here, there's always going to be one zero
 somewhere.
 And you can see right, there's a zero here.
 In fact, here too, there's one here and here.
 There's one here.
 There's one here, one here, and two here.
 So good, right?
 This, this is the only place where that's modified.
 So that corner is the direct is this corner in the final result.
 However, if we look at another corner, for example, this one here, well, this one is
 zero in the final tensor.
 But here we have it as a one.
 So our hypothesis is that in some of the other columns, this must be kind of reverted, right?
 Much like this component right here is reverted later.
 Or you know, however you want to want to watch it, this needs to be canceled out somewhere.
 So let's go and find out where it is canceled out.
 So currently, this is a one.
 Why is it a one?
 Well, it's a one because a one is here, a one is here, right?
 Because we're in other corner now, and a one is here.
 So dimension one, dimension four, dimension one here, our hypothesis is that this is going
 to be somewhere later subtracted again.
 Well, okay, there's a zero here, zero here.
 So that's not nothing.
 We have one minus one and one here.
 So three candidates.
 There's as I know, we're in the bottom row.
 There is a zero here.
 So not this column.
 There is a one and a one here.
 Okay, this already looks promising.
 Now there's a zero here.
 So it's not this column.
 So look at this column.
 There is a one boom, there is a one down here, you can't see it anymore, but it's there.
 And there is a negative one here.
 So this outer product of the last column is going to result in negative one as a as this
 corner of the cube, right?
 So in its cube, it's going to have a negative one here, instead of a one.
 And if we add those together, remember, we add those all together, because it's a tensor
 decomposition, we get zero at this place right here.
 And if we now go and look, okay, into c4, this is, yes, this is c4.
 At the last column, we should see that.
 No, wait.
 No, that's not something that's not something we can we can see right here.
 Sorry for that.
 In any case, I hope you can imagine a little bit in how that goes.
 So you build up these these, these things, these cubes, which are rank, which are low
 rank, but quite complex, right?
 And you then add them together.
 And the correct things need to cancel out such that you get back this thing right here,
 because this thing actually corresponds to the original matrix matrix multiplication.
 And if you find a correct decomposition, then that also corresponds to the multiplication.
 But the decomposition also gives you directly an algorithm to perform this multiplication
 a different one than the original tensor.
 And now it's only can you find a decomposition where this dimension right here is very low,
 right?
 And all find decompositions where this dimension is really high, because we can just consider
 the individual entries of the original tensor.
 And for each one of them, we construct such columns, right?
 So that it's one at exactly that place.
 However, if we do it in a smarter way, we can do with less columns, and thereby, our
 decomposition has a lower rank and thereby, we need less multiplications because each
 column corresponds to exactly one multiplication.
 That was long winded, but I hope you get a little bit of the idea of why it is even possible
 to speed up matrix matrix multiplication of how we represent a matrix matrix multiplication
 as a 3d tensor, and why a decomposition of that tensor gives us a new algorithm to perform
 the same thing.
 And then that the rank of the decomposition will is directly directly corresponding to
 the, to the number of multiplications we need.
 So the goal is to get a low number of terms in that decomposition.
 So what does now?
 How do you do this as a game?
 They formulate this as okay, this is all we probably talked about this, yada yada.
 And again, this is not this is not this has nothing to do with what numbers are in the
 matrix, right?
 The fact that there's zero and one here just corresponds to the algorithm itself.
 So we're working with the algorithm, we're not working with the numbers.
 Also you can see there's just zeros and ones and minus ones here.
 But this can be in fact, any decomposition, this can be negative 3.5 100,000 and so on.
 But for simplicity, and because of some symmetries, I assume, you can actually limit that in fact,
 they do limit it to negative two negative one, zero, one, and two, because of numerical
 stability.
 And because, well, I don't know, maybe maybe there's a super small smart algorithm with
 negative 3.7 as a as a coefficient.
 In any case, they now apply alpha zero to this.
 So they have a few special network architecture tricks where they exploit some properties
 of linear algebra.
 For example, they say, well, the if you change the basis of a linear operation, then it's
 it's kind of still the same problem.
 So it's you can you can change the basis of matrices, and it's still the essentially represents
 the same transformation.
 However, to this algorithm, this is like a new thing, because now that there's different
 numbers, right?
 So the algorithm looks different, because it's sort of a transformation of one another.
 Now, there's one class of research papers that say, we're going to build our neural
 network to be invariant to that.
 But there's an entirely other class and this one here falls under that with that says,
 well, great.
 So that's kind of like much more training data.
 If one training sample corresponds to like many, many, many, I can make many training
 samples out of one that's free data augmentation.
 So they use change of basis here, which is that fundamental property or a fundamental
 action in linear algebra to create more training data.
 They also say, well, look, while decomposing a 3d tensor is really hard.
 Constructing one is really easy.
 We just sample three vectors we add, we make the outer product, we do that a bunch of times
 we add those things together.
 And we have a three dimensional tensor that now you can try to decompose, right?
 So they can also create synthetic training data, all very smart tricks in order to feed
 their system with more data to train on.
 So the system is going to be trained on exactly providing these decompositions.
 We'll look at how in just a bit.
 The last thing I want to do is the neural network architecture that they analyze things
 with here, it's transformer based, who would have thought that?
 Now, interestingly, they say they generalize axial attention, they have a diagram of their
 architecture down here.
 And you don't need to know yet what they do with the architecture.
 But essentially, this is a reinforcement learning algorithm.
 So the input here is the current tensor and the history of tensors, which I find really
 interesting that they also consider the history of things.
 This goes into some sort of a torso or a body or whatnot, then outcomes some sort of embedding,
 this goes into a policy and a value head, you might be familiar with all of this.
 If you're familiar with reinforcement learning, the action space here.
 As you know, we've discussed, are to select three vectors, one of you one of V and one
 of W that so you select one of the columns of the thing we just saw, right, we saw there
 are u, v, and w, which should ultimately give you as the sum of outer products, this tau
 right here.
 And an action is you provide one of these columns of each of the entries.
 So one column at a time, this is an action, the next step in the game would be to determine
 this thing.
 The next step would be to determine the next column, the game is over, whenever the multiplication
 here is actually equal.
 So you can formulate that in a different way by saying, oh, sorry.
 You can formulate this in a different way by saying, well, the tau should be the sum
 of ui, outer product vi, outer product wi, right.
 So once I have u1, w1, and v1, I can subtract that, right.
 So this is step one of the game.
 Step two would be tau minus u1, outer product v1, outer product w1, one, not i, one, must
 be equal to the sum of i equals two to, you know, potentially infinity of ui.
 So once I have one, once I have an action, which is three vectors, I can subtract that
 from my original tensor, and then the goal is to find the next action to subtract from
 the original tensor.
 The game is over exactly then when this here is equal to zero, right.
 It can go negative in some entries, as you saw, but if all the entries of the tensor
 are zero, then the game is over.
 This is obviously a discrete problem.
 And it is in fact NP hard if the tensor is of an order higher than two.
 So this is not an easy task.
 And the action space is huge, right?
 You don't just emit one number, you don't you emit the three vectors, each with their
 respective entries.
 So that is a ginormous action space, actually much larger action space than something like
 chess or go.
 So that's why this problem is particularly difficult.
 This is a finer architecture, finer diagram of the architecture here of the torso.
 So what they do is they take the history here of the of the tensors that came along in the
 in the last time steps.
 And they projected down to this grid, you can see right here, this is s s by s by t
 s t being the number of steps or t s plus one, they projected down in various ways onto
 these grid layers, then they have linear layers projecting, not projecting linear layers,
 transforming this into some sort of C dimensional vector.
 And see here, you reduce the time dimension down to the C dimension.
 After that, you have these they call attentive modes.
 And at the end, some sort of output.
 Now the attentive modes, I hope that's this right here, policy head, duck, oh, no.
 The attentive modes are they say they, as I said, they generalize a form of axial attention.
 And then here, the way they do the actions in as in common in reinforcement learning,
 you take the embedding that comes out of the torso here.
 And this is kind of like an auto regressive language model, if you will, that outputs
 the next action.
 So here, you have no action at all.
 And then you output a policy and the policy is a distribution over your action space.
 There's also an output to the value head.
 And you do that.
 So here, next action, next action, and so on.
 The value head is simply you take that embedding from the policy head, shove it through some
 neural network, and you can train all of that end to end.
 Again, if you don't know alpha zero or reinforcement learning in general, I have many videos on
 that.
 So the gist is that you pair this network here, which we just saw is this one in kind
 of finer detail, you pair this with a so called Monte Carlo tree search.
 So in order to solve these games, you're in some sort of state, right?
 At the beginning, your matrix is full, you haven't subtracted anything, or your chess
 board is at the initial state.
 And then you consider different moves to do.
 And for each move that you could do, you then if you do it, you can consider more moves,
 right, or your opponent can consider more moves.
 And for each of those moves, again, you consider more moves.
 So this is a tree search algorithm.
 Now the alpha zero style Monte Carlo tree search works in a way that the policy and
 value head policy and value functions of your neural network, they will guide you through
 this tree search.
 So they will suggest to you nodes here that are more likely for you to be able to win
 the game again, winning in this case means getting a successful tensor decomposition.
 And some that are and say, well, now this one, you shouldn't even try, you shouldn't
 even explore that direction.
 So that saves you from considering all those possibilities, narrowing it down onto just
 a few that you then go explore further, and then you can ask your network again, well,
 if I were to go here, what would you do next?
 Well, I would maybe try this one or this one.
 Okay, and you only need to search those.
 And you iteratively train this such that once you actually play the game, and you do this,
 and you go down and at some point, you finish the game, either you reach the zero tensor,
 which means win reward of one, or you, you don't finish the game, which is a bad so very
 low reward.
 Then that feeds back into all of these things.
 So it feeds back training the neural network to make better predictions.
 In fact, the reward isn't just zero or one, they do give and I believe they describe it
 somewhere.
 They do give a negative one reward for every step that's being done.
 Nope.
 I don't exactly know where they describe that.
 But yes, there.
 So they say there's a negative reward of negative one for every step taken to encourage finding
 the shortest path.
 This is much better than just giving zero or one reward for one, this actually encourages
 a low D low rank decomposition.
 On the other hand, it also provides a denser reward signal.
 So you don't have to.
 It's not like you win, either win, because this problem is super difficult, right.
 And by to stumble by chance upon this would be not really, it would be like really lucky
 and the reward would be super sparse.
 So they say, well, you get a reward for every step taken a negative reward, so better take
 fewer steps.
 And then on top of that, they also pair a supervised reward from this synthetic demonstrations
 because in the synthetic data, not only can they generate data, they actually know the
 correct steps to do.
 So they can train the neural networks in a supervised fashion, they can say, hey, here
 is the situation.
 And we already know, because we made the problem, we already know what steps you should take.
 So that gets on top.
 Do they say that somewhere here?
 Maybe not.
 Somewhere they describe the loss in detail, where they say, well, our loss is this plus
 the supervised loss.
 In any case, that's how they do it.
 And the whole algorithm is essentially here.
 They start out with a game, which is one of the original tensors, they change the basis
 to make it to augment the data to make it into one never seen before.
 They do the Monte Carlo tree search, they determine the first step to do.
 So the tree search is just kind of imaginary, you kind of think ahead.
 Once you know what to do, you do the step, then you do the tree search again, and so
 on until you're at the end of the episode.
 That represents a played game.
 Whether you win or you lose, you take your reward and use that to train.
 So this is learning, you put that in your buffer of games, you also have your synthetic
 data right here.
 You sample these things, you train your neural network, either from a synthetic data point,
 or from one that you've already played in order to predict better what actions to do,
 which is the policy that's guiding you through the network, and also the value head, which
 is a function that estimates the value of each node in the network right here also helps
 to guide you.
 So the policy head, in fact, guides you to which path you want to go down.
 And then you don't always want to go down all the way.
 So at some point, you just cut off and you ask the value head, how much you think this
 state is worth.
 You aggregate that all on top.
 And you look at the top level of all your available actions, which one looks the most
 promising and that's what you go with.
 So that's MCTS AlphaZero style in a nutshell.
 The results, the results are pretty astounding in that you can see right here for small matrix
 matrix multiplications.
 They actually do find better algorithms.
 And you would think that something like multiplying four by four matrices would be kind of figured
 out by now.
 But no, the best known algorithm had a 49 multiplication decomposition.
 And now we have a 47 multiplication decomposition.
 Now this is modular.
 So as far as I understand, this is over a finite field.
 This is not real matrices.
 But I think for real, I'm actually not super sure.
 For real matrices, I believe the thing down here counts.
 So for example, multiplying three by four matrices to four by five matrices, previous
 best known rank 48, now 47.
 Again doesn't seem like much, but is.
 And as you go higher, this gets more drastic.
 Multiplying four by five to five by five matrices.
 There are four multiplications less in the algorithm that alpha tensor found.
 And seeing the diagram right here, as you go up in rank, so best rank known for given
 problems, and here improvement in rank, how much alpha tensor improves, see there's a
 clear diagonal line, and that is maybe a bit obvious because us humans, we can't really
 come up with, well, give me an 800 multiplication decomposition of some tensor.
 That's just kind of a bit above our league.
 So what we do is we kind of break it down in small problems and then just kind of recursively
 apply these strategies.
 And if you can consider a problem in its entirety, then obviously have a better chance of just
 you know, cancelling out some things somewhere at some point.
 Or are these just the symmetric up here?
 Okay, that could be as well.
 These are the symmetric and then these are finite versus modular, sorry, modular versus
 versus standard versus real.
 Good.
 The others can be real.
 I'm just going to stop talking now.
 Another cool thing you can do is you may have noticed nothing in the base algorithm actually
 says that, you know, low rank is the goal.
 That's simply us putting this into the reward, we say, well, for every step you do, you get
 a negative reward, or go the algorithm is encouraged to take as few steps as possible.
 However, we can just do something else.
 This is black box, right?
 There's nothing, the algorithm just gets this at the end, and it needs to learn this implicitly.
 So we can swap it out, we can say, actually, we're not that interested in lowest amount
 of steps, we're going to swap that out.
 Or in this case, we're going to add another reward on top of that.
 That says, well, we modify the reward, they say right here, we provide an additional reward
 at the terminal state, so you only get this additional reward after you actually found
 the correct solution.
 Otherwise, they would encourage the algorithm to not find correct solutions, but prioritize
 something else.
 So we give this reward.
 Once the algorithm has found the correct solution, we still retain the step reward.
 So it means it still needs to find that in as few steps as possible.
 However, equal to the negative of the runtime of the algorithm when benchmarked on a target
 hardware.
 So now they go and they take a V 100 GPU, or a TPU.
 And they say, you get additional reward if your algorithm is really fast on this particular
 hardware.
 Now the algorithm alpha or alpha tensor has no clue of what a V 100 is, or what happens
 in there is complete black box to it.
 I think they even have a diagram right here somewhere that says black box.
 So but still, through the power of reinforcement learning, the algorithm manages and says,
 well, there are a lot of a lot of algorithms with a low decomposition.
 A lot of them are kind of equivalent or thousands of algorithms that do, you know, do a decomposition
 of this tensor, which is another thing they mentioned in the paper, but I'll get to that
 in a bit.
 But I'm not going to search for one that is very fast on a particular hardware.
 And you can see right here, if we actually take an algorithm, we tell alpha tensor to
 optimize it for a TPU, then there is a significant speed up if we measure that on a TPU.
 Similarly, if we take one that's that we optimize, we tell alpha tensor to optimize for a GPU,
 right, and we get a significant speed up, not vice versa, though.
 You can really see the impact that this has, you can tell the algorithm to come up with
 a custom tailored solution.
 This is really cool.
 And I think it's you know, this must not stay with matrix matrix multiplication, right?
 You can think of compilers working in exactly this way.
 Right now, compilers have heuristics and rules of how they transform source code.
 But essentially, as long as you can prove that you're still doing the same, or I guess
 kind of the same, you can you could use these very same techniques in order to come up with
 a program with a with a sort of compile arrangement that optimizes for a particular hardware for
 a particular metric memory, speed cycles, whatnot.
 So there's so many applications of this, even beyond the many applications that matrix
 matrix multiplication already has.
 And if you thought, well, you know, in practice, we have much bigger tensors, even than, yeah,
 whatever 200 dimensional and so on.
 And these got there's got to be some limit to the algorithm at some point, because this
 seems compute intense than yes, however, even like something small, like this algorithm
 here, we can recursively apply it to get speed up even at higher dimensions.
 So that's pretty cool, too.
 It's not going to be the most optimal algorithm, but it's going to be a more optimal algorithm
 than we already have.
 So this will help at any size.
 Yeah, lastly, what I want to mention is briefly that they also say that it doesn't only help
 practically, it also helps a lot the mathematical view that we have of matrix decompositions,
 because it finds it finds like, for example, if you consider t four, which multiplies to
 four by four matrices, alpha tensor finds more than 14,000 non equivalent factorizations.
 So this means these are all different algorithms that you can use to find to to achieve the
 goal of multiplying four by four matrices to each other.
 And they're different.
 They're not just like symmetric transformations of each other.
 And that will, I think, yeah, that is a great benefit to mathematicians who care about complexity
 theory and things like this.
 All right, so that is about all I had to say about this paper.
 So to summarize, they built this, this game and the same agent, by the way, plays all
 of these games.
 So the same agent trains to multiply four by three matrices, five by five matrices,
 and so on.
 There's significant transfer learning happening.
 So they train one agent that does nothing else but start out with a problem like this,
 augment it a little bit, and then try to find a decomposition.
 It may be fail, it may succeed, it learns from it, it tries again, finds a decomposition.
 There's nothing that that that's a single player game.
 And if you get good at the game, you can find good decompositions, which correspond to algorithms
 to multiply two matrices.
 If you take very few steps in doing so, that means every step corresponds to one multiplication
 in the resulting algorithm.
 So if you're very good at it, your algorithms will have very few steps.
 And therefore, our hardware will be able to compute it more quickly because they have
 to do less of the expensive operation that is multiplication.
 All right, that was it for me.
 Let me know what you think.
 There's more to this paper.
 I invite you to read it.
 I hope I got the gist of it across.
 Bye bye.