CS231n Winter 2016: Lecture 10: Recurrent Neural Networks, Image Captioning, LSTM

Uh, test, test.

Yeah.

Okay, it works. Okay, good. We should get started soon. Um, so today we'll be talking about recurrent neural networks, which is one of my favorite topics, one of my favorite models to play with and put into neural networks just everywhere. They're a lot of fun to, uh, to play with. In terms of administrative items, uh, recall that your midterm is on Wednesday, uh, this Wednesday. You can tell that I'm really excited. I don't know if you guys are excited. You don't look very excited to me. Assignment 3 will be out due this Wednesday. Sorry, it will be out on Wednesday. It's due 2 weeks from now on Monday, but I think since we're shifting it, I think, to Wednesday— we planned to have released it today, but we're going to be shifting it to roughly Wednesday, so we'll probably defer the deadline for it by a few days. And Assignment 2, if I'm not mistaken, was due on Friday. So if you're using 3 late days, then you'd be handing it in today. Hopefully not too many of you are. I'm doing that. Are people done with assignment 2, or how many people are done? Okay, most of you. Okay, good. Great. Okay, so we're doing well. So currently in the class, we're talking about convolutional neural networks. Last class specifically, we looked at visualizing and understanding convolutional neural networks. So we looked at a whole bunch of pretty pictures and videos, and we had a lot of fun trying to interpret exactly what these convolutional networks are doing, what they're learning, how they're working, and so on. And so we debug this through several ways that you maybe can recall from last lecture. Actually, over the weekend I stumbled by some other visualizations that are new. I found these on Twitter, and they look really cool. And I'm not sure how people made these because there's not too much description to it, but it looks really cool. This is turtles and tarantula, and then this is chain and some kind of a dog. And so the way you do this, I think it's something like DeepDream. It's again optimization into images, but they're using a different regularizer on the image. So in this case, I think they're using a bilateral filter, which is this kind of a fancy filter. So if you put that regularization on the image, then my impression is that these are the kinds of visualizations that you achieve instead. So that looks pretty cool, but I— yeah, I'm not sure exactly what's going on. I guess we'll find out soon. Okay, so today we're going to be talking about recurrent neural networks. What's nice about recurrent neural networks is that they offer a lot of flexibility in how you wire up your neural network architectures. So normally when you're working with neural nets, you're in the case on the very left here, where you're given a fixed-sized input vector, here in red, then you process it with some hidden layers in green, and then you produce a fixed-sized output vector in blue. So say an image comes in, which is a fixed-sized image, and we're producing a fixed-sized vector, which is the class scores. With recurrent neural networks, we can actually operate over sequences. Sequences at the input, output, or both at the same time. So for example, in the case of image captioning, and we'll see some of it today, you're given a fixed-sized image, and then through a recurrent neural network, we're going to produce a sequence of words that describe the content of that image. So that's going to be a sentence that is the caption for that image. In the case of sentiment classification in NLP, for example, we're consuming a number of words in sequence, and then we're trying to classify whether the sentiment of that sentence is positive or negative. In the case of machine translation, we can have a recurrent neural network that takes us a number of words in, say, English, and then it's asked to produce a number of words in in French, for example, as a translation. So we'd feed this in, into a recurrent neural network in what we call sequence-to-sequence kind of setup. And so this recurrent network would just perform translation on arbitrary sentences in English into French. And in the last case, for example, we have video classification where you might want to imagine classifying every single frame of a video with some number of classes. But crucially, you don't want the prediction to be only a function of the current timestep, the current frame of the video, but also all the frames that have come before it in the video. And so recurrent neural networks allow you to wire up an architecture where the prediction at every single timestep is a function of all the frames that have come in up to that point. Now, even if you don't have sequences at input or output, you can still use recurrent neural networks even in the case on the very left, because you can process your fixed-sized inputs or outputs sequentially. So for example, one of my favorite examples of this is from a paper from DeepMind from a while ago where they were trying to transcribe house numbers. And instead of just having this big image feed into a ConvNet and try to classify exactly what house numbers are in there, they came up with a recurrent neural network policy where there's a small ConvNet and it's steered around the image spatially with a recurrent neural network. And so the recurrent network learned to basically read out house numbers from left to right sequentially. And so we have fixed-sized input, but we're processing it sequentially. Conversely, we can think about— this is also a well-known paper called Draw. This is a generative model. So what you're seeing here are samples from the model where it's coming up with these digit samples. But crucially, we're not just predicting these digits at a single time, but we have a recurrent neural network, and we think of the output as a canvas, and the recurrent neural network goes in and paints it over time. And so you're giving yourself more chance to actually do some computation before you actually produce your output. So it's a more powerful kind of form of processing data. Was there a question over there?

Yeah, two slides back, I didn't really understand what it meant to have two arrows going out. Does it mean that it's like— going back into the previous block as input, or—?

[Speaker:ANDREJ KARPATHY] Yeah, so every one of these arrows is kind of like a dependency in terms of— I guess we'll see specifics of exactly what this means. For now, arrows just indicate functional dependence. So things are a function of things before, and we'll go into exactly what that looks like in a bit.

OK, so—

[Speaker:AUDIENCE] So what this picture draws— no, no. Uh, this one? Yeah, what is showing here? Oh, so these are generated house numbers. Uh, so the network looked at a lot of house numbers and came up with a way of painting them. And so these are not in the training data. These are made-up house numbers, uh, from the model. None of these are actually in the training set. So these are like made up? These are made up, yeah. They look quite real, but they're actually made up from the model. So a recurrent neural network is basically this thing here a box in green, and it has a state, and it basically receives, uh, through time, it receives input vectors. So at every single timestep, we can feed in an input vector into the RNN, and it has some state internally, and then it can modify that state as a function of what it, um, what it receives at every single timestep. And so there will, uh, of course be weights inside the RNN, and so when we tune those weights, the RNN will have different behavior in terms of how its state evolves as it receives these inputs. Now usually, we can also be interested in producing an output based on the RNN's state. So we can produce these vectors on top of the RNN. But so you'll see me show pictures like this, but I just like to note that the RNN is really just the block in the middle where it has a state and it can receive vectors over time, and then we can base some prediction on top of its state in some applications. Okay. So concretely, the way this will look like is, The RNN has some kind of a state, which here I'm denoting as a vector h, and, um, but this can be also a collection of vectors or just a more general state. Um, and we're going to base it as a function of the previous hidden state at previous iteration time t minus 1 and the current input vector xt. And this is going to be done through a function which I'll call a recurrence function f, and that function will have parameters w. And so as we change those w's, uh, we're going to see that the RNN will have different behaviors. And then of course we want some specific behavior out of the RNN, So we're going to be training those weights on data. So you'll see examples of that soon. For now, I'd like you to note that the same function is used at every single time step. We have a fixed function f of weights w, and we apply that single function at every single time step. And that allows us to use the recurrent neural network on sequences of— without having to commit to the size of the sequence, because we apply the exact same function at every single time step, no matter how long the input or output sequences are. So in a specific case of a recurrent neural network, a vanilla recurrent neural network, the simplest way you can set this up and the simplest recurrence you can use is what I'll refer to as a vanilla RNN. In this case, the state of a recurrent neural network is just a single hidden state h. And then we have a recurrence formula that basically tells you how you should update your hidden state h as a function of the previous hidden state and the current input xt. And in particular, in the simplest case, we're going to have these weight matrices, W hh and W x h, and, um, they're going to basically project both the hidden state from the previous time step and the current input. And then those are going to add, and then we squish them with a tanh, and that's how we update the hidden state at time t. So this recurrence is telling you how h will change as a function of its history and also the current input at this time step. And then we can base prediction— we can base predictions on top of h, for example, using just another matrix projection on top of the hidden state. So this is the simplest concrete case in which you can wire up a neural network. Okay? So just to give you an example of how this will work, so right now I've just talked about x, H and Y in abstract forms in terms of vectors, we can actually endow these vectors with semantics. And so one of the ways in which we can, um, use a recurrent neural network is in the case of character-level language models. And this is one of my favorite ways of explaining RNNs because it's, uh, intuitive and fun to look at. So in this case, we have character-level language models, uh, using RNNs. And the way this will work is we will feed a sequence of characters into the recurrent neural network. And at every single timestep, we'll ask the recurrent neural network to predict the next character in the sequence. So we'll predict an entire distribution for what it thinks should come next in the sequence that it has seen so far. So suppose that in this very simple example, we have the training sequence "hello," and so we have a vocabulary of 4 characters that are in this dataset: H, E, L, and O. And we're going to try to get a recurrent neural network to learn to predict the next character in a sequence on this training data. And so the way this will work is we'll set up— we'll feed in every one of these characters one at a time into a recurrent neural network. So you'll see me feed in H at the first timestep, and here the x-axis is the times, uh, time. So we'll feed in H, then we'll feed in E, L, and L. And here I'm encoding characters using what we call a one-hot representation, where we just turn on the bit that corresponds to that character's order in the vocabulary. Then we're going to use the recurrence formula that I've shown you, where at every single timestep, suppose we start off with H as all zero, and then we apply this recurrence to compute the hidden state vector at every single timestep using this fixed recurrence formula. Suppose here we have only 3 numbers in the hidden state, we're going to end up with a 3-dimensional representation that basically at any point in time summarizes all the characters that have come until then. So we have— we've applied this recurrence at every single timestep, and now we're going to predict at every timestep what should be the next character in the sequence. For example, since we have 4 characters in this vocabulary, we're going to predict 4 numbers at every timestep. So for example, in the very first timestep, we fed in the letter H, and the RNN with its current setting of weights computed these unnormalized log probabilities here for what it thinks should come next. So it thinks that H is 1.0 likely to come next, it thinks that E is 2.2 likely, L is -3 likely, and O is 4.1 likely right now in terms of unnormalized log probabilities. Of course, we know that in this training sequence, we know that E should follow H. So in fact, this 2.2, which I'm showing in green, is the correct answer in this case. And so we want that to be high, and we want all these other numbers to be low. And so in every single timestep, we have basically a target for what next character should come in the sequence. And so we just want all those numbers to be high and all the other numbers to be low. And so that's of course encoded in the gradient signal of the loss function. And then that gets backpropagated through these connections. So another way to think about it is that every single timestep, we basically have a softmax classifier So every one of these is a softmax classifier over the next character, and at every single point we know what the next character should be. And so we just get all those losses flowing down from the top, and they will all flow through this graph backwards through all the arrows. We're going to get gradients on all the weight matrices, and then we'll know how to shift the matrices so that the correct probabilities are coming out of the RNN. So we'd be shaping those weights so that the correct behavior— the RNN has the correct behavior as you feed in characters. So you can imagine how we can train this over data. Are there any questions about this diagram? Go ahead.

The Wxh and the Why are the same for every arrow, or do they depend on—

Yeah, thank you. So at every single timestep, we're applying, as I mentioned, the same recurrence, the same functions always. So we have a single Wxh at every timestep. We have a single Why at every timestep, and the same Whh applied at every timestep here. So we've used Wxh, Why, Whh 4 times. In this diagram. And in backpropagation, when we backpropagate through, you'd of course have to account for that because we'll have all these gradients adding up to the same weight matrix because it has been used at multiple time steps. And this is what allows us to process variably sized inputs because at every time step we're doing the same thing, so we're not a function of the absolute amount of things in your input. Okay, question? [Speaker:AUDIENCE] What are common schemes for initializing the first page layer? What are common things for initializing the first h0? I think setting it to 0s is quite common. Set h in the beginning to 0. Good? Doesn't the order that you see the dataset matter? Does the order in which we receive the dataset matter? Yes, because— so are you asking if I plugged in these characters at a different order? No, I'm talking about words in different order. So if you see hello first or some other word. Yeah. So if you see— if this was a longer sequence, the order in this case always does matter, because at every single point in time, If you think about it functionally, like, this hidden state vector at this timestep is a function of everything that has come before it, right? And so this order just matters for as long as you're feeding it in. We're going to go through some specific examples, which I think will clarify some of these points. Okay? So let's look at a specific example. In fact, if you want to train a character-level language model, it's quite short. So I wrote a gist that you can find on GitHub. Where this is a 100-line implementation in NumPy for a character-level RNN that you can go through. I'd actually like to step through this with you so you can see concretely how we could train a recurrent neural network in practice. And so I'm going to step through this code with you now. So we're going to go through all the blocks. In the beginning, as you'll see, the only dependence here is NumPy. We're loading in some text data. So our input here is just a large collection of— a large sequence of characters, in this case, a text input.txt file. and then we get all the characters in that file, and we find all the unique characters in that file, and then we create these mapping dictionaries that map from characters to indices and from indices to characters. So we basically order our characters. So say we've read in a whole bunch of file and a whole bunch of data, and we have 100 characters or something like that, and we've ordered them in a sequence. So we associate indices to every character. Then here we're going to do some initializations. First, our hidden size is a hyperparameter, as you'll see with recurrent neural networks. So here I'm choosing it to be 100. Here we have a learning rate. Sequence length here is set to 25. This is a parameter that you'll be— you'll become aware of with RNNs. Basically, the problem is if our input data is way too large, say like millions of time steps, there's no way you can put an RNN on top of all of it because you need to maintain all of this stuff in memory so that you can do backpropagation. So in fact, we won't be able to keep all of it into mem— in memory and do backprop through all of it. So we'll go in chunks through our input data. In this case, we're going through chunks of 25 at a time. So as you'll see in a bit, um, we have this entire dataset, but we'll be going in chunks of 25 characters at a time. And at every time, we're just going to backpropagate through 25 characters at a time because we can't afford to do backpropagation for longer because we'd have to remember all that stuff. And so we're going in chunks here of 25. And then we have all these W matrices that here I'm initializing randomly and some biases. So W, X, H, H, H, and H, Y. And those are all of our parameters that we're going to train with backprop. Okay? Now, I'm going to skip over the loss function here, and I'm going to skip to the bottom of the script. Here we have a main loop, and I'm going to go through some of this main loop now. So there are some initializations here of various things to 0 in the beginning, and then we're looping forever. What we're doing here is I'm sampling a batch of data. So here is where I actually take a batch of 25 characters out of this dataset. So that's in the list inputs, And the list inputs basically just has 25 integers corresponding to the characters. The targets, as you'll see, is just all the same characters but offset by 1, because those are the indices that we're trying to predict at every single timestep. So, uh, so inputs and targets are just lists of 25 characters. Targets is offset by 1 into the future. So that's where we sample basically a batch of data. Here we, um, this is some, uh, sampling code. So at every single point in time, as we're training this RNN, We can, of course, try to generate some samples of what it currently thinks characters should actually— what these sequences look like. So the way we use character-level RNNs in test time is that we're going to seed it with some characters, and then this RNN basically always gives us a distribution over the next character in a sequence. So you can imagine sampling from it, and then you feed in the next character again, and you sample from the distribution, and you keep feeding it in. So you keep feeding all the samples into the RNN, and you can just generate arbitrary text data. So that's what this code will do, and it calls the sample function. So we'll go into that in a bit. Then here I'm calling the loss function. The loss function receives the inputs, the targets, and it receives also this hprev. hprev is short for hidden state vector from the previous chunk. So we're going in batches of 25, and we are keeping track of what is the hidden state vector at the end of your 25 letters so that we can— when we feed in the next batch, we can feed that in as the initial h at that timestep. So we're making sure that the hidden states are basically correctly propagated from batch to batch through that h_prev variable, but we're only backpropagating those 25 timesteps. Uh, so we feed that into loss function and we get the loss and the gradients and all the weight matrices and all the biases. And here I'm just printing the loss, and then here's a parameter update where the loss function told us all the gradients, and here we are actually performing the update, which you should recognize as an AdaGrad update. So I have all these cached thing— I have all these cached variables for the gradient squared, which I'm accumulating and then performing the AdaGrad update. Okay? So I'm going to go into the loss function and what that looks like now. The loss function is this block of code. It really consists of a forward and backward method. So we're computing the forward pass and then the backward pass in green. So I'll go through those two steps. So in the forward pass, you should recognize basically We get those inputs, the targets. We're iterating— we receive these 25 indices, and we're now iterating through them from 1 to 25. We create this x input vector, which is just zeros, and then we set the one-hot encoding. So whatever the index in the input is, we turn that bit on for— with a 1. So we're feeding in the character with a one-hot encoding. Then here I'm computing the recurrence formula using this equation. So h is at t. Here h is— and all these things I'm using dictionaries to keep track of everything at every single timestep. So we compute the hidden state vector and the output vector using the recurrence formula in these two lines. And then over there, I'm computing the softmax function. So I'm normalizing this so that we get probabilities. And then your loss is negative log probability of the correct answer. So that's just a softmax classifier loss over there. So that's the forward pass. And now we're going to backpropagate through the graph. So in the backward pass, we go backwards through that sequence from 25 all the back— all the way back to 1. And maybe you'll recognize— I don't know how much detail I want to go in here, but you'll recognize that I'm backpropagating through a softmax. I'm backpropagating through the activation functions. I'm backpropagating through all of it, and I'm just adding up all the gradients and all the parameters. And one thing to note here especially is that these gradients on the weight matrices like W_h_h, I'm using a plus equals because at every single timestep, all of these weight matrices get a gradient, and we need to accumulate all of it into all the weight matrices because we keep using all these weight matrices at the same— at at every timestep. And so we just backprop into them over time. And that gives us the gradients, and then we can use that in loss function, perform the parameter update. And then here we have finally a sampling function. So here is where we try to actually get the RNN to generate new text data based on what it has seen in the training data and based on the statistics of the characters and how they follow each other in the training data. So we initialize with some random character, and then we go for until we get tired. And we compute the recurrence formula, get the probability distribution, sample from that distribution, re-encode it in one-hot representation, and then we feed it in in the next time step. So we keep iterating this until we actually get a bunch of text. So is there any question over just like the rough layout of how this works? Go ahead.

So when you're doing the gradient propagation, are you bringing in So in this example, for example, would you— like, I think it says E-L-L-O at the top there.

Are you bringing in 4 of those 4 vectors and like, are you treating that as the Y for that? So you have a batch of 25, for example. That's right. And each of those Ys would be a vector that's a— you call it a one-hot? Yeah.

And so are you treating—

do you do the backpropagation with that, all those 25 Ys at once. That's right, exactly. So we have basically 25 softmax classifiers at every batch, and we backprop all of those at the same time, and they'll all add up in the connections going backwards. That's right. OK, go ahead. So we don't use regularization here? Do we use regularization here? You'll see that I probably do not. Yeah, I guess I skipped it here. But you can in general— I think sometimes I tried regularization, and I don't think it's as common to use it in recurrent nets as outside. Sometimes it gave me worse results, so sometimes I skip it. But it's kind of a hyperparameter. Go ahead. [Speaker:AUDIENCE] So when you say you choose a batch of 25, is it like 25 characters that follow one another? [Speaker:ANDREJ KARPATHY] Yeah, that's right. [Speaker:AUDIENCE] Won't there maybe be multiple words? [INAUDIBLE] [Speaker:ANDREJ KARPATHY] Yeah, that's right. So in the sequence of 25 characters, here we are very low level on the character level. And we don't actually care about words. We don't know that words exist. Is just characters, indices. So this RNN, in fact, doesn't know anything about characters or language or anything like that. It's just indices and sequences of indices, and that's what we're modeling. Um, yeah, go ahead. Is there a reason that we use a constant segment size instead of, like, using, like, spaces as delimiters, for example? Uh, can we use spaces as delimiters or something like that, uh, instead of just constant batches of 25? I think you maybe could, but then it kind of, uh, it's just, uh, you have to make a, assumptions about language. We'll see soon why you wouldn't actually want to do that, because you can plug anything into this, and we'll see that we can have a lot of fun with that. Okay. So let me show you now what we can do. We can take a whole bunch of text. We don't care where it came from. It's just a sequence of characters, and we feed it into the RNN, and we can train the RNN to, uh, create text like it. And so for example, you can take all of William Shakespeare's, uh, works. You concatenate all of it. It's just a giant sequence of characters. And you put it into the recurrent neural network, and you try to predict the next character in a sequence for William Shakespeare poems. And so when you do this, of course, in the beginning, the recurrent neural network has random parameters, so it's just producing a garble at the very end. So it's just random characters. But then when you train, the RNN will start to understand that, okay, there are actually things like spaces, there's words. It starts to experiment with quotes. It— and it basically learns some of the very short words like here, or on, and so on. And then as you train more and more, this just becomes more and more refined. And the recurrent neural network learns that when you open a quote, you should close it later, or that sentences end with a dot. It learns all of this stuff statistically just from the raw patterns without actually having to hand-code anything. And in the end, you can sample entire infinite Shakespeare based on this on the character level. So just to give you an idea about what kind of stuff comes out, alas, I think he shall become approached, and the Dane with little strain, would be attained into being never fed, and who is but a chain and subject of his death, I should not sleep. So this is the kind of stuff that you would get out of this recurrent network. Go ahead. But this could never generate a quote longer than 25 characters long, right? Because it can't remember that it opened a quote. Yeah, thank you. So you are bringing up a very subtle point, which I'd like to get back to in a bit. Yeah. OK, so we can run this on Shakespeare, but we can run this on basically anything. So we were playing with this with Justin, I think, like roughly a year ago. And so Justin took— he found this book on algebraic geometry. And this is just a large LaTeX source file. And we took that LaTeX source file for this algebraic geometry and fed it into the RNN. And the RNN can learn to basically generate mathematics. So this is a sample. So basically, this RNN just spits out LaTeX. And then we compile it. And of course, it doesn't work right away. We had to tune it a tiny bit. But basically, the RNN, after we tweaked some of the mistakes that it has made, you can compile it. And you can generate mathematics. And so you'll see that it basically creates all these proofs. It learns to put little squares at the ends of proofs. It creates lemmas, and so on. Sometimes the RNN also tries to create diagrams to varying amounts of success. And my favorite part about this is that on the top left, the proof here, it's omitted. This RNN was just lazy. But otherwise, this stuff is quite indistinguishable, I would say, from actual algebraic geometry. So let X be a nonzero scheme of X. OK, I'm not sure about that part. But otherwise, the gestalt of this looks very good. So you can throw arbitrary things at it. So I tried to find the hardest arbitrary thing that I could throw at a character-level RNN. I decided that source code is actually very difficult. So I took all of Linux source, which is just all the C code. You concatenate it, and you end up with, I think, 700 megabytes of just C code and header files. And then you just throw it into the RNN, and then it can learn to generate code. And so this is generated code from the RNN. And you can see that basically it creates function declarations. It knows about inputs. Syntactically, it makes very few mistakes. It knows about variables and sort of how to use them sometimes. It indents the code. It creates its own bogus comments. [LAUGHTER] syntactically, it's very rare to find that it would open a bracket and not close it and so on. This actually is relatively easy for the RNN to learn. And so some of the mistakes that it makes actually is that, for example, it declares some variables that it never ends up using, or it uses some variables that it never declared. And so some of this high-level stuff is still missing. But otherwise, it can do code just fine. It also knows how to recite the GNU GPL license character by character. That is learned from data. And it knows that after the GNU GPL license, there are some include files, there are some macros, and then there's some code. So that's basically what it has learned. Good? Was this done with MinCharRNN, or what was the structure you used? Yeah, so MinCharRNN that just I've shown you is very small, just a toy thing to show you what's going on. Then there's a CharRNN, which is a more kind of a mature implementation in Torch, which is just MinCharRNN scaled up and runs on GPU. And so you can play with that yourself. And so this in particular was a— We'll go into this by the end of the lecture. It's a 3-layer LSTM, and so we'll see what that means. It's a more complex kind of form of recurrent neural network. Okay? Just to give you an idea about how this works, so this is from a paper that we played with a lot with this with Justin last year, and we were basically trying to pretend that we're neuroscientists, and we threw a character-level RNN on some test text, and so the RNN is reading this text, this snippet of code, and we're looking at a specific cell in the hidden state of the RNN, and we're coloring the text based on whether or not that cell is excited or not. Okay? So you can see that many of the hidden state neurons are not very interpretable. They kind of fire on and off in kind of weird ways because they have to do— some of them have to do quite low-level, character-level stuff like how often does E come after H and stuff like that. But some of the cells are quite interpretable. So for example, we find cells like a quote detection cell, that this cell just turns on when it sees a quote, and then it stays on until the quote closes. And so this quite reliably keeps track of this, and it just comes, uh, out from backpropagation. The RNN just decides that the character-level statistics are different inside and outside of quotes, and this is a useful feature to learn. And so it dedicates some of its hidden state to keeping track of whether or not you're inside a quote. And this goes back to your question, which I wanted to point out here, that this, uh, RNN was trained on, I think, a sequence length of 100. But if you measure the, uh, the length of this quote, it's actually much more than 100. I think it's like 250. And so we worked on, uh, we only backpropagated up to 100. And so that's the only place where this cell can actually like learn itself because it wouldn't be able to spot dependencies that are much longer than that. But I think basically this seems to show that, uh, you can train this character-level detection cell as useful on sequences less than 100, and then it generalizes properly to longer sequences. So this, um, so this cell seems to work for more than 100 steps even if it was only trained— even if it was only able to spot the dependencies on less than 100. Um, this is another dataset here. This is, I think, Leo Tolstoy's War and Peace. This is— in this dataset, there's a newline character at every single— at roughly 80 characters in. So after every 80 characters roughly, there's a newline. And there's a quote— there's a line length tracking cell that we found. Where it starts off at like 1, and then it slowly decays over time. And you might imagine that a cell like this is actually very useful in predicting that newline character at the end, because this RNN needs to count 80 time steps so that it knows when a newline character is likely to come next. Okay? So there's line tracking cells. We found cells that actually respond only inside if statements. We found cells that only respond inside quotes and strings. We found cells that get more excited the deeper you nest an expression. And so all kinds of interesting cells that you can actually find inside these RNNs that completely come out just from the backpropagation. And so that's quite magical, I suppose. Go ahead. How did you figure out what each individual cell got excited by to create these visualizations? Yeah, so there's a— so in this LSTM, I think there were 2,100 cells. So you just kind of go through them. So most of them look like this. But I would say roughly 5% of them, you spot something interesting, so you just go through it manually. So you, like, turn the others off and just leave one on and see what's— Oh, no, sorry. So we are completely running the entire RNN intact, but we're only looking at a single hidden state, the firing of one single cell in the RNN. So we're running the RNN normally, but we're just kind of recording from one cell in the hidden state, if that makes sense. So this cell, just the entire RNN, I'm only visualizing one part of the hidden state, basically. There's many other hidden cells that evolved in different ways, and they're all evolving in different times, and they're all doing different things inside the RNN hidden state.

Good? Is it still single layer, or do you—

have you increased the depth to get more complex cells? Are you asking about multilayer RNNs and so on? We'll go into that in a bit. This is, I think, multilayer RNN, but you can get similar results with one layer. Good? [Speaker:AUDIENCE] How are you defining a cell turning on? [Speaker:ANDREJ KARPATHY] Yes, so these hidden cells were always between -1 and 1. They're an output of a tanh. And this is from an LSTM, which we haven't covered yet. But the firing of these cells is between -1 and 1, so that's the scale that sets this picture. OK, cool. OK, so RNNs are pretty cool, and you can actually train these sequence models over time. About roughly 1 year ago, several people have kind of realized that you can actually use this, a very neat application in the context of computer vision, to perform image captioning. So in this context, we're taking a single image and we'd like to describe it with a sequence of words, and these RNNs are very good at understanding how sequences develop over time. So in this particular model that I'm going to describe, this is actually work from roughly a year ago, happens to be my paper. I have, I have pictures from my paper, so I'm going to use those. So We are feeding a convolutional— an image into a convolutional neural network, and then you'll see that this full model is actually just made up of two modules. There's the ConvNet that is doing the processing of the image, and there's a RecurrentNet which will be very— which is very good with modeling sequences. And so if you remember my analogy from the very beginning of the course where this is kind of like playing with Lego blocks, we're going to take those two modules and stick them together. That corresponds to the arrow in between. And so what we're doing effectively here is we're conditioning this RNN generative model We're not just telling it sample text at random, but we're conditioning that generative process by the output of the convolutional network, and I'll show you exactly how that looks like. So suppose I'm going to show you what the, the forward pass of the neural net is. So suppose we have a test image and we're trying to describe it with a sequence of words. So the way this model would process the image is as follows. We take that image and we plug it into a convolutional neural network. In this case, this is a VGGNet. So we go through a whole bunch of conv, max pool, and so on until we arrive at the end. Normally at the end we have this softmax classifier which is giving you a probability distribution over, say, 1,000 categories of ImageNet. In this case we're going to actually get rid of that classifier, and instead we're going to redirect the representation at the top of the convolutional network into the recurrent neural network. So we begin the generation of the RNN with a special start, uh, vector. So, um, the input to this RNN was, I think, 300-dimensional, and this is a special 300-dimensional vector that we always plug in at the first iteration. Tells the RNN that this is the beginning of the sequence. And then we're going to perform the recurrence formula that I've shown you before for a vanilla recurrent neural network. So normally, we compute this recurrence, which we've saw already, where we compute Wxh times x plus Whh times h. And now we want to additionally condition this recurrent neural network not only on the current input and the current hidden state, which we initialize with 0, so that term goes away at the first time step. But we additionally condition just by adding w_i^h times v. And so this v is the top of the ConvNet here, and we basically have this added interaction and this added weight matrix w, which tells us how this image information merges into the very first time step of the recurrent neural network. Now, there are many ways to actually play with this recurrence and many ways to actually plug in the image into the RNN, and this is only one of them, one of the simpler ones perhaps. And at the very first time step here, this y_0 vector is the distribution over the first word in a sequence. So the way this works, you might imagine, for example, is you can see that these straw textures in a man's hat can be recognized by the convolutional network as straw-like stuff. And then through this interaction, w_i,h, it might condition the hidden state to go into a particular state where the probability of the word straw could be slightly higher. Right? So you might imagine that the straw-like textures can influence the probability of straw, so one of the numbers inside y_0, to be higher because there are straw textures in there. And so the RNN from now on has to kind of juggle two tasks. It has to predict the next char— the next word in the sequence in this case, and it has to remember the image information. So we sample from that softmax, and suppose that the most likely word that we sampled from that distribution was indeed the word straw. We would take straw and we would try to plug it in into the recurrent neural network on the bottom again. And so in this case, I think we were using word-level embeddings, so the straw Straw word is associated with a 300-dimensional vector, which we're going to learn. We're going to learn a 300-dimensional representation for every single unique word in the vocabulary. And we plug in those 300 numbers into the RNN and forward it again to get a distribution over the second word in the sequence inside y1. So we get all these probabilities. We sample from it again. Suppose that the word hat is likely now. We take hat's 300-dimensional representation, plug it in, and get the distribution over there. And then we sample again. And we sample until we sample a special end token, which is really the period at the end of the sentence. And that tells us that the RNN is now done generating. And at this point, the RNN would have described this image as a straw hat period. Okay? So the number of dimensions in this y vector is the number of words in your vocabulary plus 1 for the special end token. And we are always feeding in these 300-dimensional vectors, uh, that correspond to different words and a special start token. And then we always just backpropagate through the whole thing at a single time. So you initialize this at random, or you can initialize your VGG net with pretrained from ImageNet. And then the recurrent neural networks tell you the distributions, and then you encode the gradient, and then you backprop through the whole thing as a single model, and you just train that all jointly. And you get a captioner, image captioner. Lots of questions. OK, go ahead. Are these 300-dimensional embeddings dependent on the images used, or are they generated independently? Yeah, so these 300-dimensional embeddings They're just independent of the image. So every word has 300 numbers associated with it. How is that generated? So we're going to backpropagate into it. So you initialize it random, and then you can backpropagate into these vectors x, right? So those embeddings will shift around. They're just a parameter. Another way to think about it is it's in fact equivalent to having a one-hot representation for all the words, and then you have a giant W matrix where every single— you multiply W with that one-hot representation. And if that W has 300 output size, then it's effectively plucking out a single row of W, which ends up being your embedding. So it's kind of equivalent. So just think of it, if you don't like those embeddings, just think of it as a one-hot representation, and you can think of it that way. Go ahead. Does the model learn to output the end token? Yes, the model learns to output the end token. What do you use to define the end token? Yeah, so in the training data, the correct sequence that we expect from the RNN is the first word, second word, third word, end. So every single training example will sort of have the special end token in it. Go ahead. In H1 and H2, are you again receiving the same output from the VGGNet, or are you passing in like a twice as big— Yeah, thank you. So the question is like where— so in this example, we're only plugging in the image at the very first time step. We're not plugging it in the other time steps. You can wire this up differently where you plug it into every single state. It turns out that actually works worse. So it actually works better if you just plug it in the very first timestep, and then the RNN has to juggle these both tasks. It has to remember about the image what it needs to remember through the RNN, and it also has to produce all these outputs, and somehow it wants to do that. There's some hand-wavy reasons I can give you after class for why that's true.

So when you train it, do you just have to basically be careful to only give it the, uh, ConvNet output when you give it the start token and then give it the subsequent tokens in the labels and then the end token and then the next image for the next ConvNet. I see. You're kind of alternating inputs in that way. Uh, not quite.

So at training time, a single instance will correspond to an image and a sequence of words. And so we would plug in those words here and we will plug in that image and we, um, yeah, so like, um, so, so at training time you have all those words plugged in on the bottom and you have the image plugged in and then you unroll this graph. And you have your losses and your backdrop. And then you can do batches of images if you're careful. And so if you have batches of images, they sometimes have different length sequences in the training data. You have to be careful with that because you have to say that, OK, I'm willing to process batches of up to 20 words maybe. And then some of those sentences will be shorter and longer. And you need to, in your code, worry about that because some sentences are longer than others. We have way too many questions. Stuff too. Go ahead.

So when we are training, do we do the training of these two separately, or it is backpropagated back to the image?

Yeah, thank you. So we backpropagate everything completely jointly, end-to-end training. So you can pre-train with ImageNet, and then you put those weights there. But then you just want to train everything jointly. And that's a big advantage, actually, because we can figure out what features to look for in order to better describe the— the images at the end. Okay. So when you train this in practice, we train this on image sentence datasets. One of the more common ones is called Microsoft COCO. So just to give you an idea of what it looks like, it's roughly 100,000 images and 5 sentence descriptions for each image. Uh, these were obtained using Amazon Mechanical Turk. So you just ask people, please give us a sentence description for an image, and you record all of it, and then that's your dataset. And so when you train this model, the kinds of, uh, results that you can expect or roughly what is kind of like this. So this is RNN describing these images. So this— it says that this is a man in black shirt playing guitar, or construction worker in orange safety vest working on the road, or two young girls are playing with Lego toy, or boy is doing backflip on a wakeboard. And of course, that's not a wakeboard, but it's close. There are also some very funny failure cases, which I also like to show. This is a young boy holding a baseball bat. This is a cat sitting on a couch with a remote control. That's a woman holding a teddy bear in front of a mirror. I'm pretty sure that the texture here probably is what hap— what made it think that it's a teddy bear. And the last one is a horse standing in the middle of a street, but there's road, so there's no horse, obviously, so I'm not sure what happened there. So this is just the simplest kind of model that came out last year. There were many people who tried to work on top of these kinds of models and make them more complex. Complex. I'd just like to give you an idea of one, uh, one model that is interesting just to get an idea of how, how people play with this basic architecture. So this is a paper from, uh, last year where if you noticed in the current model, we only feed in the image a single time, time at the beginning. And one way you can play with this is that you can actually allow the recurrent neural network to look back to the image and reference parts of the image while it's describing the wor— the, the words. So as you're generating every single word, you allow the RNN to actually make a lookup back to the image and look for different features of what it might want to describe next. And you can actually do this in a fully trainable way. So the RNN not only creates these words but also decides where to look next in the image. And so the way this works is not only does the RNN output your probability distribution of the next word in the sequence, but this ConvNet gives you this volume. So say in this case, we forwarded the ConvNet and got a 14 by 14 by 512, by 512 activation volume. And at every single timestep, you don't just emit that distribution, but you also emit a 512-dimensional vector that is kind of like a lookup key of what you want to look for next in the image. And so actually, I don't think this is what they did in the, in this particular paper, but this is one way you could wire something like this up. And so this vector is emitted from the RNN, just like a re— it's just predicted using some weights. And then this vector can be dot-producted with all these 14 by 14, uh, locations. So we do all these dot-products and we achieve— or we compute basically a 14 by 14 compatibility map. And then we put a softmax on this. So basically, uh, we normalize all of this so that it's all— you get this what we call an attention over the image. So it's a 14 by 14 probability map over what's interesting for the RNN right now in the image. And then we use this probability mask to do a weighted sum of these guys with this saliency. And so this RNN can basically emit these vectors of what it thinks is currently interesting for it. And it goes back, and you end up doing a weighted sum of different kinds of features that the LSTM wants to— or the RNN wants to look at at this point in time. And so for example, the RNN is generating stuff, and it might decide that, okay, I'd like to look for something object-like now. It emits a vector of 512 numbers of object-like stuff. It interacts with ConvNets, uh, with the ConvNet activation volume, and maybe some of the object-like regions of that ConvNet, of that activation volume, like, light up in the saliency map in this, uh, 14 by 14 array. And then you just end up basically focusing your attention on that part of the image through this, uh, uh, interaction. And so you can basically just do lookups into the image while you're describing the sentence. And so this is something we refer to as a soft attention, and we'll actually go into this in a few lectures. So we're going to cover things like this where the RNN can actually have selective attention over its inputs as it's processing the input. And so that's— so I just wanted to bring it up roughly now just to give you a preview of what that looks like. Okay. Now, if we want to make RNNs more complex, one of the ways we can do that is to stack them up in layers. So this gives you, you know, more deep stuff usually works better. So the way we stack this up, one of the ways at least you can stack recurrent neural networks, and there's many ways, but this is just one of them that people use in practice, is you can straight up just plug RNNs into each other. So the input for one RNN is the hidden— is the vector of the— the hidden state vector of the previous RNN. So in this image, we have the time axis going horizontally, and then going upwards, we have different RNNs. And so in this particular image, there are 3 separate recurrent neural networks, each with their own set of weights. And, uh, these recurrent neural networks, uh, just feed into each other. OK? And so this is all always trained jointly. There's no train first one, second, third one. It's all just a single computational graph that we backpropagate through. Now, this recurrence formula at the top, I've rewritten it slightly to make it more general. We're still doing the exact same thing as we did before. This is the same formula. We're taking a vector from below in depth and a vector from before in time. We're concatenating them and putting them through this W transformation and then squashing them with the tanh. So if you remember, if you are slightly confused about this, there's— there was a W x_h times x plus W h_h times h. You can rewrite this as a concatenation of x and h multiplied by a single matrix. All right, so it's as if I stacked x and h into a single column vector. And then I have this W matrix where basically what ends up happening is that your W x_h is the first part of this matrix. And W hh is the second part of your matrix. And so this kind of formula can be rewritten into a formula where you stack all your inputs and you have a single W transformation. So it's the same formula. Um, okay, so that's how we can stack these RNNs, and then, um, they're now indexed by both time and by layer at which they occur. Now, one way we can also make these more complex is not just by stacking them but by actually using a slightly better recurrence formula. Formula. So right now, so far, we've seen this very simple recurrence formula for the vanilla recurrent neural network. In practice, you will actually rarely ever use formula like this. A basic recurrent network is very rarely used. Instead, you'll use what we call an LSTM, or long short-term memory. So this is basically used in all the papers, uh, now. So this is the, uh, the formula you'd be using also in your projects if you were to use recurrent neural networks. What I'd like you to notice at this point is, is everything is exactly the same as with an RNN. It's just that the recurrence formula is a slightly more complex function, okay? We're still taking the hidden vector from below in depth, like your input, and from before in time, the previous hidden state. We're concatenating them, putting them through a W-transform, but now we have this, uh, more complexity in how we actually achieve the new hidden state at this point in time. So we're just being, uh, slightly more complex in how we combine the vector from below and before to actually perform the update of the hidden state. It's just a more complex formula. So we'll go into some of the details of exactly what motivates this formula and why it might be a better idea to actually use an LSTM instead of an RNN. Go ahead. Why are we suddenly switching back to sigmoids and tanh? Yeah, you'll see sigmoids and tanh. And it makes sense. Trust me. We'll go through it just right now. So if you look for LSTMs online, you can look for LSTM when you go on Wikipedia or you go to Google. Google Images, you'll find diagrams like this, which is really not helping, I think, anyone. The first time I saw LSTMs, they really scared me. Like, this one really scared me. I wasn't really sure what's going on. I understand LSTMs, and I still don't know what these two diagrams are. So— OK, so I'm going to try to break down LSTM. It's kind of a tricky thing to put into a diagram. You really have to kind of step through it. So lecture format is perfect for an LSTM. OK. So here we have the LSTM equations, and I'm going to first focus on the first part here on the top where we take these two vectors from below and from before. So x and h— h is our previous hidden state and x is the input— we map them through that transformation W. And now if both x and h are of size n, so there's n numbers in them, we're going to end up producing 4n numbers, okay, through this W matrix which is 4n by 2n. So we have these 4 n-dimensional vectors, i, f, o, and g. They're short for input, forget, output, and g— I'm not sure what that's short for. It's just g. And so the i, f, and o go through sigmoid gates, and g goes through a tanh gate. Now, the way this— let's see. So the way this actually works, the LSTM, basically the best way to think about it is— oh, one thing I forgot to mention actually in the previous slide is Normally, recurrent neural network just has the single h vector at every single time step, and LSTM actually has two vectors at every single time step, the hidden vector and this what we call c, the cell state vector. So, at every single time step, we have both h and c in parallel, and, um, and the c vector here shown in yellow. So, we basically have two vectors at every single point in space here. And what LSTMs are doing is they're basically operating over this cell state. So depending on what's before you and below you, that is your context, you end up operating over the cell state with these i, f, n, o, and g elements. And the way to think about it is— I'm going to go through a lot of this. OK. So basically the way to think about this is think of i, f, n, o as just binary, either 0 or 1. We want them to be— we want them to have an interpretation of a gate. Like, think of it as either 0s or 1s. We, of course, make them later sigmoids because we want this to be differentiable so that we can backpropagate through everything. But just think of i, f, and o as just binary things that we're computing based on our context. And then what this formula is doing here, c, you can see that based on what these gates are and what g is, we're going to end up updating this c value. And in particular, this f is called the forget gate. That will be used to shut— to reset some of the cells to 0. So, the cells are best thought of as counters, and these counters basically we can either reset them to 0 with this f interaction. This is an element-wise multiplication there. I think my laser pointer is running out of battery. That's unfortunate. So, with this f interaction, if f is 0, then you can see that will zero out a cell. So, we can reset a counter, and then we can also add to a counter. So, we can add through this interaction i times g, and since i is between 0 and 1, and g is between um, -1 and 1, we're basically adding a number between -1 and 1 to every cell. So at every single timestep, we have these counters in all the cells. We can reset these counters to 0 with the forget gate, or we can choose to add a number between -1 and 1 to every single cell. Okay? So that's how we perform the cell update. And then the hidden update ends up being a squashed cell, so tanh of c, squashed cell that is modulated by this output gate. So, only some of the cell state ends up leaking into the hidden state as modulated by this vector O. So, we only choose to reveal some of the cells into the hidden state in a learnable way there. So, there are several things to kind of highlight here. One maybe most confusing part here is that we're adding a number between -1 and 1 with i times g here, but that's kind of confusing because if we only had a g there instead, then g is already between -1 and 1. Why do we need i times g? What is that actually giving us when all we want is to increment a c by a number between -1 and 1? And so that's kind of like a subtle part about an LSTM. I think one answer is that if you think about g, it's a function of— it's a linear function of your context. No one has a laser pointer by any chance, right? OK. Oh man. So g is a function of your— g goes through a tanh. So g is a linear function of your previous context squashed by tanh. And so if we were adding just g instead of i times g, then that would be kind of like a very simple function. So by adding this i in there and having multiplicative interaction, you're actually getting a more richer function that you can actually express in terms of what we're adding to our cell state as a function of the previous previous, uh, h's. And another way to think about this is that we're basically decoupling these two concepts of how much do we want to add to a cell state, which is g, and then do we want to add to a cell state, which is i. So i is like, do we actually want this operation to go through? And g is what do we want to add? And by decoupling these two, that also maybe dynamically has some nice properties in terms of how this LSTM trains. Um, but we just end up, uh, That's like the LSTM formulas. And I'm going to actually go through this in more detail as well. But maybe I should go through it now. OK. So think about this as cells flowing through. And now the first interaction here is the f dot c. So f is an output of a sigmoid of that. And so f is basically gating your cells with a multiplicative interaction. So if f is 0, you will shut off the cell and reset the counter. This i times g part is, uh, basically giving you a comp— uh, is basically adding to the cell state. And then the cell state leaks into the hidden state, but it only leaks through a tanh, and then that gets gated by o. So the o, um, o vector can decide which parts of the cell state to actually reveal into the hidden, hidden cell. And then you'll notice that this hidden state not only goes to the next iteration of the LSTM, but it also actually flows up to higher layers because this is the hidden state vector that we actually end up plugging into further LSTMs above us or that goes into a prediction. And so when you unroll this, basically the way it looks like is kind of like this, which now I have a confusing diagram of my own. That's, I guess, where we ended up with. But you get your input vectors from below. You have your hidden state from before. The x and h determine your gates. F_i, g_n, o. They're all n-dimensional vectors, and then they end up modulating how you operate over the cell state. And the cell state can— once you actually reset some counters and once you add numbers between -1 and 1 to your counters, the cell state leaks out. Some of it leaks out in a learnable way, and then it can either go up to the prediction or it can go to the next iteration of the LSTM going forward. And so that's the— so this looks ugly, so we're going to So basically, the question that's probably on your mind is, why did we go through all of this? There's some— why does this look this particular way? I should like to note at this point that there are many variants to an LSTM, and I'll make this point by the end of the lecture. People play a lot with these equations, and we've kind of converged on this as being like a reasonable thing. But there's many little tweaks you can make to this that actually don't deteriorate your performance by a lot. You can remove some of those gates, like maybe the input and so on, you can— turns out that this 10H of C, that can be a C, and it works just fine normally. But with a 10H of C, it works slightly better sometimes. And I don't think we have very good reasons for why. And so you end up with a bit of a monster. But I think it actually kind of makes sense in terms of just these counters that can be reset to 0, or you can add small numbers between -1 and 1 to them. And so it's kind of like a nice— it's actually relatively simple. To understand exactly why this is much better than an RNN, we have to go to a slightly different, uh, picture to draw the distinction. So the recurrent neural network, it has some state vector, right? And you're operating over it, and you're completely transforming it through this recurrence formula. And so you end up changing your hidden state vector from timestep to timestep. You'll notice that the LSTM instead has these cell states flowing through. And what we're doing effectively is we're looking at the cells and some of it leaks into the hidden state. Based on the hidden state, we're deciding how to operate over the cell. And if you ignore the forget gates, then we end up basically just, uh, tweaking, uh, the cell by additive interaction here. So, um, so there's some stuff that look— that is a function of the cell state, and then whatever it is, we end up additively changing the cell state instead of just transforming it right away. So it's an additive instead of a transformative interaction or something like that. Now, this should actually remind you of something that we've already covered in the class. What does it remind you of? ResNets, right? Yeah. So in fact, like, this is basically the same thing as we saw with ResNets. So normally with a ConvNet, we're transforming the representation. ResNet has these skip connections here, and you'll see that basically ResNets have this additive interaction. So we have this x here. Now we do some computation based on x, and then we have an additive interaction with x. And so, um, that's the basic block of a ResNet, and that's in fact what happens with an LSTM as well. We have these additive interactions, uh, where here the x is basically your cell, and we go off, we do some function, and then we choose to add to this cell state. But the LSTMs, unlike ResNets, have also these forget gates, uh, that we're adding. And these forget gates can choose to shut off some parts of the signal as well. Um, but otherwise it looks very much like a ResNet. So I think it's kind of interesting that we're converging on very similar kind of looking architecture that works both in ConvNets and in recurrent neural networks, where it seems like dynamically somehow it's much nicer to actually have these additive interactions that allow you to actually backpropagate much more effectively. So to that point, think about the, the backpropagation dynamics between RNN and LSTM. Especially in the LSTM, it's very clear that if I inject some gradient signal at some time steps here, so if I inject gradient signal at the end of this diagram, then these plus interactions are just like a gradient superhighway here, right? Like, these gradients will just flow through all the add— addition interactions, right? Because addition distributes gradients equally. So if I plug in gradient at any point in time here, it's just going to flow all the way back. And then of course the gradient also flows through these, uh, f's, and they end up contributing their own gradients into the gradient flow. But you'll never end up with, uh, what we refer to with RNNs, a problem called vanishing gradients. Where these gradients just die off, go to zero as you backpropagate through. And I'll show you an example concretely of why this happens in a bit. So in an RNN, we have this vanishing gradient problem. I'll show you why that happens. In an LSTM, because of this superhighway of just additions, these gradients at every single timestep that we inject into the LSTM from above just flow through the cells, and your gradients don't end up vanishing. At this point, maybe I could take some questions. Are there any questions about what's confusing here about LSTM? And then after that, I'll go into why RNNs have vanishing gradients problem. Go ahead. Why do we want O? It makes sense we can't skip O. Yeah, so this O— you're asking about the O vector, is that important? Turns out that I think that one specifically is not super important. So there's a paper I'm going to show you. It's called An LSTM Search Space Odyssey. They really played with this. Take stuff out, put stuff in. There's also like these peephole connections you can add. So this cell state here, that can be actually put in with the hidden state vector as an input. So people really play with this architecture, and they've tried lots of iterations of exactly these equations. And what you end up with is almost everything works about equal. Some of it works slightly worse sometimes. So it's very kind of confusing in this way. I'll also show you a paper where they took— they treated these update equations as just— they built trees over the update equations, and then they did this random mutation stuff, and they tried all kinds of different graphs and updates you can have. And most of them work about— some of them break, and some of them work about the same. But nothing really does much better than an LSTM. Any other questions? One last thing? Let's go into why recurrent neural networks have terrible backward flow. I'll show you a cute video also. So this is showing the vanishing gradients problem in recurrent neural networks with respect to LSTMs. So what we're showing here is we're looking at— we're unrolling a recurrent neural network over many periods, many time steps, and then we're injecting gradient at, say, 128th time step, and we're backpropagating the gradient through the network. And we're looking at what is the gradient for, I think, the inputs to hidden matrix, one of the weight matrices at every single timestep. So remember that to actually get the full update through the batch, we actually end up adding all those gradients here. And so what's, what's, what's being shown here is that as you backprop, we've only injected gradient at 1/28th timesteps and then we do backprop back through time. And this is showing the slices of that backpropagation. And what you're seeing is that the LSTM gives you lots of gradients throughout this backpropagation. So there's lots of information that is flowing through. And this RNN just instantly dies off. That— just the gradient, we say, vanishes. It just becomes tiny numbers. There's no gradient. So in this case, I think it decays in about 8 time steps or so, like 10 time steps. And so all this gradient information that we've injected did not flow through the network. And you can't learn very long dependencies because all the correlation structure has been— just died down. And so we'll see why this happens dynamically. In a bit. There's some comments here which are also funny. This is like YouTube or something again. OK, anyways. OK, so let's look at a very simple example here where we have a recurrent neural network that I'm going to unroll for you. In this recurrent neural network, I'm not showing any inputs. we only have hidden state updates. So here I'm initializing a weight, Whh, which is the hidden state— hidden-to-hidden interaction. And I'm going to basically forward a recurrent neural network. This is a vanilla recurrent net for some t time steps. Here I'm using t 50. So what I'm doing is Whh times the previous hidden time step and then ReLU on top of that. So this is just a forward pass for an RNN ignoring any input vectors coming in. It's just Whh times h, threshold, Whh times h threshold, and so on. So that's the forward pass. And then I'm going to do backward pass here where I'm injecting a random gradient here at the last timestep. So at the 50th timestep, I inject some gradient which is random. And then I go backwards and I backprop. So when you backprop through this, right, you have to backprop through a ReLU. Here I'm using a ReLU. You have to backprop through the Whh multiply, then through ReLU, Whh multiply, and so on. And so The thing to note here is, so here I'm undoing the ReLU. Here is where I'm backpropagating through the ReLU. I'm just thresholding anything that— where the inputs were less than 0. And here I am backproping the W_hh times h operation where we actually multiply by the W_hh matrix before we do the nonlinearity. And so there's something very funky going on when you actually look at what happens to these dhs, which is the gradient on the hs. As you go backwards through time, it has a very kind of funny structure that is very worrying. As you look at how this gets chained up in the loop, what are we doing here with these two time steps?

[Speaker:AUDIENCE] Potentially taking the dot product of all zeros?

[Speaker:ANDREJ KARPATHY] Taking the dot product of all zeros. Yeah, so I think at some time steps maybe the outputs, the the ReLUs were all dead and so you may have killed it, but that's not really the issue. The more worrying issue is— well, that would be an issue as well, but I think one worrying issue that people definitely spot as well is you'll see that we're multiplying by this W_hh matrix over and over and over again. Because in the forward pass, we multiply by W_hh at every single iteration. When we backpropagate through all the hidden states, we end up backpropagating this formula, W_hh times h_s. And the backdrop turns out to actually be that you take your gradient signal and you multiply it by the W_hh matrix. And so we end up multiplying by W_hh. The gradient gets multiplied by W_hh, then thresholded, then multiplied by W_hh, thresholded. And so we end up multiplying by this matrix W_hh 50 times. And so the issue with this is that the gradient signal basically— OK, two things can happen. Like if you think about working with scalar value— suppose that these were scalars, not matrices. If I take a number that's random, and then I have a second number, and I keep multiplying the first number by the second number, so again and again and again, what does that sequence go to? [Speaker:AUDIENCE] I die. [Speaker:ANDREJ KARPATHY] So there's two cases, right? If I keep multiplying with the same number, either I die or it just goes completely— [Speaker:AUDIENCE] Go to 1. [Speaker:ANDREJ KARPATHY] Yeah. Yes, so if your second number was exactly 1. Yeah? So that's the only case where you don't actually explode. But otherwise, really bad things are happening. Either we die or we explode. And here we have matrices. We don't have a single number. But in fact, it's the same thing happens. The generalization of it happens. If the spectral radius of this WHH matrix is— which is the largest eigenvalue of that matrix— if it's greater than 1, then this gradient signal will explode. If it's lower than 1, then the gradient signal will completely die. And so basically, since the RNN has this very weird— because of this recurrence formula, we end up with this very just terrible dynamics. And it's very unstable, and it just dies or explodes. And so in practice, the way this was handled was we can control the exploding gradient. One simple hack is if your gradient is exploding, you clip it. So people actually do this in practice. It's like a very patchy solution, but if your gradient is above if it's above 5 in norm, then you clamp it to 5 element-wise or something like that. So you can do that. It's called gradient clipping. That's how you address the exploding gradient problem, and then your recurrent nets don't explode anymore. But the gradients can still vanish in a recurrent neural network, and LSTM is very good with the vanishing gradient problem because of these highways of cells that are only changed with additive interactions where the gradients just flow. They never die down if you're— because you're multiplying multiplying by the same matrix again and again or something like that. So that's roughly why these are just better dynamically. So we always use LSTMs, and we do do gradient clipping usually. So because the gradients in an LSTM can potentially explode still, but they don't usually vanish.

Go ahead. Just like you used ReLU in this RNN, do people use ReLU in LSTMs? And if they have, like, what were the results? Thank you.

So here I'm using ReLU. People sometimes use tanh in vanilla recurrent neural networks as well. Um, for LSTMs, uh, it's not clear where you would plug in, uh, it's not clear in this equation like exactly how you would plug in a ReLU and where. Uh, maybe instead of the— maybe for g, I'm not sure. Instead of the tanh. So instead of tanh, we would use g here, uh, ReLU. Uh, but then, um, so these cells would only grow in a single direction, right? So maybe then you can't actually end up, uh, making it smaller. So that's not a great idea, I suppose. Yeah. So there is basically— there's no clear way to plug in a ReLU here. So yeah. One thing I'll note is that in terms of these superhighways of gradients, this viewpoint actually breaks down when you have forget gates. Because when you have forget gates where we can forget some of these f's with a multiplicative interaction, then whenever a forget gate turns on and it kills the gradient, then of course the backward flow will stop. So these superhighways are only kind of true if you don't have any forget gates. But if you have a forget gate there, then it can kill the gradient. And so in practice, when we play with LSTMs, or we use LSTMs, I suppose, sometimes people, when they initialize the forget gate, they initialize it with a positive bias because that biases the forget gate to turn on— to be always kind of turned off, I suppose. In the beginning. So in the beginning, the gradients flow very well, and then the LSTM can learn how to shut them off if it wants to later on. So people play with that bias on that forget gate sometimes. And so the last slide here, I wanted to mention that LSTMs— yeah, many people have basically played with this quite a bit. So there's a search space odyssey paper where they try various changes to the architecture. There's a paper here that tries to do this search over a huge number of potential changes to the LSTM equations, and they did a large search and they didn't find anything that worked substantially better than just an LSTM. So, yeah. And then there's this GRU, which also is relatively actually popular, and I would actually recommend that you might want to use this. A GRU is a change on an LSTM. It also has these additive interactions, but what's nice about it is that it's a shorter, smaller formula, and it only has this single h vector. It doesn't have an h and a c. It only has an h. So implementation-wise, it's just nicer to remember just a single hidden state vector in your forward pass, not two vectors. And so it's just a smaller, simpler thing that seems to have most of the benefits of an LSTM. So it's called GRU, and it almost always works about equal with LSTM in my experience. And so you might want to use it, or you can use an LSTM. They both kind of do about the same. Summary is that RNNs are very nice, but the raw RNN does not actually work very well. So use LSTMs or GRUs instead. What's nice about them is that we're having these additive interactions that allow gradients to flow much better, and you don't get a vanishing gradient problem. We still have to worry a bit about the exploding gradient problem. So it's common to see people clip these gradients sometimes. And I would say that better, simpler architectures are really trying to understand how come— like, there's something deeper going on with connection between ResNets and LSTMs, and there's something deeper about these additive interactions that I think we're not fully understanding yet, and exactly why that works so well and which parts of it work well. And so I think we need a much better understanding, both theoretical and empirical, in the space, and it's a very wide-open area of research. And so, yeah. So it's 4:10. That's the end of the class, right? [Speaker:AUDIENCE] Last chance. Is there any— —gradient can explode, right? With an LSTM, people still clip gradients. They can, I suppose, still explode. So it's not as clear why they would, but you keep injecting gradient into the cell state. And so maybe that gradient can sometimes get larger. So it's common to clip them, but I think not as maybe important maybe as an RNN. I'm not 100% sure about that point. Good? Is there a neurological basis for LSTMs? Neurological basis. I have no idea. That would be— that's interesting. Yeah. OK, I think we should end the class here, but I'm happy to take more questions here. [Speaker:AUDIENCE] Actually, I have tried your code.