Neural Networks and the Chomsky Hierarchy

arxiv:2207.02098

Original source · Paper JSON

LLMs: architectures, context, training · 2022-07-05

Cites (1) · Cited by (2)

Complete cleaned Markdown · Source Markdown including bibliography

Read in parts

1. Part 1
2. Part 2
3. Part 3
4. Part 4
5. Part 5
6. Part 6

Contents

• Neural Networks and the Chomsky Hierarchy
• Abstract
• 1 Introduction
• This work
• 2 Related work
• Learning formal languages
• Neural networks and the Chomsky hierarchy
• Memory-augmented networks
• 3 Background
• Formal language
• Generative grammar
• Recognizing a language
• Transduction vs. recognition
• 4 Methods
• Problem setup
• Tasks
• Architectures
• Data generation
• 5 Results
• 5.1 Main result
• 5.2 Analysis of learned program structure
• Regular tasks
• Deterministic context-free tasks
• Context-sensitive tasks
• 5.3 LSTMs
• 5.4 Transformers
• 6 Discussion
• 7 Conclusion
• 8 Ethics Statement & Limitations
• Acknowledgments
• Appendix A Experimental details
• A.1 Language recognition vs. transduction
• A.2 Models
• RNN
• Stack-RNN
• NDStack-RNN
• Tape-RNN
• LSTM
• Stack-LSTM
• Transformer encoder
• Transformer (autoregressive)
• Convolutional Neural Network
• A.3 Tasks
• Even Pairs ( R )
• Modular Arithmetic (Simple) ( R )
• Parity Check ( R )
• Cycle Navigation ( R )
• Modular Arithmetic ( DCF )
• Reverse String ( DCF )
• Solve Equation ( DCF )
• Stack Manipulation ( DCF )
• Binary Addition ( CS )
• Binary Multiplication ( CS )
• Compute Sqrt ( CS )
• Duplicate String ( CS )
• Missing Duplicate ( CS )
• Odds First ( CS )
• Bucket Sort ( CS )
• A.4 Problem setup
• A.5 Computational resources
• Appendix B Additional Experiments
• B.1 Main result
• B.2 Phase transition under increasing training ranges
• B.3 Analysis of state- and memory-dynamics
• B.3.1 Stack-RNN program analysis
• B.3.2 Transformer program analysis
• Setup
• Interpretation of the learned algorithm
• Failure mode for long sequences
• B.4 Convolutional Neural Networks
• B.5 Stack-LSTMs
• B.6 NDStack-RNN
• B.7 Autoregressive Models
• B.7.1 Memory-augmented recurrent neural networks
• B.7.2 Transformer
• B.8 Scaling laws and the Chomsky hierarchy
• Instructions for reporting errors