Neural Networks and the Chomsky Hierarchy

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 I've already been a postdoc for a year, I'm ancient). Here's a recent paper on Neural Networks and the Chomsky Hierarchy that tests RNNs and Transformers on formal languages (I think it doesn't test on a^nb^n directly but tests similar a-b based CF languages): https://arxiv.org/abs/2207.02098 And btw that's a good paper. Probably one of the most satisfying DL papers I've read in recent years. You know when you read a paper and you get this feeling of satiation, like "aaah, that hit the spot"? That's the kind of paper.

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

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 a Turing machine. If we leave CoT aside for a moment, it's worth exploring the work discussed in the paper "Neural Networks and the Chomsky Hierarchy"[1], which analyzes how neural networks (including LLMs) map onto different levels of the Chomsky hierarchy, with a particular focus on their ability to recognize formal languages across varying complexity. [1] https://ar5iv.labs.arxiv.org/html/2207.02098v1

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 in computation time. I wonder if we are settling in for a local-optima of bounded-depth architecture for a while due to the obsession with rapid scaling.

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 resistance to Chomsky's ideas in the various communities that have topic overlap. It really seems apparent, to me, that symbols (a universal grammar?) are needed in order to learn & adapt to the environment. If true, then the question becomes how to evolve that universality from nothing.

Man, come on. Transformers, even equipped with memory, can only represent Regular automata [1]. And you're saying that if they "must" learn to represent all of human intelligence then that is what they will have to do? With what learning ability? Not to mention: they don't "must". A Transformer-trained LLM is equivalent to a Finite State Transducer, a Regular automaton that consumes inputs and emits outputs as well as transitioning between states: the prompts are the inputs the resulting tokens are the outputs. That's all you need to make a language model, large or small. And that, too, is a Regular automaton, I note. There is no computational power there enough for what you and others claim, that LLMs "must" learn to represent intelligence. Unless we claim huamn intelligence is equivalent to a Regular automaton. _________________ [1] https://arxiv.org/abs/2207.02098

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

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, neural turing machines could learn them all including recursively enumerable (context free grammar or turing machine to produce). Transformers did outperform LSTMs in something in an alternate hierarchy if I remember. It's not conclusive since it is not training indefinitely, there are formal proofs that many architectures can do things that they can't actually effectively be trained for, but they threw a lot of compute at it.

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

It doesn't take much to check the output of that and see it isn't off by a large amount. As for the answer, look at it in groups of 5 bits. EDIT: 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 Networks and the Chomsky Hierarchy". https://arxiv.org/abs/2207.02098 PS: You never bothered to say whether the program you provided was from an LLM or from yourself. Why not?

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

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