📄 Enhanced Good-Turing and Cat-Cal: Two New Methods for Estimating Probabilities of English Bigrams (abbreviated version)

Summary

Church and Gale tackle a core problem in n-gram language modelling: estimating bigram probabilities when most possible pairs never occur in the training text. The maximum likelihood estimator (MLE) gives such pairs zero probability, and it cannot separate bigrams that share the same count. Using the 1988 Associated Press newswire, split into two near-identical halves by alternating bigrams, the authors compare two estimators. The first is Good-Turing (GT), which relies on frequencies of frequencies. The second is Categorize-Calibrate (Cat-Cal), which groups bigrams by their count in one half and then measures how often each group actually appears in the other half. Both are "enhanced" with a second predictor, jii, the expected bigram frequency if the two words were independent. This lets unseen bigrams receive about 1200 statistically distinct probabilities. Both methods also produce variances, which support fine-grained significance testing between estimators. The main finding is that Cat-Cal works best for very small counts and GT is preferable otherwise. The work matters because it shows how to back off from bigrams to unigrams in a principled, measurable way.

Key points

• Corpus: AP newswire 1988 after near-duplicate removal, with N = 4.4×10^7 tokens and V = 400,653 types. Punctuation and inserted sentence, paragraph and discourse boundary markers count as tokens.
• The corpus was split by taking every other bigram, giving halves of roughly 22M words each. Splitting by half-year instead produced samples that differed too much.
• The space of possible bigrams is V² ≈ 1.6×10^11, so nearly all pairs are unseen. In one half, 2,053,146 bigrams occur exactly once.
• Basic GT assigns unseen bigrams an adjusted count of about 1.28×10^-5, and basic Cat-Cal gives about 1.27×10^-5. The two methods differ only in the third significant figure and agree closely on variances.
• Bigrams are binned by ⌊3·log10 jii⌋ into about 35 groups. For r = 0 this yields about 1245 significantly different estimates, with a t threshold of 1.65. Enhancement still helps up to r ≈ 100.

Interesting ideas

• I1. Cat-Cal can serve as an assumption-light gold standard: bucket items by a training statistic, then read the true rate of each bucket off held-out data.
• I2. Splitting data by alternating units rather than by time or source gives two samples from the same process, which isolates differences between methods from data drift.
• I3. A second, continuous predictor such as independence-based expected frequency can tell apart events that the main count treats as identical, especially unseen ones.
• I4. Each estimate is reported with a variance, and t-scores are summed into an "equivalent number of distinct values." This shows how much real resolution a model has, beyond its average error.
• I5. The authors suggest a usable grouping variable needs two properties: you must be able to count how many types fall in each group, and it should predict the target well. A continuous, ordered variable lets you tune the bin count.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (learn): parser or tagger confidence scores could be calibrated by bucketing silver-data decisions and measuring how often each bucket is right on a held-out witness-agreed split.
• I2 (learn): when building negative controls and A/B comparisons of training recipes, interleave sentences between splits so that genre shift does not mask small method differences.
• I3 (world): unseen verb–argument or entity–relation pairs in the knowledge graph could be ranked by a product of their marginal plausibilities instead of all being treated as equally impossible.
• I4 (learn): evaluation reports could state variances and count significantly distinct confidence levels, so we know whether a scorer genuinely separates cases.
• I5 (tokens): smoothing lemma or morphological-form probabilities for rare words could use an ordered continuous back-off feature, such as unigram-based expectation, with adjustable binning.