A Short Prehistory of Statistical NLP

Language modeling draws on several overlapping traditions: formal grammars, probabilistic sequence models, and learned representations. Following those threads explains why counting, perplexity, and embeddings still appear in modern systems.

This last post in Arc 1 traces the problems those approaches addressed. Arc 2 will work through their mechanisms.

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

Early language-processing systems used hand-written rules for grammar and meaning. A grammar could describe patterns such as an adjective preceding a noun; a parser could then use those rules to analyze a sentence.

Turing's 1950 paper "Computing Machinery and Intelligence" proposed the imitation game: a judge communicates through text and tries to distinguish a machine from a human. It made conversation one way to investigate machine intelligence.

Chomsky's Syntactic Structures (1957) developed formal grammars as a way to describe sentence structure. For language-processing systems, grammars offered explicit rules that could be encoded and applied by a parser.

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. An illustrative rule might match "I feel X" and turn it into "Why do you feel X?" Its responses came from keyword-triggered decomposition and reassembly rules, a predecessor of later pattern/template systems.

Weizenbaum’s 1966 paper describes how readily readers attributed more understanding to ELIZA than its decomposition and reassembly rules provided.

SHRDLU (1971), Winograd's blocks-world system, interpreted commands such as "pick up the red block" in a small world of colored blocks on a table. It could resolve pronouns, handle ambiguity, and use conversational context within that domain.

SHRDLU relied on known objects, attributes, and actions. Extending its handcrafted representation to open-domain language would require far more knowledge and ambiguity handling.

Handcrafted grammars and knowledge bases require rules for the domains they cover. Extending them means adding and maintaining those rules, while selecting among valid parses can require context. 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 preposition to verb. A grammar can represent both parses; choosing the intended reading often also needs context or world knowledge.

The statistical revolution (1990s)

During the 1980s and early 1990s, Fred Jelinek's team at IBM developed statistical methods for speech recognition. They estimated likely word sequences from speech and text data, combining probability models with engineering and linguistic choices.

A language model estimates probabilities of sequences. Counts of words and their contexts provide one way to estimate those probabilities, without hand-writing a rule for every possible continuation.

Autoregressive language models retain that sequence-probability objective, while using learned representations to share information across contexts.

Shannon studied the predictability of English in 1951 by asking people to guess hidden characters. His experiments bounded the entropy rate, with estimates around one bit per character given substantial context. That is much less than $\log_2 27 \approx 4.75$ bits for a uniform alphabet of 26 letters plus space. The hand-tuned predictions below illustrate that use of context.

Brown et al. described statistical machine translation in 1990 and developed the IBM alignment models in detail in 1993. A noisy-channel formulation chooses the English sentence maximizing $P(\text{French}\mid\text{English})P(\text{English})$. The translation model learns latent word alignments using EM; a separate language model scores English sequences. Phrase-based statistical translation later expanded the units beyond individual words.

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 also brought discriminative models such as maximum-entropy classifiers, CRFs, and SVMs to tagging, parsing, named-entity recognition, and document classification. They used hand-engineered feature templates to capture task-specific evidence. Neural methods later learned more of those features from data.

N-gram models: simple, powerful, dominant

The workhorse of this era was the n-gram language model. 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 estimate probabilities through count tables, making training and lookup comparatively direct. Smoothing improves estimates for rare or unobserved sequences. Kneser-Ney (1995) became an influential method using lower-order continuation counts.

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$. The maximum-likelihood estimate is exactly 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. A single zero factor makes the product zero.

This is the sparsity problem. The number of possible n-grams grows exponentially with n: a vocabulary of 50,000 words permits $50{,}000^3 = 1.25 \times 10^{14}$ trigrams. Larger corpora cover more of them, but still leave many plausible contexts unseen.

Smoothing reserves probability mass for unobserved events. Add-one increments every count, interpolation mixes in lower-order estimates, and Kneser-Ney uses counts of distinct contexts in its fallback distribution. N-grams and sparsity builds the tables and works through these methods numerically.

Smoothing shares evidence through lower-order counts and backoff rules. An ordinary word n-gram model does not learn that "cat" and "dog" have similar uses, so observing "the cat sat" does not directly improve its estimate for "the dog sat." Neural representations offer a way to share evidence between such words.

The neural revival (2003–2012)

Statistical models with engineered features were common in NLP during the 1990s and 2000s. Neural language-model research developed alongside them.

Bengio et al. (2003), "A Neural Probabilistic Language Model," jointly learned word embeddings and next-word prediction. The model used context-word vectors as inputs, allowing similar words to share predictive information. Earlier recurrent work, including Elman's, had also trained neural networks on sequences.

Learned representations help with unseen combinations of known words. If "cat" and "dog" acquire similar vectors, training on "the cat sat" can improve a prediction for "the dog sat" without observing that trigram. A closed-vocabulary model still has no representation for an entirely unknown word such as "zebra" in the four-sentence corpus above. Bengio's model combined a lookup table, a hidden layer, and a vocabulary softmax.

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.

Collobert and Weston (2008) trained a shared neural architecture on tasks including part-of-speech tagging, named-entity recognition, chunking, and semantic-role labeling. Their learned features reduced reliance on separately engineered feature templates for each task.

Word2vec made these representations much cheaper to train, 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.

Pretrained word vectors became common features in NLP pipelines, used alongside task-specific features. Modern language models continue to learn representations from data, but train them jointly with deeper contextual computation.

The deep learning wave (2013–2017)

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, repeated Jacobian products can make gradients vanish or explode. 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.

Sutskever et al. (2014) demonstrated translation with an LSTM encoder and decoder trained end to end. The encoder compressed the source into a fixed-length vector, which the decoder used to generate the target. That interface placed the burden of retaining source information on one summary.

Bahdanau et al. (2014 preprint, published in 2015) let the decoder attend to individual encoder states. This gave it access to source positions beyond the final encoder summary. Seq2seq and Bahdanau attention develops that mechanism.

And then came Vaswani et al. (2017): "Attention Is All You Need." The Transformer built its encoder and decoder around attention, without recurrent or convolutional sequence layers. Self-attention itself had appeared in earlier work.

Transformers allow training computations at different token positions to run in parallel within a layer. An RNN or LSTM must compute the preceding hidden state before the next one. Removing that dependency made the transformer a better fit for parallel hardware, though autoregressive generation still proceeds token by token.

Arc 4 works through the transformer architecture and its attention connections between positions.

The interactive timeline

Selected milestones from overlapping research traditions. The dates mark publications, not a clean replacement of one approach by another.

What survived

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.

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. Perplexity was used to evaluate n-gram models and remains useful for comparing language-model probabilities under a matched evaluation protocol.

Learned representations share information across examples. Embeddings let training on one word or context affect predictions for related ones. That reduces the need to design every feature by hand, while leaving substantial choices about data and model structure.

Misconceptions

"Everything before transformers is irrelevant." Vocabulary design, perplexity, smoothing, learned representations, and encoder-decoder structure all predate transformers. Later posts use these concepts to explain current models.

"Neural networks were always dominant in NLP." Non-neural methods, including n-grams, SVMs, CRFs, and maximum-entropy models, remained common while neural approaches developed. Bengio's 2003 model was an early neural language-model result, not evidence that the field had already adopted neural networks broadly.

"Transformers invented self-attention." Earlier work used attention within a single sequence. Vaswani et al. made it the central sequence-processing mechanism of an encoder-decoder architecture, removing recurrence and convolution from those layers. That design improved training parallelism; autoregressive generation still produces tokens sequentially.

What's next

Arc 2 starts with next-token prediction, then compares count-based and neural ways to estimate those probabilities.

Additional reading (and watching)

• Brown, P. F., et al. (1990). A Statistical Approach to Machine Translation. The earlier IBM presentation of the statistical translation approach.

• 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). 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. Introduces continuation-based smoothing for n-gram models.

• 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.