Proving the probability of zero occurrences in training using Good-Turing maximum likelihood estimate

Background

Good-Turing (GT) smoothing is used in language models to estimate the counts of words in the test set that have not been seen in the training set.

In GT smoothing, $N_c$ is the count of things observed $c$ times (so a count of a count). As an example, the sentence "Sam I am I am Sam I do not eat" has unigram $N_1=3$ (do, not, eat), unigram $N_2=2$, ...

GT smoothing uses the count of words we've seen once in the training set to estimate the count of words in the test set that we've never seen before. The estimate of the count of these words in the test set that we've never seen before is given by: $$c^*\leftarrow (c+1)\frac{N_{c+1}}{N_c}.$$ This is known as the Good-Turing estimate of Maximum Likelihood Estimate (MLE) for language models. This redistributes probability masses of word occurrences.

The problem

The Good-Turing probability of a word with zero frequency is $$P_{GT}(c=0)=\frac{N_1}{N}.$$

I can't completely see where this comes from. Zero frequency in the training set implies that $c=0\implies c+1=1$, so that coefficient disappearing makes sense. Also, $N_{c+1}=N_{0+1}=N_1$ makes sense in getting the numerator.

But what confuses me is how this implies that $N_0=1$.

The reason $N_0 = 1$ is because: $$P_{GT}(c>0)=\frac{c^*}{N}=\frac{c+1}{N}\frac{N_{c+1}}{N_c},$$ so $$P_{GT}(c=0)=\frac{N_1}{NN_0}=\frac{N_1}{N}$$

How does $N_0=1$?

$N_0$ is the count of the words observed $1$ time, so don't see how this is $1$.

In other words, how is $P_{GT}(c=0)$ fully derived?

• @D.W. What I mean by $P_{GT}(c)$ is the Good Turing probability for a word that appears more than once in the training set (i.e. for that word we have $c>0$), and by $P_{GT}(c=0)$ I mean the probability of a word if that word is not observed in the training set. Does this make it clear that $P_{GT}(c>0)$ and $P_{GT}(c=0)$ both exist and are different? Perhaps my notation is unclear. Mar 30 '18 at 19:22