2021

Linear algebra with transformers

Charton, François

Understand

Transformers can learn to perform numerical computations from examples only.

I study nine problems of linear algebra, from basic matrix operations to eigenvalue decomposition and inversion, and introduce and discuss four encoding schemes to represent real numbers.
On all problems, transformers trained on sets of random matrices achieve high accuracies (over 90%).
The models are robust to noise, and can generalize out of their training distribution.

Built on

Approximation by superpositions of a sigmoidal function
George Cybenko · 1989
Earlier work this paper cites.
Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
Roger W Brockett · 1991
Earlier work this paper cites.
Approximation capabilities of multilayer feedforward networks
Kurt Hornik · 1991
Earlier work this paper cites.
A neural network for computing eigenvectors and eigenvalues
Nikola Samardzija and RL Waterland · 1991
Earlier work this paper cites.
Neural networks for computing eigenvalues and eigenvectors
Andrzej Cichocki and Rolf Unbehauen · 1992
Earlier work this paper cites.
Principal components, minor components, and linear neural networks
Erkki Oja · 1992
Earlier work this paper cites.
Optimal depth neural networks for multiplication and related problems
Kai-Yeung Siu and Vwani Roychowdhury · 1992
Earlier work this paper cites.
Long short-term memory
Sepp Hochreiter and Jürgen Schmidhuber · 1997
Earlier work this paper cites.
The Art of Computer Programming, Volume 2: Seminumerical Algorithms
Donald E. Knuth · 1997
Earlier work this paper cites.
Random Matrices
Madan Lal Mehta · 2004
Earlier work this paper cites.
Neural networks based approach for computing eigenvectors and eigenvalues of symmetric matrix
Zhang Yi, Yan Fu, and Hua Jin Tang · 2004
Earlier work this paper cites.
Linformer: Self-attention with linear complexity
Original
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma · 2006
Earlier work this paper cites.
From zhang neural network to newton iteration for matrix inversion
Yunong Zhang, Weimu Ma, and Binghuang Cai · 2008
Earlier work this paper cites.
The graph neural network model
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini · 2009
Earlier work this paper cites.
Another neural network based approach for computing eigenvalues and eigenvectors of real skew-symmetric matrices
Ying Tang and Jianping Li · 2010
Earlier work this paper cites.
Learning phrase representations using rnn encoder-decoder for statistical machine translation
Original
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio · 2014
Earlier work this paper cites.
Adam: A method for stochastic optimization
Original
Diederik P Kingma and Jimmy Ba · 2014
Earlier work this paper cites.
Neural gpus learn algorithms
Original
Łukasz Kaiser and Ilya Sutskever · 2015
Earlier work this paper cites.
Grid long short-term memory
Original
Nal Kalchbrenner, Ivo Danihelka, and Alex Graves · 2015
Earlier work this paper cites.
Pointer networks, 2015
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly · 2015
Earlier work this paper cites.
Learning simple algorithms from examples, 2015
Wojciech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus · 2015
Earlier work this paper cites.
Adaptive computation time for recurrent neural networks
Original
Alex Graves · 2016
Earlier work this paper cites.

Similar

Sgdr: Stochastic gradient descent with warm restarts
Original
Ilya Loshchilov and Frank Hutter · 2016
Cited alongside, same era.
Investigating the ability of neural networks to learn simple modular arithmetic
Theodoros Palamas · 2017
Cited alongside, same era.
Moment-based spectral analysis of random graphs with given expected degrees
Original
Victor M. Preciado and M. Amin Rahimian · 2017
Cited alongside, same era.
Failures of gradient-based deep learning
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah · 2017
Cited alongside, same era.
Attention is all you need
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin · 2017
Cited alongside, same era.
Universal transformers
Original
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser · 2018
Cited alongside, same era.
Speech-transformer: A no-recurrence sequence-to-sequence model for speech recognition
Linhao Dong, Shuang Xu, and Bo Xu · 2018
Cited alongside, same era.
Improving language understanding by generative pre-training
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever · 2018
Cited alongside, same era.
Neural arithmetic logic units
Original
Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom · 2018
Cited alongside, same era.
Learning numeracy: Binary arithmetic with neural turing machines
Original
Jacopo Castellini · 2019
Cited alongside, same era.
Generating long sequences with sparse transformers
Original
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever · 2019
Cited alongside, same era.
The use of deep learning for symbolic integration: A review of (lample and charton, 2019)
Original
Ernest Davis · 2019
Cited alongside, same era.

Then

Fast transformers with clustered attention
Original
Apoorv Vyas, Angelos Katharopoulos, and François Fleuret · 2020
Later among the works it cites.
Transformer-based acoustic modeling for hybrid speech recognition
Yongqiang Wang, Abdelrahman Mohamed, Due Le, Chunxi Liu, Alex Xiao, Jay Mahadeokar, Hongzhao Huang, Andros Tjandra, Xiaohui Zhang, Frank Zhang, and et al · 2020
Later among the works it cites.
Neural symbolic regression that scales
Original
Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Parascandolo · 2021
Closest in time.
Multiplying matrices without multiplying
Original
Davis Blalock and John Guttag · 2021
Closest in time.
On the opportunities and risks of foundation models, 2021
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang · 2021
Closest in time.
Combinatorial optimization and reasoning with graph neural networks, 2021
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković · 2021
Closest in time.
Training verifiers to solve math word problems
Original
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman · 2021
Closest in time.
The neural data router: Adaptive control flow in transformers improves systematic generalization
Original
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber · 2021
Closest in time.
Advancing mathematics by guiding human intuition with ai
A Davies, P Velickovic, L Buesing, S Blackwell, D Zheng, N Tomasev, R Tanburn, P Battaglia, C Blundell, A Juhasz, et al · 2021
Closest in time.
An image is worth 16x16 words: Transformers for image recognition at scale
Original
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby · 2021
Closest in time.
Solving arithmetic word problems with transformers and preprocessing of problem text
Original
Kaden Griffith and Jugal Kalita · 2021
Closest in time.
Teaching temporal logics to neural networks
Original
Christopher Hahn, Frederik Schmitt, Jens U. Kreber, Markus N. Rabe, and Bernd Finkbeiner · 2021
Closest in time.
Proof artifact co-training for theorem proving with language models
Original
Jesse Michael Han, Jason Rute, Yuhuai Wu, Edward W. Ayers, and Stanislas Polu · 2021
Closest in time.
Investigating the limitations of transformers with simple arithmetic tasks
Original
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin · 2021
Closest in time.
Transformer-based machine learning for fast sat solvers and logic synthesis
Original
Feng Shi, Chonghan Lee, Mohammad Khairul Bashar, Nikhil Shukla, Song-Chun Zhu, and Vijaykrishnan Narayanan · 2021
Closest in time.
Symbolic brittleness in sequence models: on systematic generalization in symbolic mathematics
Original
Sean Welleck, Peter West, Jize Cao, and Yejin Choi · 2021
Closest in time.
Big bird: Transformers for longer sequences
Original
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed · 2021
Closest in time.
Deep symbolic regression for recurrent sequences, 2022
Stéphane d’Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample, and François Charton · 2022
Closest in time.
Simplifying polylogarithms with machine learning, 2022
Aurélien Dersy, Matthew D. Schwartz, and Xiaoyuan Zhang · 2022
Closest in time.
Solving quantitative reasoning problems with language models, 2022
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra · 2022
Closest in time.
Naturalprover: Grounded mathematical proof generation with language models, 2022
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…