fheinsen

The github repository's first toy example is with 8 Taylor terms, applied to a context with 1B tokens, each token with 1K heads:

https://github.com/glassroom/sata_attention

That toy example is not practical with the quadratic formulation, because it would require computing and storing 1K attention matrices, each with 1B×1B dot-product scores. For example, at Float32 precision, those attention matrices would consume approximately 1K x 1B x 1B x 4 bytes = 3,725,290,298.5 Terabytes of memory, which is not practical.

Like every other proposed method, this one must be tested too. If it performs well in practice, AI service providers who ignore it will find themselves at a disadvantage.

Otherwise, the mathematical techniques introduced by this work are likely useful for other applications besides Transformer attention.

Unlike previous efforts, which typically stop at a low-order (e.g., quadratic) term of the Taylor expansion, this work derives a succinct, efficient, parallel general method for approximating attention with any number of Taylor terms, to arbitrary precision.

The github repository's first toy example is with 8 Taylor terms, applied to a context of 1B tokens, with attention computed over 1K heads per token. (Note that applying the quadratic formulation to 1B tokens, each with 1K heads, is not practical with current hardware, because it would require computing 1K attention matrices, each with 1B×1B dot-product scores.

Like every other proposed method, this one must be tested too. If it works, AI service providers who ignore it will find themselves at a disadvantage.

It's worth mentioning also that the mathematical techniques introduced by this work are likely of interest for other applications besides attention.

As far as I know, there is no widely accepted explanation for context rot.

Numerical error in long sequences of query-key dot-products may be a key factor.

Yes, there must be a connection. While adaptive truncation may prove impractical, it should be possible to measure spectral statistics on sample data, and specify a different fixed truncation order per layer, per head, etc. The github repository lists many other possible improvements: https://github.com/glassroom/sata_attention#proof-of-concept

[3] is linear attention, https://arxiv.org/abs/2006.16236, a well-known result with ~3K citations: https://scholar.google.com/scholar_lookup?arxiv_id=2006.1623...

This is a form of linear attention (https://arxiv.org/abs/2006.16236) that approximates standard scaled dot-product attention to arbitrary precision, by adding Taylor terms in an efficient manner. Each additional Taylor term improves the approximation. Efficiency is achieved by exploiting certain mathematical symmetries that become evident only after decomposing the standard formulation of attention into an expression over chains of tensor products. The github repository's README walks through examples. The first example is with 8 Taylor terms.

The method is more general. The github repository's first example is with eight Taylor terms (P = 8).

As the error via linear approximation approaches similar magnitude as numerical error via quadratic computation, don’t the two start becoming comparable in practice?

I ask because in practice, for inference, attention is typically computed with low-precision (4-bit, 8-bit, 16-bit) floats.

Numerical error, in fact, may be a key factor as to why quadratic attention, in practice, exhibits context rot as context gets longer, analogous to an RNN:

https://www.anthropic.com/engineering/effective-context-engi...

Yes. See this comment for context: https://news.ycombinator.com/item?id=45611863

To the best of our knowledge, this is the first time anyone has successfully trained a non-diagonal RNN computed in parallel, via prefix scan, without requiring any form of stabilization. We abstained from claiming as much out of an abundance of caution.

The manuscript formally defines GOOMs as a set of mathematical objects, shows that floating-point formats are a special case of GOOMs, and notes that they extend prior work on logarithmic number systems (LNSs), which go back to at least the early 1970's. That is, LNSs are a special case of GOOMs too. Defining and naming GOOMs enables reasoning about all possible special cases in the abstract. In practice, each implementation makes different trade-offs.

The formal definition stops short of inducing an isomorphism between GOOMs and R, to allow for the possibility of transformations that leverage the structure of the complex plane, e.g., deep learning models that process data in C and apply a final transformation from C to GOOMs, thereby allowing the data to be exponentiated to R. The library in this repository makes implementing such a model trivial, because it ensures that backpropagation works seamlessly over C, over GOOMs, and across mappings between C, GOOMs, and floats.

Take a look at the selective-resetting algorithm in the manuscript too. To the best of our knowledge, it's a new algorithm, but we opted not to claim as much, out of an abundance of caution. You will appreciate reading about it.

The paper formally defines GOOMs as the subset of the complex plane that elementwise exponentiates to the real line.

We'll update the README to make that clearer.

Thank you for pointing that out!

> GOOMs generalize the concept of "order of magnitude" to incorporate complex numbers that exponentiate to real ones. As with ordinary orders of magnitude, GOOMs are more stable than the real numbers to which they exponentiate.

> This implementation enables you to operate on real numbers far beyond the limits of conventional floating-point formats, for effortless scaling and parallelization of high-dynamic-range computations. You no longer need to scale, clip, or stabilize values to keep magnitudes within those limits.

repo:

https://github.com/glassroom/generalized_orders_of_magnitude

I'm the author of that paper. Happy to answer questions about it here.

Hi HN, I'm the author of this paper.

As it turns out, I posted it and answered a few questions about it on HN a few days ago, on this thread:

https://news.ycombinator.com/item?id=21397444

Please feel free to ask questions here too. I would be happy to answer them.

Thanks. Will do (work permitting!).

FWIW, a while back I reimplemented and tinkered a bit with the Sabour et al. version too... and did not see much promise in it.

Note that the routing algorithm I've proposed generalizes to vectors (by setting the dimension of the covector space d_cov to 1).

FYI, I reached out to two of those individuals (one is a CVPR reviewer, it turns out) and both suggested I first upload this to arXiv, so I did that yesterday. The paper is now stamped with a date, on the queue for site-wide notification. Thank you again for your feedback!

Thank you for saying that. Sometimes I forget how petty and small people can be, especially when they are under pressure, academic and otherwise.

I'll take a look at submitting it to CVPR.

In the meantime, please circulate my work. It's on record, online. The more people who are aware that others have seen it, the less likely someone will try to plagiarize it.

I'm not under any kind of academic pressure, so I don't need citations, conference slots, etc. But I do deserve credit for this, don't you think?

PS. And now that you mention it, a couple of people to whom I reached out mentioned they were under deadline over the next two weeks.

PPS. Send me an email!

Thank you!

Yes, I think this has legs.

Maximizing "bang per bit" (a) seems truly a new idea, as opposed to some minor tweak on the same old thing, and (b) the evidence so far shows it works better than previous methods.

(FWIW, we've been using this algorithm internally at work with similar outperformance over other methods, in yet another domain that is neither vision nor language... but I cannot share those results publicly.)

Before submitting this anywhere, I'd like to get more informal feedback from other AI researchers. I've reached out to people at Google Brain, Facebook AI, DeepMind, OpenAI, and a handful of top academic institutions and research groups. So far, the response has been positive, but I expect it will take everyone at least a couple of weeks, and probably longer, to read and understand the draft paper in sufficient detail to give me more than superficial comments.

New things often look like toys at first. :-)

> You’re comparing sentence classification done using transformer embeddings to older results which use inferior embeddings. How do regular convnets do when you feed them transformer embeddings?

Actually, I'm comparing it to recent models, including XLNet, MT-DNN, Snorkel, and (of course) BERT. AFAIK, convnets have not been able to outperform multihead self-attention, even on pretrained embeddings.

> Re learning reverse graphics - ok, maybe it is indeed the main feature of your work. I’d need to look into that, because from skimming your paper it’s not immediately clear what’s going on there.

I agree, it's not immediately clear. Nonetheless, I find it kind of unbelievable that a model with so few parameters can seem to do it. (I was shocked when I first saw the plots.)

> Re convnet accuracy on Norb - I’m willing to make that effort for cifar-10 as soon as you have the results.

That's a little disappointing... but OK.

Thank you so much for all your questions :-)

> How does a regular convnet do on another domain?

As far as I know, regular convnets have failed to outperform query-key-value self-attention models (i.e., transformers based on Vaswani et al.'s work) on pretty much every sequence task, including natural language tasks.

> Learning to do “reverse graphics” is only useful if you can show it is the reason behind performance improvement.

I would strongly disagree. Building systems that can learn "reverse graphics" on their own has long been a goal of computer vision. It seems a prerequisite for building machines that can build internal representations of the state of the physical world around them. Hinton et al.'s 2018 paper has a summary of recent efforts on this front on the "Related Work" section.

> What I’m saying is - no one has yet demonstrated a clear superiority of any capsules based model to the best available plain convnet.

No one is saying otherwise. :-) Convnets are still the right tool for most production systems in visual recognition today.

That said, I don't think a convnet can achieve 99.1% accuracy on smallNORB with only 272K parameters, after training from scratch without using any additional data or metadata of any kind -- like the model using my routing algorithm. If you think you can do that with a convnet, do it and put it up online (I'd love to see it :-)

I’m surprised you did not comment on the fact that my version of EM routing also achieves SOTA on another domain, natural language. Same code.

Here are the answers to your questions:

1. The final, published version is stamped “ICLR 2018,” so I used that year.

2. I don’t know if a conventional CNN can do this with 10x fewer parameters, while also learning to do a form of “reverse graphics” without explicitly optimizing for it. (I wouldn’t know how to get a CNN to do that without explicitly making it a training objective.)

3. IIRC, the convnet model from 2011 accepts 96x96 images. As to why Hinton et al. downsample images to 9x smaller, I suspect (but don’t know for sure) they had no choice to conserve memory and computation using their version of EM routing. I was able to reduce memory and computation with my variant of EM routing (by between one and two orders of magnitude) by setting the first routing layer to accept a variable number of inputs, without regard to location in image.

4. Me too. But you asked me about work other than Hinton’s, and that’s all I could find!

5. CIFAR10 is on the to-do list (work permitting!) :-)

Great questions. Happy to answer them here.

First of all, this work builds on Hinton et al.’s second paper, the one about EM routing of matrix capsules, from last year: https://ai.google/research/pubs/pub46653 This work is only minimally related to his previous paper (Sabour et al.'s paper) from two years ago!

RESPONSES TO #1:

* The same algorithm also achieves SOTA in another domain, natural language. Same code. I think it’s significant that the same code, without change, produces SOTA in two domains. See the README and tables 3 and 4 in the draft paper. Don't you think this is significant?

* It requires fewer parameters: 272K instead of 310K for Hinton et al. (2018)’s model and 2.7M for the best performing CNN on record (Cireşan et al.); see table 2. That’s 10x fewer parameters than the best performing CNN on record.

* It requires an order of magnitude less training: 50 epochs instead of 300 for Hinton et al. (2018)'s model.

* It’s trained with minimal data augmentation, unlike Hinton et al.’s and Cireşan et al.’s models (the latter, in particular, uses a ton of data augmentation). Also, unlike Hinton’s model, it accepts full-size images instead of 32x32 crops that are 9 times smaller. Finally, we do not measure accuracy as a mean of multiple crops. So, the model has fewer parameters, requires less training, and has greater capacity.

* It seems to be learning a form of "reverse graphics" on its own, from only pixels and labels, without having to optimize explicitly for it. See the README, figure 4, and the 24 plots and captions in supplemental figures 6 and 7. This is rather significant, don't you think?

RESPONSES TO #2:

* As far as I know, the best attempt at recreating Hinton et al.’s work on EM routing is by Ashley Gritzman at IBM, in July of this year -- only a bit over two months ago. As far as I can tell, his model does not come close to matching Hinton’s performance:

https://arxiv.org/abs/1907.00652

https://github.com/IBM/matrix-capsules-with-em-routing

https://medium.com/@ashleygritzman/available-now-open-source...

* There have been a few other efforts, all of which seem to fall short of Hinton's performance. Gritzman does a good job of covering those other efforts in his Medium article. None of these efforts propose any new ideas, as far as I can tell.

RESPONSES TO #3:

* Me too. So does Hinton: https://openreview.net/forum?id=HJWLfGWRb ... and so does everyone else.

* Alas, as Paul Barham and Michal Isard at Google Brain showed earlier this year, currently it can be challenging to scale capsule networks to large datasets and output spaces, in some circumstances, due in part to current software (e.g., PyTorch, TensorFlow) and hardware (e.g., GPUs, TPUs) systems, which are highly optimized for a fairly small set of computational kernels, in a way that is tightly coupled with memory hardware, leading to poor performance on non-standard workloads, including basic operations on capsules. Source: Barham and Isard (2019) - https://dl.acm.org/citation.cfm?id=3321441 (the PDF is available for free download at that link).

* My draft paper mentions Barham and Isard’s work.