HackerPapers

arXiv:2207.02098cs.LG

Neural Networks and the Chomsky Hierarchy

Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, Pedro A. Ortega

Abstract

Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20'910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.

arXiv comments
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.AIArtificial Intelligence cs.CLComputation and Language cs.FLFormal Languages and Automata Theory

On Hacker News

Linked by 7 identifiable commenters in 12 comments across 12 threads, from Aug 2022 to Jul 2026. Found in 2 HN submissions from Jul 2022 to Jan 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments12 threads

  1. An agent in 100 lines of Lisp 1 comment

    • This deepmind paper showed big limitations on nested structures with transformers, LSTMs actually did better: Neural Networks and the Chomsky Hierarchy https://arxiv.org/abs/2207.02098

      cmaView on HNParent context

  2. Interview with gwern 1 comment

    • Thanks, that's what I meant. a^nb^n is a standard test of learnability. That stuff is still absolutely relevant, btw. Some DL people like to dismiss it as irrelevant but that's just because they lack the background to appreciate why it matters. Also: the arrogance of youth (hey…

      YeGoblynQueenneView on HNParent context

  3. Chain of Thought empowers transformers to solve inherently serial problems 1 comment

    • My 2 cents: Since LLMs (Large Language Models) operate as at least a subset of Turing machines (which recognize recursively enumerable languages), the chain of thought (CoT) approach could be equivalent to or even more expressive than that subset. In fact, CoT could perfectly be…

      wslhView on HNParent context

  4. Transformer as a general purpose computer 1 comment

    • Deepmind found transformers get beat out on learning to reproduce outs towards the general computer end of the Chomsky formal language heirarchy by neural turing machines and even LSTMs: https://arxiv.org/abs/2207.02098

      cmaView on HNParent context

  5. LLMs can't simulate a Turing machine reliably 1 comment

    • Deepmind did a study of which language classes different neural network architectures can learn with generalization: https://arxiv.org/abs/2207.02098 ("Neural Networks and the Chomsky Hierarchy") LSTMs could learn slightly deeper into the Chomsky hierarchy than transformers…

      cmaView on HNParent context

  6. Modern language models refute Chomsky’s approach to language 1 comment

    • Deep Mind had this paper on that, showing weaknesses of transformers relative to other models in generalizing from example productions from different tiers of the hierarchy: https://arxiv.org/abs/2207.02098

      cmaView on HNParent context

  7. Bard is getting better at logic and reasoning 1 comment

    • The point of this "IQ Test" is to set a relatively low-bar for passing the IQ test question so that even intellectually lazy people can get an intuitive feel for the limitation of Transformer models. This limitation has been pointed out formally by the DeepMind paper "Neural…

      jaboweryView on HNParent context

  8. Ask HN: Why can GPT4 en/decode base64? 1 comment

    • There are also limits to the sequence to sequence things they can effectively learn, in some cases weaker than LSTMs: https://arxiv.org/abs/2207.02098

      cmaView on HNParent context

  9. Tighter bounds on the expressivity of transformer encoders 1 comment
  10. The New XOR Problem 1 comment

    • Recurrency will help, see the empirical results in this paper: https://arxiv.org/abs/2207.02098. LSTMs can solve the PARITY problem, generalising to longer lengths of the problem without issue. The issue with re-introducing recurrency is that no one wants to bear the O(N) growth…

      shawntanView on HNParent context

  11. What is ChatGPT doing and why does it work? 1 comment

    • Some big limitations of transformers as well: Neural Networks and the Chomsky Hierarchy [Deep Mind 2022] https://arxiv.org/abs/2207.02098

      cmaView on HNParent context

  12. Deep Learning Alone Isn’t Getting Us to Human-Like AI 1 comment

    • This is a very interesting article, in particular because it brings up that whole Chomsky topic of the grammar hierarchy (see https://arxiv.org/pdf/2207.02098.pdf). I've been intuiting that linguistics are at the root of AGI for sometime now, but there is a very unproductive…

      emiliano2022View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.