4 ms·
The Chomsky Hierarchy isn't the right way to think about, in fact the Chomsky paradigm probably held back progress in language technology over the past 70 year
by PaulHoule 11mo ago
The Chomsky Hierarchy isn't the right way to think about, in fact the Chomsky paradigm probably held back progress in language technology over the past 70 years.
In the Kuhnian sense, Syntactic Structures was the vanguard of a paradigm shift that let linguists do "normal science" in terms of positing a range of problems and writing papers about them. It was also useful in computer science for formally defining computer languages that are close enough to natural languages that people find them usable.
On the other hand, attempts to use the Chomsky theory to develop language technology failed miserably outside of very narrow domains and in the real world Markov models and conditional random fields often outperformed when the function was "understanding", "segmentation", etc.
From an engineering standpoint, the function that tells if a production is in the grammar that is central to the theory is not so interesting for language technology, I mean, if LLMs were -centric then an LLM would go on strike if you got the spelling or grammar wrong or correct you in a schoolmarmish William Safire way but rather it is more useful for LLMs to silently correct for obvious mistakes the same way that real language users do.
The other interesting thing is the mixing of syntax and semantics. For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence. Now LLMs come around and manage to show a lot of linguistic competence without the rest of the animal and boy we have egg on our face, and coming out of the shadow of the Chomsky theory, structuralism will rear it's head again. (e.g. "X is structured like a language" got hung up on the unspoken truth that "language is not structured like a language")
- ogogmad 11mo agoI think most PL parsers use recursive descent, which doesn't require any formal language theory. That said, it's possible that formal language theory has enabled regular expressions to enter widespread use - first via theory; then to make tokenisers; then included in text editors; and then to make GREP.
- Maxatar 11mo agoYou're going to have a very hard time parsing a language using recursive descent if you don't understand some formal language theory. Recursive descent algorithms have a lot of trouble with left-recursion, and can result in arbitrary backtracking if you're not careful, which can blow up memory and time. To fix left-recursion you need to rewrite your grammar, which means familiarity with formal language theory. To avoid backtracking you typically use an LL(N) or variations thereof, which once again require having a pretty good understanding of formal language theory.
- FeepingCreature 11mo agoNah. Source: have done it without formal language theory. You can do most things by printf debugging and kludging. (Left-recursion? Use a while loop! Mutable state is a pathway to many abilities functional programmers consider unnatural.)
- PaulHoule 11mo agoYou can definitely write parsers and lexers knowing just enough to be dangerous. I remember being in the PHP culture where people wrote regex-based hacks instead of the character-at-a-time or token-at-a-time state machines or state machine + a stack kind of things which would be too slow in a language like that. The less you know the faster you get in trouble when things get tough.
- Maxatar 11mo agoMy statement was specific to recursive descent parsing.
- FeepingCreature 11mo agoBut recursive descent parsing is implemented with functions operating on parser state. The whole point of it is that it's very easy to write a parser because the abstraction exactly matches to function calling in programming languages. So you can do the whole range of pl primitives too.
- DiscourseFan 11mo agoDon't worry, the LLMs are already post-structuralist (at least the ones working on them are often familiar with those thinkers). Which is incredibly disturbing, I think, for many linguists who have spent their entire careers fighting against the French, only to have such philosophical and intellectual work become the most important in the development of this new technology. Hey, at least I'm employed! (And they said it "wasn't serious," that Chomskian Linguistics was the "real science"!)
- lukev 11mo agoWell, technically, they're more structuralist than post-structuralist. Arguably they even prove that Saussure's original structuralist hypothesis was correct.
- DiscourseFan 11mo agoI really do not like posting anything about my work on this website. Not only am I extremely constrained in what I can say, many engineers seem to vilify any attempt to legitimate the business. If I could speak freely there'd be no end to what I would tell you to the contrary.
- lukev 11mo agoWell, I'm very interested in this, and if you have things you wish you could speak freely about I can be reached directly via several mediums. My name is not hard to find and I'm on Bluesky & LinkedIn if you want to reach out to me there. I'm one of the authors of this book if you want my full name to search: https://www.amazon.com/Practical-Clojure-Experts-Voice-Source/dp/1430272317/ref=sr_1_1 https://www.amazon.com/Practical-Clojure-Experts-Voice-Sourc...
- DiscourseFan 11mo agoNobody who works on these things will be able to say anything for at least a decade, but trust me there will be textbooks.
- czzr 11mo agoI don’t think LLMs contradict the Pinker description - it just turns out that the output stream embodies a lot of information, and you can construct a model (of some reasonable fidelity) of the original sources from sufficient examples of the output stream.
- suddenlybananas 11mo ago> For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence. Yeah you just need 10 trillion tokens of data.
- nabla9 11mo agoYou saw name "Noam Chomsky" and that started a process in your mind that generated the standard spiel about Syntactic Structures. Chomsky Hierarchy is his more fundamental work that joins computer science and linguistics. It was published in IRE Transactions on Information Theory. Chomsky, Noam (1956). "Three models for the description of language" https://chomsky.info/wp-content/uploads/195609-.pdf https://chomsky.info/wp-content/uploads/195609-.pdf Type-3 grammar ≡ finite-state automaton Type-2 grammar ≡ Non-deterministic pushdown automaton Type-1 grammar ≡ Linear-bounded non-deterministic Turing machine Type-0 grammar ≡ Turing machine ps. Chomsky was already aware of Finite State Automata and Turing Machines and understood that they match Type-3 and Type-0. Pushdown Automata was invented later, and connection between Type-1 grammar and Linear Bounded Automata was made few years later.
- xg15 11mo agoI think it could be useful to combine the two paradigms to maybe get a better understanding of what transformers can and cannot learn. E.g. would it be possible to create an algorithm that takes a grammar (and maybe a desired context window size) as input and constructs a transformer network that generates sentences exactly from that grammar? ("Construct" meaning directly setting the weights, without any iterative training process)
- nabla9 11mo agoThey are combined. Chomsky Hierarchies are the core of modern Computer science because they map perfectly into automata theory. They are always taught together in computer science. >E.g. would it be possible to create an algorithm that takes a grammar (and maybe a desired context window size) as input and constructs a transformer network that generates sentences exactly from that grammar? You don't need transformers for what you describe. That's 101 theory of computation class where you learn about automata, grammars, parsers, and generators.
- xg15 11mo agoYeah, I know the theory of formal grammars and automata that the Chomsky hierarchy is part of. What I meant is that language models and specifically transformer networks are usually entirely separate from that theory, so it would be useful to build a bridge between "modern" language processing using GPTs/LLMs and the classical formal theory. The most obvious overlap in usage is with programming languages: LLMs can parse and generate code in formal languages, but their processing model is completely different from syntax trees and parsers. So the question is, how do they store the formal structure of a programming language and could this be mapped back in any way to a grammar or automaton?
- jesuslop 11mo agoIn a complementary story, from light reading I gather that Zellig Harris, that advised Chomsky's dissertation, contributed decisively to distributional semantics, a forerunner of word embeddings, in turn a key to the door of neural NLP. The ML guys had a shiny toolbox ready to use for decades. Had it been more fashionable... Shalgren, Distributional Legacy: The Unreasonable Effectiveness of Harris’s Distributional Program. https://doi.org/10.1080%2F00437956.2024.2414515 https://doi.org/10.1080%2F00437956.2024.2414515