5 ms·

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

weinzierl 3y ago
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?
- kccqzy 3y ago
  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.
- visarga 3y ago
  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. </>
  - bjourne 3y ago
    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.
    - lhnz 3y ago
      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.)
- dcre 3y ago
  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.
meowkit 3y ago
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 https://en.wikipedia.org/wiki/Differentiable_programming See automatic differentiation.
- throwawaymaths 3y ago
  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)
taylorius 3y ago
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...
- throwawaymaths 3y ago
  > 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.
throwawaymaths 3y ago
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.
contravariant 3y ago
Well, a hash table is basically a function.
- srcreigh 3y ago
  Not a continuous function
theGnuMe 3y ago
The lookup/hashtable can be viewed as a matrix which is accessed by multiplying it with a vector.
visarga 3y ago
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.
- throwawaymaths 3y ago
  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.
tomp 3y ago
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.
- hoosieree 3y ago
  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.
  - HybridCurve 3y ago
    >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.
coppsilgold 3y ago
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 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?

kccqzy 3y ago
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.
visarga 3y ago
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. </>
- bjourne 3y ago
  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.
  - lhnz 3y ago
    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.)
dcre 3y ago
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.

meowkit 3y ago

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 https://en.wikipedia.org/wiki/Differentiable_programming See automatic differentiation.

throwawaymaths 3y ago
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)

taylorius 3y ago

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...

throwawaymaths 3y ago
> 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.

throwawaymaths 3y ago

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.

contravariant 3y ago

Well, a hash table is basically a function.

srcreigh 3y ago
Not a continuous function

theGnuMe 3y ago

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

visarga 3y ago

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.

throwawaymaths 3y ago
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.

tomp 3y ago

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.

hoosieree 3y ago
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.
- HybridCurve 3y ago
  >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.

coppsilgold 3y ago

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.