A language model made of nothing but counts
Tokenization & decoding · Part 5 of 8
Before neural networks, language models were just tables of counts. Build one and the ideas from the last post, probabilities, perplexity and sampling, stop being abstract. It also shows exactly what a neural model has to do better.
Count what follows what
A character n-gram model predicts the next letter from the previous few letters. To train it, slide along the text and count which letter followed each context. To predict, turn the counts for the current context into probabilities.
Test it on text it has not seen
I wrote a short text of about 2,400 characters with 40 different symbols, trained on the first 90% and measured perplexity on the rest. A model that knows nothing has perplexity 40, one choice among 40 symbols. Longer context should help, up to a point:
| Letters of context | Raw counts | With a little added to every count | Backing off to shorter contexts |
|---|---|---|---|
| 0 | 18.9 | 18.9 | 19.0 |
| 1 | 39.5 | 11.8 | 12.0 |
| 2 | 2,624 | 10.0 | 9.2 |
| 3 | 567,451 | 12.4 | 8.4 |
| 4 | 30,409,374 | 16.8 | 8.6 |
| 5 | 423,779,693 | 21.4 | 8.9 |
Read the table as a story about generalisation:
- With raw counts, even one letter of context already hurts (39.5, against 18.9 with none), and from two letters on the scores run into the thousands and millions. A longer context nearly always appears in the test text for the first time, has no counts, and so gets probability zero. Zero probability is catastrophic for the score.
- Adding a small amount to every count avoids the zeros, but it spreads probability evenly over letters that make no sense.
- Backing off to shorter contexts when the long one is rare is far better. The best model, with 3 letters of context, reaches about 8.4: roughly five times better than guessing.
What the models write
Letting the models sample text (same text, a fixed random seed) shows the same story:
- 1 letter of context:
Thas thes wont te gre t. ans the aft beattorr cucam tothe a t teandas the cis alderche. thefil ntoke - 3 letters of context:
The of the fix in light team when the wrong is replies the worder, and ever ask what counted are. Fo - 5 letters of context:
The warehouse opens at the works together to worry. At night the start. The driver sign, and the cus
Short context gives gibberish with English-like sounds. A medium context gives local phrases that do not add up to sentences. A long context starts to copy its training text, because there is little else to continue with.
Build your own
Open in Colab Count, smooth, measure perplexity and sample text on a short text. Free in your browser.
Takeaways
- A count table is a complete, tiny language model.
- Raw counts fail on unseen contexts: zero probability ruins the score.
- Smoothing and backing off to shorter contexts fix it.
- Neural models generalise to unseen contexts because similar contexts get similar vectors.
Next in the series (Part 6): Greedy and beam search: the best word or the best sentence?