Comment by throwawaymaths | Hacker News Reader

Comment by throwawaymaths | Hacker News Reader

The Yannic kilcher review is quite good.

https://youtu.be/iDulhoQ2pro

I can't ELI5 but I can ELI-junior-dev. Tl;dw:

Transformers work by basically being a differentiable lookup/hash table. First your input is tokenized and (N) tokens (this constitutes the attention frame) are encoded both based on token identity and position in the attention frame.

Then there is an NxN matrix that is applied to your attention frame "performing the lookup query" over all other tokens in the attention frame, so every token gets a "contextual semantic understanding" that takes in both all the other stuff in the attention frame and it's relative position.

Gpt is impressive because the N is really huge and it has many layers. A big N means you can potentially access information farther away. Each layer gives more opportunities to summarize and integrate long range information in a fractal process.

Two key takeaways:

- differentiable hash tables

- encoding relative position using periodic functions

NB: the attention frame tokens are actually K-vectors (so the frame is a KxN matrix) and the query matrix is an NxNxK tensor IIRC but it's easier to describe it this way

I appreciate the explanation, but I don't know what junior-dev would understand most of this. I may be just a web developer, but I couldn't understand most of this. I'd still have to read for 30m to grok it all.

Yeah sorry, it still requires math and probably some exposure to ML basics.

I think one hole in the description for simplicity is that "differentiable" it's not an adjective that applies to hash tables.

Differentiable relative to what? What is (x) in the d(hashtable)/d(x) equation?

I think it applies because lookups can be done by multiplying one-hot vectors (or masks) with matrices; this is roughly analogous to what happens when we multiply Q with K^T in a self-attention head.

Read this: https://e2eml.school/transformers.html#table_lookup

And then read: https://e2eml.school/transformers.html#attention

Matrix multiplication is differentiable as it is continuous. Therefore you can calculate partial derivatives of these operations. The ability to do that is what allows gradient descent optimization via the chain rule.

  > Differentiable relative to what?
  > What is (x) in the d(hashtable)/d(x) equation?

I think the derivative we actually care about is `∂L/∂(hashtable-lookup)` but here the `hashtable-lookup` is actually the matrix multiplication mentioned above. We want to know how much the "loss" (or error) changes with respect to each of our "lookups". Knowing how each of our "lookups" causes our model to err from the output we expect, allows us to optimise it.

Note: it's not really a "lookup" in the normal sense of the word. Hashtable lookups are discontinuous since we either have a value for a particular key or we do not. Our matrix multiplication is sort of like a fuzzy, probabilistic, continuous form of lookup in which nearby keys get partially activated based on their similarity to the query, and in which a small change in this query causes continous changes to the keys produced.

As far as my understanding of the self-attention equation (e.g. `softmax(QK^T / sqrt(d_k))V`) goes, its actually quite important that we get this fuzzy output in which lots of keys get partially activated for a particular query. If it only picked the maximum similarity and ignored the rest, there would be less information propagating through the network and it'd be harder for the network to learn relationships/interactions between inputs. This is why we scale `QK^T` by `sqrt(d_k)` in order to pass a tighter range of values into the `softmax()` function (which importantly generates probabilities that sum to 1, but contains exponentials which give it a tendency to over-emphasize the maximum value and ignore other values if they are too far apart).

That's exactly the point, though! It's surprising. A hashtable is a map from keys to values. Making it differentiable means that a small change in the key also makes a small change in the value!

differentiable relative to the model parameters. The attention mechanism does store(key(x), value(x)), followed by lookup(query(y)), where key(), value(), lookup(), query() are all designed to be differentiable.

One thing that might be worth pointing out is that the transformer architecture owes a great deal of its success to the fact that it can be implemented in a way that it can be massively parallelized in a very efficient manner.

Compared to rnns... maybe? The big nxn is really a killer.

I don't know how to judge parallelizability of different DNN models, you're comparing apples to oranges

When you train a transformer, you're training what the next expected token is. You can train all positions of the sequence each in parallel rather than having to sequentially build up the memory state as you generate the sequence with an LSTM. Mind you the inference portion of a transformer is still sequentially bottlenecked since you don't know what the output sequence is supposed to be.

I believe the other big thing is it allowed you to parallelize the training as well, so you could split those colossal training sets across many machines in a way you could not do with LSTMs.

I don't really believe this because in theory it's possible to split up training of arbitrary neural nets using decoupled neural interfaces (not that it's easy mind you) but at the point where you have openAI scale resources the bottleneck to achieving that is the difficulty of Python.

What’s a neural interface?

https://arxiv.org/abs/1608.05343

If you train in parallel, how do you combine the weights generated from different trainings in parallel?

You take a huge hit.

Believe it or not, it's a simple as averaging or adding the gradients of each training result before adding it to the model weights. The same thing happens when you train a model using batches of inputs.

It actually isn't. You have to have a synchronizer, batchsize one or else "strange things" can happen and you waste a lot of cycles. Alternatively you can do non-simple changes to your network structure to enable distributed training.

It really is that simple. Yes, there's many different approaches to this (which can become quite clever and complex, which is true of training in general), but it all really boils down to adding or averaging the gradients in most cases.

What does it mean for a lookup/hash table to be differentiable?

I wanted to ask the same and especially I've always been wondering: How is the meaning of aforementioned 'differentiable' related to the same term in math?

Same thing. You need everything to be differentiable in order to run gradient descent. To first approximation, training a neural network is just gradient descent.

The neural net is just a math function, continuous even, fully differentiable in all input points. In order to "learn" anything we compute gradients towards the function parameters. They get "nudged" slightly towards a better response, and we do this billions of times. It's like carving a raw stone block into a complex scene. If you put your data into the system it flows towards the desired output because the right path has been engraved during training.

<rant> This explains a bit how neural nets work but from this to chatGPT is another whole leap. You'd have to assign some of the merits of the AI to the training data itself, it's not just the algorithm for learning, but what is being learned that matters. The neural net is the same, but using 1T tokens of text is making it smart. What's so magic about this data that it can turn a random init into a language programmable system? And the same language information make a baby into a modern human, instead of just another animal. </>

No, it's the loss function we differentiate. The input to the loss function are the network weights. The input to the network are samples and those we do not differentiate.

While it's true that we don't differentiate the input samples, we do differentiate the loss function's output with respect to each of the network weights. We use the chain rule to calculate each of these "gradients" and that process is known as backpropagation.

(You might have intended to say this, in which cases I'm just trying to add clarity.)

Not an expert (so this could well be slightly off), but here is a physics analogy:

You're rolling a ball down a plank of wood and you want it to roll off the plank and continue to a certain spot on the ground. You know that if the ball rolls past the target, you have to angle the ramp lower. If it fails to reach the target, you angle the ramp higher. If it goes past by a lot, you make a big change to the ramp angle. If it goes past by a little, you make a small change to the ramp angle. In this way your error tells you something about the adjustment you need to make to the system to produce the desired output.

Think of a function from the ramp angle (network weights) to how far the ball lands from the target (the error). The derivative of this function tells you what kind of change in angle results in what kind of change in the error, and you can use that to update the ramp until you hit the target. To say that the model is differentiable is to say that it's possible to infer from the error what kind of changes you need to make to the weights.

Going to go out on a limb and say they are probably referring to the gradient calculus required for updating the model.

https://en.wikipedia.org/wiki/Differentiable_programming

See automatic differentiation.

Correct, but note that if you subject a standard hash table algo to AD it won't magically become a transformer. (Hashes in the "normal construction" are discrete functions and thus aren't really continuous or differentiable, neither are lookup tables)

Differentiable in this context, means that it can be learned by gradient descent, which uses derivatives to adjust a neural network model's parameters to minimise some error measure. As for how that applies to a hash function, I think the lookup gives some sort of weighting for each possible output, for each input, with the largest weightings corresponding to a "match". But tbh I'm not certain on that last part...

> As for how that applies to a hash function, I think the lookup gives some sort of weighting for each possible output, for each input, with the largest weightings corresponding to a "match"

Note that in general one "matches" more than one thing in which case (IIRC) the result will be a weighted linear combination of the query results.

I do think that this collapses to a datastructure equivalent in function to the "normal hash table" (but not in performance, lol) in the degenerate case where every input yields strictly a single result with zero activation in all other results, so it's not invalid to call it a differentiable lookup table.

You can take a (calculus) derivative of the mathematical construct that represents the lookup table. And yeah, it is very not obvious how a "lookup/hash table" could be differentiable, based on how it's implemented say, in a leetcode exercise. That's part of the genius of the transformer.

Well, a hash table is basically a function.

Not a continuous function

The lookup/hashtable can be viewed as a matrix which is accessed by multiplying it with a vector.

It's not really doing hashing, which is random, but instead it makes meaningful connections, like connecting an adjective to its noun, or a pronoun to a previous reference of the name. That is why it is called "Attention is all you need" and not "Hashing is all you need". Attention includes some meaning, it is attentive to some aspect or another.

Hashing does not have to be random, it just has to compress the domain. Modulo number is a perfectly valid hash for some use cases.

Edit: just looked it up, doesn't even have to compress the domain, identity hash is a thing.

I'm not a ML expert but I know a bit about math.

It's "differentiable" in the same way that e.g. the "jump function" (Heaviside step function) is differentiable (not as a function from real numbers to real numbers, but as a distribution). It's derivative is the "point impulse function" (Dirac delta function), which, again, is a distribution, not a real function.

Distributions are nicely defined in math, but can't really be operated with numerically (at least not in the same way as real/float functions), but you can approximate them using continuous functions. So instead of having a function jump from 0 to 1, you "spread" the jump and implement it as a continuous transition from e.g. `0-epsilon` to `0+epsilon` for some tiny epsilon. Then you can differentiate it as usual, even numerically.

Similarly, hash table lookup is a dis-continuous function - the result of `hash.get(lookup)` is just `value` (or `null`). To make it continuous, you "spread" the value, so that nearby keys (for some definition of "nearby") will return nearby values.

One way to do this, is to use the scalar product between `lookup` and all keys in the hashtable (normalized, the scalar product is close to 1 if the arguments are "nearby"), and use the result as weights to multiply with all values in the hashtable. That's what the transformer does.

Thanks for this explanation. I couldn't wrap my mind around the "differentiable hash table" analogy, but "distribution of keys" -> "distribution of values" starts to click.

I'm not an ML expert either but I have taken graduate level courses and published papers with "machine learning" in the title, so I feel like I should be able to understand these things better. The field just moves so fast. It's a lot of work to keep up. Easy-to-digest explanations like this are underrated.

>The field just moves so fast. It's a lot of work to keep up. Easy-to-digest explanations like this are underrated.

This is really the truth. I can't possibly understand how people in this field who are talented can still keep up. I have a binder full of seminal papers that I have to cull to make room for more recent and relevant research every few months. I feel there is a lot of potential in simplifying the details of the mechanisms that drive a lot of it, but nobody has time to stop, consolidate the information and publish it. And if they did, it would just be another outdated textbook in a few years.

thank you. This made it click.

What actually happens is that each vector grabs a fraction of each other vector and adds it to itself (simplification omitting some transforms along the way). Equating this with the concept of a hash function does not make sense in my opinion but some authors do it anyway.

It's differentiable because how much of a fraction to grab is the result of a simple dot product followed by a softmax.

I came here to post this video. It’s a great primer on the topic and it gives you ideas to prompt gpt and have it output more.

It’s how I got an understanding of beam search, a technique employed in some of the response building.

I had to look up "tl;dw" and realized it meant "too long; didn't watch" and not my first AI-laden instinct of "too long, didn't write" :-D

what is a differentiable hash table? I understand differentiation, I don't understand differential hash table ... does that mean for every tiny gradient of a key, a corresponding gradient in value can be expected?

Having read the paper myself, I'm impressed with the quality of your explanation. Well done!

How does N relate to the number of parameters that is frequently mentioned?

In my screed, N is the attention width. (How many token it looks at at a time) number of parameters is O(KxNxNxL) where k is the vector size of your tokens, and l is the # of layers. There are other parameters floating around, like in the encoder and decoder matrices, but the NXN matrix dominates.

This is an awesome explanation. You guys are the real heroes

Reply on news.ycombinator.com