A Short Prehistory of Statistical NLP

I think understanding where we came from makes the current state of things make a lot more sense. Like, why do we call it a "vocabulary"? Why are n-grams still relevant? Why is perplexity the metric everyone reaches for first? Why does every paper on transformers compare against "statistical baselines"?

Transformers didn't appear from nowhere. Every design choice in modern LLMs, every architectural decision, every training trick, is a reaction to something that came before. Something that worked, or more often, something that failed in an instructive way.

This post is a map of that territory. It's the last post in Arc 1, and it's different from the others. The first seven posts were math: vectors, distributions, cross-entropy, gradients, optimizers. Here we're telling a story. But it's a story that will make all of Arc 2 (and really, the rest of the series) land more cleanly, because you'll know why each idea was invented, not just what it does.

Let me start from the beginning.

The rule-based era (1950s–1980s)

The first serious attempt to get machines to process language was, predictably, to teach them the rules. Language has grammar, right? Subjects precede verbs in English. Adjectives go before nouns. If you could just write down all the rules, a computer could parse any sentence.

It started with Turing. His 1950 paper "Computing Machinery and Intelligence" proposed the imitation game: a machine converses with a human judge through text, and if the judge can't reliably tell it's a machine, the machine is intelligent. Whatever you think about that as a definition of intelligence, it framed the problem. Language became the test case for machine intelligence. It's been that way ever since.

Chomsky's Syntactic Structures (1957) gave the field its theoretical backbone. He showed that natural language could be described by formal grammars, hierarchical rules for generating valid sentences. This was a profound insight for linguistics. But it also sent a generation of AI researchers down a particular path: if language has formal rules, then understanding language means discovering and encoding those rules.

The most famous product of this era was ELIZA, built by Weizenbaum at MIT in 1966. ELIZA was a chatbot that played the role of a Rogerian therapist. It worked by pattern matching. If you said "I feel sad," it would match on "I feel X" and respond with "Why do you feel sad?" No understanding whatsoever. Just keyword-triggered decomposition and reassembly rules, which is the ancestor of the pattern/template tricks we'd now associate with regex-style systems.

And people loved it. Weizenbaum was disturbed by how quickly his own secretary started having emotional conversations with the thing. He wrote an entire book warning about the dangers of attributing intelligence to machines that were clearly just shuffling symbols. The question of how much intelligence to read into a surface-level imitation hasn't gone away.

Then there was SHRDLU (1971), Winograd's blocks-world system. You could tell it "pick up the red block" and it would understand the command, reason about the state of the world, and execute the action. It handled pronoun resolution, ambiguity, even some conversational context. Genuinely impressive.

In a tiny world of colored blocks on a table.

That was the catch. SHRDLU worked because its world was small enough to hand-code completely. Every object had a known shape, color, and position. Every possible action was enumerated. Every sentence it needed to understand was about blocks. The moment you tried to scale this approach to open-domain language, it collapsed. Language is too ambiguous. Too context-dependent. Too vast. You can't write enough rules.

By the early 1980s, the rule-based approach had reached its zenith with expert systems and hand-crafted knowledge bases. These were expensive to build, brittle in practice, and couldn't handle the relentless ambiguity of real human language. A single word like "bank" has dozens of meanings. A sentence like "Time flies like an arrow; fruit flies like a banana" has nearly parallel surface form, but the second half forces a different parse: "flies" flips from verb to plural noun and "like" flips from verb to preposition. You can't resolve that with rules. You need context, statistics, world knowledge, the stuff that doesn't fit in a grammar.

The statistical revolution (1990s)

The turn happened gradually through the 1980s and then decisively in the early 1990s. The key figure was Fred Jelinek at IBM, who was working on speech recognition. His team had been building statistical models for converting audio to text, and they were dramatically outperforming the rule-based systems that linguists had been crafting by hand.

The famous (possibly apocryphal) quip: "Every time I fire a linguist, the performance of the speech recognizer goes up."

That line sounds like a joke, but it captures a genuine paradigm shift. The insight was: you don't need to understand language to model it. You need to model the probability of sequences. Given a bunch of text data, you can count how often certain words follow certain other words, and use those counts to estimate probabilities. The model doesn't know what words mean. It knows what words tend to appear next to each other.

This is the intellectual ancestor of everything we do today. GPT-4 doesn't understand language either, at least not in the way you and I do. It models the probability distribution over what comes next. It's a sophisticated version of the same fundamental idea Jelinek's team was pursuing in the late 1980s.

Shannon had already framed this in 1951 as a guessing game. Hide the next character of a piece of English text from a person, ask them to guess, and measure how often they're right. The number of bits of surprise per character is a measure of how predictable English is. Shannon estimated about 1 bit per character once you have enough context, which is wildly less than the ~4.7 bits you'd need if every letter were equiprobable. That gap, between max entropy and actual entropy, is the room a language model gets to operate in. Watch the per-character entropy collapse as context accumulates:

The landmark paper was Brown et al. (1993) from the IBM group. They introduced statistical machine translation: given a French sentence, find the English sentence that maximizes $P(\text{English} | \text{French})$. Using Bayes' rule, this decomposes into a language model (what's the probability of this English sentence?) and a translation model (how likely is this alignment between French and English words?). Both were estimated from data with the EM algorithm. No linguistic rules. Just counting and probability. Those word-alignment models later gave way to phrase-based statistical MT (Koehn et al., Moses), which ran production translation through the late 2000s.

Around the same time, Hidden Markov Models became the standard tool for part-of-speech tagging and speech recognition: model a sequence as hidden states (the tags) generating observed symbols (the words), estimate the transition and emission probabilities from labeled data, then use Viterbi to recover the most likely state sequence for a new sentence.

The 2000s added a wave of discriminative models that fit neither the n-gram nor the HMM mold. Maximum-entropy classifiers, CRFs, and SVMs became the workhorses for tagging, parsing, named-entity recognition, and document classification. They ran on hand-engineered feature templates rather than raw counts, which bought accuracy over n-gram baselines but kept the field dependent on human-designed features. That dependence is what the neural revival eventually broke.

The pattern was clear: data + statistics > rules. Given enough data and the right probabilistic framework, you could build systems that handled ambiguity gracefully, because the statistics naturally captured the fact that "bank" usually means a financial institution unless you're talking about rivers.

N-gram models: simple, powerful, dominant

The workhorse of this era was the n-gram language model. The idea couldn't be simpler. To estimate the probability of a word given its history, just count how often that sequence appeared in your training data.

For a bigram model (n=2):

How often did "the cat" appear in the corpus, divided by how often "the" appeared? That's your estimate for $P(\text{cat} | \text{the})$. For a trigram model, you condition on the two previous words. For a 4-gram, three. And so on.

N-gram models dominated language modeling for about two decades. They were fast to train (just count things), fast at inference (just look things up), and with the right smoothing techniques, surprisingly effective. Kneser-Ney smoothing (1995) was the gold standard for redistributing probability mass to unseen n-grams, and it held that position for fifteen-plus years.

But there's a fundamental problem, and you can hit it with a corpus of four sentences. Train a bigram model on "the cat sat on the mat," "the cat ate the fish," "the dog sat on the rug," "the dog ate the bone." Then ask it for $P(\text{zebra} | \text{the})$. The count of "the zebra" is 0 and the count of "the" is 8, so the estimate is $0/8$. Not low probability. Zero.

And a sentence's probability is the product of its bigram probabilities, so "the zebra ate the fish" gets probability zero too, no matter how ordinary the rest of it is. Perplexity comes back infinite. One unseen pair poisons the entire sentence.

This is the sparsity problem, and more data doesn't rescue you from it. The number of possible n-grams grows exponentially with n. For a trigram model over a vocabulary of 50,000 words, there are $50{,}000^3 = 1.25 \times 10^{14}$ possible trigrams. No corpus is big enough to observe even a meaningful fraction of them. Most of the n-grams you need at test time were never seen during training.

Smoothing is the family of fixes: steal probability mass from the events you did see and hand it to the ones you didn't. Add-one sprays it uniformly, interpolation mixes in a lower-order fallback, Kneser-Ney asks the smarter question of how many distinct contexts a word shows up in. The next arc opens with n-grams and sparsity, which builds the count tables and works through each of those methods on real numbers.

But every one of those methods is still shuffling a fixed pool of probability mass between symbols. None of them can learn that "the zebra" is a perfectly reasonable phrase because "the" often precedes animal names, or that "incredible" and "amazing" are near-synonyms that should have similar distributions. To an n-gram model every word is an opaque symbol with no relationship to any other. There's no notion of similarity, so there's no generalization.

That limitation is what neural language models were invented to fix.

The neural revival (2003–2012)

For most of the 1990s and 2000s, neural networks were out of fashion. The AI winters had cooled enthusiasm, SVMs and random forests worked well for many tasks, and the hardware wasn't there for training large networks. NLP was firmly statistical-but-not-neural.

The paper that changed the trajectory was Bengio et al. (2003), "A Neural Probabilistic Language Model." Earlier neural sequence work existed (Elman's recurrent networks, for example), so this wasn't the first time anyone trained a neural net on language. What Bengio et al. did was give the field its canonical neural probabilistic LM, jointly learning word embeddings and next-word prediction. Instead of treating each word as an opaque symbol and counting co-occurrences, you learn a continuous vector (an embedding) for each word and predict the next word from the embeddings of the context.

That's what breaks the zebra problem. If "cat" and "dog" land near each other (because they showed up in similar contexts during training), a model that's seen "the cat sat" can assign reasonable probability to "the dog sat" without ever having seen that trigram. The representations carry similarity information that raw counts can't. Architecturally the model was modest, a lookup table, one hidden layer, and a softmax over the vocabulary, but it was learning something categorically different from counting. It was learning representations.

A different line of work made a related point out of raw co-occurrence counts rather than a trained network, and Pennington et al. would later turn it into GloVe. That thread gets its own post later: GloVe and fastText.

Then Collobert and Weston (2008) pushed further. They showed you could train a single neural architecture to do multiple NLP tasks: part-of-speech tagging, named entity recognition, chunking, semantic role labeling. The features were learned, not hand-engineered. This was a direct challenge to the prevailing practice of designing task-specific feature templates for each NLP problem. One architecture, learned features, competitive performance across the board.

But the real explosion came with the Word2vec line of work, starting in 2013. Mikolov et al. at Google introduced two simplified architectures, CBOW and Skip-gram, that trained word embeddings fast and at scale, along with the practical tricks (subsampling frequent words, negative sampling instead of a full softmax) that made the approach cheap enough to run on billions of tokens. The resulting vectors turned out to encode semantic relationships as geometry, which is where the famous "king minus man plus woman lands near queen" example comes from. The full walkthrough of how that works, and why the offsets line up, is in word2vec.

Word2vec made embeddings mainstream. Suddenly every NLP pipeline started with pre-trained word vectors instead of hand-crafted features. And that shift, from feature engineering to representation learning, is one of the most important conceptual transitions in the history of the field. It's still the core idea behind modern LLMs: let the model learn its own representations from data.

The deep learning wave (2013–2017)

Once embeddings went mainstream, the next question was obvious: what if you don't just use embeddings as input features for a traditional classifier, but instead use deep neural networks for the entire pipeline? End-to-end learning. Raw text in, predictions out.

Recurrent neural networks (RNNs) seemed like the natural architecture for sequences. They process tokens one at a time, carrying a hidden state that accumulates information from the history. In theory that lets a model remember arbitrary long-range dependencies. In practice, gradients shrink exponentially as you backpropagate through timesteps, so by 50 steps back there's no usable signal left, and the model can't learn the dependencies it was supposed to. Arc 2 covers RNNs and the vanishing gradient properly.

LSTMs (Hochreiter and Schmidhuber, 1997, though not widely adopted until the 2010s) mitigated this by adding a separate cell state with gates that control what gets remembered, forgotten, and emitted. That's the subject of LSTMs and GRUs.

LSTMs worked well enough to power the next leap. Sutskever et al. (2014) showed you could translate between languages with two of them, an encoder that reads the source sentence into a single fixed-length vector and a decoder that generates the target from it. No alignment tables, no phrase-based rules, just end-to-end training. And it worked surprisingly well, until the sentences got long and that one fixed vector became a bottleneck.

Bahdanau et al. (2015) patched the bottleneck by letting the decoder look back at all the encoder states instead of a single summary. That's attention entering the mainstream, invented as a fix for a specific seq2seq problem rather than as a grand idea about architecture. Seq2seq and Bahdanau attention takes both apart.

And then came Vaswani et al. (2017): "Attention Is All You Need." Self-attention, no recurrence, no convolutions. The Transformer.

What made it land wasn't only that it worked well, though it did. It was that it parallelized. RNNs and LSTMs process tokens in order, so you can't compute the hidden state at position 50 until you've computed the 49 before it. Transformers attend over all positions at once, which turns out to be a much better fit for hardware built for massive parallelism, and that's what let them scale to the sizes we see today.

Arc 4 is where the architecture actually gets built. For now the point is just where it sits in the story: transformers solved the parallelism problem RNNs couldn't, while capturing long-range dependencies better than the recurrent models they replaced.

The interactive timeline

The full arc from rules to statistics to neural networks to transformers. Each era's failures motivated the next era's innovations.

What survived

Here's the thing that I find fascinating about this history. Transformers replaced essentially all of the architectures from these earlier eras for frontier general-purpose language modeling. Nobody is building a GPT competitor as an LSTM or an n-gram model in 2026. But n-grams in particular still quietly run in narrower production niches: ASR decoders still use them as language models inside WFST-based pipelines, on-device speech and IME stacks lean on them for latency and footprint, and frameworks like NVIDIA's Riva still ship the tooling to train and serve them. The architectures are obsolete at the frontier; the concepts from these eras are everywhere in the modern stack.

The vocabulary. The idea that a language model operates over a fixed set of discrete tokens comes straight from statistical NLP. Modern tokenizers (BPE, WordPiece, SentencePiece) are more sophisticated than word-level vocabularies, but the core concept is the same: define a finite set of symbols, map text to sequences of those symbols, model the probability distribution over those sequences. We'll cover this in detail in Arc 3.

The language model as a probability distribution. $P(w_t | w_1, \ldots, w_{t-1})$. This formulation, the chain rule decomposition that we covered in Post 1.3, goes back to Shannon. Every autoregressive model, from bigrams to GPT-4, is estimating this conditional distribution. The architecture changed beyond recognition. The objective didn't.

Perplexity. Still the standard intrinsic evaluation metric for language models. We covered it in Post 1.4. It's the exponentiated cross-entropy, $2^{H(p,q)}$ when $H$ is in bits or $e^{H(p,q)}$ when $H$ is in nats. Same metric, different base, so check which one a paper means before comparing numbers. It was the primary evaluation metric for n-gram models long before anyone dreamed of transformers, and when someone today reports perplexity 8.5 on WikiText-103, they're using a metric that was designed for and popularized by the statistical NLP community.

Data quality and scale matter more than architecture. This is maybe the deepest lesson from the statistical era. Jelinek's team didn't win because they had a better algorithm than the linguists. They won because they had more data and a framework that could exploit it. The same lesson applies today, arguably even more so. Scaling laws (Kaplan et al., 2020; Hoffmann et al., 2022) show that model performance is a predictable function of data, compute, and parameters. The architecture matters, but the data matters more.

Representation learning beats feature engineering. This is the lesson from the neural revival. Collobert and Weston showed it. Word2vec made it visceral. And it's still the core thesis of deep learning: let the model learn its own representations from data, instead of designing them by hand.

Misconceptions

"Everything before transformers is irrelevant." It's a common framing in post-2020 writeups, but the vocabulary concept, the perplexity metric, the shift from rules to statistics, the importance of data quality, these are all things that show up constantly in working with modern models. The architectures are obsolete. The concepts are load-bearing.

"Neural networks were always dominant in NLP." They really weren't. From the late 1990s through about 2012, the dominant paradigm was statistical but non-neural: n-gram models, SVMs, CRFs, maximum entropy classifiers. Neural networks for NLP were a niche research interest. Bengio's 2003 paper was published to a mostly indifferent community. It took another decade, the convergence of big data, GPU computing, and key architectural innovations, before neural approaches became dominant. The shift was fast once it started, but the long winter before it is important context.

"Transformers were inevitable." They were not. Attention was invented as a pragmatic fix for a specific problem: the information bottleneck in seq2seq models. Bahdanau's attention let the decoder look at all encoder states instead of just one summary vector. That was a clever engineering solution, not a theoretical breakthrough. The leap to self-attention, where tokens in a single sequence attend to each other, where you drop recurrence entirely and replace it with attention, that was Vaswani et al.'s unexpected contribution. It could easily not have happened, or happened much later, or happened in a form that didn't scale. The path from "attention helps seq2seq" to "attention is all you need" was not a straight line.

What's next

That's the end of Arc 1. We have the math (vectors, distributions, cross-entropy, gradients, optimizers) and now the history that explains why the math is arranged the way it is.

Arc 2 starts with next-token prediction, the objective that Jelinek's team, the n-gram modelers, Bengio, and GPT-4 all share, and then builds the whole statistical-to-neural progression back up from counting.

Additional reading (and watching)

• Turing, A. M. (1950). Computing Machinery and Intelligence. Mind, 59(236), 433-460.
• Chomsky, N. (1957). Syntactic Structures. Mouton & Co.
• Weizenbaum, J. (1966). ELIZA — A Computer Program For the Study of Natural Language Communication Between Man And Machine. Communications of the ACM, 9(1), 36-45.
• Winograd, T. (1971). Procedures as a Representation for Data in a Computer Program for Understanding Natural Language. MIT AI Laboratory.
• Jelinek, F. (1985). The Development of an Experimental Discrete Dictation Recognizer. Proceedings of the IEEE, 73(11). The "fire a linguist" quote is widely attributed to Jelinek, though its exact origin and wording are disputed. See also Jelinek, F. (1997). Statistical Methods for Speech Recognition. MIT Press.
• Brown, P. F., et al. (1993). The Mathematics of Statistical Machine Translation: Parameter Estimation. Computational Linguistics, 19(2), 263-311.
• Kneser, R. & Ney, H. (1995). Improved Backing-Off for M-Gram Language Modeling. ICASSP 1995. The smoothing method that held the state of the art for fifteen years.
• Bengio, Y., et al. (2003). A Neural Probabilistic Language Model. JMLR, 3, 1137-1155.
• Collobert, R. & Weston, J. (2008). A Unified Architecture for Natural Language Processing. ICML 2008.
• Mikolov, T., et al. (2013). Efficient Estimation of Word Representations in Vector Space. arXiv:1301.3781.
• Hochreiter, S. & Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation, 9(8), 1735-1780.
• Sutskever, I., Vinyals, O., & Le, Q. V. (2014). Sequence to Sequence Learning with Neural Networks. NeurIPS 2014.
• Bahdanau, D., Cho, K., & Bengio, Y. (2015). Neural Machine Translation by Jointly Learning to Align and Translate. ICLR 2015.
• Vaswani, A., et al. (2017). Attention Is All You Need. NeurIPS 2017.
• Shannon, C. E. (1951). Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 50-64. The guessing-game experiment that estimated the entropy of English at roughly 1 bit per character.