David Bau: So here.
David Bau: Great. Yes, and then it's gonna hear me. Okay, and then we'll wait for sharing and login.
David Bau: But my my proposal is this is it?
David Bau: You know, lot of people like, we're a lot of the papers that we write that we present that we read are interesting to to a broader community. And I see a lot of people posting stuff like videos on the Internet, which are probably as as this organizes, our own talks are. Sometimes we just like, you know, we're just practicing talks.
David Bau: I think that they're often better than the the stuff that's out there on Youtube. And so my suggestion is.
David Bau: let's just record ourselves. And then, if we think that there's something that we happen to have recorded
David Bau: that it might be useful out there, then then we can post these things. Does that make sense?
David Bau: And so I don't know if this this discussion will be useful.
David Bau: Let me, I'll I'll bring up the thing so that we have
David Bau: Is this visible? Got it on here? We got it here, so got it.
David Bau: Got it
David Bau: excellent! And what is this? I can't click on this because it's like screen share like, look at that. I gotta get rid of this. Get rid of this alright.
David Bau: So so we'll we'll talk about Hippo and Mamba today, maybe maybe more one than other. I'm not sure if we'll get all the way through this stuff I wanted to chat about, and we can.
David Bau: we can. Maybe possibly split this over more than one session if we don't get, and we can maybe make this interactive. So if you guys have questions and and things, and so I don't know if this will end up being useful for
David Bau: sort of video form.
David Bau: But but we'll try and we'll see how it looks. How do I make this? Oh, I can make this bigger with my Mac, okay, that's great.
David Bau: Alright. And the zoom link is my, yeah, maybe one of you guys, can
David Bau: you throw my regular zoom again?
David Bau: Yeah, okay, yeah. Do we have any other people who are waiting for?
David Bau: Hey, Sheridan, can you hear us
David Bau: share it in?
David Bau: Hey, Sheridan, are you on? There is Sheridan hit, hey? Sheridan.
David Bau: Is your audio work? Okay? Oh, wait. Okay, it's probably asking if it's okay that it's recording?
David Bau: Alright, hey, Sheridan, can you check your audio? Does it work.
Sheridan Feucht: Can you hear me?
David Bau: Okay, excellent, excellent. So yeah, if you ever want, if you ever have a question, you can just unmute and say, so. Okay.
David Bau: so here's what we're gonna talk about. So
David Bau: we're gonna talk about the hippo paper. We're gonna talk about the Mambo paper. We're gonna talk about S. 4 paper, and then one of the other papers is about 4 papers in this history, but I think to understand the papers, that there's some background which makes this a little bit unusual. So I'm gonna try to cover
David Bau: the background and give a little bit of the context.
David Bau: And then, after covering the background. Then we'll go into the specific innovations in the papers.
David Bau: and I have slides, but they're very incomplete. So we might page open
David Bau: the papers, and when we get to that part, and just look at what the results and their claims are and things like that. And there's some funny things that strike me as a little bit funny. I think I understand most of
David Bau: what's going on in them. And then some of you guys have already been implementing things around the mama model. So from a practitioner's point of view, there's a bunch of people at the table who understand things better than me.
David Bau: So especially Jaden, who's like reimplemented a bunch of the the the mama model
David Bau: for for dissecting.
David Bau: And so if we get to it, and we might, which we might not this week, but for when we get to that part, then we'd love to have you guys in sense.
David Bau: Alright. So okay, the outline is of what we really should talk about is is this
David Bau: so? Okay? So s, 4 stands for what does it stand for?
David Bau: Structured state space was as
David Bau: well. What's that extra ads for
David Bau: anyway. Sequence sequence base. What is? Do you know what it is?
Sheridan Feucht: I can see.
David Bau: Yeah, I couldn't. Whoever unmuted, I couldn't hear. But it's okay, II it's there's so there's 4 s's in it and and so we'll we'll define what a a state space model is before we get to the structured sequence business, and then it it they have. It happens to be an Lti, a linear time invariant system. We'll talk about the historical context there.
David Bau: and then, and then we'll talk about discretization. What makes Ltis fast and what the interest is here.
David Bau: Then we'll go back and we'll actually look at the papers after that background. So we'll look at the hippo paper.
David Bau: Then there's a diagonal hippo paper. Or diag, you know, there's an s. 4 paper. There's a diagonal s. 4 paper we'll talk about those.
David Bau: And then the thing that we probably don't have time for is we'll actually talk about the mama paper itself.
David Bau: And how it departs from the previous work, which we, you know I can get into. But I don't have slides. Okay.
David Bau: alright. So, okay.
David Bau: so what is a state space model?
David Bau: so this actually so, who who actually is like take, who has like an electrical engineering degree, or something like, who? Who? Yeah? You do. So you know what a state space model is. Right? It's probably how you learn convolutions.
David Bau: right? It's like, instead, like all of us know convolutions because we learned it in computer vision. Right? It's like, Oh, it's just these things where you.
David Bau: you know, learned convolutional kernels. But actually, the whole theory of convolutions
David Bau: has an older origin, and it really comes from this. And so
David Bau: so th, there's a there's a even more fundamental statement, this, but I'll I'll I'll I'll I'll start here, which is a little, a little bit in the middle
David Bau: of control theory. right? Which is.
David Bau: you often have systems that more or less look like this. You've got time series that you worry about like. what temperature is it in this room I had to go get the sweater because I'm so cold to day.
David Bau: And so and so what's going on is you've got some physics system where it's cloudy outside. Today it's cold. It's drawing the temperature down. You've got inputs and outputs. You've got the complicated dynamical system, and you have these controls. There's a thermostat on the wall.
David Bau: and it's deciding
David Bau: whether to turn on the heat or whether to turn off the heat. And so if you think of that as maybe the input to your system. Then you can try to model like the output to the system, which might be the actual temperature in the room.
David Bau: right? So there's all sorts of different systems that have these dynamical behaviors where there's some input.
David Bau: and there's some output. And it varies
David Bau: over time.
David Bau: Okay? And so and so you you could actually like model the system as a bunch of functions.
David Bau: So you could have a function
David Bau: like if I turn on the heat.
David Bau: then it's going to influence the derivative. Have a hit
David Bau: right like H could be the heat right?
David Bau: And
David Bau: and so how?
David Bau: Turning on the heat influence the derivative is like this function. B, right
David Bau: and then. Now, once I once the heat is going right. it it has.
David Bau: It has some dynamics of its own
David Bau: right, you know. Maybe it has some momentum or something like we're heating up all the objects in the room, and once they get some heat, then it's hard to cool them off again. And things like that, right? So there's there's like, there's there's an internal dynamics which is sort of represented by a like. Maybe when the room itself is hot already, then it also applies derivative to itself.
David Bau: right? That makes sense. And so
David Bau: and then maybe there's a particular thing that I worry about, like, how? What's my own personal temperature in this big heating system, like like, he could actually be a, vector, it could be. I'm actually measuring the heat and all sorts of different points in the room. And this is different dynamics, the table rooms that warms up the air and so on. But then there's a particular thing that I care about, just
David Bau: how hot am I? And that's like the output. So that's maybe an output scalar. Why, right? And so, there could be some
David Bau: third function, which is, how do I read all this heat in the room to figure out the thing that I care about
David Bau: right makes sense. So that's that's a classical
David Bau: control theory setting.
David Bau: And and yeah, so people are really worried about these kinds of things. And but here's the funny thing. So for a neural network, people.
David Bau: right, you've got this number coming in this number coming out, it seems very different from like neural network stuff.
David Bau: But actually, if you bundle a bunch of numbers together as input and a bunch of vectors, a bunch of numbers as output like, if you had
David Bau: a thousand inputs x one, through x 1,000, a thousand outputs. YY. One through what? And then you had some kind of recur anything. This looks kind of like a recurrent network.
David Bau: Right? You've got something feeding into your hidden state. H. Is not deep now. H. Is like a hidden state
David Bau: right? Something's feeding into your hidden state.
David Bau: The hidden state figures out how it's going to evolve over time. And then, when you read, want to read out the next layer so X could be input from the previous layer. Y could be output to the next layer. Right? And and this is this is kind of
David Bau: you can. You could also use this diagram to describe how a recurrent network is behaving right?
David Bau: It's just it, you know. But same kind of system. Okay? So so that's that's that's the historical
David Bau: thing. Now, when you, when you study state space models or these kind of things as an electrical engineer, the first thing they they tell you is the general case is really hard to do. And so we're gonna look at the the L Ti case. So the L. Ti. Stands for linear time, invariant
David Bau: and and one way of looking at linear time invariant is you can restrict all of these little operators that you have in this thing
David Bau: to linear operations that our time invariant. So what's like a linear operation this time invariant? It's not a general function that can take.
David Bau: you know, arbitrary computations.
David Bau: It's like a matrix.
David Bau: right? It doesn't look that is not allowed to look at what time it is right now
David Bau: is only allowed to look at the input data. and then it only is allowed to do. And a linear operation and input data to tell you that put data. So
David Bau: so what we would have here is. So if you have a scalar input X to your system like a time series, input then you're gonna expand that out to how it influences
David Bau: the derivative of your hidden state or your heat, or whatever right? Your hidden state thing here.
David Bau: And and that's a vector so it's because it's required to be linear. The the only thing you're allowed to do
David Bau: is have have, like a constant of proportionality.
David Bau: So it's like imagine, like
David Bau: the heat turns on. So the heat has these 2 states, one or 0 and a different at a different point in time state, it's either one, either one or 0, and all we get to do is say, when it's on.
David Bau: then it influences the derivative of the heat at these locations in the room. According to this, vector the heater is over in this corner. So it it. It applies a high, constant proportionality to the derivative, to the points in that corner. But it's far from those corners and proportionality is low.
David Bau: But it's just like a fixed
David Bau: factor. Right? So so this vector. That describes the fixed effect, the fixed factors of influence
David Bau: we normally call B,
David Bau: and then we have the dynamics of the system. So once you have a derivative, then you can integrate that derivative, and it gives you like, what the actual hidden state is over time, what the actual heat is in the room over time at all the different points.
David Bau: and
David Bau: and it will have some dynamics of how that heat propagates, or how the hidden state changes and evolves over time by itself.
David Bau: And that is that takes a vector as input and it takes the derivative that it that it creates as output. Both of those are vectors.
David Bau: And so that's actually a matrix. So the Dennet. But it's but we're requiring it to be linear. So it's just a matrix. So it's like an N by N matrix. For.
David Bau: like, how many hidden points that we're measuring?
David Bau: Okay? And then after that, then we have the scalar that we care about. And we just that's another matrix. But that's also another. Vector, it's like a row vector. Or something. Right? So we're just using that as a projection.
David Bau: And so we we take our are
David Bau: our state, our hidden state that we care about. We project it out to the scale as we want. So there's 3 vectors that we want. There's 3 matrices we want A, B and Ca is a general N, by N, matrix B is an N dimensional up projection C is an n dimensional down projection
David Bau: make sense. So that's that's like a linear time, invariant
David Bau: state space model. I've simplified a couple of the things that might they might do in engineering, where they might add a few more matrices
David Bau: make sense. But this is basic framework. Yup.
David Bau: yes, so. And the connection from there to. There is just integration. So
David Bau: so the only thing is like as time
David Bau: increments. then H is only allowed to change according to this derivative.
David Bau: So now you have this funny thing where the state space model is not constraining, what is H at time 0 or anything like that. So that's kind of up to you. That's you've got these initial conditions.
David Bau: So. But if you had, if you start your agent some given, so there's some things that are not defined by this model. But if you start in some given.
David Bau: you know initial condition, then this model will define how it all evolves from there.
David Bau: Make sense
David Bau: such as such as annotated as for
David Bau: so if you just said that at like State 0, the
David Bau: so where? The yeah, you could just call it 0 and stay 0 if you want.
David Bau: So yeah, I think when you work out the calculus and stuff, it'll turn out that you know, you can start at any given state, and then it'll be convenient to.
David Bau: you know. Have the starting state be different things depending on the situation that we're in. Yeah, so, but yeah, so, but given given any starting state this out, it evolves
David Bau: right?
David Bau: Alright. So okay, linear time. What's a big deal about making this linear. So first of all, yeah, if we make it linear, then we know what we're talking about, just some matrices. That's nice. But so linear time invariant. The reason that they teach it in class.
David Bau: in engineering class. It's it's this very generic concept.
David Bau: It's studied by Fourier as a hint.
David Bau: right? And a bunch of other people goes way back
David Bau: couple centuries
David Bau: and and and it doesn't they, not even just systems that are expressed in the way that we talked about with this A, B and C thing. So, but basically any a linear time invariant system is any system
David Bau: as a time series input and time series output. And and if you satisfy linearity and time invariance, then your linear time invariant. That's what it is. So so what is linearity? Linearity is like, okay.
David Bau: we have 2 inputs.
David Bau: right? Like, like, Oh, we have this one pattern of how the heat goes on and off we have another pattern of how the heat goes on and off
David Bau: right if you took those 2 different time series and you added them together.
David Bau: then the rest of the system, like, has some outputs in the end. Right? So the outputs will go so
David Bau: well. If the whole system is linear, then you're guaranteed that the outputs that you get. If you were to add up. The inputs
David Bau: are just the sum of the outputs
David Bau: or or scaling as well. So summing and scaling it just works linearly right? That makes sense. So that's what linear means.
David Bau: And a lot of systems in the real world are not linear like, give you push things to the edge. They they will saturate or whatever they won't behave linearly.
David Bau: And so what the physics or the engineering people will say is like, Yeah, this is for setting systems when they're in the linear domain like, you're not eating everything up to boiling point or something like that. This is just like when everything is sort of near its equilibrium.
David Bau: And you're just sort of perturbing everything nicely. Okay? And so so that's what linearity is. And time variance is the more obvious
David Bau: thing which just basically means, oh, it doesn't really matter if you ran
David Bau: your simulation starting now, or if you ran it starting tomorrow or an hour from now, the the system behaves the same. regardless of the exact time that you start. It doesn't matter what you call time 0,
David Bau: right? If you started at timeline it would behave the same.
David Bau: And so this is just saying, if you shift it by time, K, then the output will also shift by time. K,
David Bau: make sense. Okay, so that's that's a formal definition. And just from these 2 basic facts. Fourier discovered all these amazing properties that are always true
David Bau: of these systems. Oh, okay. So besides that, okay, so sorry.
David Bau: But before I talk about that one of the other things that is going on here
David Bau: is
David Bau: I should have put this slide in the other order
David Bau: is that
David Bau: it might freak us out, that we have all these derivatives. Anything cause like.
David Bau: you know, we're like computer science, people like we, we do things discreetly, especially with sequence models. It's like, there's a next token, you know.
David Bau: where is this is like? Not
David Bau: not a continuous path from below to world. Right? There's like, Hello. And then there's world right?
David Bau: And so up.
David Bau: So in practice. And actually. And this is true for all the systems that even engineers do. Now, you know, you don't measure systems like continuously, measure things discretely, and everything is digitized in the modern world. You know, all engineers are dealing with this discretization issue. So basically, a standard way of analyzing these systems is you discretize them?
David Bau: Right? And so I actually solve a little of the math of discretization here for you. So here's outlook. So basically. if you know
David Bau: that the derivative
David Bau: of H with respect to T is is some thing.
David Bau: then what you what you're going to do is you want to figure out what you really want is over some duration of time. T might be a small duration like 1 s, or something like that. We're going to discretize over 1 s
David Bau: instead of the derivative of H over T, we just want the delta.
David Bau: like, what is that age actually going to change?
David Bau: And and we can actually solve the delta by actually exactly solving this differential equation
David Bau: over time. T,
David Bau: and we just like we have to just crack open our ode or ordinary differential equation textbook to see. You know, there's like a separable differential equation or something, and figure out like how we're gonna solve this thing. But
David Bau: you can look up on Wikipedia like how how to set up the differential equation. But it basically turns into an integral.
David Bau: And and the assumption behind this is that
David Bau: in order discretize.
David Bau: you know, it's it's gonna be impossible to integrate this. If X is wiggling around
David Bau: arbitrarily during our 1 s. so that that one of the common assumptions is
David Bau: just assume that X is constant for all duration. You know what X is, and it's just constant. And so that's what we're going to represent the input X as as a constant, then they call that the 0 or old, I mean, it's just imagine it's constant for that.
David Bau: And if if you do that. then
David Bau: and that you do these integrations. So basically, you know, if you can, you like, I guess this shouldn't be too surprising. So if you didn't have the Bx.
David Bau: So the second term here is there. you know, comes from the Bx. If you didn't have the Bx. And it was just like
David Bau: partial partial of H equals, you know, a times. H.
David Bau: Then you know.
David Bau: what has this form like? What? What function has its own derivative, like E to the X has its own derivative right. E to the x is E to the x, and e to the ax is a E to the XA ax. So basically, what you'd expect is.
David Bau: you'd expect that.
David Bau: that if you were to put
David Bau: E to the you know
David Bau: a T,
David Bau: or you know, in for this thing.
David Bau: then it would it would come out. So if you put E to the A T up here in this derivative, then a would pop out, and the answer would be a times E to the A T
David Bau: that make sense.
David Bau: So for this simple case, you would get this term, and when you throw on the B thing. Then you get some other.
David Bau: You know junk that you have to chase around. You can see on Wikipedia how you can chase it around that make sense.
David Bau: So so this is basically how this works is when you go to the discrete case, then
David Bau: you get another system where the change in H over time. T is given by
David Bau: this is a matrix exponential, a funny beast. But it's also a matrix.
David Bau: right?
David Bau: And so it's its matrix. A sub T
David Bau: matrix multiplied by your hidden state
David Bau: plus this other matrix, which is, you know, just this combination of matrices from the continuous case
David Bau: multiplied by your input this is, you know, another vector here. And then it just tells you how much you should. So this this really looks like a recurrent mat. Now that makes sense. This is like how much we change H by
David Bau: right? So residual edition page.
David Bau: And it's just
David Bau: a layer of a neural network plus a vector of a neural network
David Bau: to tell us what's going on. And so and so, because everything is still a matrix after being discretized.
David Bau: it's all still linear. There's all like a linear system, right? And so
David Bau: linear systems. The nice thing about linear systems is that they're always super super simple.
David Bau: And so they'll teach you this in engineering class that you can.
David Bau: Once, if you have a linear system, you can fully understand it by understanding. It's what they call their impulse response.
David Bau: Right? So what is impulse response? So we just we'll just feed 1 one like this is like an interpretability thing. Right? So we have one probe that we're gonna use to understand the system. And here's the probe.
David Bau: You just give it a Dirac delta. We'll just give it. Give it an input
David Bau: which is is is is 0 everywhere except at one
David Bau: point in time, at like T equals 0. And then and then we wanna make sure it adds to one. So if it's if it's the continuous space
David Bau: integrates to one, if it
David Bau: if it's the discrete case that just has a value, one at that point make sense.
David Bau: And so we give it that. Input and then we just see how the system behaves after that. And so the way the output behaves. If you just give it this pulse input is called the impulse response.
David Bau: and it'll be just some weird wave of like how the internal dynamics behave after this point. and if the wave might go on for infinity. and so we'll call the impulse response, H sub f.
David Bau: And then, because of linearity. if you gave it a higher spike.
David Bau: Then the output would just be like month. Scale up. Hf.
David Bau: it writ simple, simple, right? And if you moved your spike over by a second. then then the output. Hf, we just move over by a segment.
David Bau: And then, if you had a series of values like
David Bau: 3, 2, 5, 7. Right? Then
David Bau: you the the output would have to be 3 times the H of F value, plus 2 times the H of F value shifted plus 5 times H. Of value shifted over again and
David Bau: 7 times H. And if it was there after that, that would be that that would be whole. That would be so so by only knowing H of F
David Bau: right, by only knowing this impulse response.
David Bau: you can know all of the dynamics of F
David Bau: make sense. So I don't care like the fancy
David Bau: matrices and all the stuff that you had in F,
David Bau: right? You've got this one output vector
David Bau: H of F, which describes the whole thing that make sense. That cool
David Bau: right doesn't matter how complicated the internals are.
David Bau: Right. So all Lti systems
David Bau: are super simple in the end.
David Bau: It's which is why I don't know why it's so cold in here that this problem should be solvable.
David Bau: right? These control systems things right? You should be able to make, you should be able to solve it. You should be able to project
David Bau: how like what the future behavior is. you can go forward and backwards through things you should be able to figure out when you should be able to turn on the heater. It should be able to keep the room at a steady temperature. If you want. And things like that that make sense. And it's because these systems are so
David Bau: predictable, because all you have to do is is is, add up impulse, response. And you can. You can see what the whole future looks like. Make sense. Yeah. And so what is this? Adding up all the impulse response is called
David Bau: what is called a convolution. That's what it is.
David Bau: And so, you know, a hf, the impulse response is infinite. So these convolutions are integrated over an infinite we can envision. We call it an infinite receptive field.
David Bau: right?
David Bau: But there's still there's still convolutions that we're used to. So you understand what they are.
David Bau: Okay. Now the funny thing is, once you have, like an infinite receptor field.
David Bau: then a convolution is not such a time saver
David Bau: because, you know, you might have to have an infinite sum over it. But
David Bau: it turns out that the classical way of dealing with that is, you move over to the frequency domain, and then you add up everything and multiply everything in the frequency domain. So you use fft. So do I talk. Yeah. So
David Bau: yeah. So I'll I'll so like the the key trivia
David Bau: that leads to the fft thing was like the amazing discovery of Fourier. Is this, is it? So? There's other things that you can get out of these accident.
David Bau: So let's say, your input is periodic.
David Bau: like pushing a swing. Right?
David Bau: Then we look at the output function.
David Bau: What property is it gonna have? It will also be periodic. It will be periodic with the same period. right? And then not only that.
David Bau: What if you provide input which is not only periodic but purely sinusoidal
David Bau: right? If your input is purely sinusoidal.
David Bau: then your output can't be any other shape
David Bau: other than Sinusoto. You you can't like have a Lti system where you have sinusoidal, input and you get like a square wave output or a triangle wave, or some saw 2 thing, or
David Bau: you know the sound of a. the sound of a guitar, or something like that. It like you can't. You can only get pure sine waves out.
David Bau: And and so this was like one of the big discoveries before you. It's kind of amazing. And so now it it's it's going to be a pure sign wave
David Bau: of the same frequency. But it might be a different amplitude. and it might be shifted
David Bau: in in a
David Bau: in phase right like before and backward at a time.
David Bau: But it's just another. It's like the same other than that. It's the same sine wave that you put in
David Bau: right. And so, and you and you can prove this by integrating over this convolution. Right? There's like, you know. So
David Bau: but you can. Yeah, you can prove the Sine Wave property.
David Bau: And Fourier did. And it led to Fourier analysis. So basically, since
David Bau: putting any sine wave in always leads to assign your sorted out. but only shifted.
David Bau: It means that you can fully understand a system.
David Bau: an Lti system
David Bau: by asking, how much does it amplify and shift every frequency. And so that's called the frequency response
David Bau: right? And once, you know, so the frequency response is just. you know, sort of the convolution of this with sine waves.
David Bau: And once once you know the frequency response. you can also solve for
David Bau: what the output is given any. Input so if you know the frequency.
David Bau: If you know the frequency profile of your input, like, what frequencies are in it.
David Bau: And you know the frequency response of your system. then all you have to do is go to every frequency of your input.
David Bau: and then, element-wise.
David Bau: multiply it by how much that frequency is amplified by your system
David Bau: right. and then also take a note of how much has shifted by the system. you know in phase.
David Bau: and then and then then that will give you an output, frequency, response and phase shift. and then you can re expand that out to just the output thing. But if you, if you notice what happened here
David Bau: is that once you're in the frequency domain. everything is like had them are like pointwise but the same
David Bau: you you have this one. It's actually a complex number
David Bau: that you have this one complex number for every frequency that tells you what's the amplification in phase shift.
David Bau: and you just multiply that by the the magnitude and phase shift of your input
David Bau: and you get the magnitude and phase shift of your output just like straight down the column.
David Bau: And so that's highly parallelizable once you're in the frequency domain. So
David Bau: so that that was the original idea of S 4 models. It's like, Hey. we're going to go, do? We're going to do this recurrent thing
David Bau: right? And but we're gonna make sure it's Lti. We're gonna make sure it's linear and time invariant.
David Bau: And once it's Lt. I.
David Bau: You know it might be a beast. Lti. It might be like, have these like long impulse responses or something right, but once once it's Lti.
David Bau: We can train fast, because
David Bau: what we're gonna do is we're gonna
David Bau: do the fft over all this token your hidden state data, or all this token input data. Whatever it will do. Do this fft over, it
David Bau: will trans transfer it to the, You know, frequency domain.
David Bau: And then we'll know that
David Bau: impulse response. We'll know that frequency response
David Bau: of all of our recurrent
David Bau: matrices and stuff like that will solve it. The math to get all these, all these frequency responses well oop in parallel.
David Bau: Multiply all that stuff through, and then we'll do an inverse F of T, and then go back onto the next layer. So frequency is this weird, weird thing. right? With all with the I'm sorry. So so so not frequency
David Bau: training was this weird, weird thing with the old S 4 models.
David Bau: because during training, you do this fft in the middle of it, and you do this big parallel operation that's not
David Bau: in the time domain at all, it's in the frequency domain. And then you do this inverse F of T, and then you come back out of the recurrent layer.
David Bau: and then you keep on going weird, weird, weird, right?
David Bau: But fax. and it's cool. Okay, so that was the original
David Bau: idea of why, that's why. Oh, yeah. So that's why I'm talking about here. So basically, there's actually 2 reasons. So there's
David Bau: so Ltis are fast for a couple reasons. So since their convolution, they can be paralyzed by doing this 3 step process that I talked about.
David Bau: So you can fft to go to the frequency domain.
David Bau: You can do an element-wise.
David Bau: like, you know diagonal operation in the frequency domain to amplify and, you know, attenuate and shift
David Bau: any frequency. and then you do the inverse fft to go back
David Bau: to the time or sequence domain that you're you're interested in, and every layer you do that. So so that's very parallel.
David Bau: There's a second reason, Ltis are
David Bau: fast, even if you don't do this fft trick. there's a couple nice things. If you look at the recurrence right once, once it's linear.
David Bau: there's there's one thing that keeps on moving backwards. There's this, a matrix that you keep on repeating over and over again, right? So B as input C as output no big deal. It's kind of like.
David Bau: you know, you can kind of imagine you've got this input neural network for each token or something like this as the.
David Bau: And then you got this output neural network for each token that C.
David Bau: But then there's this recurrent A which is telling you like how this hidden state
David Bau: evolves over time over between tokens, and it keeps on being repeated over and over. And if that were nonlinear.
David Bau: then that's that this this recurrent thing, if the recurrent thing were nonlinear, it would be really hard to deal with, because you'd actually have to run it sequentially to see how it behaves behaves in the future.
David Bau: Because that's how nonlinear things are you like you have to literally run them. You don't know if they're gonna have some weird behavior
David Bau: in the middle that impacts all the feature you just have to look and see right. But if it's linear.
David Bau: then it linear operations are associative. They're associative. Which means that
David Bau: you can start multiplying them at the end and go to the beginning, or you can start multiplying them beginning and going to the end. It doesn't matter what order you.
David Bau: You do the multiplication in
David Bau: right like. You won't regret having started in the wrong place or grouping things in the wrong way
David Bau: that make sense.
David Bau: So that's so, that's kind of another. So if you can group things in in weird ways, that's also very parallelizable that now you can have your Gpus work on both beginning and end at the same time, and they won't regret having
David Bau: work on it.
David Bau: because they know they can combine their results in whatever order they want later.
David Bau: make sense
David Bau: right? And so another thing is, you can like, if you're if you're repeatedly repe you know, repeating this, you can use that you should just directly exponentiate it like, oh.
David Bau: I need to know the tenth. you know. Time step. I can just take a and raise it to the tenth power.
David Bau: Just do that immediately, and no right? So there's there's a bunch of advantages from being linear. Besides, just this fft thing. But in the original S. 4 paper.
David Bau: the FFT. Thing was their. That was their go to strategy. But this these other reasons. Later
David Bau: they they make their appearance in Mamba. Okay? So that's why I mentioned it.
David Bau: Make sense.
David Bau: Okay? Yes. Last, one
David Bau: person required uniform. Gnc.
David Bau: point. That's right.
David Bau: Yeah. See? I'm giving away the game here
David Bau: and and the last slide. So basically, what? So you asked, what what is the last thing? Note that idea. Number 5 doesn't require uniform BC or a T. So
David Bau: so there's
David Bau: yeah. So there's linearity and time invariance. And and what I'm pointing out here in Number 5, or by like looking into Number 5, is that the interesting properties
David Bau: of Number 5 about the speed focus in on the linearity
David Bau: of matrix A,
David Bau: and they actually don't focus in
David Bau: on the linearity of B or C,
David Bau: and then, oddly enough, for the associative property.
David Bau: you don't even need all the all the time, Deltas T. Sub. I's to be the same.
David Bau: They could even be different
David Bau: like the first T, so one could be different from the second T sub. 2 could be different from the third T sub. 3. It doesn't matter like these linear operations are still associative.
David Bau: Right? So I'm just like checking assumptions here.
David Bau: right like Lti has a lot of gives you a lot of stuff. It makes sure that Lti make sure that B and C and A are all linear.
David Bau: And then the standard Lti system. T. Sub. I's are all uniform.
David Bau: but and and and because we've got all that stuff we can do ffts right. But the if you follow the other 4 and 5 reasons.
David Bau: The Ltis are kind of fast.
David Bau: then the interesting thing is that the reasons reasons reasons for
David Bau: depends on a being linear and uniform.
David Bau: but not B or C and reason number 5
David Bau: doesn't even depend
David Bau: on the time step being uniformed, it could actually even change that make sense. So I'm just just checking out assumptions here.
David Bau: But this is the check that the Mamba guys did that led to their paper
David Bau: that make sense.
David Bau: If a is time invariant.
David Bau: so a sub t is the notation I'm using for the discretization. So when you, when you discretize over a Delta T
David Bau: time period. Right?
David Bau: then you're you're just evolving the derivative. you know, a h over that duration of time. And so if you have a shorter time slice.
David Bau: then
David Bau: you don't. You don't evolve the derivative that long. And if you have a longer time, slice, let me just evolve along it.
David Bau: Okay.
David Bau: so no, it's just a weird thing. It's a weird observation at this point. No reason it
David Bau: we we should have a fit about it because we don't know what we're using these Lti systems for yet it's just background.
David Bau: Okay. alright.
David Bau: But but it depends on T, then it becomes like, it becomes really, really, really hard to train something. Yeah. So there's advantages you have for a being linear
David Bau: right? And there's also computational advantages for a being constant.
David Bau: So so now you've got this issue of a sub t, not so like, maybe the A
David Bau: maybe like the the whole world is easier if a sub t is constant, but
David Bau: maybe it's not so bad if A is constant and a sub t is allowed to vary.
David Bau: So that's so. So that's so. That's what Maba is gonna be about. We'll talk about that later. Okay.
David Bau: okay, yeah. And mamba, they basically,
David Bau: you know, trying to add.
as much flexibility in the system because they're trying to be transformers. Okay, so okay, so now, okay, so let's back up.
David Bau: So that's your, okay. So
David Bau: you guys.
David Bau: you're not ready to get your electrical engineering degree. Yet another question.
David Bau: yeah, cause I think, in remember paper. They also mentioned that like they could also be they could also be like running depending on the selection with respect to X could be nonlinear could be a month. But the only reason they're not doing that is because if you automatically. If you make the other team things based on the selection mechanism
David Bau: automatically, like, based on selection, we can check that. So like, I, yeah, it's good question. I think that.
David Bau: yeah. Could you? Could you have a be more data dependent than it is? Yeah, maybe you could. Ii
David Bau: I I'm not sure. I'm not sure. I think that
David Bau: you know there's this. I mean, of course, you can write down any data pants you want. The the question is, could they get the same efficiencies that they get? If A is not constant, I think that it starts to become difficult. So if you think of the
David Bau: dependencies like they're trying to paralyze this thing
David Bau: and and to paralyze it. They can't have
David Bau: things way in the future, depend on things way in the past at this bottleneck they have to be able to so like.
David Bau: if the only like. If the key thing you need is essentially a to the N.
David Bau: Then all you really need to know
David Bau: is A is a parameter, is going to be and end up going to be a trainable parameter for your system. So E, it's global. Everybody knows what a is. All the tokens know
David Bau: you have noticed, and then every token knows. II know that I'm the thousandth token.
David Bau: I know my N. Is a thousand. so if I know the parameters, and I know I'm the thousandth sopen. then I can summarize this recurrent dynamics up to my point by just raising a to the nth power a to the 1,000. Now I'm done
David Bau: right. I don't need to actually run all 1,000 steps that make sense.
David Bau: And so if A is not, if a has a data dependence where each
David Bau: different time steps, a depends on the input, data. then I think that some of the things start becoming more difficult.
David Bau: Now, one of the things that they do is so we're getting into Mamba here right? But one of the things they do is, they say, well.
David Bau: if only the time step depends on
David Bau: input in the canary.
David Bau: then you do have this data penance. It's kind of this issue. But
David Bau: the argument is that
David Bau: adding up all the time, so that you we've sort of want like we're gonna want the dynamics of a sub sum of all the time before me, or something like that, right?
David Bau: And getting a cumulative sum. Maybe we can do that pretty fast in parallel. It's another associative operation.
David Bau: highly linear, by just adding up, adding up times. and and so we could also treat that as if it was parallel, as if everybody knew it. Right. That makes sense.
David Bau: So. But but for more complicated dependencies, I'm not sure. I think that we'd have to think through it
David Bau: right? Okay, cool.
David Bau: Alright. So so Lti's are like this. Oh, we're going backwards, going forward. Let's go forward. Okay, so oh, wait. Yes.
David Bau: yes. So now we begin.
David Bau: So now we're ready. Okay? So as as historical context, as you guys all know.
David Bau: the reason that these things are interesting is because transformers are kind of sucky.
David Bau: but really slow.
David Bau: And what's what transformers are good at
David Bau: what's up
David Bau: transform? I mean. So so transformers are not psychiatry. They're quite awesome. Right? Okay? So but but here's what they're good at. What? What tri, what transformers are good at is
David Bau: They're very good at modeling long-range dependencies through this attention. Mechanism
David Bau: and and they're very good at training very fast in parallel. So so if you have, if you have all 1 million tokens of your document at a time.
David Bau: Then the way the transformers are set up is you can put all your input tokens in and you shift over by one, and you put all your output tokens there and then you can do parallel gradient descent over all of the tokens all at once, and and the
David Bau: the length of the back propagation that you have to do is just proportional
David Bau: to the number of layers that you have. and then you're done
David Bau: right. And and that's and and everything can be done in parallel one token
David Bau: at a time on a gpu, even though you had these crazy.
David Bau: you know, sort of dependencies. So there is this funny softmax attention that happens in in the middle.
David Bau: But it's designed to be this parallelized operation that you can do.
David Bau: And so so transformers are very good at training very fast.
David Bau: But where transformers suck
David Bau: is when you have to do inference right? So when you are.
David Bau: when you have your 100 tokens that came before, and you're trying to continue a chat. Gpt conversation and Chat Gp. Has to decide what to do next. Well.
David Bau: let's say.
David Bau: Chat Gp just finished calling out to some tool. It just made some graph in python. It's all done. It's coming back.
David Bau: and now it has to resume this conversation.
David Bau: and but it has to swap in. It hasn't been, you know, doing conversation for, you know, 30 s.
David Bau: Well.
David Bau: it it can't just. You can't just have a little vector that it continues on from.
David Bau: You have to remember your previous Kilobyte of text. You have to feed this whole Kilobyte in.
David Bau: and then once you feed the whole thing in, then it has to figure out how to pay attention to the whole thing, which, if it's a Kilobyte, it's like this N squared operation like it actually has to re remember, like what it was thinking
David Bau: for all of the N squared, you know, attentions that it was doing in order to like, reconstruct all the hidden states. So there's all this.
David Bau: There's all this N squared attention stuff that has to happen, and then and then, after you do that, then if you want to generate another 1,000 tokens, then you continue with this n squared nonsense. You know, you have to keep on like, you know, coming up with another token, and then looking back and seeing how now, through all these catching strategies that people use
David Bau: to try to.
David Bau: To try to make this faster. But even though you can kind of cash, it's very, very slow, and it's it's especially slow, because it takes some memory
David Bau: that make sense.
David Bau: So so transformers are fast to train.
David Bau: and slow and memory hungry in inference.
David Bau: You know, people call this like the N squared inference cost problem, right? Where the yeah, a lot of things are proportional to the square of the context window and and expense. Okay? So so the claim to fame of
David Bau: S. 4
David Bau: and Mamba, and also all these linear attention schemes. So
David Bau: I'll I'll shout out to Schmidt Uber
David Bau: of Lstm. Fame.
David Bau: we'll we'll make the claim that way back in the day they proposed linear attention.
David Bau: right and and linear attention has this advantage that it's faster. And it put for related reasons here, till for why, like LT. I's are fast
David Bau: and
David Bau: and so so there's all these kind of linearized techniques and other techniques to other crazy techniques that people have been trying
David Bau: to make transformers faster.
David Bau: Now, so the question is
David Bau: alright.
David Bau: We can make it faster, like I've given you a hint that you can make it faster by getting rid of the non-linearity by keeping it linear
David Bau: right? Keeping it. If you made it into an Lti system.
David Bau: then maybe you could use ffts or something to make it fast right?
David Bau: But then the question is, how do you make it perform well. like, what's the secret
David Bau: to like like a linear system is kind of less powerful than a nonlinear system. If you think about what Lstm did right. They have all these nonlinear gates and the nonlinear gates are supposed to be there to allow you
David Bau: to learn nonlinear rules, for like
David Bau: we're gonna remember some data for a long time. We're gonna forget some data. We're gonna pick through our data and and and and and make choices about how we carefully use this small amount of hidden state that we have.
David Bau: and
David Bau: and if if you get rid of the nonlinearities in the recurrence, then how how do you make that
David Bau: perform? Well, because, look, I'll tell you what an Lti system is. An Lti system is like when you go to the Grand canyon, and you shout into it, and then it echoes right? That's like an Lts out to us. And Hello! Hello! Hello! Hello! Right!
David Bau: And if you think about doing this. and it it has a memory. You'll remember what you said.
David Bau: but its memory is very short, and it echoes a few times.
David Bau: and then it's gone. And so Lti systems
David Bau: behave like this. They're like resonant systems
David Bau: that they. They have some memory of the past, but they tend to forget everything very quickly. And so if you have a linear recurrence
David Bau: than this this picture. that this might be a model of cognition.
David Bau: Right? It's like very bizarre
David Bau: right? It's like.
David Bau: really, are we? Are we? Gonna is it gonna be like ringing a bell or the bell? It stops ringing pretty quickly.
David Bau: Make sense.
David Bau: Okay, so so what the history of the paper is the papers are is that Google? breaks out. And oh, I said, 2022, actually in 2,020 got the wrong year here. Can I edit this edit? This
David Bau: is actually 2020
David Bau: and you know I haven't put the advisors names here. They're all Christopher Ray. But he, he wrote this paper in 2020 about
David Bau: how you could make an Lti system that actually remembers things for a long time.
David Bau: and I'll I'll work through what that is. Make sense.
David Bau: And then
David Bau: and then he wrote this nice paper, that sort of set off the craze which says we should all be doing this. That's the S. 4 paper.
David Bau: So he he really did all the work here in the hippo paper.
David Bau: and then and then people sent, you know. Then sort of the nerds read it, and then and then he thought, It's time to evangelize it. So he wrote this nice summary paper a couple of years later, soon a little bit more accessible, trying to get everybody to do this right.
David Bau: And then, soon after that
David Bau: another fellow, Gupta
David Bau: Said, this is all too complicated. You can simplify it, you you just the diagonal thing works. I you know I implement your thing. But I commented out this complicated line of code, I don't want to implement or something. It just worked anyway, right? And so so Gupta wrote his own paper. And then Google Gupta teamed up to write a nice little bit more exhausted paper on this. It's that paper. But the diagonal case.
David Bau: And then after. So that makes it faster and easier. Right?
David Bau: And then Mamba basically says, Oh.
David Bau: and that now, now that we've made everything diagonal.
David Bau: we can really simplify things, and we get rid of the f fft. We can, you know, add all sorts of other features to it, make it more, more more performant.
David Bau: and and and guess what we're going to make this bold claim that we can outperform transformers, toe to toe
David Bau: with the same number of parameters. We can get lower perplexity. We're going to beat transformers at their own game
David Bau: that make sense.
David Bau: and which is kind of like everybody's been trying to do this like all the linear attention, people and everything. But you know, it's all been really sad.
David Bau: right? It's all been. you know. We can almost get as good as transformers, and we have this advantage that we're much faster in inference.
David Bau: But this is like one of the first out there that's like, Oh, no, we're fast at inference.
David Bau: but were better than transformers interesting. And then so like, I tweeted to you guys
David Bau: so Sasha was one of the ones who's excited by this. And so he has his students working on it. And they he, he publishes paper called Mama Bite. Did you see that one that's cute?
David Bau: And they said, Oh, yeah, actually even better. If you throw away the Tokenizer.
David Bau: Then if you count Gpu, you know, sort of, you know, clock cycles. and you know, bandwidth. Mama bite like Mombasa is like
David Bau: so much more efficient that it doesn't need a tokenizer. And if you take away the Tokenizer, it performs even better for clock cycle per per per per what.
David Bau: and and then really opens up a huge gap with transformers. Now these are all academics. So they're all working with relatively small models. So I think that you know we're still waiting for, you know, maybe a bigger industrial player, somebody with a lot of Gpu to scale these models up bigger
David Bau: to see if this continues to be the case. But
David Bau: bold claims. So that's where we are. Okay as a historical context. So let let me go. Get into Hippo, and I'll show you how Hippo works. Okay? So the original
David Bau: S, for Hippo idea
David Bau: is this is that you know Ltis are kind of crummy because they forget inputs quickly.
David Bau: And but you know, we have this recurrent.
David Bau: a matrix
David Bau: which sort of remembers things. So here's like a thought experiment
David Bau: like, could you design
David Bau: in a matrix which you can like, put something into your hidden vector, H,
David Bau: and then over the and let's say, you had d dimensions in your hidden state.
David Bau: you know there are 1,000 dimensions of your hidden state. so like what's simple, simple a matrix would have the property that we could fit, put in a scalar to encode our scalar somehow in our d dimensional, hidden state vector
David Bau: and then we run the recurrence, for like a thousand steps.
David Bau: and then and then at any given step. If somebody asked at step 500, if somebody says, Hey, what was my number? 500 steps ago.
David Bau: they could directly read that out of the hidden State. or 999 steps from now somebody says, what was my
David Bau: number? 909 steps before they could read it. Now, maybe after 1,010 steps. It it doesn't know anymore. But how about for a sliding window like, could you have a thousand dimensional, vector
David Bau: how would you like? So remember.
David Bau: like your your number, for like a thousand time steps, is there a simple linear operation that would do this.
David Bau: Well, the the identity doesn't work, because
David Bau: if I stick it in the ident, let's say, my, so I have 2 things I have to figure out. There's A B vector, that I'm not writing here. And there's A, vector so I have to decide where I'm gonna put
David Bau: my number in to the vector, so so if I let's say, I put my number in in their first.
David Bau: you know, component of vector so my number is 77. Okay, I gotta remember 77. So I'll just, I just, you know.
David Bau: add 77
David Bau: to the first component of my hidden state. So thi am I in state? Start at 0? So there's 77 there, it's all the rest of Zeros
David Bau: right now the next time step happens. And somebody said, oh.
David Bau: now, my! Now my number of the day is negative. 55,
David Bau: right? Native 55.
David Bau: So if if you said the identity was my recurrence, then at the next hidden state. Now, I wouldn't have all zeroes anywhere. I have 77 in the first spot.
David Bau: and zeroes in all the rest of the spots.
David Bau: And now negative 55 comes by. And then I just have to add, linear. So I just do the same addition I did before gonna add.
David Bau: you know, negative 55 to my negative. 77. Now in the hidden state, it says 22,
David Bau: and it's all zeros. So now I've lost that information of the original 77, 55. I can't tell what happened
David Bau: that make sense.
David Bau: because it's I've entangled them. I've mixed up 77 55. I can't disentangle them anymore like that. The linearity has worked against us
David Bau: right?
David Bau: That make sense like, I don't know what happened. I don't know if it was 77, negative, 55, or it was just 0 and 22 might have been 0 in the 22. I don't know, can't tell.
David Bau: Right makes sense. So what would be a better scheme that for at least for a thousand time steps?
David Bau: You can remember every single one of the numbers.
David Bau: You have a thousand dimensions. Just put the hidden States in the in the matrix themselves.
David Bau: Yes, but how would you arrange that for your choice of B. Any choice of a I'll give you a hint
David Bau: if you know high torch. The answer is on the slide.
David Bau: But you have to know what the second argument is here
David Bau: in this diag function.
David Bau: It's not the identity.
David Bau: it's offset, it's offset, it's offset. Yeah, alright. Okay, Piper checker.
David Bau: Yes, that's that's what it is. So why would that help? So do you? And so, yeah. it's not the identity it's offset by one right off the identity. Pope. Okay, explain me. how would that help
David Bau: what happens if we take a vector
David Bau: and we multiply it made by a matrix which is not the identity, but where all the ones are off by one
David Bau: shifts it down. So if I had, like some pattern in my
David Bau: vector. And multiply it by this crazy matrix where everything is
David Bau: off the diagonal by one.
David Bau: then the output will be like well. the second one is now reading from the what the first one used to be, and the third one is reading from what the second one used to be.
David Bau: Everything I just shift
David Bau: see
David Bau: is just shift. So I can just like so might be can just like. Write in the number at the first entry of the matrix.
David Bau: and I can have this off diagonal one. and then that might. That's my recurrence, and it just shifts. And it just shifts right?
David Bau: Cool. Right? II gotta say, it's cool. Right? Alright. So yeah.
David Bau: for you. Input also.
David Bau: Yes, yeah. Yeah. So you every every time step you get a new input and then so what B is about is about encoding what's the rule for adding input to the hidden state. So like here, I've given you a very simple rule, just like stick the input in the first entry of the hidden state. So my B is actually
David Bau: the unit vector like the E sub 0 unit, vector that just says, put it in the zeroth entry
David Bau: that make sense. Yeah.
David Bau: Yeah. So that's that's how that that dynamic works.
David Bau: So
David Bau: so, yeah, oh, yeah. BI said, E, sub, one is that E sub, 0 is yeah, cause I have one based. Okay, that's fine. So be so we're gonna set B
David Bau: to the E sub, one, vector, just stick this stuff in the beginning
David Bau: that will store your value your number in the first entry of your hidden state.
David Bau: and then
David Bau: for your recurrence, you have this shifted identity that's just shifted off by one.
David Bau: and that will manage the queue every time you go ahead and say it'll shift everything down by one.
David Bau: right? There's some problems with this right, but it's it's it. But you know it has a fixed, finite window and
David Bau: stuff, but it's pretty good. This would be better then.
David Bau: you know, just a random.
David Bau: you know matrix or something right? This this thing will remember things for a long time, I mean May. Maybe we should try this instead of hippo. Hippo is more complicated than this.
David Bau: right? They didn't talk about this use case or this possibility in in the hippo paper. But to me, this sort of how you think about
David Bau: how you could use an Lti system for a memory, and it's very analogous to what they do in the pump, which would be more complicated. And we'll go through it. Make sense.
David Bau: Yeah. So this would be like an exact thing if you wanted to remember d things exactly. And you had a d dimensional, hidden state. Then you could do this. So this is kind of like the way that you might explain, like our room stuff. If you have d dimensions. You can remember. D things exactly. But if you're
David Bau: if you wanna be more aggressive about it, you could remember more than d things in exactly with a little bit of error. And so what Hippo is is about? It's kind of has this resemblance to Rome? Right? You you sort of you know.
David Bau: Thi! There's this scheme that you could use to remember. Do things exactly, but it's done in a very nice way, so that if you that they they like, generalize as well like, if you try to remember more stuff, then it'll do what it can.
David Bau: And, and, you know, introduce a little bit of error. make sense. Yeah.
David Bau: I can't remember which paper it was. But like, I think we talked about how there are different ways of remembering like we try to squeeze a set of information and like one.
David Bau: this is the this is the hippo paper. So let's go. Let's get into it. So that's so. Let's let's let's talk about what they actually do. So this is just
David Bau: like a this is a tinker toy idea of it. And so let me. So
David Bau: the the actual hippo paper.
David Bau: This is also tinker toy. Not quite hippo yet, but it's the next step, right is
David Bau: instead of it, just literally putting all the things in
David Bau: right. The hippo paper is. Let's record the time series in a polynomial.
David Bau: and I'll I'll show you how that works in the basic case, and then I'll then I'll describe to you in words how Hippo like, does it better?
David Bau: Okay.
David Bau: so there's this. So okay, so let me define like a what's called a Vandermond matrix, is there basically a Vandermond matrix? Maybe you know. Okay, so linear algebra people, maybe. Okay, that's great.
David Bau: So a Vandermod matrix is is basically a
David Bau: a matrix where?
David Bau: each column. So like where? The okay? So
David Bau: let's say, we have
David Bau: m equally spaced points
David Bau: in our little number line. Say, we're interested in the range from negative one to one or something like that. And we just like we, we don't in space. So okay, we've got all these like
David Bau: x one x 0 up to XM,
David Bau: which are just. oh, no, my, am I running into a meeting?
David Bau: Okay, I have to double check here.
David Bau: Share? Oh, no, it's just sharing it again. I hate.
David Bau: It's like it's like at 3. It's like, Oh, did I schedule something at 3, and then.
David Bau: okay.
David Bau: so if you had like, M, equally spaced points.
David Bau: then
David Bau: then that's cool. That's just like a vector, like a lens space vector, going from.
David Bau: you know, beginning to end, equally spaced.
David Bau: But what you can do is you can make this interesting matrix called the Vanderman matrix, which is, has columns which are the powers of that. Vector
David Bau: so the Zeroth power is just the first column is just all ones.
David Bau: And then the first power is just that vector by itself. But then the second column, the next column after that is just the vector squared and the vector cubed vector
David Bau: fourth. And this rate. So the Vandermond matrix is basically a matrix where you stack up as many powers of this vector as you want.
David Bau: make sense. And it doesn't need to be equally spaced. It could be any samples I've ex you chose, but you know, usually it's for demonstration purposes. For random interest. You just take equally space points
David Bau: match. and then and so down below is an example of a Vandermonde matrix. For some reason
David Bau: I found this on the apple website. I guess they have some Api that uses a Vanderbilt matrix, and they want to explain it to people. And
David Bau: Apple always has really nice illustrations. So I stole it from their website.
David Bau: And and so
David Bau: so, yeah, this is a Vandermon matrix where you, it's it's like, they took the points. 0 1, 2, 3, 4, okay. And
David Bau: now now, let's say we wanted to remember something
David Bau: using this scheme using this polynomial scheme. And so the way that I'm gonna what I'm gonna be looking for
David Bau: is, I want a polynomial
David Bau: that will remember my time series. So I might have some random time series. Negative 1, 0 5, 1427. Something like that's that's some time series, and and which I've drawn here is these Red X's. Actually
David Bau: Chad, Gp drew it for me.
David Bau: right? So I've drawn these numbers here as these Red X's right. And and what I'm looking for is I'm looking for like a you know, Fourth Degree polynomial, or something that actually cleanly
David Bau: goes through all these points to remember them
David Bau: right? And so how would I find such a polynomial? Well, I could just like, say, Okay, the algebra question and try to solve all the algebra. But but actually
David Bau: you can solve it very mechanically, using the Vandermonde matrix. So
David Bau: think about it this way. So if if the the polynomial coefficients are a 0 through a 4,
David Bau: right
David Bau: then, if II don't know what they are, but if I multiply this this vector by this Vandermon matrix.
David Bau: then it what will give me is it'll give me the expansion of a polynomial
David Bau: at each one of the points.
David Bau: So at Point x 0,
David Bau: which is 0, then
David Bau: the constant will contribute whatever a is, 0 is, and then none of the other. You know powers of X 0 contribute anything. She's all zeros right? But at at the point x, one equals one.
David Bau: Then the value comes from adding up all the coefficients. It's a 0 times, you know, right? And then a one times one, and then a one times one squared times, one cubed right? And
David Bau: and so that's that's that that corresponds to this this one row. It's kinda nice, and that will tell me
David Bau: like what I like. My goal will be to add, have have it all. Add up to this point, and have it all. Add up to this apple point here.
David Bau: If I go to the third one, it does the same thing. It gives me this and fourth one and say, it all works. I. You know this is a good way of doing polynomial evaluation I use about Vandermonde matrix. And then I just multiply by the coefficients of my polynomial as a. Vector.
David Bau: and then I can. I can get a vector out of all my polymer evaluations and all the points
David Bau: that that I sampled in my X factor
David Bau: that make sense.
David Bau: So so that's that's how to encode polynomials as matrices. And and so, if we wanted to remember this time series
David Bau: and store it in, you know, polynomial coefficients. Then we could just solve
David Bau: invert this matrix Van Orman matrix multiplied by this y, and then it gives us this vector right? Matrix. Well, vector you know, doctrine, elimination or something.
David Bau: Solve this thing? Yeah, makes sense.
David Bau: I mean, what's special about? I mean, if if he is a inversible matrix, we should be able to do that with any kind of metrics. Yeah, yeah. But you know, polynomial, I kind of know.
David Bau: Okay, yeah. So I guess the idea is
David Bau: that you know, we understand what polynomials are. And so the nice. Okay, there's a couple of nice things about this. But basically.
David Bau: once you have polynomial coefficients, then you you kind of know what it is that you're dealing with. And so if if somebody said, Hey, you know what I want to ask for, what your estimate is for your value. Halfway in between these 2 points.
David Bau: Right
David Bau: then, what would be like a good estimate for, like the value at some unmeasured point?
David Bau: Well, I don't know. You could draw a straight line between them. But that'd be like a linear interpolation.
David Bau: Why not do like the best polynomial interpolation you have? That's cool. So if we had that polynomial we could just plug in
David Bau: that number halfway between. It would give us the best polynomial, interpolant
David Bau: right? That makes sense. So so that that's kind of the attraction of the polynomial thing is that we sort of know what this thing is.
David Bau: we know, like it'll probably generalize in nice ways that might interpolate nicely at the points in between
David Bau: and and stuff like that. And so because we're gonna eventually get to this domain where we are loading more information into this polynomial than we have
David Bau: free variables. We're going to want it to generalize pretty well. right? So we wanted to like interpolate pretty well. So I think that's why
David Bau: you know, they think in terms of polynomials.
Okay.
David Bau: also. Yes, linearity. Yes. So you could have a a crazy thing. And this linear bought. But but I think that Arno was so is is linearity a constraint? But I think Arnold was pointing out that you could choose any linear operation. It doesn't need to be the Vandermonde matrix like any other V,
David Bau: you know, could kind of play this role like your your. This is a change of basis. So a Vandermonde matrix is a change of basis from the time series, space
David Bau: to the coefficient space.
David Bau: And and and I think that you know, Arab is correctly pointing out that you could change bases in a number of different ways. You don't need to change basis in this particular way. It's okay, right? But maybe other ones are just good, which I think is true. And I think that the Hipaa people will choose a different basis than the Vandermond basis. But I'm I'm showing you the Vandermond basis to try to draw the connection to polynomials, which is something that the hip major.
David Bau: that what people use.
David Bau: Okay? And it's kind of the simplest way to draw a polynomial basis is you, you, you form a Vandermine matrix. Okay?
David Bau: And so when you do this.
David Bau: If you actually solve this thing, then you you get the you invert the matrix. And this is actually the solution. A 4. Is this a 3? Is this a 0? Is this right? And then?
David Bau: And then so if you can read off the actual polynomial out of the solution, right? So this is this is the pond. Now, this is actually what we will store. We'll store the coefficients of this guy
David Bau: that make sense. And then that stores all our data points that we have.
David Bau: Okay. So okay, so here we're, I'm showing the classical presentation of Vanam matrices. Since
David Bau: really, our goal in this paper is to use
David Bau: a store time series.
David Bau: and it's gonna be X sub t, which is like the data at time. T, so here in this on this page, I'm using X for the time. But I'm gonna switch notation. I'm gonna use T for time later, because we're gonna actually use X for like values. Okay.
David Bau: makes sense. So next slide, I think we're gonna switch. Just so it's not a shocker. Okay, so
David Bau: no, let let's let's let's do our shifting thing that II showed you before.
David Bau: Right? So remember, we had this memory where we shifted over by one time step, and that was like a key thing tablet and like you can do this with polynomials, too.
David Bau: Right? So how do you can slide to the whole polynomial over by one step, and it becomes another polynomial.
David Bau: And and so, if you had the polynomial coefficients like a 0, a one a 2 from before
David Bau: right then what we want to know is we want to know what the new polynomial coefficients are. If you slide them over, if you slide over the polymer, and what does it mean to slide over polynomial. It means like we're going to evaluate it at T minus y instead of T,
David Bau: right? So our new polynomial RP. One is, gonna be whatever the old polymer was but shifted over by one time. Step
David Bau: where you know. That makes sense.
David Bau: I might have gone plus or minus reversed or something. But actually, it's nice that I put minus in here, because you can see how the sign flips work. Okay.
David Bau: so so let's evaluate this thing. So that's easy. So we just it's like high school algebra
David Bau: we throw in T minus one every time there was a T right
David Bau: make sense, and then we just evaluate upon th, that's what it looks like. So, and I've already evaluated and gathered terms. So a 0, the constant term is a 0. And then there's an a one that was multiplied by a negative one here, so negative a one.
David Bau: And then there's this, a 2 that's going to be multiplied by a positive one after the squaring, this binomial here.
David Bau: Right? And so. So this is just a sign, Flip. And then this one here is like a and then
oh, it it! There's no. So this is the linear thing. There's no linear contribution from this. But this is
David Bau: just a one. And then this is
David Bau: a 2 times. This is going to be a negative twot, right? So a negative 2 a times T,
David Bau: right? And then there's and if you go out to the third term there'll be a positive 3 a. And so on.
David Bau: and then and then this is, and then you go to the the queue, the square term, and it looks like this, and so on, anyway.
David Bau: So check it out right? So we've got a new, a 0 for, and our new polynomial. And it's what is it is the linear combination of the old coefficients.
David Bau: It's a linear combination. I'm just summing and multiplying.
David Bau: And and so is the new a one. It's also a linear combination of all the old coefficients
David Bau: and the new a 2 is also a linear combination. This shifting, this whole shifting business
David Bau: is a linear operation over the coefficients. Cool, right? Bennett.
David Bau: Still linear. Still, an Lti man.
David Bau: okay. And here's what the matrix looks like in this case, one's on the diagonal.
David Bau: It got this negative. 1, 2, 3 off the diagonal. Got some 1 3, you know.
David Bau: I know there's some. There's some.
David Bau: you know, binomial thing going on here. Right? Nicole. Yeah.
David Bau: So that's what this looks like. Okay, so let's
David Bau: so we're going to store everything in polynomial coefficients now instead of in and some other. Vector so let's call the pond enough coefficients here. This is our hidden state.
David Bau: And there's our hidden state at time. Step T, and this is our hidden state at time. Step T, plus one right. And this is like the matrix that we're going to use to evolve from one of the Hid States to the next. Let's pull the diagonal out of it, and we'll we'll write it in a certain form that it's a little bit more familiar to that previous slide. So basically.
David Bau: we have our.
our, our old hidden state. HT.
David Bau: And we have our new hidden state like moveable move forward by a timestamp. And basically, the new one is equal to the old hidden state plus
David Bau: this matrix, which I pulled out the identity and just said, Yeah, here it is right.
And you know, pluses matrix times the thing. So let's call this thing
David Bau: a sub t. And now it looks just like that recurrent state space thing that we saw
David Bau: in this figure a while ago. Right? So that's this. This thing here, Delta T. Delta h is a sub t times H, plus some way of inputting new new data
David Bau: that make sense. And so basically. you know. So we have this.
David Bau: you know, Delta delta H is a sub t plus some way of some way of adding, how do we add new data to epile?
David Bau: Right? So we're shifting everything to the right? Let's say, every time step like. So some new data comes along.
David Bau: how do we add it?
David Bau: But so here's a formula for how to add new data to a polynomial. It's fairly simple.
David Bau: So add new data. We need one special polynomial.
David Bau: the polynomial that goes to the point, new data 0 0 0, 0 0 0,
David Bau: right? 1, 0 0 0 0.
David Bau: So I just asked GPD. 4 to solve that for me. So I said, Okay, here, I need a polynomial that goes through one here and 0 0 0. By by the way, Chat Gpt
David Bau: gave me the negative of this polynomial.
David Bau: so I don't know if it would have gotten points on the exam for this one.
David Bau: but it was close enough. I just told her to negate the answer. and and this is what it, what it did. Okay? And and so this is the special polynomial
David Bau: that that for a third degree, that that has this property.
David Bau: I can express the polynomial coefficients as a little vector here
David Bau: that make sense. And that vector is what we call B sub t, so like, it's easy, like, if my input data coming in with 77 like
David Bau: gave you that example. Then this would feed in this, this vector, adding this polynomial to our.
David Bau: I don't know what what would feed in one. All I have to do is multiply this by 77, and it would feed in 77 at that point. So I just have to scale it. And so scaling the polynomial coefficients by my new data is just this multiplication here.
David Bau: Right? So this B, vector the actual coefficients that we want to add are B times. Whatever the new data is. make sense.
David Bau: See? Does that feel very physical? Now, it's like a little machine that we've made. This thing does the shift.
David Bau: And this thing does the feed new data in
David Bau: right? And that's Hippo.
David Bau: Okay? So before we go into hippo.
David Bau: which changes one or 2 things.
David Bau: How how do you read out memory after it's read after? Oh, after it's written.
David Bau: how how to read memory after it's read.
do that previously.
David Bau: Yeah, what would we do?
David Bau: So we've got this set of coefficients here. We've got this. you know. C, one c, 2 c. 3 or h, one h. 2, a. 3 where we have, we have these coefficients. And so if somebody said.
David Bau: Hey, you've done all this polynomial shifting, and you've done all this polynomial data feeding.
David Bau: And now I want to know
David Bau: what number occurred
David Bau: 50 steps ago.
David Bau: right at time equals T equals. you know, point 5 or something right? How do I know what happened at time equals TO. Equals 0 point 5 in the in that that ancient time, long time ago.
David Bau: If it's stored in my polynomial, how? How do I read that out?
David Bau: Just multiply it by like
future pulp serial pulp?
David Bau: Yeah, you take point 5. Just so that's right. So we form like the Vander like a Vandemon matrix. Click, row.
David Bau: right for my time that I'm interested in. And that's exactly what I'm doing here. So II swatched robes and columns. Okay, so, but here's Vandermon matrix column, or I should have written it the other way. Okay.
David Bau: so. But this you take our time, which might be time point 5.
David Bau: And then you say, Okay, raise it to the 0 power, the one power, the square, the cube, the fourth, and so on. We have our Bandimod row that I've drawn as a column here. Fix it later.
David Bau: and then you dot product it with your hidden state, which has all the coefficients, and then it expands out the polynomial at that point.
David Bau: evaluating the polymer plan and remembering the memory. make sense easy, Peasy. You can read out of this memory
David Bau: so you can write stuff into the memory. You can shift it, and you can read out of it. So that's why it's like a memory.
David Bau: Make sense.
David Bau: Okay? Wacky.
David Bau: Okay. yes, it is the.
David Bau: It's just the polynomial just evaluated the thing which is just a dot product with the proper evaluation vector
David Bau: that makes sense. And so like, I think in practice, if there's a neural network, you don't know if you need to know what happened at time. T equals point 5 or whatever right? So you you might not form this. You know vector intentionally, you just let gradient descent figure out what it needs to know when and then, if it, if gradient descent were to need to know what happened at time, equals 2.5. You know that it could learn these weights. There's there exists a set of weights that will tell it.
David Bau: What was there
David Bau: in the memory, and it can. It can learn how to recall it if it needs to.
David Bau: Second question.
David Bau: If you're doing top, they learn anything remotely like this.
David Bau: I don't know. I don't think anybody's left.
David Bau: They're too new. Nobody's not interp on them
David Bau: green fields
David Bau: spread out before us.
David Bau: What's your intuition with many discoveries to find I don't know. I think that
David Bau: III do I. My my prediction is that
David Bau: They will have
David Bau: things that emerged that look a lot like attention.
David Bau: So just like attention is has these cool, sparse patterns where they're going back and looking at physical.
David Bau: you know, tokens using key value query, you know, mechanics.
David Bau: and they're not looking at everything. They just pay attention to very specific things, right?
David Bau: I think that what we'll probably see is in mobile style
David Bau: networks. They'll look at the hidden State, but they won't look at the whole hidden State.
David Bau: They'll design specific projections to pay attention to
David Bau: specific sets of time series points
David Bau: and read them out, and if we kind of understand
David Bau: the encodings that they use, we might be able to read that directly, to see, like exactly what time series points they're trying to read out of the memory.
David Bau: Things like that
David Bau: is all for nothing. No, no, there's some. It's still. It's still there. I'll show you what's what's what's left of it, though.
David Bau: Okay, so the name is below.
David Bau: Bring them back there into the single, vector, which is a sit. No, the memory is a single vector, H, and then what a is is. It's a learned dynamics.
David Bau: It's like neural network weights. Think of A, B and C as neural network weights. The capital letters
David Bau: go back to the first. Oh, I'm sorry I use this A, I should have used H. Here, I'll fix this slide.
David Bau: and this should be all. Hs, is this is this editable?
David Bau: Yeah? Oh, yeah. Cause see, I said, call this H.
David Bau: I should. I should just call it H,
David Bau: see, this should all be h's, let's fix this.
David Bau: See? People gonna see me editing this on Youtube. Okay.
David Bau: so yeah, so I so sorry to use the same letter a. I just ran out of letters.
David Bau: This was a you know. It's you know why it's cause I got this from apple and apple. Want to use the letter? A, so II
David Bau: I you know, I stole this graphic from Apple, and it started a bad trend.
David Bau: I should, you know, should use C or H or something for these coefficients.
David Bau: Right? Age would be nice.
David Bau: So I fix this slide. You encoder and input sequence.
David Bau: Yes. you encode your input sequence into H,
David Bau: and then and then and then from one time step to the next. You multiply H by this matrix.
David Bau: which which will like shift it over. Yes, offset it.
David Bau: And then and then, when you want to read out what happened in an old time step. Then you need to
David Bau: expand the polynomial by basically querying the H again.
David Bau: you query your H
David Bau: by, you don't need a big matrix to query it. You just need a vector to query. and what the in the Vandermine case, the vector is just your time step
David Bau: the requiring it raised to each of the powers in each of the elements of the vector.
David Bau: I'll show you that one again in a second. So but but the shifting makes sense, right? Okay, so, and where I'm almost done with this, I'm just gonna fix this slide. Any other questions while I'm fixing this slide.
David Bau: Hey? We're almost done here. See, our boy's not too bad.
David Bau: And we we can plan. But it's okay.
David Bau: so
since they're digital breeds
David Bau: yeah so in this game, it is there's a point where it's not recoverable, because just it, this scheme is actually not a heck of a lot better than
David Bau: the
David Bau: the, the the simple scheme that we talked about at the beginning.
David Bau: it cause every time it just shifted over by one inch or something like this, and then, when it shifts it over to the end.
David Bau: Then this shifting operation?
David Bau: Well.
David Bau: what will happen to the polymer when we shift it? Oh, actually, it's good question.
David Bau: what happens to the pilot when we shift it over
previous points of sculpt.
David Bau: So it's like the exact same exact, same situations for it. If you would have been coded by the
David Bau: directly in the hidden States.
David Bau: This is a good question, though it's a good question, right? Cause like we. There's nothing that's preventing us from expanding
David Bau: fema like it.
David Bau: If if we have only
David Bau: 4 polynomial coefficients right? If we only have 4 polynomial coefficients here, then, in principle.
David Bau: the pond can only remember 4 points, and then it doesn't have capacity to remember points after that. But I'd be interested. So like if you try to expand out.
David Bau: You know
David Bau: time equals time ice one time. Nice, 2 10 x. Oh, I think that you, I think that you run out of you basically run out of
David Bau: coefficients here, because notice that
David Bau: when we look at the
David Bau: the coefficients in front of T 2
David Bau: then it only looks at H. 2 and above.
David Bau: and we look at T. Cubed. You'll only look at whatever I think that there's this triangular form. Eventually it'll shift off the end, and then it won't have any influence anymore.
David Bau: But I think that's worth checking.
David Bau: Oh, another way of looking at that you can see a physically is when I get rid of the identity here. You can see that in this particular thing it it has a form just like our
David Bau: This delta has a form just like our shift here that we had see. Stop the identity. So all the new stuff is all shifted. It's all above the diagonal.
David Bau: And so I think that
David Bau: maybe and maybe you can
David Bau: combine the reason here and see that has a limited window.
David Bau: But they do something smarter in the actual.
David Bau: Okay? Yeah, yeah, they do alright. Yes, they do. So here's the secret. So so this is all conceptually like what is underneath, Hippo. But that's
David Bau: like, but I've been able to communicate it to you in, you know, half an hour and
David Bau: And so the actual hippo paper took them like a year to develop. And so what did they do? They did it all like they pushed it all the way through, like they did all the math, and they try to make it well behaved and get good performance and stuff like that. And so, Vandermond matrices are terrible in practice. They're very ill conditioned.
David Bau: You know. They're very hard to invert. They they lose a lot of precision when you try to invert them and stuff like that. But
David Bau: but you can use a different polynomial basis
David Bau: than just the monomials
David Bau: and the way to get a well behaved polymer basis. You can just take the Vandermonde basis like the Vandermond matrix and you can just orthogonize it. You can just use QR factorization or Branch Schmitt. But you can just you just run through row wise
David Bau: and just make sure that every every row is orthogonal to all the previous rows.
David Bau: and then subtract and project away. You know whatever is not orthogonal to make that true that's called gradient orthogonalization. If you just do that
David Bau: to the Vandermon matrix, then you end up with these different polynomials.
David Bau: you get the they're called the Legendre polynomials.
David Bau: And so it's so sounds very fancy makes it makes you feel like, you know, sophisticated mathematician, we have a Legendre polynomial method.
David Bau: And but that's that is basically the same thing as this, and and and not only that.
David Bau: but they work it out
David Bau: in their appendix, all in continuous space. So I've been illustrating everything in the discrete space, because it's kind of fun to just think of, you know, finite dimensions and stuff. You can think of it very concretely, but they work out everything in the continuous space with integrals
David Bau: stuff in there. But it's it's the same.
David Bau: it's the same right?
David Bau: And then and then and then the last thing that they do is
David Bau: they have multiple, different shifting methods. So I've shown you this way of like shifting over by one time step and then letting things fall off the end of the window. Right?
David Bau: Well, they're trying to beat transformers. Not just Matcha. And that's what transformers do. They have like? A fixed context window.
David Bau: and they want to have an infinite context window. So they do develop this fixed contents. Context window kind of shift
David Bau: find out window math.
David Bau: but then they also work out different shifting strategies. like one shifting strategy. That they do is a squishing strip strategy where
David Bau: you have the pony here and now you squish the panel. so you don't shift it and forget the old types. If you just squish it by about 1% or something like that. And then you're adding your new point, and you just keep on squishing it.
David Bau: That make sense.
David Bau: Yeah. And so there's they have 2 different squishing schemes.
David Bau: One
David Bau: leads to using a slightly different basis. They call the Legare polynomials.
David Bau: which I was not familiar with before I have to admit.
David Bau: But but it leads to this exponential squishing scheme.
David Bau: and then they have a different squishing scheme, which is still a Jagger polynomials. But you have to treat them in a different way. And and it it's it's squishing. So here's their here's their pictures.
David Bau: So this is the sliding window scheme.
David Bau: where everything in the window is equally important, they're all equally weighted. And then, if you have exponential decay of the weights. then it turns out that that that gives you a different polynomial basis.
David Bau: and so is the Legare Eponymios.
David Bau: And so each of these is like you're translating
David Bau: the Polymers. They call it T. So you're translating your polynomial by one.
David Bau: and if you have an exponential decay, so you've got this infinite time horizon. You can still like. Translate your infinite time horizon by one, and has this nice property. It's infinite, but it's exponential decay.
David Bau: But then they're like, why do we have wanna have a bias against old things? Right? We want to treat the old things on on equal basis as the new things.
David Bau: so they'd like it to be sort of all rectangular in weight, like equal weight, but they'd like it to be that when you're early in the sequence.
David Bau: then all the short, brief duration of old things are all very important, and when you're late in the sequence. They want it to look like this. And so so they they call this a scaling window instead of a
David Bau: translation window. And and this is their favorite method. and they have a way of of working it out. And so it bugs me a little bit
David Bau: because they this is a weird formulation where they scale everything by one over T. By, like.
David Bau: you know, the amount of time has gone by.
David Bau: and and they work it all out with 10 t's, and the 10. T. Is like factor out.
David Bau: And then in the end. when they apply their recurrence. So see this thing here. they're applying their you know, their, their, their
David Bau: th, this, this, this thing they have, this A and the B, but the one over t are still in there. Right? So is this an LTI. Or what is this? I'm not really sure.
David Bau: Right? There's like this one over T term.
David Bau: and it is this time invariant, or is it not like I can't like?
David Bau: I haven't totally wrapped my head around it, and it bugs me a little bit. but they seem very comfortable with the idea that this is still an Lti and stuff like this. But there's this time dilation that happens
David Bau: with this case that they like. And it's important, because it's how you know.
David Bau: it's like the thing that they're advocating for it, though. right? So I don't know if it's important to understand this better or not make sense. but it bugs me a little bit. I don't a hundred per cent. Get it. Okay, so this is. there's a detail.
David Bau: but it's on 31 in the hippo paper. Aye, maybe I wish it was in the main paper, and they explained it a little better.
David Bau: But this way, it's okay.
David Bau: Okay.
David Bau: Alright. So that's but that's it. But it's still cool. And that's and so here's there. Here's like, so in the end, when they do all this math. They solve all these integrals. And it's sort of like
David Bau: this is the calculus version of doing all the algebra that you know. III put you through for shifting over everything by one, but they also similarly get matrices in the end, and I'll show you what the Hippo matrix is so this a matrix that they get end up. Getting
David Bau: is like this, like a 5 dimensional. A matrix says on the diagonal has this nice 1, 2, 3, 4, 5.
David Bau: It's it's it's really telling you how to change these.
David Bau: you know. Polynomial coefficients from one time step to the next time step. That's what the A is telling you.
David Bau: And so it's really interesting like that. you know, the last polynomial, coefficient like gets amplified by a lot. But then you have to sort of add it to all these other things.
David Bau: That come in for the other coefficient stuff like that. So there's a general form for this
David Bau: thing. Here, here is the general form, this, this, this equation, here is.
David Bau: this is this is what it is. That's the a matrix. And I just wanted to physically see what the a matrix look like. So I just I just wrote it out
David Bau: that make sense. So
David Bau: and then the B matrix is also a vector that looks like this. So here's here. Physically, the B matrix looks like this. So this is
David Bau: this is the hippo way of adding new data. So you have a new data point.
David Bau: you multiply it by. You know this, this, this vector. Of square roots. And then and then that gives you the new coefficients, and then you want to evolve the coefficients, and you just multiply it through by this thing.
David Bau: and then and then in principle
David Bau: you should be able to read out any. Here's your here's their sample data of stuff that they're trying to memorize. and then they're also they they pit themselves against an Lstm. Here, so
David Bau: they say the black is the ground. Truth.
David Bau: you know, the red is what Hippo was able to remember.
David Bau: Can I can. I scroll here? I don't know. I can scroll
David Bau: right. The the black is a ground truth. The red is what Hippo was are able to remember in the blue is what else Tam was able to remember. and I guess you know it's a really bad graph, cause. You can't see. But I think the point they're making is that the red is hiding behind all the
David Bau: the black and matches it exactly, except for a couple points here and there. right.
David Bau: whereas whereas the Lstm is really having a lot of trouble, and so they have other graphs of like the error rate and stuff like this. And so
David Bau: but they didn't put Lstm and their other graphs. Their performance looks like this. So you see, it's a good memory. That's what they're saying.
David Bau: Cool right
David Bau: is the is the arrow unified, unified through all the time. But at that that all depends on
David Bau: uniform uniform. Yeah, yeah. So this is their. This is their overtime step error plots. And they're saying just over some empirical tests, over some challenging data
David Bau: it, how how uniform the error is depends on which of these compression schemes you use.
David Bau: So their 3 favorite compression schemes are
David Bau: Legendre, T. Legendre, S. And Lagarity. Okay, so like. So
David Bau: Legendre, T is the sliding window thing.
David Bau: and so you can see the error goes like this through all the time, but then, at the end it like zooms up. and so like. My guess is that the the window is sort of ending around this point. And so when you get to the end of the window, the error rises.
David Bau: and and then same thing with the exponential window, even though in principle it has.
David Bau: like, you know, infinite time horizon it. It absorbs a lot more error when it gets near the end of the window. Anyway, I mean, it's not. It doesn't have a window, but it it sacrifices
David Bau: in in a very similar way for the standard number of parameters.
David Bau: But then, when you have this their favorite one, Alexandra S.
David Bau: Then
David Bau: there's no window. When you get to the end. It also it like it doesn't have the same sacrifice, actually does better on the older stuff. So they like this bias better when they plot the absolute errors.
David Bau: then these absolute errors are lower
David Bau: for all the time steps. So they seem to like this better. So that's why they're advocating. Yeah, this is the thing. This is. Our discovery
David Bau: makes sense. Has this weird time dilation thing. I don't like it. But
David Bau: but like everything else, I think I get everything else like how that it's how the coefficients of the time are evolving that kind of thing. Hmm.
David Bau: yeah. How do you read out? You do this. So instead of having a Vandermonde row here like this.
David Bau: so the Legendre polynomials have. This is monomials in each entry for the Vanamont case.
David Bau: The Legendre polynomials have some other polynomial that you put in each row right whatever they are.
David Bau: and and so will you just take your t of the time step that you want to read out.
David Bau: And then you form the Legendre, you know, vector of that. T evaluated each with the Legendre polynomials. And then and then you just dot product to coefficients, and it'll read it out.
David Bau: Cool, right?
David Bau: You can physically, you know, form it.
David Bau: I can close one
David Bau: so in principle like, if we wanted to.
David Bau: we could. We could have a viewer that says.
David Bau: You know, if we were if we were doing S. 4 and Hippo right. You could have a viewer that says, Here's here's like the time series that this thing memorized, and we can plot it all
David Bau: for all the time. Steps
David Bau: make sense
David Bau: when we're shifting and adding this.
David Bau: there's no, and that's enough. Thank you.
David Bau: Yeah. I'm sure there's aliasing happening. So when you shift it, when you shift it over and you switch, and you shift and stuff like that right? So
David Bau: right, I think that's where these errors come from. So like in this case, where the red line doesn't exactly match the black line.
David Bau: It must be. It must be coming from these aliasing, you know, sort of
David Bau: sort of effects
David Bau: like it doesn't have perfect resolution to remember every data point. So
David Bau: these, these, these, these things are guessed by interpolation.
David Bau: and the guesses are off by bit.
David Bau: Yeah, but like in the initial tokens, we would expect
David Bau: the shifting and adding to the
David Bau: that's right. When you have more coefficients and data points, then you would hope that this is pretty much exact.
David Bau: But then, when you have data points that start to exceed the number of coefficients you have, then it's got to be Lossy.
David Bau: Right?
David Bau: Right? Yeah.
David Bau: Yeah. And then this is sort of a picture of the best it's trying to do. Yeah.
David Bau: So now, coming like a comparison with.
David Bau: So the pro, the problem with the transfer over the end square that we need to. So here, what you're saying is we can do that in linear time.
David Bau: So so there's 2 things so that
David Bau: disadvantage I'll I'll put the disadvantages in in in in this in this way.
David Bau: So the disadvantage of a transformers is really slow in inference.
David Bau: But it's it's good. It's fast in training, right?
David Bau: And the disadvantage of these Rnns is the opposite. They're pretty fast in training and a pretty memory. Efficient training, I mean. In our training, in in inference
David Bau: and inference.
David Bau: But they're really bad to train for a couple reasons.
David Bau: right? So they're bad to train because they are hard to parallelize.
David Bau: Right? They have these long, long back prop chains that are hard to paralyze. Because if you back prop through Lstm, which has this nonlinearity, that's recurrent.
David Bau: you really have to go through the whole sequential operation for a forward pass to understand what's going on, and then you really have to reverse it through this long chain of tokens
David Bau: for the backward pass, so that the longer the chain of tokens is, the longer the back prop passes and the harder it is to parallelize. Right? So so that's so, so. Lstms are really hard to paralyze the training for
David Bau: and by moving to this linear thing. it's
David Bau: they already have this advantage because they're using this recurrent.
David Bau: So we haven't quite put it in the context of of neural networks yet, but they already have this advantage, that
David Bau: every here. I'll I'll show you the advantage here. You can see it on this picture.
David Bau: So
David Bau: every y, every output
David Bau: only depends.
David Bau: I mean, you can. You can cut the graph here right? It only depends on the current hidden state.
David Bau: Right? It doesn't depend on any of the previous hidden states. So because of that. you know, if you built this into a language model.
David Bau: Then you can predict the next token only by only knowing the current
David Bau: state. You don't need to know any previous states. So that's pretty nice. That's like. That's exactly what you want for, like efficient in France.
David Bau: So so if we already have that structure which is cool.
David Bau: the the challenge that they've been struggling with and dealing with is, how do you get training to be fast.
David Bau: right?
David Bau: And so to get training to be fast?
David Bau: They are
David Bau: that it's what's leading them to force linearity on this whole system cause they're like, Oh, if it's linear, we can paralyze it better. Maybe we can use fft or something
David Bau: right, we more exploit associativity right? And then and then we'll be able to paralyze training.
David Bau: and so so does that answer your question.
David Bau: Okay. yeah.
David Bau: The other thing that they're trying to do is they're trying to match the performance of transformers and so to match it.
David Bau: They wanna make sure that when they insert information into this linear system that it remembers it for as long as possible.
David Bau: They like they they when they ring the bell, they want that bell to keep on ringing forever
David Bau: that make sense.
David Bau: And and so that's what this.
David Bau: So they they express it. They express the ringing of the bell as a polynomial problem. And they're like, Hey. we physically can read out the history from this polynomial byte with a dot product with a linear thing.
David Bau: And so we can prove to ourselves.
David Bau: with this polynomial expression of the problem that this thing really remembers things for ever that make sense.
David Bau: Okay, let's be able to do that to me
David Bau: during infants that not as heavy as transformers, because there's no attention.
David Bau: there's no attention, which means, because there's no attention. You don't have to know any more hidden state than just one.
David Bau: And people is trying to say we can make the claim faster by legalizing them.
David Bau: The
David Bau: yes, we're gonna be just like Alice. Tm, except that
David Bau: we're going to get rid of all this fancy non-linearity stuff they have in Alice Tam. And we just make it linear. Which means that you can do things like raise raise the recurrence to a power.
David Bau: Right? It's just linear.
David Bau: right? So we can just say A to the N, if we need to.
David Bau: And and we know it's cool, or we can, or we can do the multiplication in a different order. Right?
David Bau: Yeah, yeah, we can do any. And we can associate.
David Bau: Football doesn't have to be like an independent same restaurant. I just
David Bau: in their experiment. I remember it's it. So
David Bau: Hippo doesn't decoding anything, but I think that it's important for the intuition
David Bau: that, like, if you want to decode any of the old points out of hippo, you can do it with a dot product right? Just by by the information's there. They're basically
David Bau: that that, you know, polynomial evaluation is a dot product. And so so the following things can be read out of a hippo coefficient.
David Bau: you know I have a hidden, hidden state easily.
David Bau: You can read out.
David Bau: It's
David Bau: recollection of what the polynomial value was at any time equals. T.
David Bau: Obviously, through linearity, you can read out any multiple of that that you want you. If you had multiple time steps that you wanted to read.
David Bau: you could read out that that any linear combination of multiple time steps that you wanted, you could have the average of 5 time steps if you wanted to read it out, any of these things would be a single dot product.
David Bau: Right?
David Bau: So so for for any summary statistic that you might want, which is like a linear combination of previous time step things that were memorized.
David Bau: you could learn a single neuron that reads it out. By looking at that neuron, we just take as inputs the the coefficients of the polynomial. And that single neuron, there's some weighted sum
David Bau: that will give you that.
David Bau: You know that. Read that readout
David Bau: right? That makes sense. So I think that's that's the intuition. For why?
David Bau: Why this polynomial scheme is interesting at all.
David Bau: because you can evaluate the poly like a neuron, can evaluate the polynomial in any reasonable way that you want
David Bau: is that, still having trouble to understand any perspective related.
is any of these?
David Bau: Alright! Here we go. you ready for the next paper. We have 10 min. Alright.
David Bau: So some of these things I haven't read is clear carefully, but but so but you get the hippo idea. And so the hippo got India got people excited enough to.
David Bau: They had the whole S. 4 paper. And there's this S. 4 craze and a lot of people doing things add.
David Bau: And so so the problem with hippo is
David Bau: this matrix.
David Bau: I mean.
David Bau: it's kind of it's a viral matrix, right? And there's stuff that we have to do with it. Like
David Bau: there was this thing that I brushed under the rug. Where, when you discretize this, so this is in the continuous case, right? When you discretize it, you have to say, like
David Bau: E to the A, so there's this matrix exponentiation going on. If you go look up the Wikipedia page for matrix exponentiation, you can see that it's like
David Bau: it's like a continuing research topic of how to do that. Efficiently right, you know. Like number, you know, scalar exponential scalar exponentiation is pretty easy.
David Bau: But matrix exponentiation is like, you know.
David Bau: you know, is is involved.
David Bau: And so so you've got to do a bunch of things with this hippo matrix
David Bau: and and so they as a result in Hippo, there's like a long section of
David Bau: how this is of a special form, and you don't have to do general matrix exponentiation. You can decompose this into a diagonal plus a little rank and do other things, and then you can like, do all these math operations, and but it's kind of a pain. All this stuff is a pain, and some of it is slow.
David Bau: right? And so so so here's a discovery.
David Bau: So when the original hippo paper says. you know, you can decompose the hippomatrix
David Bau: into a diagonal plus a low rank matrix.
David Bau: what they're doing is, they say, take this, take all the rows of this, and subtract some offset
David Bau: or something like this. and then you get this other form of the hippomatrix.
David Bau: which which is symmetric now. So if you subtract a certain thing from all the rows, or II forget exactly what the low rank thing they have to subtract is, it's probably somewhere in the paper.
David Bau: Oh, yeah, yeah, so. But you subtract something. Here's the low rank thing.
David Bau: Yeah, there's this, vector, if you take the vector your outer product with itself. It gives you a low rank thing that you try to subtract from
David Bau: from all the things. And if you subtract this thing.
David Bau: then you get like a symmetric matrix.
David Bau: right? And so this is like the symmetric version of the hippo matrix, which is just an offset from the original hippo matrix. And so for all of this matrix exponentiation and stuff symmetric is great. Why is symmetric? Great
David Bau: symmetric is great because is diagonalizable?
David Bau: Because you can do a symmetric eigenvalue, decomposition of the thing.
David Bau: and you know, and so here's the eigenvalue decomposition of the thing. And so
David Bau: so you can. Actually, you can actually do an eigenvalue decomposition of any matrix
David Bau: right? But the I but the V's might not be well behaved like the Eigenvectors might be like some weird, really badly behaved thing which leads to like numerical problems.
David Bau: right?
David Bau: But the nice thing about symmetric matrix is that the V is orthogonal. So it's just like a rotation. It's just a nice change of basis like, without like ruining any of the scaling problems that you might have. Right. So so you have your old coefficients. Well, instead, all this is saying is that you know we had our coefficients for all thing. But if you, if you, if you just could take
David Bau: this step, please, of rotating your perspective according to this V, which is this of rotation of orthogonal
David Bau: rotation, instead of your coefficients, use these ones instead. then
David Bau: you give the Gpu the luxury of only having to exponentiate and associate and things like this with this, a matrix
David Bau: which is diagonal that make sense. And so
David Bau: so wouldn't that be nice if you could, if you could do this, and and and then like a race to the end. Power.
David Bau: you know, stacks up this v times
David Bau: a times VT times v, times a times VT. You know, over and over again, but v. Times, VT is identity in all telescopes.
David Bau: So you do one be at the beginning, one be at the end, and everything else in the middle is just like this diagonal thing raised to these powers.
David Bau: So it's cool. It's like much, much easier like the codes you have to write. To get this to work is much simpler. Now
David Bau: make sense. yeah, and probably much faster. Okay, so
David Bau: so. But the problem is that the hippo matrix.
David Bau: they had this clever shift that they like stuff like this.
David Bau: The hippo matrix is not symmetric like this. The ample matrix is asymmetric. It has this form that I showed you before. It's all above the diagonal. So what the heck is this thing?
David Bau: Well, it was then the hippo guys discovered that you could decompose a hippo matrix into this if you shifted it over by a simple matrix, a rank, one matrix. So
David Bau: they said, so you have to do matrix exponentially in this matrix exponentiation on this, and then you also have to do a use, a different algorithm to do the matrix exponentiation on this low rank
David Bau: thing and then add it all together, and it all works right. And so
David Bau: that's what the hippo guys said you should do
David Bau: right.
David Bau: And then Gupta came along, and he says, I don't know how to do matrix annotation over a low, rank thing. Let's like, what if we just skip? What if we just use this part of the matrix.
David Bau: And then he just ran all the benchmarks. Oh, looks like it works just as well.
David Bau: And the hippo guys are like, we have no theory behind this. We have no idea. This is not like.
David Bau: you know, based on Legendre polynomials or anything right? It's just like, go up to just realize that you could just do this half of the problem. And it works, okay, it works a little worse. And so actually, it's not totally true. So basic. So yeah.
David Bau: yeah. So there's a lot of advantages, that of diagonal form and and so on. So this is, you know, all this stuff, right? You can raise them to powers and
David Bau: to different things. But
David Bau: and so actually, I haven't read the paper in detail. There's a long theory section in the paper, but with the paper going, Gupta.
David Bau: instead of just having empirical results, saying, Hey, it works just as well. They they try to develop some theory, for like, why it is that you can drop this extra term, and
David Bau: why it sort of behaves the same. And so they have all these, you know.
David Bau: results same. So like the ideal hippo matrix, like remembers things like with this, that level accuracy.
David Bau: And then, if you but if you limit it to a certain number of dimensions, and you drop the
David Bau: you know you drop this other term, then your memory kind of looks like this.
David Bau: but if you increase the number of dimensions, then it sort of neatens up
David Bau: right? And so if you're in this high dimensional
David Bau: regime.
David Bau: then it's pretty close to just as good as the original hippo matrix right? And so the more dimensions you have.
David Bau: the less
David Bau: problems you're you're you're buying for yourself by dropping this thing that Gupta didn't want to deal with
David Bau: that makes sense the rank. One thing before, like there's this full. There's this full like dance matrix
David Bau: it. They they have to add to the diagonal to get the full hippo matrix.
David Bau: and and they more, more or less, that I guess the discovery from crypto is like, even though that like fills up every entry of the matrix.
David Bau: It's like not important. You can drop it and just keep the diagonal part that make sense.
David Bau: But they they also don't. Oh, so so far. Yes, go. Go. And, Gupta, I just like use this instead.
David Bau: How is that even like encoding
David Bau: if you get get rid of everything besides the bag.
David Bau: Yeah, I don't know. But here's here's the like, the dang out like this. You can't put much stuff in a day, or what the heck is this thing. So this is the matrix here, as far as far as I'm concerned, this is it, this this thing here?
David Bau: Right? So this is a plot of the Eigenvalues, the the diagonal form, eigenvalues.
David Bau: And
David Bau: you know, if you have various different forms that that have the legendra, the linear quad info, I don't know, whatever the difference games again.
David Bau: right? But if it's dang and all it is, it's like a series of scalars all the way down the day. Well, that's all. The thing is right. And so what are the scalars? What? What's so magic about these scalars? So the first one's pretty big, and then it drops off, but with a certain curve, and it drops off from there, and it drops off, drops off
David Bau: like
David Bau: they've reduced the hippo matrix
David Bau: to a scaling curve. And they say.
David Bau: like, basically it goes by.
David Bau: what is it? Leg S. Theoretically approximates the dynamics of original s. 4. Blue, and has eigenvalues following inverse law.
David Bau: one over. N,
David Bau: so if you just go to your data matrix and you initialize it
David Bau: with one over N, then you're pretty close to the hippo matrix.
David Bau: After all of that nonsense that I spent the whole day explaining to you
David Bau: right? It pretty much comes pretty close to the performance of this hippo matrix. Just fill in your diagonal one over end. I don't know what B is. Yeah, II don't know if they follow along be, or they say, you know, you gotta learn about gradient descent or something
David Bau: right? That make sense.
David Bau: You still have the icon values.
David Bau: Yeah, you have the Eigenvectors outside, so you could reconstruct a bunch of stuff. But the thing is
David Bau: they they also dropped this whole low, rank thing. So the low, rank thing was essential, for, like the interpretability of like understanding.
David Bau: like what the hippomatrix was doing right. And so they dropped that. So if you set that to 0, I'm not sure. So I haven't read the technical parts of this paper.
David Bau: I just know that exists. So they talk about. They're
David Bau: their derivation. And section 3 and section 5.2, and this and that right? And so
David Bau: if we wanna see if the diagonalization form also acts as a memory that we can actually read out they they might already know that in this paper, so it'd be worth reading in more detail. We could take a look at it if you want
David Bau: that makes sense. So I think that brings us to the end of the time. I haven't shown you what mama is yet as next, but but but I think that you had sort of have the ingredients, so that you asked this question like.
David Bau: doesn't like mama, throw away everything
David Bau: that all the hipaa people like worked on and stuff. And we're like, yeah, halfway there, we throw away half of it. Here it is. But
David Bau: but you know, I guess what these the hipaa, people would say, is, don't minimize the discovery of this one over end business. It seems like simple initialization. right? But maybe
David Bau: you know who would have stumbled on the idea that it. The best way of initializing a linear recurrence diagonal thing
David Bau: is to have the distribution go as one over N
David Bau: right? And
David Bau: it turns out that that's that's what you do. And then it'll behaves really well
David Bau: that make sense. And yeah, it reminds me of. you know, in in class. We read the
David Bau: that you know
David Bau: Xavier Glorat's initial, you know, weight initialization papers right?
David Bau: And and he has all this derivation. The students are all like scared of, like the derivations you have to do to show that you wanna initialize weights or something like this. Well, wait until, like years later people are like, Hey, you gotta initialize this thing by one over. And why? Why do that? Oh, read these 3 papers, and then, my gosh, the mathematical like.
David Bau: you know, reasoning that goes into where this one over N comes from.
David Bau: It's going to be like a what what did they? How did they come up with this. But now you guys know the story.
David Bau: Okay.
David Bau: and then and then, Moba, they're gonna move on from this, and they're gonna relax more. This is gonna throw away more of the hip of stuff to try to make it more powerful.
David Bau: So we'll talk about it next app. Okay. Alright guys. off we go. Sure. Yeah. Thank you. That 5,
David Bau: that
everything could be based on select.