Transcript - Lesson 11

Lesson 11: Deep Learning Foundations Practical Deep Learning for Coders - Jeremy Howard

Hi everybody, welcome to Lesson 11. This is the third lesson in Part 2.

Depending on how you count things, there's been a lesson A and a lesson B, it's kind of the fifth lesson in Part 2, I don't know what it is. So we'll just stick to calling it Lesson 11 and avoid getting too confused. I'm already confused.

My goodness, I've got so much stuff to show you. I'm only going to show you a tiny fraction of the cool stuff that's been happening on the forum this week, but it's been amazing.

Showing student's work

I'm going to start by sharing this beautiful video from John Robinson —"Robinsn" I should say—, and I've never seen anything like this before. As you can see, it's very stable and it's really showing this beautiful movement between seasons. So what I did on the forum was I said to folks, hey, you should try interpolating between prompts, which is what John did. And I also said you should try using the last image of the previous prompt interpolation as the initial image for the next prompt. And anyway, here it is, came out beautifully.

John was the first to get that working, so I was very excited about that.

And the second one I wanted to show you is this really amazing work from @sebderhy, Sebastian, who did something that I've been thinking about as well.

I'm really thrilled that he also thought about this, which was he noticed that this update we do, unconditional embeddings plus guidance times text embeddings minus unconditional embeddings [u + g * (t - u)], has a bit of a problem, which is that it gets big.

To show you what I mean by it gets big is like, imagine that we've got a couple of vectors on this chart here. And so we've got, let's see, so we've got, let's just, okay, so we've got the original unconditional piece here, so we've got u.

So let's say this is u. Okay. And then we add to that some amount of t minus u. So if we've got like t, let's say it's huge, right? And we've got u again. Then the difference between those is the vector which goes here, right? Now you can see here that if there's a big difference between t and u, then the eventual update which actually happens is, oopsie-daisy, I thought that was going to be an arrow. Let's try that again. The eventual update which happens is far bigger than the original update. And so it jumps too far.

So this idea is basically to say, well, let's make it so that the update is no longer than the original unconditioned update would have been. And we're going to be talking more about norms later, but basically we scale it by the ratio of the norms.

And what happens is we start with this astronaut and we move to this astronaut. And it's a subtle change, but you can see there's a lot more before, after, before, after, a lot more texture in the background.

And like on the Earth, there's a lot more detail before, after.

You see that? And even little things like before, the bridal kind of rains, whatever, were pretty flimsy. Now they look quite proper.

So it's made quite a big difference just to kind of get this scaling correct.

So there's a couple of other things that Sebastian tried, which I'll explain in a moment, but you can see how some of them actually resulted in changing the image.

And this one's actually important because the poor horse used to be missing a leg and now it's not missing a leg, so that's good. And so here's the detailed one with its extra leg.

So how did he do this? Well, so what he did was he started with this unconditioned prompt plus the guidance times the difference between the conditional and unconditioned.

And then as we discussed, the next version, well actually the next version we then saw is to basically just take that prediction and scale it according to the difference in the lengths.

So the norms is basically the length of the vectors. And so this is the second one I did in Lesson 9. You'll see it's gone from here.

So when we go from 1a to 1b, you can see here it's got, look at this, this boot's gone from nothing to having texture, this or whatever the hell this thing is, suddenly he's got texture and look, we've now got proper stars in the sky. It's made a really big difference. And then the second change is not just to rescale the whole prediction, but to rescale the update.

And when we rescale the update, it actually not surprisingly changes the image entirely because we're now changing the direction it goes. And so, I don't know, is this better than this? I mean, maybe, maybe not, but you know, I think so, you know, particularly because this was the difference that added the correct fourth leg to the horse before.

And then we can do both. We can rescale the difference and then rescale the result. And then we get the best of both worlds.

As you can see, big difference. We get a nice background. This weird thing on his back's actually become an arm.

That's not what a foot looks like. That is what a foot looks like. So these little details make a big difference, as you can see.

So this is a really cool, or two really cool new things.

New things tend to have wrinkles though. Wrinkle number one is after I shared on Twitter, Sebastian's approach, Ben Poole, who's a Google Brain, I think, if I remember correctly, pointed out that this already exists. He thinks it's the same as what's shown in this paper, which is a diffusion model for text to speech.

I haven't read the paper yet to check whether it's got all the different options or whether it's checked them all out like this. So maybe this is reinventing something that already existed and putting it into a new field, which would still be interesting.

Anyway, so hopefully, folks on the forum, you can help figure out whether this paper's actually showing the same thing or not. And then the other interesting thing was John Robinson got back in touch on the forum and said, oh, actually, that tree video doesn't actually do what we think it does at all. There's a bug in his code. And despite the bug, it accidentally worked really well.

So now we're in this interesting question of trying to figure out like, oh, how did he create such a beautiful video by mistake? OK, so reverse engineering exactly what the bug did and then figuring out how to do that more intentionally. And this is great, right? It's really good to having a lot of people working on something. And the bugs often, yeah, they tell us about new ideas. So that's very interesting.

So watch this space where we find out what John actually did and how come it worked so well.

And then something that I just saw like two hours ago on the forum, which I'd never thought of before, but I'd thought of something a little bit similar.

Rekil Prashanth said, well, what if we took this? So as you can see, all the students are really bouncing ideas of each other. It's like, oh, it's interesting. We're doing different things with a guidance scale.

What if we take the guidance scale and rather than keeping it at 7.5 all the time, let's reduce it.

And this is a little bit similar to something I suggested to Johno a few weeks ago where I said —he was doing some stuff with like modifying gradients based on additional loss functions.

And I said to him, maybe you should just use them like occasionally at the start, because I think the key thing is once the model kind of knows roughly what image it's trying to draw, even if it's noisy, you know, you can let it do its thing. And this is exactly what's happening here is Rekil's idea is to say, well, let's decrease the guidance scale. So at the end, it's basically zero. And so once it kind of is going in the right direction, we let it do its thing.

So this little doggy is with the normal 7.5 guidance scale.

Now have a look, for example, its eye here. It's pretty disin- uninteresting, pretty flat.

And if I go to the next one, as you can see now, actually look at the eye, that's a proper eye.

Before, totally glassy black. Now proper eye. Or like look at all this fur, very textured, previously very out of focus.

So this is, again, a new technique. So I love this, you know, you folks are trying things out, and some things are working and some things not working. And that's all good. I kind of feel like you're going to have to slow down because I'm having trouble keeping up with you all. But apart from that, this is great. Good work.

I also wanted to mention on a different theme to check out Alex's notes on the lesson, because I thought he's done a fantastic job of showing like how to study, how to study a lesson. And so what Alex did, for example, was he made a list in his notes of all the different steps we did as we started the From the Foundations.

What is the library that it comes from, links to the documentation.

And I know that Alex's background actually is history, you know, not computer science.

And so, you know, for somebody moving into a different field like this, this is a great idea, you know, particularly to be able to like look at like, okay, what are all the things that I'm going to have to learn and read about? And then he did something which we always recommend, which is to try the lesson on a new data set. And he very sensibly picked out the Fashion MNIST data set, which is something we'll be using a lot in this course, because it's a lot like MNIST.

And it's just different enough to be interesting. And so he described in his post or his notes, how he went about doing that. And then something else I thought was interesting in his notes at the very end was he just jotted down my tips.

It's very easy when I throw a tip out there to think, oh, that's interesting, that's good to know. And then it can disappear. So here's a good way to make sure you don't forget about all the little tricks.

And I think I've put those notes in the forum wiki, so you can check them out if you'd like to learn from them as well. So I think this is a great role model. Good job, Alex. Okay, so during the week, Johno taught us about a new paper that had just come out called DiffEdit, and he told us he thought this was an interesting paper. And it came out during the week, and I thought it might be good practice for us to try reading this paper together.

So let's do that. So here's the paper, DiffEdit. And you'll find that

Workflow on reading an academic paper

probably the majority of papers that you come across in deep learning will take you to arXiv.

arXiv is a preprint server. So these are models, these are papers that have not been peer reviewed. I would say in our field, we don't generally or I certainly don't generally care about that at all, because we have code, we can try it, we can see things, whether it works or not. You know, we tend to be very, you know, most papers are very transparent about here's what we did and how we did it, and you can replicate it.

And it gets a huge amount of peer review on Twitter. So if there's a problem, generally within 24 hours, somebody has pointed it out.

So we use arXiv a lot. And if you wait until it's been peer reviewed, you know, you'll be way out of date because this field is moving so quickly.

So here it is on arXiv, and we can read it by clicking on the PDF button.

I don't do that. Instead I click on this little button up here, which is the save to Zotero button. So I figured I'd show you like my preferred workflows. You don't have to do the same thing.

There are different workflows, but here's one that I find works very well, which is Zotero is a piece of free software that you can download for Mac, Windows, Linux, and install a Chrome connector.

Oh, Tanishq is saying the button's covered. All right. So in my taskbar, I have a button that I can click that says, save to Zotero, sorry, not taskbar, Chrome menu bar. And when I click it, I'll show you what happens. So after I've downloaded this, the paper will automatically appear here in this software, which is Zotero. And so here it is, DiffEdit.

And you can see it's told us, it's got here, the abstract, the authors, where it came from.

And so later on, I can go and like, if I want to check some detail, I can go back and see the URL. I can click on it, pops up. And so in this case, what I'm going to do is I'm going to double click on it. And that brings up the paper.

Now the reason I like to read my papers in Zotero is that I can annotate them, edit them, tag them, put them in folders and so forth, and also add them to my kind of reading list directly from my web browser. So as you can see, I've started this fast diffusion folder, which is actually a group library, which I share with the other folks working on this fast diffusion project that we're all doing together. And so we can all see the same paper library. So @mariboo on YouTube chat is asking, is this better than Mendeley? Yeah, I used to use Mendeley and it's kind of gone downhill.

I think Zotero is far, far better, but they're both very similar.

Okay, so we double click on it. It opens up and here is a paper.

Read DiffEdit paper

So reading a paper is always extremely intimidating.

And so you just have to do it anyway. And you have to realize that your goal is not to understand every word. Your goal is to understand the basic idea well enough that, for example, when you look at the code, hopefully it comes with code, most things do, that you'll be able to kind of see how the code matches to it and that you could try writing your own code to implement parts of it yourself. So over on the left, you can open up the sidebar here.

So I generally open up the table of contents and get a bit of a sense of, okay, so there's some experimental results. There's some theoretical results.

Introduction related work, okay, tells us about this new DiffEdit thing, some experiments.

Okay. So it's a pretty standard approach that you would see in papers. So I would always start with the abstract.

Okay, so what's it saying this does? So generally it's going to be some background sentence or two about how interesting this field is. It's just saying, well, image generation is cool, which is fine. And then they're going to tell us what they're going to do, which is they're going to create something called DiffEdit.

And so this is a, what is it for? It's going to use text condition diffusion models. So we know what those are now. That's what we've been using.

That's where we type in some text and get back an image of that, that matches the text, but this is going to be different. It's the task of semantic image editing. Okay. We don't know what that is yet.

So let's put that aside and think, okay, let's make sure we understand that later. The goal is to edit an image based on a text query.

Oh, okay. So we're going to edit an image based on text. How on earth would you do that? Ah, they're going to tell us right away what this is.

Semantic image editing. It's an extension of image generation with an additional constraint, which is the generated image should be as similar as possible to the given input. And so generally, as they've done here, there's going to be a picture that shows us what's going on.

And so in this picture, you can see here, an example, here's an input image.

And originally it was attached to a caption, a bowl of fruits.

Okay. So we want to change this into a bowl of pears. So we type a bowl of pears and it generates, Oh, a bowl of pears, or we could change it from a bowl of fruit to a basket of fruits and, Oh, it's become a basket of fruits. Okay. So I think I get the idea, right?

What it's saying is that we can edit an image by typing what we want that image to represent.

So this actually looks a lot like the paper that we looked at last week.

So that's cool. So the abstract says that currently, so I guess there are current ways of doing this, but they require you to provide a mask. That means you have to basically draw the area you're replacing. Okay.

So that sounds really annoying, but our main contribution. So what this paper does is we automatically generate the mask.

So they simply just type in the new query and get the new image. So that sounds actually really impressive. So if you read the abstract and you think, I don't care about doing that, then you can skip the paper, you know, or, or look at the results and if the results don't look impressive, then just skip the paper. So that's, that's kind of your first point where we can be like, okay, we're done.

But in this case, this sounds great. The results look amazing. So I think we should keep going.

Okay. "achieves state-of-the-art editing performance, of course. Fine. Let me try some, right, whatever. Okay.

So the introduction to a paper is going to try to give you a sense of, you know, what they're trying to do. And so this first paragraph here is just repeating what we've already read in the abstract and repeating what we see in figure one. So saying that we can take a text query, like a basket of fruits, see the examples.

All right, fine. We'll skip through there. So key thing about academic papers is that they are full of citations.

You should not expect to read all of them because if you do, then to read each of those citations, that's full of citations and then they're full of citations.

And before you know it, you've read the entire academic literature, which has taken you 5,000 years. So for now, let's just recognize that it says text conditional image generations undergoing revolution. Here's some examples. Well, fine. We actually already know that. Okay.

DALL-E is cool. Latent Diffusion. That's what we've been using. That's cool. Imagen, apparently that's cool. So cool.

All right. So we kind of know that. So generally there's this like, okay, our area that we're working on is important. And in this case, we already agree it's important so we can skip through it pretty quickly.

There're vast, vast amounts of data are used. Yes, we know.

Okay. So diffusion models are interesting. Yes, we know that they de-noise starting from Gaussian noise.

We know that. So you can see like there's a lot of stuff once you kind of in the field, you can skip over pretty quickly.

You can guide it using CLIP guidance. Yeah. That's what we've been doing. We know about that. Oh, wait, this is new. Or by inpainting, by copy pasting pixel values outside a mask. All right. So there's a new technique that we haven't done, but I think it makes a lot of intuitive sense that is during that diffusion process. If there are some pixels, you don't want to change such as all the ones that aren't orange here, you can just paste them from the original after each stage of the diffusion. All right. That makes perfect sense. If I want to know more about that, I could always look at this paper, but I don't think I do for now.

Okay. And again, it's just repeating something they've already told us that they're they require us to provide a mask. So that's a bit of a problem.

And then, you know, this is interesting. It's also says that when you mask out an area that's a problem because if you're trying to, for example, change a dog into a cat, you want to keep the animal's color and pose. So this is a new technique, which is not deleting the original, not deleting a section and replacing it with something else, but it's actually going to take advantage of knowledge about what that thing looked like.

So that, this is two cool new things. So hopefully at this point, we know what they're trying to achieve. If you don't know what they're trying to achieve when you're reading a paper, the paper won't make any sense.

So again, that's a point where you should stop. Maybe this is not the right time to be reading this paper. Maybe you need to read some of the references.

Maybe you need to look more at the examples so you can always skip straight to the experiments.

So I often skip straight to the experiments. In this case, I don't need to because they've put enough experiments on the very first page for me to see what it's doing. So yeah, don't always read it from top to bottom. Okay, so.

All right, so they've got some examples of conditioning a diffusion model on an input without a mask. Okay.

For example, you can use a noise version of the input as a starting point. Hey, we've done that too. So as you can see, we've already covered a lot of the techniques that they're referring to here. Something we haven't done, but makes a lot of sense is that we can look at the distance to the input image as a loss function. Okay. So that makes sense to me and there's some references here. All right. So we're going to create this new thing called DiffEdit. It's going to be amazing. Wait till you check it out. Okay, fine.

Okay. So that's the introduction. Hopefully you found that useful to understand what we're trying to do.

The next section is generally called related work as it is here, and that's going to tell us about other approaches.

So if you're doing a deep dive, this is a good thing to study carefully.

I don't think we're going to do a deep dive right now. So I think we can happily skip over it. We could kind of do a quick glance of like, oh, image editing, conclude colorization, retouching style transfer.

Okay, cool. Lots of interesting topics. Definitely getting more excited about this idea of image editing.

And there's some different techniques. You can use CLIP guidance. Okay.

They can be computationally expensive. We can use diffusion for image editing.

Okay, fine. We can use CLIP to help us. So there's a lot of repetition in these papers as well, which is nice because we can skip over it pretty quickly. More about the high computational costs.

Okay. So they're saying this is going to be not so computationally expensive. That sounds hopeful.

And often the very end of the related work is most interesting as it is here where they've talked about how somebody else has done "concurrent to ours". Somebody else is working at exactly the same time and they've looked at some different approach.

Okay. So not sure we learned too much from the related work, but if you were trying to really do the very, very best possible thing, you could study the related work and get the best ideas from each.

Okay. Now, background. So this is where it starts to look scary.

Understanding the equations in the "Background" section

And this is often the scariest bit, the background. This is basically saying like mathematically, here's how the problem that we're trying to solve is set up. And so we're going to start by looking at denoising diffusion probabilistic models, DDPM. Now, if you've watched Lesson 9B with Wasim and Tanishq, then you've already seen some of the math of DDPM.

And the important thing to recognize is that basically no one in the world pretty much is going to look at these paragraphs of text and these equations and go, oh, I get it.

That's what DDPM is. That's not how it works, right?

To understand DDPM, you would have to read and study the original paper, and then you would have to read and study the papers it's based on and talk to lots of people and watch videos and go to classes just like this one. And after a while, you'll understand DDPM.

And then you'll be able to look at this section and say, oh, okay, I see.

They're just talking about this thing I'm already familiar with. So this is meant to be a reminder of something that you already know.

It's not something you should expect to learn from scratch. So let me take you through these equations somewhat briefly because Wasim and Tanishq have kind of done them already, because every diffusion paper pretty much is going to have these equations. Okay. So, oh, and I'm just going to read something that Johno's pointed out in the chat.

He says, it's worth remembering the background is often written last and tries to look smart for the reviewers, which is correct. So feel free to read it last too.

Yeah, absolutely. I think the main reason to read it is to find out what the different letters mean, what the different symbols mean, because they'll probably refer to them later. But in this case, I want to actually take this as a way to learn how to read math. So let's start with this very first equation, which, how on earth do you even read this? So the first thing I'll say is that this is not an e, right? It's a weird looking e. And the reason it's a weird looking e is because it's a Greek letter. And so something I always recommend to students is that you learn the Greek alphabet because it's much easier to be able to actually read this to yourself.

So here's another one, right? If you don't know, that's called theta. I guess you have to read it as like circle with line through it.

It's just going to get confusing trying to read an equation where you just can't actually say it out loud. So what I suggest is that you learn that, learn the Greek alphabet and let me find the right place.

So it's very easy to look it up just on Wikipedia is the Greek alphabet.

But if we go down here, you'll see they've all got names and we can go and try and find our one curvy e. Okay, here it is. Epsilon and oh, circle with a line through it.

Theta. All right. So practice and you will get used to recognizing these. So you've got epsilon theta.

This is just a weird curly L. So that's, this is used for the loss function.

Okay. So how do we find out what this symbol means and what this symbol means? Well, what we can do is there's a few ways to do it.

One way, which is kind of cool is we can use a program called MathPix which, MathPix.

Here we are, MathPix. And what it does is you basically select anything on your screen and it will turn it into LaTeX.

So that's one way you can do this is you can select on the screen, it turns it into LaTeX. And the reason it's good to turn it into LaTeX is because LaTeX is written as actual stuff that you can search for on Google. So that's technique number one.

Technique number two is you can download the other formats of the paper and that'll have a download source. And if we say download source, then what we'll be able to do is we'll be to actually open up that LaTeX and have a look at it.

So we'll wait for that to download while that's happening. Let's keep moving along here. So in this case, we've got these two bars.

So can we find out what that means? So we could try a few things.

We could try looking for two bars ("||"), maybe math notation.

Oh, here we are. Looks hopeful. What does this mean in mathematics? Oh, and here there's a glossary of mathematical symbols.

Here there's a meaning of this in math.

So that looks hopeful. Okay. So it definitely doesn't look like this. It's not between two sets of letters.

Ah, but it is around something that looks hopeful. So it looks like we found it.

It's a vector norm. Okay. So then you can start looking for these things up. So we can say norm or maybe vector norm.

And so once you can actually find the term, then we kind of know what to look for.

Okay. So in our case, we've got this surrounding all this stuff.

And then there's twos here and here. What's going on here? All right.

If we scroll through. Oh, this is pretty close actually.

So okay. So two bars can mean a matrix norm, otherwise a single for a vector norm.

That's just here in particular. So it looks like we don't have to worry too much about whether it's one or two bars. Oh, and here's the definition.

Oh, that's handy. So we've got the two one. All right. So it's equal to root sum of squares.

So that's good to know. So this norm thing means a root sum of squares.

But then we've got a two up here. Well, that just means squared. Ah, so this is a root sum of squares squared.

Well, the square of a square root is just the thing itself. Ah, so actually this whole thing is just the sum of squares.

It's a bit of a weird way to write it in a sense. You could perfectly well have just written it as, you know, like sum of, you know, whatever it is, squared.

Fine. But there we go.

Okay. And then what about this thing here? Weird E thing. So how would you find out what the weird E thing is? Okay, so our LaTeX has finally finished downloading.

And if we open it up, we can find there's a dot tex file in here. Here we are, main.tex. So we'll open it.

And it's not the most, you know, amazingly smooth process, but you know, what we could just do is we could say, okay, it's just after it says, minimizing the de-noising objective. Okay.

So let's search for minimizing the de- oh, here it is, minimizing the de-noising objective.

So the LaTeX here, let's get it both on the screen at the same time.

Okay. So here it is. L mathcal{L} = mathbb{E} x naught t epsilon. Okay.

And here's that vertical bar thing, epsilon minus epsilon theta x_t, and then the bar thing two two.

All right. So the thing that we've got new is mathbb{E}. Okay. So finally, we've got something we can search for.

mathbb{E}. Ah, fantastic. What does mathbb{E} mean? That's the expected value operator.

Aha, fantastic. All right. So it takes a bit of fussing around, but once you've got either Mathpix working or actually another thing you could try, because Mathpix is ridiculously expensive in my opinion, is there is a free version called pix2tex that actually is a Python thing.

And you could actually even have fun playing with this because the whole thing is just a PyTorch Python script. And it even describes, you know, how if you used a transformers model and you can train it yourself in Colab and so forth.

But basically, as you can see, yeah, you can snip and convert to LaTeX, which is pretty awesome.

So you could use this instead of paying the Mathpix guys.

Anyway, so we are on the right track now, I think. So expected value.

And then we can start reading about what expected value is, and you might actually remember that because we did a bit of it in high school, at least in Australia we did.

It's basically like, let's maybe jump over here.

So expected value of something is saying, what's the likely value of that thing? So for example, let's say you toss a coin, which could be heads or it could be tails. And you want to know how often it's heads. And so maybe we'll call heads one, tails zero.

So you toss it and you get a one, zero, zero, one, one, zero, one, zero, one.

Okay. And so forth. Right. And then you can calculate the mean of that.

Right. So if that's X, you can calculate X bar the mean, which would be the sum of all that divided by the count of all that.

So it'd be one, two, three, four, five, five divided by one, two, three, four, five, six, seven, eight, nine. Okay. So that would be the mean. But the expected value is like, well, what do you expect to happen? And we can calculate that by adding up for all of the possibilities for each, I don't know what it's called them, X, for each possibility X. How likely is X and what score do you get if you get X? So in this example of heads and tails, our two possibilities is that we either get heads or we get tails. So if for the version where X is heads, we get probability is 0.5 and the score, if it's an X, I guess I should use that, the score if it's an X is going to be one. And then what about tails? The tails, the probability is 0.5 and the score, if you get tails is zero.

And so overall the expected is 0.5 times one plus zero is 0.5.

So our expected score, if we're tossing a coin is 0.5, if getting heads is a win.

Let me give you another example. Another example is let's say that we're rolling a die and we want to know what the expected score is if we roll a die.

So again, we could roll it a bunch of times and see what happens.

And so we could sum all that up, (as) before and divide it by the count. And that'll tell us the mean for this particular example, but what's the expected value more generally? Well, again, it's the sum of all the possibilities of the probability of each possibility times that score.

So the possibilities for rolling a die is that you can get a one, a two, a three, a four, a five or a six. The probability of each one is a sixth.

Okay. And the score that you get is, well, it's this, this is the score. And so then you can multiply all these together and sum them up, which would be one sixth plus two sixths plus three sixths plus four sixths plus five sixths plus six sixths. And that would give you the expected value of that particular thing, which is rolling die, rolling, rolling a die.

So that's what expected value means. All right. So that's a really important concept that's going to come up a lot as we read papers.

And so in particular, this is telling us what are all the things that we're averaging it over that was the expectations over. And so there's a whole lot of letters here.

You're not expected to just know what they are. In fact, in every paper, they could mean totally different things. So you have to look immediately underneath where they'll be defined.

So X0 is an image. It's an input image.

Epsilon is the noise and the noise has a mean of 0 and a standard deviation of I, which if you watch the Lesson 9B you'll know it's like a standard deviation of one when you're doing multiple normal variables. Okay. And then this is kind of confusing. Eta just on its own is a normally distributed random variables. It's just grabbing random numbers, but Eta-the… sorry, psilon, but Epsilon-heta is a noise estimator.

That means it's a function. You can tell it's a function kind of, cause it's got these parentheses and stuff right next to it. So that's a function.

So presumably most functions like this in these papers are neural networks.

Okay. So we're finally at a point where this actually is going to make perfect sense. We've got the noise.

We've got the prediction of that noise. We subtract one from the other.

We square it and we take the expected value. So in other words, this is mean squared error.

So wow, that's a lot of fiddling around to find out that we've, this whole thing here means mean squared error. So the loss function is the mean squared error.

And unfortunately I don't think the paper ever says that it says minimizing the de-noising objective L bladi bladi bladi. But anyway, we got there eventually.

Fine. We also, as well as learning about X0, we also learn here about Xt. And so Xt is the original unnoised image times some number plus some noise times one minus that number.

Okay. And so hopefully you'll recognize this from Lesson 9B. This is the thing where we reduce the value of each pixel and we add noise to each pixel. So that's that.

All right. So I'm not going to keep going through it, but you can kind of basically get the idea here is that once you know what you're looking for, the equations do actually make sense. But all this is doing is, remember, this is background, right? This is telling you what already exists. So this is telling you, this is what a DDPM is. And then it tells you what a DDIM is.

DDIM is, look, just think of it as a more recent version of DDPM. It's some very minor changes to the way it's set up, which allows us to go faster.

Okay. So the thing is though, once we keep reading, what you'll find is none of this background actually matters.

But, you know, I thought we'd kind of go through it just to get a sense of like, what's in a paper.

Okay. So for the purpose of our background, it's enough to know that DDPM and DDIM are kind of the foundational papers on which diffusion models today are based.

Okay.

So the encoding process, which encodes an image onto a latent variable.

Okay. And then this is basically adding noise. This is called DDIM encoding.

And the thing that goes from the input image to the noise image, they're going to call capital Er.

And r is the encoding ratios. That's going to be something like how much noise are we adding.

If you use small steps, then decoding that. So going backwards gives you back the original image. Okay. So that's all the stuff that we've learned about. That's what diffusion models are.

All right. So this looks like a very useful picture.

3 steps of DiffEdit

So maybe let's take a look and see what this says. So what is DiffEdit? DiffEdit has three steps.

Step one. We add noise to the input image. That sounds pretty normal. Here's our input image X0.

Okay. And we add noise to it. Fine. And then we denoise it.

Okay. Fine. Ah, but we denoise it twice. One time we denoise it using the reference text R horse. Well this special symbol here means nothing at all. So either unconditional or horse. All right. So we do it once using the word horse.

So we take this and we decode it, estimate the noise, and then we can remove that noise on the assumption that it's a horse. Then we do it again.

The second time we do that noise, when we calculate the noise, we pass in our query Q, which is zebra. Wow. Those are going to be very different noises. The noise for horse is just going to be literally these Gaussian pixels. These are all dots, right? Because it is a horse. But if the claim is no, no, this is actually a zebra, then all of these pixels here are all wrong. They're all the wrong color. So the noise that's calculated, if we say this is our query, it's going to be totally different to the noise if we say this is our query. And so then we just take one minus the other, and here it is here. So "we derive a mask based on the difference in the denoising results". And then you take that and binarize it.

So basically turn that into ones and zeros. So that's actually the key idea.

That's a really cool idea, which is that once you have a diffusion model that's trained, you can do inference on it where you tell it the truth about what the thing is, and then you can do it again, but lie about what the thing is. And in your lying version, it's going to say, okay, all the stuff that doesn't match zebra must be noise. And so the difference between the noise prediction when you say, hey, it's a zebra versus the noise prediction when you say, hey, it's a horse will be all the pixels that it says, no, these pixels are not zebra. The rest of it, it's fine. There's nothing particularly about the background that wouldn't work with a zebra.

Okay, so that's step one. So then step two is we take the horse and we add noise to it. Okay, that's this Xr thing that we learned about before. And then step three, we do "decoding conditioned on the text query" using the mask to replace the background with pixel values.

So this is like the idea that we heard about before, which is that during the inference time, as you do diffusion from this fuzzy horse, what happens is that we do a step of diffusion inference, and then all these black pixels, we replace with the noise version of the original.

And so we do that multiple times. And so that means that the original pixels in this black area won't get changed. And that's why you can see in this picture here, and this picture here, the backgrounds all the same. And the only thing that's changed is that the horse has been turned into a zebra.

So this paragraph describes it. And then you can see here, it gives you in a lot more detail. And the detail often has all kinds of like little tips about things they tried and things they found, which is pretty cool.

So I won't read through all that because it says the same as what I've already just said. One of the interesting little things they note here actually is that this binarized mask, so this difference between the R decoding and the Q decoding tends to be a bit bigger than the actual area where the horse is, which you can kind of see with these legs, for example. And their point is that they actually say that's a good thing because actually often you want to slightly change some of the details around the object.

So this is actually fine. All right. So we have a description of what the thing is. Lots of details there.

And then here's the bit that I totally skip, the bit called theoretical analysis, where this is the stuff that people really generally just add to try to get their papers past review. You have to have fancy math. And so they're basically proving, you can see what it says here, insight into why this component yields better editing results than other approaches. I'm not sure we particularly care because like it makes perfect sense what they're doing. It's intuitive and we can see it works. I don't feel like I need it proven to me, so I skip over that.

Homework

So then they'll show us their experiments to tell us what data sets they did the experiments on.

And so then, you know, they have metrics with names like LPIPS and CSFID.

You'll come across FID a lot. This is just a version of that. We're basically, they're trying to score how good their generated images.

We don't normally care about that either. They care because they need to be able to say, you should publish our paper because it has a higher number than the other people that have worked on this area. In our case, we can just say, you know, it looks good. I like it.

So excellent question in the chat from Mikołaj, which is, so with this only work on things that are relatively similar. And I think this is a great point, right? This is where understanding this helps to know what its limitations are going to be.

And that's exactly right. If you can't come up with a mask for the change you want, this isn't going to work very well on the whole.

Yeah. Because those, the masked areas, the pixel is going to be copied. So for example, if you wanted to change it from, you know, a bowl of fruits to a bowl of fruits with a bokeh background, or like a bowl of fruits with, you know, with a purple tinged photo of a bowl of fruit, if you want the whole color to change, that's not going to work, right? Because you're not masking off an area. Yeah. So by understanding the detail here, Mikołaj has correctly recognized a limitation or like, what's this for? This is for things where you can just say, just change this bit and leave everything else the same.

All right. So there's lots of experiments. So yeah. For some things that you care about the experiments a lot, if it's something like classification for stuff for generation, the main thing you probably want to look at is the actual results. And so, and often for whatever reason, I guess, because this is most people read these electronically, the results often you have to zoom into a lot to be able to see whether they're really good.

So here's the input image. They want to turn this into an English Foxhound.

So here's the thing they're comparing themselves to SDEdit and change the composition quite a lot and their version, it hasn't changed it at all. It's only changed the dog. And ditto here, semi-trailer truck, SDEdits totally changed it and DifFdit hasn't. So you can kind of get a sense of like, you know, the authors showing off what they're good at here. This is what this technique is effective at doing, changing animals and vehicles and so forth. It does a very good job of it.

All right. So then there's going to be a conclusion at the end, which I find almost never adds anything on top of what we've already read. And as you can see, it's very short anyway.

Now quite often the appendices are really interesting. So don't skip over them. Often you'll find like more examples of pictures.

They might show you some examples of pictures that didn't work very well, stuff like that. So it's often well worth looking at the appendices.

Often some of the most interesting examples are there. And that's it. So that is, I guess our first full on paper walkthrough. And it's important to remember this is not like a carefully chosen paper that we've picked specifically because you can handle it.

Like this is the most interesting paper that came out this week. And so, you know, it gives you a sense of what it's really like.

And for those of you who are ready to try something that's going to stretch you, see if you can implement any of this paper. So there are three steps.

The first step is kind of the most interesting one, which is to generate, automatically generate a mask.

And the information that you have and the code that's in the Lesson 9 notebook actually contains everything you need to do it. So maybe give it a go. Maybe if you can mask out the area of a horse that does not look like a zebra.

And that's actually useful in itself. Like that allows you to create segmentation masks automatically. So that's pretty cool. And then if you get that working, then you can go and try and do step two.

If you get that working, you can try and do step three. And this only came out this week. So I haven't really seen examples of easy to use interfaces to this. So here's an example of a paper that you could be the first person to create a call interface to it.

So there's some, yeah, there's a fun little project. And even if you're watching this a long time after this was released and everybody's been doing this for years, still good homework, I think, to practice if you can.

All right, I think now's a good time to have a 10 minute break.

So I'll see you all back here in 10 minutes.

Okay, welcome back. One thing during the break that Diego reminded us about, which I normally describe and I totally forgot about this time is Detexify, which is another really great way to find symbols you don't know about.

So let's try it for that expectation. So if you've got a Detexify and you draw the thing, it doesn't always work fantastically well, but sometimes it works very nicely.

Yeah, in this case, not quite. What about the double line thing?

It's good to know all the techniques, I guess.

I think it could do this one. I guess part of the problem is there's so many options that actually, you know, okay, in this case, it wasn't particularly helpful.

Normally it's more helpful than that. I mean, if we use a simple one like Epsilon, I think it should be fine.

There's a lot of room to improve this app actually, if anybody's interested in a project. I think you could make it, you know, more successful.

Okay, there you go. Sigma sum, that's cool. Anyway, so it's another useful thing to know about just Google for Detexify.

Okay, so let's move on with our From the Foundations now.

And so we were working on trying to at least get the start of a forward pass of a linear model or a simple multi-layer perceptron for MNIST going.

And we had successfully created a basic tensor. We've got some random numbers going.

Matrix multiplication from scratch

So what we now need to do is we now need to be able to multiply these things together, matrix multiplication. So matrix multiplication, to remind you, in this case, so we're doing MNIST, right? So we've got, I think we're going to use a subset. Let's see. Yeah. Okay. So we're going to create a matrix called m1, which is just the first five digits.

So m1 will be the first five digits.

So five rows and dot, dot, dot; dot, dot, dot. and then 780, what was it again? 784 columns, 784 columns, because it's 28 by 28 pixels and we flattened it out.

So this is our first matrix and our matrix multiplication. And then we're going to multiply that by some weights.

So the weights are going to be 784 by 10 random numbers.

So for every one of these 784 pixels, each one is going to have a weight.

So 784 down here, 784 by 10. So this first column, for example, is going to tell us all the weights in order to figure out if something's a zero.

And the second column will have all the weights in deciding the probability of something's a one and so forth. That's assuming we're just doing a linear model.

And so then we're going to multiply these two matrices together. So when we multiply matrices together, we take row one of matrix one, and we take column one of matrix two, and we take each one in turn.

So we take this one and we take this one, we multiply them together.

And then we take this one and this one, and we multiply them together.

And we do that for every element wise pair, and then we add them all up. And that would give us the value for the very first cell. That would go in here. That's what matrix multiplication is. Okay, so let's go ahead then and create our random numbers for the weights, since we're allowed to use random number generators now. And for the bias, we'll just use a bunch of zeros to start with. So the bias is just what we're going to add to each one. And so for our matrix multiplication, we're going to be doing a little mini batch here. We're going to be doing five rows of, as we discussed, five rows of, so five images flattened out.

And then multiply by this weights matrix.

So here are the shapes. m1 is five by 784, as we saw. m2 is 784 by 10. Okay, so keep those in mind.

So here's a handy thing, m1.shape contains two numbers and I want to pull them out.

I want to call the, I'm going to think of that as, I'm going to actually think of this as like A and B rather than m1 and m2. So this is like A and B. So the number of rows in A and the number of columns in A, if I say equals m1.shape, that will put 5 in ar and 784 in ac. So you'll probably notice this.

I do this a lot, this de-structuring. We talked about it last week too. So we can do the same for m2.shape, put that into B rows (br) and B columns (bc).

And so now if I write out ar, ac and br, bc, you can again see the same things from the sizes.

So that's a good way to kind of give us the stuff we have to loop through. So here's our results. So our resultant tensor, well, we're multiplying together all of these 784 things and adding them up.

So the resultant tensor is going to be 5 by 10.

And then each thing in here is the result of multiplying and adding 784 pairs.

So the result here is going to start with zeros and this is the result.

And it's going to contain ar rows, five rows and bc columns, 10 columns, 5 comma 10. Okay. So we have to fill that in. And so to do a matrix multiplication, we have to first, we have to go through each row one at a time.

And here we have that: go through each row, one at a time, and then go through each column, one at a time. And then we have to go through each pair in that row column one at a time. So there's going to be a loop in a loop in a loop.

So here's going to loop over each row. And here we're going to loop over each column.

And then here we're going to loop —so each column bc. And then here we're going to loop over each column of a, which is going to be the same as the number of rows of b, which we can see here, ac: 784, br: 784, they're the same. So it wouldn't matter whether we said ac or br.

So then our result for that row and that column, we have to add onto it the product of i, k in the first matrix, by k, j in the second matrix. So k is going up through those 784.

And so we're going to go across the columns and down, sorry, across the rows and down the columns.

So across the row, well, as it goes down this column.

So here is the world's most naive, slow, uninteresting matrix multiplication.

And if we run it, okay, it's done something. We have successfully, apparently, hopefully successfully, multiplied the matrices m1 and m2. It's hard to read this, I find, because punch cards used to be 80 columns wide. We still assume screens are 80 columns wide. Everything defaults to 80 wide, which is ridiculous, but you can easily change it.

So if you say set_print_options, you can choose your own line width.

You can see, well, we know that's 5 by 10. We did it before. So if we change the line width, okay, that's much easier to read now.

You can see here are the 5 rows and here are the 10 columns for that matrix multiplication.

I tend to always put this at the top of my notebooks and you can do the same thing for NumPy as well.

So what I like to do, this is really important, is when I'm working on code, particularly numeric code, I like to do it all step by step in Jupyter. And then what I do is once I've got it working is I copy all the cells that have implemented that and I paste them and then I select them all and I hit shift+M to merge, get rid of anything that prints out stuff I don't need.

And then I put a header on the top, give it a function name, and then I select the whole lot and I hit control or Apple right square bracket and I've turned it into a function. But I still keep the stuff above it so I can see all the step by step stuff for learning about it later.

And so that's what I've done here to create this function.

And so this function does exactly the same things we just did. And we can see how long it takes to run by using %time.

And it took about half a second, which gosh, that's a long time to generate such a small matrix. This is just to do five MNIST digits.

So that's not going to be great. We're going to have to speed that up.

I'm actually quite surprised at how slow that is because there's only 39,200.

So if you look at how we've got a loop within a loop within a loop, a loop within a loop within a loop, it's doing 39,200 of these. So Python, yeah, Python, when you're just doing Python, it is slow. So we can't do that. That's why we can't just write Python. But there is something that kind of

Speed improvement with Numba library

lets us write Python. We could instead use Numba.

Numba is a system that takes Python and turns it into basically into machine code.

And it's amazingly easy to do. You can basically take a function and write njit, @njit on top. And what it's going to do is it's going to look at —the first time you call this function, it's going to compile it down to machine code and it will run much more quickly. So what I've done here is I've taken the innermost loop. So just looping through and adding up all these.

So start at zero, go through and add up all those just for two vectors and return it.

This is called a dot product in linear algebra. So we'll call it dot.

And so Numba only works with NumPy, doesn't work with PyTorch. So we're just going to use arrays instead of tensors for a moment.

Now have a look at this. If I try to do a dot product of 1, 2, 3 and 2, 3, 4, it's pretty easy to do.

It took a fifth of a second, which sounds terrible. But the reason it took a fifth of a second is because that's actually how long it took to compile this and run it. Now that it's compiled, the second time, it just has to call it. It's now 21 microseconds. And so that's actually very fast. So with Numba, we can basically make Python run at C speed. So now the important thing to recognize is if I replace this loop in Python with a call to dot, which is running in machine code, then we now have one, two loops running in Python, not three.

So our 448 milliseconds. Well, first of all, let's make sure if I run it, run that matmul, it should be close to my t1. t1 is what we got before, remember? So when I'm refactoring or performance improving or whatever, I always like to put every step in the notebook and then test. So this test_close() comes from fastcore.test and it just checks that two things are very similar. They might not be exactly the same because of little floating point differences, which is fine. Okay.

So our matmul is working correctly, or at least it's doing the same thing it did before. So if we now run it, it's taking 268 microseconds, okay, versus 448 milliseconds.

So it's taking about 2,000 times faster just by changing the one innermost loop.

So really all we've done is we've added @njit to make it 2,000 times faster.

So Numba is well worth knowing about. It can make your Python code very, very fast.

Okay. Let's keep making it faster.

So we're going to use stuff again, which kind of goes back to APL.

And a lot of people say that learning APL is a thing that's taught them more about programming than anything else. So it's probably worth considering learning APL.

And let's just look at these various things. We've got a is 10, 6, -4.

So remember at APL, we don't say equals. Equals actually means equals funnily enough. We, to say set to, we use this arrow and it's a, this is a list of 10, 6, 4.

Okay. And then b is 2, 8, 7.

Okay. And we're going to add them up a+b.

So what's going on here? So it's really important that you can think of a symbol like a as representing a tensor or an array. APL calls them arrays, Pytorch calls them tensors, NumPy calls them arrays. They're the same thing. So this is a single thing that contains a bunch of numbers.

This is an operation that applies to arrays or tensors. And what it does is it works what's called element wise.

It takes each pair 10 and 2 and adds them together, each pair 6 and 8, add them together.

This is element wise addition. And Fred's asking in the chat, how do you put, put in these symbols? If you just mouse over any of them, it will show you how to write it.

And the one you want is the one at the very bottom. The very bottom, which is the one where it says prefix.

Now the prefix is the backtick character. So here it's saying prefix hyphen gives us times.

So if I type P hyphen, there we go. So I've got a back tick dash b is a x b for example. So yeah, they all have shortcut keys, which you learn pretty quickly. I find. And there's a fairly consistent kind of system for those shortcut keys too.

All right. So we can do the same thing in PyTorch. It's a little bit more verbose in PyTorch, which is one reason I often like to do my mathematical fiddling around in APL. I can often do it with less boilerplate, which means I can spend more time thinking, you know, I can see everything on the screen at once.

I don't have to spend as much time trying to like ignore the tensor around bracket square bracket dot comma blah, blah, blah. It's all cognitive load, which I'd rather ignore. But anyway, it does the same thing. So I can say a + b and it works exactly like APL.

So here's an interesting example. I can go (a < b).float().mean().

So let's try that one over here. a < b. So this is a really important idea, which I think was invented by Ken Iverson, the APL guy, which is the true and false represented by zero and one. And because they're represented by zero and one, we can do things to them. We can add them up and subtract them and so forth.

It's a really important idea. So in this case, I want to take the mean of them and I'm going to tell you something amazing, which is that in APL, there is no function called mean.

Why not? That's because we can write the mean function, which is… so that's four letters, mean, m-e- a-n. We can write the mean function from scratch with four characters. I'll show you. Here's the whole mean function. We're going to create a function called mean and the mean is equal to the sum of a list divided by the count of a list.

So this here is sum divided by count. And so I have now defined a new function called mean, which calculates the mean, mean of a is less than b. There we go.

And so, you know, in practice, I'm not sure people would even bother defining a function called main because it's just as easy to actually write its implementation in APL.

In NumPy or whatever Python, it's going to take a lot more than four letters to implement mean.

So anyway, it's, you know, it's a math notation. And so being a math notation, we can do a lot with little, which I find helpful because I can see everything going on at once.

Anywho. Okay. So that's how we do the same thing in PyTorch. And again, you can see that the less than in both cases are operating element wise. Okay. So a is less than b is saying 10 is less than 2, 6 is less than 8, 4 is less than 7 and gives us back each of those trues and falses as zeros and ones. And according to the emoji on our YouTube chat, Siva's head just exploded as it should. This is why APL is life changing.

Okay. Let's now go up to higher ranks. So this here is a rank one tensor. So a rank 1 tensor means it's a list of things.

It's a vector. It's where else a rank 2 tensor is like a list of lists. They all have to be the same length lists, or it's like a rectangular bunch of numbers and we call it, in math, we call it a matrix. So this is how we can create a tensor containing 1, 2, 3 4, 5, 6 7, 8, 9.

And you can see often what I like to do is I want to print out the thing I just created after I created it. So two ways to do it.

You can say, put an enter and then write m and that's going to do that. Or if you want to put it all on the same line, that works too.

You just use a semicolon. Neither one's better than the other. They're just different. So we could do the same thing in APL.

Of course, in APL, it's going to be much easier. So we're going to define a matrix called m which is going to be a 3 by 3 tensor containing the numbers from 1 to 9.

Okay and there we go. That's done it in APL. A 3 by 3 tensor containing the numbers from 1 to 9.

A lot of these ideas from APL you'll find have made their way into other programming languages. For example, if you use Go, you might recognize this.

This is the Iota character and Go uses the word Iota.

They spell it out in a somewhat similar way. A lot of these ideas from APL have found themselves into math notation and other languages.

It's been around since the late 50s. Okay so here's a bit of fun.

Frobenius norm

We're going to learn about a new thing that looks kind of crazy called Frobenius norm.

And we'll use that from time to time as we're doing generative modeling. And here's the definition of a Frobenius norm. It's the sum over all of the rows and columns of a matrix. And we're going to take each one and square it.

We're going to add them up and they're going to take the square root. And so to implement that in PyTorch is as simple as going n times m dot sum dot square root.

So this looks like a pretty complicated thing when you kind of look at it at first.

It looks like a lot of squiggly business. Or if you said this thing here, you might be like, what on earth is that? Well now you know it's just square, sum, square root.

So again, we could do the same thing in APL.

So let's do, so in APL we want the, okay, so we're going to create something called sf.

Now it's interesting, APL does this a little bit differently. So dot sum by default in PyTorch sums over everything.

And if you want to sum over just one dimension, you have to pass in a dimension keyword.

For very good reasons APL is the opposite. It just sums across rows or just down columns.

So actually we have to say sum up the flattened out version of the matrix and to say flattened out you use comma.

So here's sum up the flattened out version of the matrix.

Okay so that's our sf, oh sorry, and the matrix is meant to be m times m.

There we go. So there's the same thing. Sum up the flattened out m by m matrix.

And another interesting thing about APL is it always is read right to left. There's no such thing as operator precedence, which makes life a lot easier.

Okay and then we take the square root of that. There isn't a square root function, so we have to do to the power of 0.5.

And there we go, same thing. All right, you get the idea. Yes, so very interesting question here from mariboo.

Are the bars for norm or absolute value, and I like Siva's answer, which is the norm is the same as the absolute value for a scalar. So in this case you can think of it as absolute value and it's kind of not needed because it's being squared anyway.

But yes, in this case the norm, well in every case for a scalar the norm is the absolute value, which is kind of acute discovery when you realize it. So thank you for pointing that out Siva.

All right, so this is just fiddling around a little bit to kind of get a sense of how these things work. So really importantly, you can index into a matrix and you'll say rows first and then columns. And if you say colon, it means all the columns.

So if I say row 2, here it is row 2, all the columns, sorry, this is row 2, so that's 0 —APL starts at 1 or the columns that's going to be 7, 8, 9.

And you can see, I often use comma to print out multiple things and I don't have to say print in, in Jupiter. It's kind of assumed.

And so this is just a quick way of printing out the second row and then here, every row column 2.

So here is every row of column 2. And here you can see 3, 6, 9.

So one thing very useful to recognize is that for tensors of higher rank than 1, such as a matrix, any trailing colons are optional. So you see this here, m[2], that's the same as m[2, :]. It's really important to remember. So m[2], you can see the result is the same. So that means row 2, every column.

So now with all that in place, we've got quite an easy way. We don't need a number anymore.

We can multiply. So we can get rid of that innermost loop. So we're going to get rid of this loop because this is just multiplying together all of the corresponding rows of a with the, sorry, all the corresponding colons of a row of a with all the corresponding rows of a column of b. And so we can just use an element wise operation for that.

So here is the ith row of a, and here is the jth column of b And so those are both, as we've seen, just vectors, and therefore we can do an element wise multiplication of them and then sum them up.

And that's the same as a dot product. So that's handy.

And so again, we'll do test_close. Okay. It's the same. Great. And again, you'll see, we kind of did all of our experimenting first, right? To make sure we understood how it all worked and then put it together. And then if we time it: 661 microseconds. Okay.

So it's interesting. It's actually slower than, which really shows you how good Numba is, but it's certainly a hell of a lot better than our 450 milliseconds.

But we're using something that's kind of a lot more general now.

This is exactly the same as dot as we've discussed. So we could just use torch dot, torch.dot(), I suppose I should say.

And if we run that, okay. Little faster. It's still, interestingly, it's still slower than the Numba, which is quite amazing actually.

All right. So that's… that one was not exactly a speed up, but it's kind of a bit more general, which is nice.

Now we're going to get something into something really fun, which is broadcasting.

Broadcasting with scalars and matrices

And broadcasting is about what if you have arrays with different shapes? So what's a shape? The shape is the number of rows or the number of rows and columns or the number of, what would you say, faces, rows and columns and so forth. So for example, the shape of m is 3 by 3.

So what happens if you multiply or add or do operations to tensors of different shapes?

Well, there's one very simple one, which is if you've got a rank 1 tensor, the vector, then you can use any operation with a scalar and it broadcasts that scalar across the tensor.

So a > 0 is exactly the same as saying a is greater than tensor([0, 0, 0])

So it's basically copying that across three times. Now it's not literally making a copy in memory, but it's acting as if we had said that. And this is the most simple version of broadcasting. Okay.

It's broadcasting the 0 across the 10 and the 6 and the -4 and APL does exactly the same thing.

A < 5, so 0, 0, 1. So it's the same idea.

Okay. So we can do plus with a scalar and we can do exactly the same thing with higher than rank one. So two times a matrix is just going to do: two is going to be broadcast across all the rows and all the columns.

Okay. Now it gets interesting. So broadcasting dates back to APL, but a really interesting idea is that we can broadcast not just scalars, but we can broadcast vectors across matrices or broadcast any kind of lower ranked tensor across higher rank tensors, or even broadcast together two tensors of the same rank, but different shapes and a really powerful way. And as I was exploring this, I was trying to, I love doing this kind of computer archeology. I was trying to find out where the hell this comes from. But it actually turns out from this email message in 1995 that the idea actually comes from a language that I'd never heard of called Yorick, which still apparently exists. Here's Yorick.

And so Yorick has talked about broadcasting and conformability. So what happened is this very obscure language has this very powerful idea and NumPy has happily stolen the idea from Yorick that allows us to broadcast together tensors that don't appear to match. So let me give an example. Here's a tensor called c that's a vector. It's a rank 1 tensor, 10, 20, 30, and here's a tensor called m, which is a matrix. We've seen this one before, and one of them is shape 3 comma 3. The other is shape 3.

And yet we can add them together.

Now, what's happened when we added it together? Well what's happened is 10, 20, 30 got added to 1, 2, 3, and then 10, 20, 30 got added to 4, 5, 6, and then 10, 20, 30 got added to 7, 8, 9. And hopefully you can see this looks quite familiar. Instead of broadcasting a scalar over a higher rank tensor, this is broadcasting a vector across every row of a matrix.

And it works both ways, so we can say c + m gives us exactly the same thing.

And so let me explain what's actually happening here. The trick is to know about this somewhat obscure method called expand_as().

And what expand_as() does is this creates a new thing called t, which contains exactly the same thing as c, but expanded or kind of copied over so it has the same shape as m. So here's what t looks like. Now t contains exactly the same thing as c does, but it's got three copies of it now.

And you can see we can definitely add t to m because they match shapes.

So we can say m plus t, we know we can play m plus t because we've already learned that you can do element wise operations on two things that have matching shapes.

Now by the way, this thing t didn't actually create three copies. Check this out. If we call t dot storage, it tells us what's actually in memory. It actually just contains the numbers 10, 20, 30, but it does a really clever trick. It has a stride of 0 across the rows and a size of 3 comma 3. And so what that means is that it acts as if it's a 3 by 3 matrix. And each time it goes to the next row, it actually stays exactly where it is. And this idea of strides is the trick which NumPy and PyTorch and so forth use for all kinds of things where you basically can create very efficient ways to do things like expanding or to kind of jump over things and stuff like that, switch between columns and rows, stuff like that. Anyway, the important thing here for us to recognize is that we didn't actually make a copy. We made it completely efficient and it's all going to be run in C code very fast. So remember this expand_as is critical. This is the thing that will teach you to understand how broadcasting works, which is really important for implementing deep learning algorithms or any kind of linear algebra on any Python system because the NumPy rules are used exactly the same in JAX, in TensorFlow, in PyTorch and so forth.

Now I'll show you a little trick, which is going to be very important in a moment. If we take c, which remember is a vector containing 10, 20, 30, and we say .unsqueeze(0), then it changes the shape from 3 to 1 comma 3.

So it changes it from a vector of length 3 to a matrix of 1 row by 3 columns.

This will turn out to be very important in a moment. And you can see how it's printed. It's printed out with two square brackets.

Now I never use unsqueeze because I much prefer doing something more flexible, which is if you index into an access with a special value, None, also known as np.newaxis(), it does exactly the same thing. It inserts a new axis here. So here we'll get exactly the same thing, 1 row by all the columns, 3 columns.

So this is exactly the same as saying unsqueeze. So this inserts a new unit axis. This is a unit axis, a single row in this dimension, and this does the same thing. So these are the same.

So we could do the same thing and say, unsqueeze(1), which means now we're going to unsqueeze into the first dimension. So that means we now have 3 rows and 1 column.

See the shape here, the shape is inserting a unit axis in position 1, 3 rows and 1 column.

And so we can do exactly the same thing here. Give us every row and a new unit axis in position 1, same thing. So those two are exactly the same.

So this is how we create a matrix with 1 row. This is how we create a matrix with 1 column.

None comma colon versus colon comma None or unsqueeze.

We don't have to say, as we've learned before, None comma colon, because, do you remember? Trailing colons are optional. So therefore just c[None] is also going to give you a row matrix, 1 row matrix.

This is a little trick here. If you say dot, dot, dot, that means all of the dimensions. And so dot, dot, dot comma None will always insert a unit axis at the end, regardless of what rank a tensor is.

So yeah, so None and np new mean exactly the same thing. np newaxis is actually a synonym for None. If you've ever used that, I always use None because why not? Short and simple. So here's something interesting. If we go c[:, None], so let's go and check out what c[:, None] looks like.

c[:, None] is a column.

And if we say expand as m, which is 3 by 3, then it's going to take that 10, 20, 30 column and replicate it. 10, 20, 30; 10, 20, 30; 10, 20, 30.

So we could add, so remember like, well, remember I will explain that when you say matrix plus c[:, None], it's basically going to do this .expand_as() for you.

So if I want to add this matrix here to m, I don't need to say .expand_as() I just write this, I just write m + c[:, None].

And so this is exactly the same as doing m + c, but now rather than adding the vector to each row, it's adding the vector to each column. So you plus 10, 20, 30; 10, 20, 30; 10, 20, 30.

So that's a really simple way that we now get kind of a free, thanks to this really nifty notation.

There's a nifty approach that came from Yorick. So here you can see m + c[None, :] is adding 10, 20, 30 to each row and m + c[:, None] is adding 10, 20, 30 to each column.

All right, so that's the basic like hand wavy version. So let's look at, like, what are the rules and how does it work?

Okay, so c[None, :] is 1 by 3. c[:, None] is 3 by 1.

What happens if we multiply c[None, :] by c[:, None]? Well it's gonna do, if you think about it, which you definitely should, cause thinking's very helpful.

What is going on here? Oh, took forever.

Okay, so what happens if we go c[None, :] times c[:, None]? So what it's gonna have to do is it's gonna have to take this 10, 20, 30 column vector or 3 by 1 matrix, and it's gonna have to make it work across each of these rows. So what it does is expands it to be 10, 20, 30; 10, 20, 30; 10, 20, 30. So it's gonna do it just like this.

And then it's gonna do the same thing for c[None, :]. So that's gonna become three rows of 10, 20, 30. So we're gonna end up with 3 rows of 10, 20, 30 times 3 columns of 10, 20, 30, which gives us our answer.

And so this is gonna do an outer product. So it's very nifty that you can actually do an outer product without any special functions or anything just using broadcasting.

And it's not just outer products. You can do outer Boolean operations. And this kind of stuff comes up all the time, right? Now remember, you don't need the comma colon, so get rid of it. So this is showing us all the places where it's greater than, it's kind of an outer Boolean, if you wanna call it that.

So this is super nifty and you can do all kinds of tricks with this because it runs very, very fast.

So this is gonna be accelerated in C. So here are the rules.

Broadcasting rules

When you operate on two arrays of tensors, NumPy and PyTorch will compare their shapes.

So remember the shape, this is a shape. You can tell it's a shape because we said shape and it's goes from right to left. So that's the trailing dimensions.

And it checks whether dimensions are compatible. Now they're compatible if they're equal, right? So for example, if we say m * m, then those two shapes are compatible because in each case, it's just gonna be 3, right? So they're gonna be equal. So if the shape in that dimension is equal, they're compatible.

Or if one of them is 1. And if one of them is 1, then that dimension is broadcast to make it the same size as the other.

So that's why the outer product worked. We had a 1 by three times a 3 by 1.

And so this 1 got copied 3 times to make it this long. And this 1 got copied 3 times to make it this long.

Okay, so those are the rules. So the arrays don't have to have the same number of dimensions. So this is an example that comes up all the time.

Let's say you've got a 256 by 256 by 3 array or tensor of RGB values. So you've got an image in other words, a color image.

And you want to normalize it. So you want to scale each color in the image by a different value. So this is how we normalize colors.

So one way is you could multiply or divide or whatever, multiply the image by a 1 dimensional array with 3 values.

So you've got a 1D array. So that's just 3. Okay. And then the image is 256 by 256 by 3.

And we go right to left, and we check are they the same? We say yes, they are.

And then we keep going left and we say are they the same? And if it's missing, we act as if it's one. And if we keep going, if it's missing, we act as if it's one. This is going to be the same as doing 1 by 1 by 3.

And so this is going to be broadcast, these 3 elements will be broadcast over all 256 by 256 pixels. So this is a super fast and convenient and nice way of normalizing image data with a single expression. And this is exactly how we do it in the fastai library, in fact.

Matrix multiplication with broadcasting

So we can use this to dramatically speed up our matrix multiplication.

Let's just grab a single digit, just for simplicity. And I really like doing this in Jupyter Notebooks. And if you build Jupyter Notebooks to explain stuff that you've learned in this course or ways that you can apply it, consider doing this for your readers, but add a lot more prose. I haven't added prose here because I want to use my voice. If I was, for example, in our book that we published, it's all written in notebooks and there's a lot more prose, obviously.

But like really, I like to show every example all along the way using simple as possible.

So let's just grab a single digit. So here's the first digit. So its shape is, it's a 784 long vector. Okay.

And remember that our weight matrix is 784 by 10.

Okay. So if we say digit[:, None] dot shape, then that is a 784 by 1 row matrix. Okay.

So there's our matrix. And so if we then take that 784 by 1 and expand as m2, it's going to be the same shape as our weight matrix.

So it's copied our image data for that digit across all of the 10 vectors representing the 10 kind of linear projections we're doing for our linear model.

And so that means that we can take the digit[:, None]. So 784 by 1 and multiply it by the weights. And so that's going to get us back 784 by 10.

And so what it's doing, remember, is it's basically looping through each of these 10 784 long vectors.

And for each one of them, it's multiplying it by this digit.

So that's exactly what we want to do in our matrix multiplication.

So originally we had, well, not originally, most recently, I should say, we had this dot product where we were actually looping over j, which was the columns of b. So we don't have to do that anymore because we can do it all at once by doing exactly what we just did. So we can take the ith row and all the columns and add an axis to the end.

And then just like we did here, multiply it by b. And then dot sum.

And so that is, again, exactly the same thing. That is another matrix multiplication, doing it using broadcasting. Now this is, like, tricky to get your head around.

And so if you haven't done this kind of broadcasting before, it's a really good time to pause the video and look carefully at each of these four cells before and understand what did I do there? Why did I do it? What am I showing you?

And then experiment with trying to, and to remember that we started with m1[0], right? So just like we have here a[i]I. So that's why we've got [i, :, None] , because this digit is actually m1[0]. This is like m1, zero, colon, none.

So this line is doing exactly the same thing as this here, plus a sum.

So let's check if this matmul is the same as it used to be, yet it's still working. And the speed of it, okay, not bad. So 137 microseconds.

So we've now gone from a time from 500 milliseconds to about 0.1 milliseconds.

Funnily enough on my, oh, actually now I think about it, my MacBook Air is an M2, whereas this Mac Mini is an M1. So that's a little bit slower.

So my Air was a bit faster than 0.1 milliseconds. So overall, we've got about a 5,000 times speed improvement.

So that is pretty exciting. And since it's so fast now, there's no need to use a mini batch anymore. If you remember, we used a mini batch of, where is it, of five images. But now we can actually use the whole data set because it's so fast. So now we can do the whole data set.

There it is. We've now got 50,000 by 10, which is what we want. And so it's taking us only 656 milliseconds now to do the whole data set. So this is actually getting to a point now where we could start to create and train some simple models in a reasonable amount of time.

So that's good news. All right.

I think that's probably a good time to take a break. We don't have too much more of this to go, but I don't want to keep you guys up too late.

So hopefully you learned something interesting about broadcasting today. I cannot overemphasize how widely useful this is in all deep learning and machine learning code.

It comes up all the time. It's basically our number one most critical kind of foundational operation.

So yeah, take your time practicing it and also good luck with your diffusion homework from the first half of the lesson. Thanks for joining us and I'll see you next time.

Transcript - Lesson 12

Lesson 12: Deep Learning Foundations to Stable Diffusion Practical Deep Learning for Coders - Jeremy Howard

Hi everybody, welcome back to Lesson 12 of Practical Deep Learning for Coders.

So got a lot of stuff to cover today, so let's dive straight in. And I actually thought I would start by sharing something which I've seen been getting a lot of attention recently, which is the CLIP Interrogator.

CLIP Interrogator & how it works

So the CLIP Interrogator is a Hugging Face Spaces, I guess, Gradio app where I uploaded my image here and its output, let's just zoom in a bit, its output a text prompt for creating a CLIP embedding from, I guess.

So I've seen a lot of folks on Twitter and elsewhere on the internet saying that this is producing the CLIP prompt that would generate this image.

And generally speaking, the CLIP, the prompts it creates are rather rude. My one's less rude than some, although, you know, extremely long forehead, maybe not, thanks very much, but your personal data avatar, funny professional photo.

I don't know what tectonics has been to me here without eyebrows. So this doesn't actually return the CLIP prompt that would generate this photo at all.

And the fact that some people are saying that makes me realize that some people have no idea what's going on with Stable Diffusion. So I thought we might take this as an opportunity to explain why we can't do that and what we can try and do instead.

So let's imagine that my friend took a photo and —of himself— and he wanted to send me his photo and he thought he would compress it a whole lot. So what he did was he put it through the CLIP image encoder.

Okay. So that's going to take this big image and it's going to turn it into an embedding. And the embedding is much, much smaller than the image. It's just a vector of a few floats.

So then my friend hopes that they could send me this embedding. And so they send that over in an email and they say, there you go, Jeremy, there's the CLIP embedding of the photo I wanted to send you. So now you just have to decode it to turn it back into a picture.

So now I've got the embedding and I have to decode it. How would you do that?

Well, you can't. We have a function here, let's call it f, which is the clip image encoder, which takes as input an image, which I'll call x and returns an embedding.

Does that mean that there is some other function and inverse functions —we normally write with a minus one—, an inverse function with which I can take that embedding, let's say we call that y, we pass it y and it would give us back our photo.

And so y, remember, is f(x). So to put it another way, this is f inverse of f of f of y. So an inverse function is something that undoes a function and so that gives you back y. Is there an inverse function for the CLIP image encoder? Well, not everything has an inverse function.

For example, consider the function like, let's say in Python, which takes def f of x, returns zero. Can you invert that function, if you get back, you pass in three, you get back zero, is there a function, oopsie, zero, is there a function that's gonna take the output and give you back the input? No, of course not, because you just threw the whole thing away. So not all functions can be inverted.

And indeed, in this case, we've started with a function, which is whatever 512 by 512 by 3, say, and we've turned it into something much, much smaller. I can't remember exactly how big a CLIP image encoding is, embedding is, but it's much smaller. So clearly we're losing something.

But what I could do is I could put it through a diffusion process.

And so remember, a diffusion process is something where we have learned, we have taught or… we shouldn't, I don't know if taught, well an algorithm has learned to take some noise.

So we could start with some noise, and we could start with an image embedding. We haven't done this before, but we could do that. We could train something that takes noise and image embedding and removes a bit of the noise. And we could run that a bunch of times.

And it wouldn't give us back the original picture, but hopefully it would give us something back if it's a conditional. So remember, using the conditional diffusion approach, we'd get back something that might be something like our original image.

So that's what diffusion is, right? Diffusion is something that takes an embedding and inverts an encoder to give you back something that hopefully might generate that embedding.

Now, of course, remember, we don't actually get image embeddings when we do prompts in stable diffusion. Instead, we have text embeddings.

But if you remember, that actually doesn't matter. Because do you remember how we actually, well "we", OpenAI, trained CLIP so that they had various pictures along with their captions, and they trained an algorithm that was explicitly designed to make it so that each image returned a embedding for the image that was similar to the embedding that the text encoder created for the caption.

And remember, all of the stuff that didn't match, it was trained to be different. And so that means that a text embedding, which describes this picture, and the actual image embedding of this picture should be very similar if they're CLIP embeddings.

That's the definition of CLIP embeddings. So you see this idea that you could take a text or image embedding and turn it back into an image perfectly makes no sense.

This is the very definition of the thing we're trying to do when we do CLIP. And because what we're basically trying to do is invert the embedding function, these kinds of problems are generally referred to as "inverse problems".

So Stable Diffusion is something that attempts to approximate the solution to an inverse problem.

So why does that mean that CLIP interrogator is not actually inverting the picture to give us back the text? Well, it's just as nonsensical. If we've got an image embedding, right, trying to undo that to get back to the picture and trying to undo that to get back to a suitable prompt is equally infeasible. Both of them require inverting an encoder.

And that just doesn't exist. The best we can do is, or at least the best we know how to do at the moment, is to approximate that using a diffusion process.

Okay, so that's why these texts that it spits back are fun and interesting, but they are not the thing that you can put back into Stable Diffusion and have it generate the same photo.

And the nice thing is that actually the code for this is available.

And you can take a look at it. Here's the app.

And you'll see what it does is it has a big list of —let's have a look at some examples.

So it has a big, this has big lists of examples, for example, a big list of artists.

And it has a big list of mediums and a big list of movements, and so forth.

It's got all this hard coded pieces of text. And so what it does is it basically mixes and matches those various things together to see which one works well.

And it combines it with the output of something called the BLIP language model, which is not designed to give you an exactly accurate description of an image, but it has been specifically trained to give an okay-ish caption for an image and it actually works reasonably well. But again, it's not it's not the inverse of the clip encoder. So okay, so that's how that all works.

Matrix multiplication refresher

So where we had got to was that we had done matrix multiplication with broadcasting, where we had broadcast the entire column from the right hand matrix all at once.

And that allowed us to get it down to a point where we only have one for loop written in Python.

And generally speaking, we do not want to be doing loop— looping through too many things in Python, because that's the slow bit. So the two inner loops we originally had, which just to remind us, originally were here, these two inner loops, looping through 10, and then to 784 respectively, have been replaced with a single line of code. So that was pretty great. And our times now is increased— is improved by 5,000 times. So we're 5,000 times faster than we started out.

So another trick that we can use, which I'm a big fan of, is something called Einstein summation.

Einstein summation

And Einstein summation is a compact representation for representing products and sums.

And this is an example of an Einstein summation. And what we're going to do now is we're going to replicate our matrix product with an Einstein summation. And believe it or not, the entire thing can be pushed down to just these characters, which is pretty amazing. So let me explain what's happening here. The arrow is separating the left hand side from the right hand side.

The left hand side is the inputs. The right hand side is the output. The comma is between each input. So there are two inputs.

The letters are just names that you're giving to the number of rows and the number of columns.

So the first matrix we're multiplying by has i rows and k columns.

The second has k rows and j columns. It's going to go through a process which creates a new matrix that —actually this is not even doing, this is not yet doing the matrix multiplication.

This is without the sum. This one's going to create a new matrix that contains i rows and k, well, how do we say it? i faces and k rows and j columns.

So a rank three tensor. So the number of letters is going to be the rank.

And the rules of how this works is that if you repeat letters between input arrays, so here's my inputs, ik and kj, we've got a repeated letter.

It means that values along those axes will be multiplied together. So it means that each item in each row of, sorry, in each, yeah, across a row will be multiplied by each item down each column to create this i by k by j output tensor.

So to remind you, our first matrix is 5 by 784. That's m1.

Our second matrix is 7084 by 10. That's m2.

So i is 5, k is 784 and j is 10. So if I do this torch.einsum, then I will end up with a i by k by j. It'll be 5 by 784 by 10.

And if you have a look, I've run it here on these two tensors, m1 and m2, and the shape of the result is 5 by 784 by 10. And what it contains is the original 5 rows of m1, the original 10 columns of m2, and then for the other 784, that dimension, they're all multiplied together because it's been copied between the two arguments to the einsum.

And so if we now sum up that over this dimension, we get back.

So what we get back, if we go back to the original matrix multiply we do, we had 10.94, negative, negative 0.68, et cetera. And so now with this Einstein summation version, we've got back exactly the same thing. Because what it's done is it's taken each of these columns by rows, multiplied them together to get this 5 by 784 by 10, and then added up that 784 for each one, which is exactly what matrix multiplication does.

But we're going tu use one of the two things from Einstein summation. The second one says if we omit a letter from the output, so the bit on the right of the arrow, it means those values will be summed. So if we remove this k, which gives us ik and kj goes to ij, so we've removed the k entirely, that means that sum happens automatically.

So if we run this, as you see, we get back again, matrix multiplication.

So Einstein summation notation is, you know, it takes some practice getting used to, but it's very convenient. And once you get used to it, it's actually a really nice way of thinking about what's going on. And as we'll see in lots of examples, often you can really simplify your code by using just a tiny little Einstein summation.

And it doesn't even have to be a sum, right? You can, you don't have to omit any letters if you're just doing products. So maybe it's a bit misnamed.

So we can now define our matmul as simply this torch.einsum.

So if we now check it, test_close that the original result is equal to this new matmul. And yes, it is. And let's see how the speed looks. 15 milliseconds.

Okay. And that was for the whole thing.

So compared to 600 milliseconds. So as you can see, this is much faster than even the very fast broadcasting approach we used. So this is a pretty good trick, is torch.einsum.

Okay. But of course, we don't have to do any of those things because PyTorch already knows how to do matmul. So there's two ways we can run matmul directly in PyTorch.

You can use a special at (@) operator. So x_train @ weights is the same as matmul(x_train, weights), as you see, test_close. Or you can say torch.matmul.

And interestingly, as you can see here, the speed is about the same as the einsum.

So there's no particular harm, no particular reason not to do an einsum. So when I say einsum, that stands for Einstein summation notation.

All right. Let's go faster still. Currently we're just using my CPU.

Matrix multiplication put on to the GPU

But I have a GPU. It would be nice to use it. So how does a GPU work? An Nvidia GPU, and indeed, pretty much all GPUs, the way they work is that they do lots and lots of things in parallel. And you have to actually tell the GPU what are all the things you want to do in parallel, one at a time. And so what we're going to do is we're going to write in pure Python something that works like a GPU, except it won't actually be in parallel, so it won't be fast at all. But the first thing we have to do if we're going to get something working in parallel is we have to create a function that can calculate just one thing, even if a thousand other things are happening at the same time, it won't interact with anything else. And there's actually a very easy way to think about matrix multiplication in this way, which is what if we try to create something which just as we've done here fills in a single item of the result? So how do we create something that just fills in row zero, column zero?

Well what we could do is we could create a new matmul where we're going to pass in the coordinates of the place that we want to fill in. So we're going to start by passing it (0, 0).

We'll pass it the matrix— matrices we want to multiply, and we'll pass in a tensor that we've pre-filled in with zeros to put the result into. So we're going to say, okay, the result is torch.zeros, rows by columns, call matmul for location (0, 0), passing in those two matrices and the bunch of zeros matrix ready to put the result in.

And if we call that, we get the answer in cell (0, 0). So here's an implementation of that. So the implementation is first of all, we've been passed the (0, 0) coordinates. So let's destructure them. So hopefully you've been experimenting with destructuring because it's so important.

You see it all the time into i and j. That's the row and the column.

Make sure that that is inside the bounds of our output matrix.

And we're going to start by start at zero and loop through all of the rows of a and all of the columns of b for i and j. Sorry, all of the columns of a and all of the rows of b for i and j, just like the very innermost loop of our very first Python attempt.

And then at the end, pop that into the output. So here's something that fills in one piece of the grid successfully. So we could call this rows by columns times, each time passing in a different grid. And we could do that in parallel because none of those different locations interact with any other location.

So something which can calculate a little piece of an output on a GPU is called a kernel. So we'd call this a kernel. And so now we can create something called launch_kernel.

We pass it the kernel. So that's the function. So here's an example, launch_kernel passing in the function.

And how many rows and how many columns are there in the output grid.

And then give me any arguments that you need to calculate it. So in Python, *args just says any additional arguments that you pass are going to be put into an array called args. If you use something like C, you might've seen like variadic arguments or parameters. It's the same basic idea.

So we're going to be calling launch_kernel. We're going to be saying launch the kernel matmul, using all the rows of a, all the columns of b, and then the args, which are going to be the *args, are going to be m1, the first matrix, m2, the second matrix, and res, another torch.zeros we just created. So launch_kernel is going to loop through the rows of a, and then for each row of a, it'll loop through the columns of b and call the kernel, which is matmul, on that grid location passing in m1, m2, and res.

So *args here is going to unpack that and pass them as three separate arguments.

And if I run that, run all of that, you'll see it's done it. It's filled in the exact same matrix.

Okay, so that's actually not fast at all. It's not doing anything in parallel, but it's the basic idea. So now to actually do it in parallel, we have to use something called CUDA. So CUDA is a programming model for Nvidia GPUs.

And to program in CUDA from Python, the easiest way currently to do that is with something called Numba. And Numba is a compiler. Oh, well, you've seen it actually already for non-GPU.

It's a compiler that takes Python code and spits out, you know, compiled fast machine code.

If you use its CUDA module, it'll actually spit out GPU accelerated CUDA code.

So rather than using at @njit like before, we now say @cuda.jit

And it behaves a little bit differently, but you'll see that this matmul, let me copy the other one over so you can compare, compare it to our Python one.

Our Python matmul and this @cuda.jit matmul look, I think identical, except for one thing, instead of passing in the grid, there's a special magic thing called cuda.grid And you say, how many dimensions does my grid have? And you unpack it. So that's, you don't have to, it's just a little convenience that Numba does for you. You don't have to pass over the grid.

It passes it over for you. So it doesn't need this grid. Other than that, these two are identical, but the decorator is going to compile that into GPU code.

So now we need to create our output tensor just like before, and we need to do something else, which is we have to take our input matrices and our output.

So our input tensors, the matrices in this case, and the output tensor, and we have to move them to the GPU. Or I should say, copy them to the GPU.

So cuda.to_device copies a tensor to the GPU. And so we've got three things getting copied to the GPU here. And therefore we store the three things over here.

Another way I could have written this is I could have said map, which I kind of quite like doing, a function, which is cuda.to_device to each of these arguments.

And this would be the same thing. This is going to call cuda.to_device on x_train and put it in here on weights and put it in here and on r and put it in here.

That's a slightly more convenient way to do it.

Okay. So we've got our 50,000 by 10 output. That's just all zeros, of course. That's just how we created it.

And now we're going to try and fill it in. There is a particular detail that you don't have to worry about too much, which is in CUDA. They don't just have a grid, but there's also a concept of blocks. And there's something we call here TPB, which is threads per block.

This is just a detail of the CUDA programming model. You don't have to worry about too much. You can just basically copy this.

And what it's going to do is it's going to call each grid item in parallel with a number of different processes, basically. So this is just the code which turns the grid into blocks. And so you don't have to worry too much about the details of that. You just always run it.

Okay. And so now how do you call the equivalent of launch_kernel? Well, it's a slightly weird way to do it, but it works fine.

You call matmul, but because matmul has @cuda.jit, it's got a special thing, which is you have to put something in square brackets afterwards, which is you have to tell it how many blocks per grid. That's just the result from the previous cell and how many threads per block in each of the two dimensions.

So again, you can just copy and paste this from my version, but then you pass in the three arguments to the function. This will be a, b, and c. And this is how you launch a kernel. So this will launch the kernel matmul on the GPU.

At the end of it, rg is going to get filled in. It's on the GPU, which is not much good to us.

So we now have to copy it back to the CPU, which is called the host, copy to host, to run that.

And it's done. And test_close shows us that our result is similar to our original result. So it seems to be working.

So that's great. I see Siva on the YouTube chat is finding that it's not working on his Mac.

That's right. So this will only work on an NVIDIA GPU, as basically all of the GPU, nearly all the GPU stuff we look at only works on NVIDIA GPUs.

Mac GPUs are gradually starting to get a little bit of support from machine learning libraries, but it's taking quite a while. It's got quite a way to go, as I say this at least towards the end of 2022. If this works for you later on, that's great.

Okay. So let's time how fast that is. Okay. So that was 3.61 milliseconds.

And so if we compare that to the PyTorch matmul on CPU, that was 15 milliseconds.

So that's great. So it's faster still. So how much faster... Oh, by the way, we can actually go faster than that, which is we can use the exact same code we had from the PyTorch up. But here's a trick. If you just take your tensor and write .cuda() after it, it copies it over to the GPU.

If it's on a NVIDIA GPU, do the same for weights.cuda() So these are our two CUDA versions.

And now I can do the whole thing. And this will actually run on the GPU.

And then to copy it back to the host, you just say .cpu() So if we look to see how fast that is, 458 microseconds. So that is...

Somebody just pointed out that I wrote the wrong thing here. 1e-3. Okay.

So how much faster is that? 458 microseconds, our original, on the whole dataset, was 663 micromiliseconds. So compared to our broadcast version, we are another thousand times faster. So overall, this version here compared to our original version, which was here... Here, the difference in performance is 5 million X. So when you see people say, yeah, Python can be pretty slow, it can be better to run stuff on the GPU.

If possible, we're not talking about a 20% change. We're talking about a 5 million X change.

So that's a big deal. And so that's why you need to be running stuff on the GPU.

All right. Some folks on YouTube are wondering how on earth I'm running CUDA when I'm on a Mac. And given it says local host here.

That's because I'm using something called SSH tunneling, which we might get to sometime.

I suspect my live coding from the previous course might have covered that already. But this is basically you can use a Jupyter Notebook that's running anywhere in the world from your own machine using something called SSH tunneling, which is a good thing to look up.

Okay. One person asks if Einstein summation burrows anything from APL. Yes, it does actually.

So it's kind of the other way around, actually. APL burrows it from Einstein notation.

So I don't know if you remember I mentioned that Ken Iverson, when he developed APL, was heavily influenced by tensor analysis. And so this Einstein notation is very heavily used there. If you'll notice, a key thing that happens in Einstein notation is there's no loop. There isn't this kind of sigma, you know, i from here to here, and then you put the i inside the function that you're summing up.

Everything's implicit. And APL takes that a very long way.

And J takes it even further, which is what Ken Iverson developed after APL. And this kind of general idea of removing the index is very important in APL, and it's become very important in NumPy, PyTorch, TensorFlow, and so forth.

So finally, we know how to multiply matrices. Congratulations.

So let's practice that. Let's practice what we've learned.

So we're going to go to 02_meanshift to practice this.

Clustering (Meanshift)

And so we're going to try to exercise our kind of tensor manipulation operation muscles in this section. And the key actually endpoint for this is the homework.

And so what you need to be doing is getting yourself to a point that you can implement something like this, but for a different algorithm.

Why do we care about this? Because this is like learning your times table, your times tables, if you're doing, you know, mathematics, it's this kind of like thing that's going to come up all the time. And if you're not good at your times tables, everything else, a lot, a lot of other things, particularly at primary school and high school, you know, they get difficult. You get slower and it's frustrating.

And you spend time thinking about these mechanical operations rather than getting your work done.

It is, it's important that when you have an idea about something you want to try or debug or profile or whatever, that you can quickly translate that into working code and the way that code is written for GPUs or even for fast running on CPUs is using broadcasting, Einstein notation, matrix modifications, and so forth. So you've got to, you've got to, got to, got to practice super important. So we're going to practice it by running, by developing a clustering algorithm and the clustering algorithm we're going to work on is something called mean shift clustering, which hopefully you've never heard of before.

And I say that because I just think it's a really fun algorithm, but not many people have come across, excuse me. And I think you'll find it really useful.

So what is cluster analysis? Cluster analysis is very different to anything that we've worked on in this course so far and that there isn't a dependent variable that we're trying to match.

But instead we're just trying to find, are there groups of similar things in this data and those groups we call clusters. And as you can see from the Wiki page, there's all kinds of applications of cluster analysis across many different areas.

I will say that sometimes cluster analysis can be overused or misused.

It's really best for when your, your various columns are the same kind of thing and have the same kind of scale.

For example, pixels are all the same kind of thing. They're all pixels. So one of the examples they use is market research. So I wouldn't use cluster analysis for socio-demographic inputs because they're all different kinds of things.

But the example they give here makes a lot of sense, which is looking at data from surveys. If you've got a whole bunch of like, from one to five answers on surveys.

Create Synthetic Centroids

All right, so let's take a look at this. And the way I like to build my algorithms is to create some, often, to create some synthetic data that I know how I want it to behave. And so we're going to create six clusters and each class is going to have 750 samples in it.

So first of all, I'm going to randomly create six centroids.

And so the centroid is going to be like the middle of where my clusters are. So I'm going to randomly create them.

I need them n_clusters by 2 because I need an X and a Y coordinate for each one.

And so now I'm going to randomly generate data around those six centroids.

Okay, so to do that, I'm going to call a little function I made here called sample.

And I'm going to run it on each of those six centroids.

And so I'll show you what that looks like. So here's what that data looks like. So the Xs are the six centroids and the colored dots is the data. So if you were given this data without the Xs, the idea would be to come back with figuring out where the Xs would have been.

Like where are these clustering around? And so if you can get clusters, that's the goal here, is to find out that there's a few discreetly, distinctly different types of data in your data set.

So for example, for images, I've used this before to discover that there are some images that look completely different to all the other ones. For example, they were taken at nighttime or they're of a different object or something like that.

So how does sample work? Well we're passing in the centroid and so what we want is we're going to get back… So each of those centroids contains an X and a Y.

So MultivariateNormal() is just like normal. It's going to give you back normally distributed data, but more than one item. That's why it's multivariate.

And so we passed in two means, a mean for X and a mean for our Y.

And so that's the mean that we're going to get. And our standard deviation is going to be five.

Why do we use torch.diag( tensor([5., 5.]) )? That's because we're saying, that's because that for multivariate normal distributions, there's not just one standard deviation for each column that you get back.

There could also be a connection between columns. So columns might not be independent.

So you actually need, so it's called a covariance matrix, not just a variance.

We discussed that a little bit more in Lesson 9b, if you're interested in learning more about that.

Okay, so this is something that's going to give us back random columns of data with this mean and this standard deviation. And this is the number of samples that we want.

And this is coming from PyTorch. So PyTorch has a whole bunch of different distributions that you can use, which can be very handy.

So there's our data. Okay, so remember for clustering, we don't know the different colors. And we don't know where the Xs are. That's kind of our job is to figure that out. We might just briefly also look at how to plot.

So in this case, we want to plot the Xs and we want to plot the data.

So it looks like this. So all I do is I loop through each centroid.

And I grab that centroid samples, and they're just all done in order. So I grab it from i time n_samples up to (i +1) times n_samples.

And then I create a scatterplot with the samples on them. And what I've done is I've created an axis here. And you'll see why later that we can also pass one in, but I'm not passing one in. So we create a plot and an axis. And so in Matplotlib, you can keep plotting things on the same axis.

So then I plot on the centroid, a big X, which is black, and then a smaller X, which is what is that, magenta. And so that's how I get these Xs. So that's how plot data works. Okay, so how do we create something

Mean shift algorithm

now that starts with all the dots and returns where the Xs are?

We're going to use a particular algorithm, particular clustering algorithm called Mean Shift.

And Mean Shift is a nice clustering approach, because you don't have to say how many clusters there are.

So it's not that often that you actually got to know how many clusters there are. So we don't have to say. Quite a few things like the very popular k-means require you to say how many. Instead, we just have to pass them in a bandwidth, which we'll learn about, which can actually be chosen automatically. And it can also handle clusters of any shape. So they don't have to be ball-shaped like they are here. They can be kind of like L-shaped or ellipse-shaped or whatever. And so here's what's going to happen.

We're going to pick some point. So let's say we pick that point just there.

And so what we now do is we go through each data point.

So we'll pick the first one. And so we then find the distance between that point and every other point. So we're going to have to say, what is the distance between that point and that point and that point and that point and that point and that point? And also the ones further away, that point and that point.

And you do it for every single point compared to the one that we're currently looking at.

Okay, so we get all of those as a big list.

And now what we're going to do is we're going to take a weighted average of all of those points.

Now that's not interesting without the weighting.

If we just take our average of all of the points and how far away they are, we're going to end up somewhere here, right? This is the average of all the points.

But the key is that we're going to take an average.

Let me find the right spot. The key is we need to find an average that is weighted by how far away things are. So for example, this one over here is a very long way away from our point of interest. And so it should have a very low weight in the weighted average, whereas this point here, which is very close, should have a very high weight in our weighted average. So what we do is we create weights for every point compared to the one that we're currently interested in using what's called a Gaussian kernel that we'll look at. The key thing to know is that points that are further away from our point of interest, which is this one, are going to have lower weights.

That's what we mean there. They're penalized. The rate at which weights fall to zero is determined by this thing that we set at the start called the bandwidth. And that's going to be the standard deviation of our Gaussian. So we take an average of all the points in the data set, a weighted average weighted by how far away they are.

So for our point of interest, this point's going to get a big weight, this point's going to get a big weight, this point's going to get a big weight, that point's going to get a tiny weight, that point's going to get an even tinier weight. So it's mainly going to be a weighted average of these points that are nearby. And the weighted average of those points, I would guess, is going to be somewhere around about here.

And would have a similar thing for the weighted average of the points near this one, that's going to probably be somewhere around about here, or maybe over here.

And so it's going to move all of these points in closer, it's almost like a gravity, right? They're kind of going to be moved like closer and closer in towards this kind of gravitational center.

And then these ones will go towards their own gravitational center, and so forth.

Okay, so let's take a look at it.

All right, so what's the Gaussian kernel? This is the Gaussian kernel, which was a sign in the original march for science, back in the days when the idea of not following scientists was considered socially unacceptable. We used to have much for these things, if you remember. So this is not normal.

So this is the definition of the Gaussian kernel, which is also known as the normal distribution. This is the shape of it. I'm sure you've seen it before.

And here is that formula copied directly off the science march sign.

Okay, here we are, you can see the square root, two, pi, et cetera. Okay, and this here is the standard deviation.

Plotting gaussian kernels

Now what does that look like? It's very helpful to have something that we can very quickly plot any function. That doesn't come with Matplotlib, but it's very easy to write one. Just say, oh, let's, as X, let's use all the numbers from 0 to 10, 100 of them spaced evenly. That's what linspace() does.

Linearly spaced 100 numbers in this range. That's going to be our Xs. So plot those Xs and plot f(X), the Ys. So here's a very nice little plot_func we want.

And here it is. And as you can see here, we've now got something where if you are this, like very close to the point of interest, you're going to get a very high weight. And if you're a long way away from the point of interest, you'll get a very low weight. So that's the key thing that we wanted to remember is something that penalizes further away points more.

Now you'll notice here, I managed to plot this function for a bandwidth of 2.5. And the way I did that was using this special thing from functools called partial. Now the first thing to point out here is that very often, drives me crazy, I see people trying to find out what something is in Jupyter.

And the way they do it is they'll scroll up to the top of the notebook and search through the imports and try to find it. That is the dumb way to do it.

The smart way to do it is just to type it and press shift enter, and it'll tell you where it comes from. And you can get its help with question mark and you can get it source code with two question marks. Okay. So just type it to find out where it comes from.

Okay. So this is, as Siva's mentioned in the chat, also known as currying or partial function application.

This creates a new function. So let's just grab it.

We create a new function and this function f is, is the function Gaussian, but it's going to automatically pass bw equals 2.5. This is a partially applied function. So I could type f(4), for example, that's going to be a tensor.

There we go. And you can see that's exactly what this is. Go up to 4, go across. Yep. About 0.44.

So we use partial function application all the time. It's a very, very, very important tool. Without it, for example, plotting this function would have been more complicated. With it, it was trivially easy.

I guess the alternative, like one alternative, which would be fine, but slightly more clunky would be, we could create a little function in line.

So we could have said, Oh, plot a function that I'm going to define right now, which is called lamb—, which is Lambda x, which is Gaussian of x with a bandwidth of 2.5. You could do that too. You know, it's, it's fine. But, but yeah, partials I think are a bit neater, a bit less to think about. They often produce some neater and clearer code.

Okay. Why did we decide to make the bandwidth 2.5? As a, as a rule of thumb choose a bandwidth, which covers about a third of the data.

So if we kind of found ourselves somewhere over here, right? A bandwidth which covers about a third of the data would be enough to cover two clusters ish.

So you'd want to be kind of like this big. So somewhere in the middle there so that's the basic idea. Yeah.

So, but you can play around with bandwidths and get different amounts of clusters.

I should mention, like, often when you see something that's kind of on the complicated side, like a Gaussian, you can often simplify things. I think most of the implementations and writeups I've seen talk about using Gaussians, but if you look at the shape of it, it looks a lot like this shape. So this is a triangular weighting, which is just using clamp_min(). So it's just using a linear with clamp_min().

And yeah, it occurred to me that we could probably use this just as well. So I decided to define this triangular weighting and then we can try both.

Anyway, so we'll start with, we're going to use the Gaussian version.

All right. So we're going to be literally moving all the points towards their kind of center of gravity.

So we don't want to mess up our original data. So we clone it. That's a PyTorch thing is .clone(). It's very handy.

And so big X is our matrix of data. I mean, it's actually a, that's right, matrix of data. Yeah. And then little x will be our first point. And it's pretty common to use big X, capital letters for matrices. So this is our data.

This is the first point. Okay. So there it is. So we're going to start at (26.2, 26.3).

So (26.2, 26.3). So somewhere up here.

Calculating distances between points

So little x its shape is just, it's a rank 1 tensor of shape 2, big X is a rank 2 tensor of 1,500 data points by 2, the x and y.

And if we call x[None], that would add a unit access to that.

And the reason I'm going to show you that is because we want to find the distance from little x to everything in big X. And the way we do a distance is with minus, but you wouldn't be able to go, you wouldn't be able to go x – X and get the right actually do you get the right answer?

Let's think about that extra shape. Oh, you've got that already.

Oh no, actually that is going to work. Isn't it? So yes. All right.

So you can see why we've got these two versions here. If we do x[None], we've got something of shape 1, 2.

Now we can subtract that from something of shape 1,500, 2, because the 2s match up because they're the same and the 1,500 and the 1 matches up because you remember our NumPy rules, everything matches up to a unit axis. So it's going to copy this matrix across every row of this matrix and it works.

But do you remember there's a special trick, which is if you've got two shapes of different lengths, we can use the shorter length and it's going to add unit axes to the front to make it as long as necessary. So we actually don't need the x[None].

We can just use little x and it works because it's going to say, is this compatible with this? Well, the last axis, remember we go right to left. The last access matches the second last axis. Oh, it doesn't exist.

So we pretend that there's a unit axis and it's going to do exactly the same thing as this.

So if you have not studied the broadcasting from last week carefully, that might not have made a lot of sense to you. And so definitely at this point, you might want to pause the video and go back and reread the NumPy broadcasting rules from last time and practice them because that's what we just did. We used NumPy broadcasting rules and we're going to be doing this dozens more times throughout the rest of the course and many more times in fact in this lesson. Okay. So now I think it's a pretty good place to have a pause. So I'll see you back here in nine minutes.

Hi everybody. Welcome back. So we had got to the point where we had managed to get the distance between our first point x and all of the other points in the data. And so we're just looking at the first eight of them here. So the very first distance is of course zero on the X axis and zero on the Y axis because it is the first point.

The other thing is that because we… the way we created the clusters is they're all kind of next to each other in the list.

So these are all in the first cluster. So none of them are too far away from each other. So now that we've got all the distances, it's easy enough to, well not the distances on X and Y, it's easy enough to get the distance … kind of Euclidean distance. So we can just square that difference and sum, and square root. And actually maybe this is a good time to talk about norms and to talk about what we just did there.

Calculating distances between points (illustrated)

We've got all these data points.

So here's one of our data points and here's the other one of our data points.

And there's some distance across the X axis and there's some distance along the Y axis.

We could call that change in X and change in Y.

And one way to think about this distance then is it's this distance here.

So to calculate that we can use Pythagoras. So a² + b² = c²

Or in our case, so this would be c, a and b, say, so in our case it would be the square root of the change in X squared plus the change in Y squared.

And rather than saying square root, we could say to the power of a half, another way of saying the same thing. But there's a different way we could find the distance.

We could first go along here and then go up here.

And so that one would be change in X, if you like, to the one plus change in Y to the one to the power of one-oneth. I'm writing it a slightly odd way for reasons you'll see in a moment. It's just this otherwise.

In general, if we've got a whole list of numbers, we can add them up.

Let's say there are some list V. We can add them up. We can do each one to the power of some number alpha.

And take that sum to the one over alpha. And this thing here is called a norm.

So you might remember we came across that last week and we come across it again this week. They basically come up, I don't know, they might end up coming up every week.

They come up all the time, particularly because the two norm, which we could write like this (||v||), or we could write like this (|v|), or we could write like this (|v|2). They're all the two norm.

This is just saying it's this equation for alpha equals two. And Stefano is pointing out we should actually have an absolute value. I'm not going to worry about that. We're just doing real numbers here. So we'll keep things simple. Oh, well, I guess for higher than one. No, you're probably right.

Something like three. Yeah, I guess we do need an absolute value there. That's a good point because, okay, we could have this one.

And so the distance actually has to be the absolute value. So the change in X is the absolute value of that distance.

Yes, thank you, Stefano. Okay, so we'll have the absolute value. Okay, so the two norm is what happens when alpha equals two.

And we would call this, in this case, we would call this the Euclidean distance.

But actually where it comes up more often is when you're doing like a loss function. So the Mean Squared Error is just, well, the Root Mean Squared Error, I should say, is just the two norm.

Whereas the Mean Absolute Error is the one norm. And these are also known as L2 and L1 plus.

And remember what we saw in that paper last week, we saw it in this form, there's a two up here, which is where they got rid of the square root again.

So that would have just been change in X squared plus change in Y squared. And now we don't even need the parentheses.

Oopsie-Daisy. Okay. So, all of this is to say that for, you know, this comes up all the time, because we're very, very often interested in distances and errors and things like that.

I'm trying to think, I don't feel like I've ever seen anything other than one or two.

So although it is a general concept, I don't think we're going to see probably things other than one or two in this course.

I'd be excited if we do, that would be kind of cool.

So here we're taking the Euclidean distance, which is the two norm.

So this has got eight things in it, because we've summed it over dimension one.

So here's your first homework, is to rewrite using torch.einsum().

You won't be able to get rid of the x minus X, you'll still need to have that in there. But when you've got a multiply followed by a sum, you won't be able to get rid of the X square root either, you should be able to get rid of the multiply and the sum by doing it in a single torch.einsum(). So we're summing up over the first dimension, which is this dimension. So in other words, we're summing up the X and the Y axis. Okay, so now

Getting the weights and weighted average of all the points

we can get the weights by passing those distances into our Gaussian.

And so as we would expect, the biggest weights, it gets up to 0.16.

So the closest one is itself, it's going to be at a big weight. These other ones get reasonable weights and the ones that are in totally different clusters have weights small enough that at three significant figures they appear to be zero.

Okay, so we've got our weights. So the weights are 1,500 long vector and of course our original data is 1,500 by 2, the X and the Y for each one.

So we now want a weighted average. We want this data, we want its average weighted by this. So normally an average is the sum of your data divided by the count. That's a normal average.

A weighted average, each item in your data, let's put some i's around here just to be more clear, each item in your data is going to have a different weight.

And so you multiply each one by the weights. And so rather than dividing by n, which is just the sum of ones, we would divide by the sum of weights.

So this is an important concept to be familiar with, weighted averages.

So we need to multiply every one of these x's by this.

Okay, so can we say weight times X? No. All right, why didn't that work?

So, remember we go right to left. So first of all, it's going to say, let's look at the 2 and multiply that by the 1,500. Are they compatible? These are compatible if they're equal or if at least one of them is 1.

These are not equal and they're not 1, so they're not compatible. That's why it says the size of a tensor a must match. Now when it says match, it doesn't mean they have to be the same. One of them can be 1.

Okay, that's what it means to match. They're either equal or one of them is 1. So that doesn't work. On the other hand, what if this was 1,500 comma 1? If it was 1,500 comma 1, then they would match because the 1 and the 2 match because one of them is a unit axis and the 1,500 and the 1,500 match because they're the same.

So that's what we're going to do. Because that would then copy this to every one of these, which is what we want. We want weights for each of these X, Y tuples.

So to add the trailing unit axis, we say every row and a trailing unit axis.

So that's what that shape looks like. So we can now multiply that by X.

And as you can see, it's now weighting each of them. And so each of these x's and y's down the bottom, they're all zero.

So we can sum that up and then divide by the sum of weights. So let's now write a function that puts all this together.

So you can see this really important way of like, to me, the only way that makes sense to do particularly scientific numerical programming, I actually do all my programming this way, but particularly scientific and numerical programming is write it all out step by step, check every piece, have it all there documented for you and for others, and then copy the cells, merge them together and indent them to indent its control right spare bracket and put a function header on top. So here's all those things we just did.

And now rather than just grabbing the first x, we enumerate through all of them.

So that's the distance we had before. That's the weight we had before. There's the product we had before. And then finally sum across the rows, divide by the sum of the weights. So that's going to calculate for the ith, it's going to move. So it's actually changing capital X.

So it's changing the ith thing in capital X so that it's now the weighted sum.

Oh, actually, sorry, the weighted average of all of the other data, weighted by how far it is away.

So that's going to do a single step. So the mean shift update is extremely straightforward, which is clone the data, iterate a few times, and do the update.

So if we run it, takes 600 milliseconds. And what I've done is I've plotted the centroids moved by two pixels or two, well, not two pixels, two units so that you can see them. And so you can see the dots is where our data is.

And they're dots now because every single data point is on top of each other on a cluster. And so you can see they are now in the correct spots.

So it has successfully clustered our data. So that's great news. And so we could test out our hypothesis. Could we use triangular just as well as we could have used Gaussian? So control slash comments and uncomments.

Yep, we got exactly the same results. So that's good.

It's really important to know these keyboard shortcuts, hit H to get a list of them.

Some things that are really important don't have keyboard shortcuts. So if you click help, edit keyboard shortcuts, there's a list of all the things Jupyter can do.

And you can add keyboard shortcuts to things that don't have them. So for example, I always add keyboard shortcuts to run all cells above and run all cells below.

As you can see, I type Q and then A for above and Q and then B for below.

All right. Now that was kind of boring in a way because it did five steps.

But we just saw the result. What did it look like one step at a time?

This isn't just fun. It's really important to be able to see things happening one step at a time because there are so many algorithms we do which are like updating weights or updating data. So for Stable Diffusion, for example, you're very likely to want to show your incrementally denoising and so forth.

So in my opinion, it's important to know how to do animations. And I found the documentation for this unnecessarily complicated because a lot of it's about how to make them performant. But most of the time we probably don't care too much about that. So I want to show you a little trick, a simple way to create animations without any trouble. So Matplotlib.animation has something

Matplotlib animations

called FuncAnimation. That's what we're going to use. To create an animation, you have to create a function.

And the function, you're going to be calling FuncAnimation, passing in the name of that function and saying how many times to run it.

And that's what this frames argument. This says run this function this many times. And then create an animation that basically contains the result of that with a 500 millisecond interval between each one.

So what's this do one going to do? To create one frame of animation, we will call our one_update().

Here it is. one_update(). We're going to call this. That's going to update our Xs.

And then we're going to have an axis, which we've created here.

So we're going to clear whatever was on the plot before and plot our new data on that axis.

And then the only other thing you need to do is that the very first time it calls it, we want to plot it before running.

And d is going to be passed automatically the frame number. So for the zeroth frame, we're going to not do the update.

We're just going to plot the data as it is already.

I guess another way we could have done that would have been just to say if d, then do the update, I suppose. That should work too. Maybe it's even simpler.

Let's see if I just broke it. Okay. So we're going to clone our data. We're going to create our figure in our subplots.

We're going to call FuncAnimation() calling do_one 5 times.

And then we're going to display the animation. And so let's see. So HTML takes some HTML and displays it.

And to_jshtml() creates some HTML. That's why it's created this HTML includes JavaScript. And so we'll click run one, two, three, four, five. There's the five steps. So if I click loop, you'll see them running again and again.

Fantastic. So that's how easy it is to create a Matplotlib animation.

So hopefully now you can use that to play around with some fun Stable Diffusion animations as well.

You don't just have to use to_jshtml(). You can also create movies, for example.

You can call to_html5_video() would be another option and you can save an animation as a movie file. So there's all these different options for that, but hopefully that's enough to get you started. So for your homework, I would like you when you create your K-means or whatever, to try to create your own animation or create an animation of some Stable Diffusion thing that you're playing with.

So don't forget this important ax.clear(). Without the ax.clear() it prints it on top of the last one, which sometimes is what you want, to be fair, but in this case, it's not what I wanted.

All right. So kind of slow, half a second for not that much data.

Accelerating our work by putting it on the GPU

I'm sure it would be nice if it was faster. Well, the good news is we can GPU accelerate it.

The bad news is it's not going to GPU accelerate that well because of this loop.

This is looping 1,500 times. If we, so looping is not going to run on the GPU.

So the best we could do with this would be to move all this to the GPU. Now the problem is that calling something on the GPU 1,500 times from Python is a really bad idea because there's this kind of huge communication overhead of this kind of flow of control and data switching back between the CPU and the GPU. It's the kernel launching overhead.

It's bad news. So you don't want to have a really big, fast Python loop that inside it calls CUDA code because GPU code.

So we need to make all of this run without the loop, which we could do with broadcasting.

So let's roll up our sleeves and try to get the broadcast version of this working.

So generally speaking, the way we tend to do things with broadcasting on a GPU is we create batches or mini batches.

So to create batches or mini batches, we know we just call them batches nowadays. We create a batch size. So let's say we're going to do a batch size of five. So we're going to do five at a time.

All right. So how do we do five at a time? This is only doing one at a time. How do we do five at a time?

As before, let's clone our data. And this time little x for our testing. So we're going to do everything ahead of time, little tests as we always do.

This is not now X[0] anymore, but it's X[:bs]. So it's the first five.

This is now the first five items. Okay. So little x is now a 5 by 2 matrix. This is our mini batch, the first five items.

As before our data itself is 1,500 by 2. All right. So we need a distance calculation, but previously our distance calculation. Previously our distance calculation only worked if little x was a single number and it returned just the distances from that to everything in big X, but we need something that's actually going to be, return a matrix, right? We've got, let's say we've got 5 by 2 in little x and then in big X, we've got something much bigger, not to scale obviously.

We've got 1500 by 2. And what is the distance between these two things? Well, if you think about it, there's going to be a distance between item one and item one, but there's also going to be a distance between item one and item two, and there's going to be a distance between, let's use a different color for the next one, item two and item one. Right? So the output of this is actually going to be a matrix.

The distances are actually going to give us a matrix where, I mean, it doesn't matter which way around we do it. We can decide, but if we do it this way around, for each of the 5 things in the mini batch, there will be 1,500 distances, the distance between every one. So we're going to need to do broadcasting to do this calculation.

So this is the function that we're going to create, and it's going to create this, as you can see, 5 by 1,500 output, but let's see how we get it.

So can we do X – x? No, we can't. Why is that? That's because big X is 1,500 by 2 and little x is 5 by 2. So it's going to look at, remember our rules, right to left. Are these compatible? Yes, they are.

They're the same. These compatible?

No, they're not. Okay, because they're different. So that's not possible to do. What if, though, we wanted to… what if we insert in big X an axis at the start here and in little x, we add an axis in the middle here, then now these are compatible because you've got, they're the same —because I should use arrows really.

These are compatible because one of them is a 1. And these are compatible because one of them is the 1 as well.

So they are all compatible. And what it's going to do is it's going to do this subtraction between these directly. And it's going to copy this across all 1,500 rows.

It'll copy it. This is going to be copied. And then this table across 5 rows, and then this will be copied across these 1,500 rows.

Because that's what broadcasting does. I mean, it's not really copying, but it's effectively copying.

And so that gives us, we can now subtract them, and that gives us what we wanted, which is 5 by 1,500.

And there's also by 2 because there's both the X and the Y. So that's why this works. That's what this is doing here.

It's taking this attraction, it's squaring them and then summing over that last shortest axis, summing over the X and the Y squareds.

And then take square root. I don't know why I said torch dot square root. We could have just put dot square root at the end, but same, same. In fact, it's worth mentioning that. So most things that you can do on tensors, you can either write torch dot as a function, or you can write it as a method. Generally speaking, both should be fine.

Not everything, but most things work in both spots. Okay, so now we've got this matrix, which is 5 by 1,500.

And the nice thing is that our Gaussian kernel doesn't actually have to be changed to get the weights, believe it or not.

And the reason for that is —now how do we get the source code? I could move back up there, or I can just type gaussian?? and see it. And the nice thing is that this is just, this is a scalar. So it broadcasts over anything. And then this is also just a scalar. So this is all going to work fine without any fiddling around. Okay.

So now we've got a five by 1,500 weight. So that's the weight for each of the 5 things, our mini batch, for each of the 1,500 things, each of the most compared to. And then we've got the shape of the data itself, X dot shape, which is the 1,500 points.

So now we want to apply each one of these weights to each of these columns.

So we need to add a unit axis to the end. So to add a unit axis to the end, we could say [:, :, None], but dot dot dot ( [...] ) means all of the axes up until however many you need. So in this case, the last one comma none ( […, None] ). This is going to add an axis to the end.

So this is going to turn, this is going to turn weight dot shape from 5 comma 1,500 to 5 comma 1500 comma 1.

And this is going to add an axis to the start. Remember it's the same as X[None, :, :] And so let's check our rules. Left, right to left. These are compatible because one of them is 1.

These are compatible because they're both the same and these are compatible because one of them is 1.

Okay. So it's going to be copying each weight across to each of the X and Y, which is what we want. We want to, we want to weight both of those components and it's going to copy each of the 1,500 points.

Sorry. Each of the point 5 times, because we do in fact want to weight every one of the 5 things in our mini batch, a separate set of weights for each of them. So that sounds perfect. So that's how I think through these calculations.

Okay. So we can now do that multiplication, which is going to give us something of 5 by 1,500 by 2, because we end up with the maximum of our ranks.

And then we sum up over those 1,500 points and that's going to give us, now, 5 new data points.

Now something that you might notice here is that we've got a product and a sum.

And when you see a product and a sum that tells you that maybe we should use einsum.

So in this case, we've got our weight. We've got 5 by 1,500.

So let's call those i and j as for the 5 and 1,500. We've got the X is 1500 by 2. Now we want to take the product of that and that.

So we'll need to use the same name for this row. So we use j again.

Okay. And then k is the number of rows. That's the 2.

And then we want to end up with i by k. So torch.einsum() gives exactly the same result.

That's great. But you might recognize this. That's exactly the same einsum we had just before when we were doing matrix multiplication.

Oh, that is a matrix multiplication. We've just reinvented matrix multiplication using this rather nifty trick. So we could also just use that.

And so, again, this is like what I was just playing around with this morning as I started to look at this and I was thinking like, oh, can we simplify this? I don't like this kind of like messing around with axes and summing over dimensions and whatnot. And so it's nice to get things down to einsum or, better still, get them down to matrix multipliers.

It's just clearer. It's stuff that we all recognize because we use them all the time. They all work.

Performance would be pretty similar, I suspect. Okay.

So now that we've got that, we then need to do our sum.

And we've got our 5 points. This is our 5 denominators.

So we've got our numerator that we calculated up here for our weighted average.

The denominator is just the sum of the weights, remember. And so numerator divided by denominator is our answer.

So again, we've gone through every step. We've checked out all the dimensions all along the way.

So nothing's going to surprise us. Don't try and write a function like this just bang from scratch, right? You've got to drive yourself crazy.

Instead do it step by step. So here's our mean shift algorithm. Clone the data. Go through five iterations.

And now go from naught to n, batch size at a time.

So Python has something called slices. So we can create a slice of X starting at 1 up to i plus batch size, right? Unless you've gone past n, which goes use n.

And so then we just copying and pasting each of the lines of code that we had before. Actually, I just copy the cells and merge them.

Of course, I don't actually copy and paste because it's slow and boring. And there's my final step to create the new X[s]. And so notice here, s is not a single thing.

It's a slice of things. You might not have seen slice before, but this is just internally what Python's doing when you use colon.

And it's very convenient when you need to use the same slice multiple times.

Okay. So let's do that using CUDA. I would run it first without CUDA, but I mean, I've done all the steps before, so it should be fine. So pop it on the GPU and run meanshift(). And let's see how long that takes.

It takes 1 millisecond. And previously without GPU, it took 400 milliseconds. And you know, the other thing we should probably think about doing is looking at other batch sizes as well, because now we're looping over batches, right? So if we make the batch size bigger, that for loop is going to do less looping.

So what if we make that 16? Will that be any faster? I actually never tried this before.

That's interesting. It's actually slower. Huh.

There you go. Fascinating. What if it was eight? Amazing. So the big batches don't quite seem to be working so well for some reason. So I wonder if I've... Hang on. What's going on? Why is it changing how it should be? My batch size was 5. Why is it slower suddenly?

I think it's just a bit varying. That's probably the answer. So it just varies a lot. Okay.

So it doesn't seem like changing the batch size is changing much here.

So that's fine. So we'll just leave it where it was. And then check looking at the data. Oh, that looks lovely.

Oh, I see. Thank you people on YouTube pointing out that I'm passing batch size. So I actually need to put it here.

Right. So if we used a batch size of 5, no wonder it was messing up. Oh, look at that. I've totally made it slow now. 157 milliseconds.

Ha ha. Okay. 64. 13 milliseconds. All right.

Finally, that makes much more sense. 256.

1024. Okay. So the bigger, bigger is better.

And I guess we could actually do all 5,000 at once probably. Nice.

All right. Thank you YouTube friends for solving that bizarre mystery.

Okay. All right. So that's pretty great. I mean, you know, to see that we can GPU optimize a mean shift. Actually Googled for this to see if it's been done before.

And it's the kind of thing that people like write papers about.

So I think it's great that we can do it so easily with PyTorch, which is the kind of thing that previously had been considered, you know, a very challenging academic problem to solve.

So maybe you can do something similar with some of these. Now I haven't told you what these are. So part of the homework is to go read about them and learn about them. DBSCAN, funnily enough, actually is an algorithm that I accidentally invented and then discovered a year later had already been invented.

That was a long time ago. I was playing around with J, which is the successor to APL on a very old Windows phone. And I had a long plane flight and I came up with an algorithm and implemented the whole thing on my phone using J and then discovered a year later that I just invented DBSCAN.

This is actually a really cool algorithm and it's got a lot of similarities to Mean Shift.

LSH comes up all the time. So that's great. And in fact, I have a strong feeling, and I've been thinking about this for a while, that something like LSH could be used to speed this whole thing up a lot. Because if you think about it, and again, maybe this already exists, I don't know.

But if you think about it, when we did that distance calculation, the vast majority of the weights are nearly zero. And so it seems pointless to create that big, you know, kind of eventually 1,500 by 1,500 matrix, that's slow.

It would be much better if we just found the ones that were like pretty close by and just took their average. And so you want an optimized nearest neighbors, basically. And so this is an example of something that can give you a kind of a fast nearest neighbors algorithm.

Or, you know, there are things like k-d trees and octrees and stuff like that. So if you want to like, have a bonus bonus, invent a new mean shift algorithm, which picks only the closest points to avoid quadratic time. All right. So not very often you get an assignment, which is to invent a new mean shift algorithm, I guess a super super bonus. Super super bonus.

Publish a paper that describes it.

All right, you definitely get four points if you do that. We'll give you a number of points equal to the impact factor of the journal you get it published in. Okay.

So what I want to do now is move on to calculus, which for some of us may not be our favorite topic.

That's funny, Stefano wrote the einsum version here already. I didn't notice. Okay. Always ahead of his time, that guy. Let's talk about calculus.

If you're not super comfortable with derivatives and what they are and why we care, 3Blue1Brown has a wonderful series called the essence of calculus, which I strongly recommend watching.

It's just a pleasure, actually, to watch as it's everything that is on 3Blue1Brown, a pleasure to watch. And so we're not going to get into backprop today.

Instead, we're just going to have a quick chat about calculus.

Calculus refresher

Where do we start? So the good news is, just like you don't have to know much linear algebra at all, you basically just need to know about matrix multiplication.

You also don't need to know much calculus at all. Just derivatives.

So let's think about what derivatives are. So I'm going to borrow actually the same starting point that 3Blue1Brown uses in one of their videos to consider a car.

And we're going to see how far away from home it is at various time points.

Okay. So after a minute, let's say after a second, it's traveled 5 meters.

And then after 2 seconds, it's traveled 10 meters. Okay.

And after 3 seconds, you can probably guess, it's traveled 15 meters.

So there's this concept here of a, got it the wrong way around, obviously. So time, distance.

Okay. So there's this concept of location.

It's like how far have you traveled at a particular point in time? So we can look at one of these points and find out how far that car has gone.

We could also take two points and we can say where did it start at the start of those two points and where did it finish at the end of those two points.

And we can say between those two points, how much time passed and how far did they travel in 2 seconds, they traveled 10 meters.

So we could now also say, all right, well, the slope of something is rise over run.

Oopsie-Daisy, 10 meters in 2 seconds. And notice we don't just divide the numbers.

We also divide the units. We get 5 meters per second.

So, this here is now change the dimensions entirely.

We're now not looking at distance, but we're looking at speed or velocity.

And it's equal to rise over run. It's equal to the rate of change.

And what it says, really, is as time, the X axis, goes up by 1 second, what happens to the distance in meters? As one second passes, how does the number of meters change? And so maybe these aren't points at all. Maybe there's a function.

Right? It's a continuum of points. And so you can do that for the function.

So the function is a function of time. Distance is a function of time.

And so we could say, what's the slope of that function?

And we can get the slope from point A to point B using rise over run.

So from t1 to t2, the amount of time that's passed is t2 minus t1.

That's how much time has passed. Let's say this is t1, this is t2.

And the distance that they've traveled, well, they've moved from wherever they are at the end to wherever they were at the start.

So that's the change in distance divided by the change in time. Change in distance divided by change in time.

Okay. Let's say that's Y.

So another way, now the thing is, when we talk about calculus, we talk about finding a slope.

But we talk about finding a slope of something, that's often more tricky than this, right? We have slopes of things that look more like this. And we say, what's this slope? Oops, I'm terrible at drawing. Let's maybe put it over here because I'm left-handed. What's this slope?

Now what does it mean to have the idea of a velocity at an exact moment in time? It doesn't mean anything.

At an exact moment in time, you're just like, it's frozen, right? What's happening exactly now? But what you can do is you can say, well, what's the change in time between a bit before our point and a bit after our point? And what's the change in distance between a bit before our point and a bit after our point? And so you can do the same kind of rise over run thing, right? But you can make that distance between t2 and t1 smaller and smaller and smaller.

So let's rewrite this in a slightly different way. Let's call the denominator the distance between t1 plus a little bit, we'll call it d. It's that minus t1.

So this is t2, right? It's t1 plus a little bit. So we say, oh, here's t1, let's add a little bit.

And notice that when we write it this way, let's actually let's do the rest of it. So now f(t2) becomes F( t1 plus a little bit ). And this is the same.

And now notice here that t1 plus d minus t1, we can delete all that because it just comes out to d.

So this is another way of calculating the slope of our function. And as d gets smaller and smaller and smaller, we're kind of getting a triangle that's tinier and tinier and tinier. And it still makes sense, it's still that some time has passed and the car has moved, right? But it's just smaller and smaller amounts of time.

Now if you did calculus at college or at school, you might've done all this stuff messing around with limits and epsilon, delta and blah, blah, blah.

I've got really good news. It turns out you can actually just think of this d as a really small number, where d is the difference.

And so when we calculate the slope, we can write it in a slightly different way as the change in Y divided by the change in X.

This here is the change in Y and this here is the change in X.

And so in other words, this here is a very small number, a very small number.

And this here is the result in the function of changing by that very small number.

And this way of thinking about calculus is known as the calculus of infinitesimals.

And it's how Leibniz originally developed it. And it's been turned into a whole theory nowadays.

And the reason I talk about it here is because when we do calculus, you'll see me doing stuff all the time where I act like dX is a really small number.

And when I was at school, I was told I wasn't allowed to do that. I've since learned that it's totally fine to do that.

So for example, next lesson, we're going to be looking at the chain rule, which looks like this.

So dY/dX equals dY/dU times dU/dX.

And I'm just going to say, oh, these two small numbers can cancel out.

And that's why obviously they're the same thing. And that's all going to work out nicely.

So anywho, what would be very helpful would be if before the next lesson, if you're not totally up to date with your remembering all the stuff you did in high school about calculus, is watch the 3Blue1Brown course. We are not going to be looking, I don't think at all, at integration.

So you don't have to worry about that. Also we are not going to, on the whole, be doing any derivatives by hand. So for example, there are rules such as dY/dX if Y equals X squared is 2X.

These kind of rules you're not really going to have to learn because PyTorch is going to do them all for you. The one that we care about is going to be the chain rule, but we're going to learn about that next time. Okay, I hope I don't get beaten to a bloody pulp the next time I walk into a mathematician's conference. I suspect I might, but hopefully I get away with this.

I think it's safe. We'll see how we go.

Thanks everybody very much for joining me and really look forward to seeing you next time where we're going to do back propagation from scratch. We've already learned to multiply matrices, so once we've got back propagation as well, we'll be ready to train a neural network.

All right, thanks all. Bye.