Elamur Research⌕
☰
home / papers / 2019 / Are Transformers universal approximators of sequence-to-sequence functions?

Are Transformers universal approximators of sequence-to-sequence functions?

Paper · 2019 · Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat et al.

Summary

Transformers are widely used for NLP, but it has been unclear which sequence-to-sequence mappings they can actually represent. Every token passes through the same weights, and tokens interact only through pairwise dot products. Yun et al. answer this with a formal expressivity analysis. They first show that stacks of Transformer blocks can approximate, to arbitrary precision, any continuous permutation equivariant function with compact support. They then show that adding trainable positional encodings removes the equivariance limitation, so any continuous sequence-to-sequence function on a compact domain can be approximated. The proofs assign distinct roles to the two layer types. Self-attention computes a "contextual mapping," which assigns each distinct input context its own unique representation. The feed-forward layers then map those representations to the required outputs. Motivated by this split, the authors try cheaper substitutes for attention in BERT-style pre-training: bi-linear projections and separable convolutions. The results matter because they give a theoretical account of why contextual embeddings work. They also suggest that some attention layers could be swapped for more efficient components.

Key points

  • Theorem 2: a very narrow class, T^{2,1,4}, can approximate any permutation equivariant target in L_p distance. This class has 2 attention heads of size 1 and a feed-forward hidden width of 4. The analysis leaves out layer normalization.
  • Theorem 3: with trainable positional encodings, arbitrary continuous functions on a compact domain can be approximated. The construction is very deep, requiring O(n(1/δ)^{dn}) layers.
  • Lemma 6: this lemma formalizes contextual mappings and proves that self-attention layers can compute them.
  • Experimental setup: BERT BASE (110M parameters) was pre-trained on English Wikipedia and BooksCorpus, then evaluated on MNLI and SQuAD.
  • Results (Table 1, MLM accuracy / MNLI accuracy):
ModelParametersMLM accuracyMNLI accuracy
Transformer110M63%78.2%
SepConv102.5M60%73%
BProj90M59%72.3%
Average Attention88.3M28%66%

Used as standalone models, the cheaper layers score below the Transformer. However, replacing only some of the lower self-attention layers with them can improve performance.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢GoogleMountain View · United States492 works · 440,462 citations🎓Massachusetts Institute of TechnologyCambridge · United States243 works · 76,506 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi and Sanjiv Kumar. 2019. Are Transformers universal approximators of sequence-to-sequence functions?. arXiv:1912.10077.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1912.10077 · arXiv 1912.10077

@misc{yun2019are,
  title = {{Are Transformers universal approximators of sequence-to-sequence functions?}},
  author = {Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi and Sanjiv Kumar},
  year = {2019},
  doi = {10.48550/arxiv.1912.10077},
  eprint = {1912.10077},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1912.10077}
}

References

29 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Nir Ailon and Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):302–322, 2009. find
  2. François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1251–1258, 2017. find
  3. Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does BERT look at? an analysis of BERT’s attention. arXiv preprint arXiv:1906.04341, 2019. find
  4. Andy Coenen, Emily Reif, Ann Yuan, Been Kim, Adam Pearce, Fernanda Viégas, and Martin Wattenberg. Visualizing and measuring the geometry of BERT. arXiv preprint arXiv:1906.02715, 2019.
  5. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314, 1989. find
  6. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  7. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
  8. Yunchao Gong, Sanjiv Kumar, Henry A Rowley, and Svetlana Lazebnik. Learning binary codes for high-dimensional data using bilinear projections. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 484–491, 2013. find
  9. Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:1710.11278, 2017. — [arXiv:1710.11278](https://arxiv.org/abs/1710.11278) find
  10. We refer to Section D for a complete description of the setup. John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Te…
  11. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 (2):251–257, 1991. find
  12. Lukasz Kaiser, Aidan N Gomez, and Francois Chollet. Depthwise separable convolutions for neural machine translation. arXiv preprint arXiv:1706.03059, 2017. find
  13. Hongzhou Lin and Stefanie Jegelka. ResNet with one-neuron hidden layers is a universal approximator. In Advances in Neural Information Processing Systems, pp. 6169–6178, 2018. find
  14. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pre-training approach. arXiv preprint arXiv:1907.11692, 2019.
  15. Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Advances in neural information processing systems, pp. 6231–6239, 2017. find
  16. Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention-based neural machine translation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1412–1421, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
  17. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 3111–3119, 2013.
  18. Jorge Pérez, Javier Marinković, and Pablo Barceló. On the Turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03429, 2019. find
  19. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. Technical Report, OpenAI, 2018. find
  20. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical Report, OpenAI, 2019. find
  21. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383–2392, 2016.
  22. Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint arXiv:1903.01939, 2019. — [arXiv:1903.01939](https://arxiv.org/abs/1903.01939) find
  23. Laurent Sifre and Stéphane Mallat. Rigid-motion scattering for image classification. Ph. D. dissertation, 2014. find
  24. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998–6008, 2017.
  25. Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in a transformer language model. arXiv preprint arXiv:1906.04284, 2019.
  26. Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers),…
  27. Felix Wu, Angela Fan, Alexei Baevski, Yann N Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. arXiv preprint arXiv:1901.10430, 2019.
  28. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. XLNet: Generalized autoregressive pretraining for language understanding. arXiv preprint arXiv:1906.08237, 2019.
  29. Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pp. 19–27, 2015…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yun-2019-transformers-universal-approximators-sequence-sequence/