the same with the demos for completing a phrase based on Crime & Punishment... having all recently seen the text completion demos of GPT-2 the Reformer examples are decidedly underwhelming
I mean, I'm sure it's a great new technique and all
There is no argument for why the LSH would work well, especially at the beginning of training. As the weights are initially random, bucket assignment would be random as well. If predicting at position A requires info from position B, but they are not in the same bucket, there will be no gradient to get the query embedding of A closer to the key embedding of B. The reversible layer trick is neat though.
Perhaps I'm wrong, but it seems to me that deciding on the bucket is the discrete decision. If you have two "words"/"contexts" in a sequence that ought to attend to each other, but they don't get bucketed together early in training, then there is no gradient pushing those two hidden states to be close to each other, because there is no comparison being done between the two contexts.
In a standard transformer, on the backprop we can see something like "oh, you would have been quite closer to the correct answer on this sentence if you had matched the context for 'dog' with the context for 'treat' about 20 words back." But, here, if 'dog' doesn't get bucketed with 'treat', then there's no such gradient pressure.
Eventually (and with enough hashing+bucketing), the embedding of the more relevant contexts will move closer together, but I'd suspect this might occur more slowly. Here's the authors describing the process:
> We don’t differentiate through the hash bucket assignment procedure, or the choice of what order to sort the items into. Rather, these operations take query/key vectors as input where LSH maps nearby vectors to the same bucket with high probability. Therefore, the sorting re-adjusts any time parameter updates to cause relevant vector pairs to have higher dot product, and “unhelpful” vector pairs to have lower dot products.
e: And here is a reviewer noting what I suspected about number of gradient updates,
> the performance achieved by the proposed method after 140k iterations is achieved by the full attention after ~40k iterations [on imagenet64]
Yep, and I'm not saying its a bad approach! Just trying to answer "why is that any worse than, say, starting with randomly initialized weights in general?" wrt gradient passing
I'm not sure I'd agree with the "noisy" characterization - which to me implies stochasticity-, whereas this is just blocking off the flow of gradient information to save memory.
I agree that eventually this could work because on some training examples, two related entries will be in the same bucket.
However, I'm not sure this would really scale to parsing an entire book all at once like the author suggest. While the algorithmic complexity might scale, the odds for two related items that could be chapters appart to end up in the same bucket seems so close to zero that training time would explode.
In particular, this approach removes all kind of domain knowledge. For images, it means ignoring entirely the prior that neighboring pixels are related, which is typically encoded through the use of convolutions. With a Reformer, not only does the locality behavior need to be learnt from scratch, but on top of that it will only happen after a sufficient number of iterations so that neighboring pixels do end up in the same bucket.
For parsing books, I think it would make much more sense to build a hierarchical model with one part parsing only a paragraph at a time and generating an intermediate embedding that could then be used as a representation of the paragraph in a larger scale Transformer working over entire chapter, and then another level going from chapters to the entire book, rather than putting all the words at once together in a giant Reformer with no domain knowledge at all and praying that with enough training data and epochs, the model will learn everything from scratch.
I think what they did in the paper is to increase the chances by multiple rounds of hashing, up to 8 times. They show experimentally that 8 times was good enough to be equivalent to a regular transformer.
Wouldn't the important embedding be of the token at position A and the token at position B rather than the positions themselves? Since there's a lot fewer tokens than positions you're fairly likely to get the two tokens to hash together at least a few times.
edit: I'd image the position itself (ie: word number in text rather than token) could be embedded using sin-cosine or by breaking it up into chapter/paragraph/word. Seems more meaningful and efficient than word number in text. That would prevent this issue on that side of things.
Probably, but it seems like it would run into diminishing returns except on the longest articles, because AFAIK the articles in wikitext are provided alphabetically, and consecutive articles may have little or nothing to do with each other, rendering the very wide window pointless.
Eh? My understanding from the article was that long is anything beyond a couple paragraphs, many (though maybe a minority by count) of the Wikipedia pages are much longer than this.
Last I saw any Wikipedia statistics, the average page was ridiculously small, like a few paragraphs. People just happen to not spend much time reading 'stubs', is all, but you can get an idea by spending some time on Special:Random. So, most WP articles are something that would fit entirely into many architectures' windows: for example, GPT-2 at 1024 context is roughly 3k characters (and you can easily scale GPT-2 way beyond that, see sillysaurus's comment above - we're training a GPT-2 with a context window of 25k right this second). Chonky paragraphs!
Reformer's advantage would come only from the subset of articles longer than that, and only from the improvement in prediction from the subset of characters out of window at the beginning of the article in trying to predict toward the end of the article. And then you have the article boundaries which largely 'reset' the memory. Reformer's advantage then would have to come from the chance that there is a relevant article somewhere accidentally alphabetically close enough to be in its window while predicting the current article.
But it would also be completely different from (and easier than) the existing benchmark of wikitext, which is what everyone uses and judges NN natural language modeling progress by, so there wouldn't be too much research interest in it, and it's not clear how useful it would be. After all, AIs don't get to reorganize the entire universe to make inputs come in the most convenient order for compression.
This seems like a big deal. An asymptotic reduction in the resource explosion created by larger attention windows should allow the development of substantially more complex models here.
Vowpal Wabbit has been doing this 'hashing trick' since the 200s.
It also the feature interaction, which are the same thing as a layer in transformers (all against all matrix).
So it seems like they are still catching up to where John Langford and crew were over a decade ago.
And, the vowpal wabbit approach is extremely fast to train because it's only doing stochastic gradient descent on a linear function - linear regression. Transformers are much slower to train.
EDIT: Downvoters, please see my last leaf to see why they're effectively the same. The guy responding here seems unfamiliar with all the functionality of vowpal wabbit.
The Google paper's hashing has, as best I can see, nothing to do with the Vowpal Wabbit's 'hashing trick.'
The VW hashing trick is about hashing your input data (ie: words, fields, etc.) into an array to lower storage requirements and deal with novel data at run time.
The google paper is about ordering the intermediate states of the neural network (ie: vectors) while preserving distance. This is done so you can chunk the resulting ordered list and perform computations on individual chunks (and their neighbors).
The only thing in common I see is the fact they both use the word hashing.
They are doing the same thing - using less memory by hashing.
The hashing trick in VW hashes multiple same words into one integer, not the same as reformer, but similar to how reformer puts similar vectors together.
With VW's ngram/skipgram features, you get the same kind of effect - similar strings hash into the same hash.
So locality sensitive hashing = (is around about the same thing as) ngram/skipgram on strings plus hashing trick.
Except in Google's paper the hashing does not directly reduce memory usage in any way. It's a lossless operation on the original vectors unlike VW's lossy operation. Google's representation allows for memory reduction down the line but those mechanisms have nothing to do with hashing.
Locality sensitive hashing is a way to put similar vectors into the same buckets - by omission etc. It does this by hashing, but the intent is to approximate nearest neigbours.
skipgram/ngrams turn features into other features by omission etc, and so makes similar things the same. The hashing trick then reduces memory usage.
So yes, you're right the hashing in locality sensitive hashing is different in intent, but my point is, that both these approaches are designed to be more memory and compute efficient.
And vowpal's feature interactions give you transformer layers.
Add up all these together, and they have about the same net effect.
You keep insisting that they're the same when they're not, and then you try to subtly expand your original claim of "using less memory by hashing" to "to be more memory and compute efficient" (emphasis mine), just to force them into the same bucket.
Yes, obviously locality sensitive hashing is a form of hashing. The fact that it's locality sensitive is important for this application, but you'd rather ignore that and insist on labeling them as the same thing just because they're both hashing.
What is reformer?
Transformer where LSH is applied.
One type of LSH is SimHash. ngrams of strings, followed by 32 bit hash.
Vowpal Wabbit -n flag for ngrams.
vw -interact xxx -n2 -n3 and you get ngrams + 32 bit hash doing SGD over a vector.
This vector is equivalent to a 2 layer reformer.
Non-linear activation is not needed because polynomials are already nonlinear.
So vw + interact + ngrams (almost)= reformer encoder. (if reformer uses SimHash, then they are identical).
Transformer/Reformer have an advantage, the encoder-decoder can learn from unlabeled data.
However, you can get similar results from unlabeled data using preprocessing such as introducing noise to the data, and then treating it as noise/non-noise binary classification. (it can even be thought of as reinforcement learning, with the 0-1 labels as the reward using vw's contextual bandits functionality. This can then do what GAN's do - climb from noise to perfection).
> This vector is equivalent to a 2 layer reformer.
There is no feed forward layer, no skip connections and no layer normalization in VW. In the reformer, hashing is followed by dot products. In VW hashing just collides some tokens, followed by a linear layer.
Also, 2 layers of transformer is a little shallow. In practice it's 12-14 layers or more.
In order to be equivalent, there would need to be equally good results on translation from VW, but I've never seen it used for translation. I'm wondering why?
- hashing followed by dot product in transformer you said
- you were doing dot products at each layer to introduce non-linearity in transformer (and neural nets in general). Polynomials are already non-linear, so you don't need that. Transformer and vw -interact are polynomials. Maybe the feedforward layers and skip connections are not actually needed.
- 12 layers ? vw -interact xxxxxxxxxxxxx is 12 layers. You need a lot of memory for that, but in principle vw interact can do any number of them
These results are coming from google and their massive compute resources. If they ran vw with -interact x^13 they might get similar results.
We're really talking about polynomial approximation here, both transformer and vw used in this way. And that is in theory able to approximate any continuous function (just like neural networks).
One neat trick is that you can extend GPT-2 117M's context window from 1024 up to 30k on a TPU, since TPUs can allocate up to 300GB of memory for backprop. https://twitter.com/gwern/status/1218001309435072513
It's not quite 1M words, but a 30k context window is big enough for e.g. most midi songs.
44 comments
[ 3.2 ms ] story [ 96.0 ms ] threadI mean, I'm sure it's a great new technique and all
because bucket choice is a discrete decision - and discrete decisions are hard to pass gradients through
Perhaps I'm wrong, but it seems to me that deciding on the bucket is the discrete decision. If you have two "words"/"contexts" in a sequence that ought to attend to each other, but they don't get bucketed together early in training, then there is no gradient pushing those two hidden states to be close to each other, because there is no comparison being done between the two contexts.
In a standard transformer, on the backprop we can see something like "oh, you would have been quite closer to the correct answer on this sentence if you had matched the context for 'dog' with the context for 'treat' about 20 words back." But, here, if 'dog' doesn't get bucketed with 'treat', then there's no such gradient pressure.
Eventually (and with enough hashing+bucketing), the embedding of the more relevant contexts will move closer together, but I'd suspect this might occur more slowly. Here's the authors describing the process:
> We don’t differentiate through the hash bucket assignment procedure, or the choice of what order to sort the items into. Rather, these operations take query/key vectors as input where LSH maps nearby vectors to the same bucket with high probability. Therefore, the sorting re-adjusts any time parameter updates to cause relevant vector pairs to have higher dot product, and “unhelpful” vector pairs to have lower dot products.
e: And here is a reviewer noting what I suspected about number of gradient updates,
> the performance achieved by the proposed method after 140k iterations is achieved by the full attention after ~40k iterations [on imagenet64]
I'm not sure I'd agree with the "noisy" characterization - which to me implies stochasticity-, whereas this is just blocking off the flow of gradient information to save memory.
In particular, this approach removes all kind of domain knowledge. For images, it means ignoring entirely the prior that neighboring pixels are related, which is typically encoded through the use of convolutions. With a Reformer, not only does the locality behavior need to be learnt from scratch, but on top of that it will only happen after a sufficient number of iterations so that neighboring pixels do end up in the same bucket.
For parsing books, I think it would make much more sense to build a hierarchical model with one part parsing only a paragraph at a time and generating an intermediate embedding that could then be used as a representation of the paragraph in a larger scale Transformer working over entire chapter, and then another level going from chapters to the entire book, rather than putting all the words at once together in a giant Reformer with no domain knowledge at all and praying that with enough training data and epochs, the model will learn everything from scratch.
edit: I'd image the position itself (ie: word number in text rather than token) could be embedded using sin-cosine or by breaking it up into chapter/paragraph/word. Seems more meaningful and efficient than word number in text. That would prevent this issue on that side of things.
Reformer's advantage would come only from the subset of articles longer than that, and only from the improvement in prediction from the subset of characters out of window at the beginning of the article in trying to predict toward the end of the article. And then you have the article boundaries which largely 'reset' the memory. Reformer's advantage then would have to come from the chance that there is a relevant article somewhere accidentally alphabetically close enough to be in its window while predicting the current article.
But it would also be completely different from (and easier than) the existing benchmark of wikitext, which is what everyone uses and judges NN natural language modeling progress by, so there wouldn't be too much research interest in it, and it's not clear how useful it would be. After all, AIs don't get to reorganize the entire universe to make inputs come in the most convenient order for compression.
It also the feature interaction, which are the same thing as a layer in transformers (all against all matrix).
So it seems like they are still catching up to where John Langford and crew were over a decade ago.
And, the vowpal wabbit approach is extremely fast to train because it's only doing stochastic gradient descent on a linear function - linear regression. Transformers are much slower to train.
EDIT: Downvoters, please see my last leaf to see why they're effectively the same. The guy responding here seems unfamiliar with all the functionality of vowpal wabbit.
The VW hashing trick is about hashing your input data (ie: words, fields, etc.) into an array to lower storage requirements and deal with novel data at run time.
The google paper is about ordering the intermediate states of the neural network (ie: vectors) while preserving distance. This is done so you can chunk the resulting ordered list and perform computations on individual chunks (and their neighbors).
The only thing in common I see is the fact they both use the word hashing.
The hashing trick in VW hashes multiple same words into one integer, not the same as reformer, but similar to how reformer puts similar vectors together.
With VW's ngram/skipgram features, you get the same kind of effect - similar strings hash into the same hash.
So locality sensitive hashing = (is around about the same thing as) ngram/skipgram on strings plus hashing trick.
Locality sensitive hashing is a way to put similar vectors into the same buckets - by omission etc. It does this by hashing, but the intent is to approximate nearest neigbours.
skipgram/ngrams turn features into other features by omission etc, and so makes similar things the same. The hashing trick then reduces memory usage.
So yes, you're right the hashing in locality sensitive hashing is different in intent, but my point is, that both these approaches are designed to be more memory and compute efficient.
And vowpal's feature interactions give you transformer layers.
Add up all these together, and they have about the same net effect.
Yes, obviously locality sensitive hashing is a form of hashing. The fact that it's locality sensitive is important for this application, but you'd rather ignore that and insist on labeling them as the same thing just because they're both hashing.
Simhash algorithm, the LSH i knew about (which i mistakenly thought is LSH) works exactly like VW. It is ngrams + hash.
http://matpalm.com/resemblance/simhash/
https://en.wikipedia.org/wiki/SimHash
Simhash, a type of local sensitive hashing - using hash functions on ngrammed data.
That is exactly what Vowpal Wabbit does.
Why neural networks? https://en.wikipedia.org/wiki/Universal_approximation_theore...
Can polynomials do this? (Yes) https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theo...
What is transformer and attention? https://pathmind.com/wiki/attention-mechanism-memory-network
Attention = Polynomial (x2,x3 etc.)
Polynomial = interaction. VW flag -interaction
1 layer transformer = xx. (x^2)
2 layer tranformer = xxx. (x^3)
3 ... etc
What is reformer? Transformer where LSH is applied.
One type of LSH is SimHash. ngrams of strings, followed by 32 bit hash.
Vowpal Wabbit -n flag for ngrams.
vw -interact xxx -n2 -n3 and you get ngrams + 32 bit hash doing SGD over a vector.
This vector is equivalent to a 2 layer reformer.
Non-linear activation is not needed because polynomials are already nonlinear.
So vw + interact + ngrams (almost)= reformer encoder. (if reformer uses SimHash, then they are identical).
Transformer/Reformer have an advantage, the encoder-decoder can learn from unlabeled data.
However, you can get similar results from unlabeled data using preprocessing such as introducing noise to the data, and then treating it as noise/non-noise binary classification. (it can even be thought of as reinforcement learning, with the 0-1 labels as the reward using vw's contextual bandits functionality. This can then do what GAN's do - climb from noise to perfection).
There is no feed forward layer, no skip connections and no layer normalization in VW. In the reformer, hashing is followed by dot products. In VW hashing just collides some tokens, followed by a linear layer.
Also, 2 layers of transformer is a little shallow. In practice it's 12-14 layers or more.
In order to be equivalent, there would need to be equally good results on translation from VW, but I've never seen it used for translation. I'm wondering why?
- you were doing dot products at each layer to introduce non-linearity in transformer (and neural nets in general). Polynomials are already non-linear, so you don't need that. Transformer and vw -interact are polynomials. Maybe the feedforward layers and skip connections are not actually needed.
- 12 layers ? vw -interact xxxxxxxxxxxxx is 12 layers. You need a lot of memory for that, but in principle vw interact can do any number of them
These results are coming from google and their massive compute resources. If they ran vw with -interact x^13 they might get similar results.
We're really talking about polynomial approximation here, both transformer and vw used in this way. And that is in theory able to approximate any continuous function (just like neural networks).
It's not quite 1M words, but a 30k context window is big enough for e.g. most midi songs.