Reformer, the Efficient Transformer
ai.googleblog.com
ai.googleblog.com
I 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.
It's not quite 1M words, but a 30k context window is big enough for e.g. most midi songs.
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).
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.