Brief
Using NumPy and Python dicts, implement modified Kneser–Ney smoothing with interpolation, three discounts per order, and export to the ARPA file format (the standard text format for n-gram models). Kneser–Ney gives probability to word sequences you never saw by subtracting a small discount from every seen count and handing that mass to shorter contexts. Interpolation means you always mix in the shorter-context estimate. 'Three discounts per order' means separate discounts for n-grams seen once, twice, and three or more times, for each n-gram length. Train on the first 90M characters of text8 and evaluate on the last 5M. Add top-k sampling (sample only from the k most likely next words) and nucleus sampling (sample from the smallest set of words whose probabilities add up to p). Report bits per character so the later LSTM and GPT projects can compare on the same split.
VICTORY CONDITIONS
- perplexity within 1% of KenLM; your ARPA file loads in KenLM's query tool and gets identical scores there (word-level perplexity (how surprised the model is on average; lower is better) and bits/char on the held-out text8 slice; peak RAM).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- n-gram language model
- A model that predicts the next word from counts of how often each short word sequence appeared in training text.
- Kneser–Ney smoothing
- A way to move a little probability from seen word sequences to unseen ones, based on how many different contexts a word appears in.
- Perplexity
- The exponential of the average negative log-likelihood; roughly, how many words the model is choosing between at each step.
- Bits per character
- The average number of bits the model needs to encode each character; lower is better and it is comparable across tokenizers.
- ARPA format
- A plain-text file format for n-gram models that tools like KenLM can read.
Why it rates ★☆☆☆☆
n-gram LMs are pre-2013 technology. The value is the baseline it gives the later projects.