Kneser Ney smoothing, why the maths allows division by 0?

Question

I'm studying Natural Language Processing and the various smoothing approaches. I'm finding a little hard to understand how to handle unknown words with the Kneser-Ney smoothing. In particular I'm puzzled by the fact that the formula allows in divisions by 0 in case of unknown words and the papers I have read simply say that with unknown words the $P_{(KN)}$ = 0. However in the formula there is a division by 0 which as far as I know should not be allowed.

The equation for bigram probabilities is as follows (more details on Wikipedia):

$P_{(KN)}(w_i|w_{i-1}) = \frac{max(c(w_{-1}, w_{1}) - \delta, 0)}{\sum_{w'}{c(w_{i-1}, w')}} - \lambda_{w_{i-1}}P_{KN} $

It estimate the conditional probability of a word $w_i$, given the word $w_{i-1}$ that preceded this word within a sentence.

Now the problem arises when we haven't encountered in training corpus any word $w_{i-1}$, the denominator $\sum_{w'}{c(w_{i-1}, w')} = 0$ as this is the sum of the count of all contexts where the word $w_{i-1}$ preceded any other words, being the word $w_{i-1}$ unknown this count can only be 0.

An example of where this formula is applied with a 0 denominator is here

https://west.uni-koblenz.de/sites/default/files/BachelorArbeit_MartinKoerner.pdf page 39.

Probably it is as much a Statistical question as it is a Math question.

How can a formula have a denominator that can take the value of 0 without handling for such condition in any way?

And obviously if I got to apply that formula in R I know that I can add some pre-condition that checks the denominator for not being zero and skip the entire formula and just return a 0 probability, but again isn't the formula not very rigorous on its denominator?

Answer 1

There isn’t a division by zero because of two assumptions, all of which are standard procedures in n-gram language modeling.

1. Your vocabulary $V$ is defined from your training corpus. (Consequence: every word $w \in V $ has been seen at least once. $c(w) \geq 1, \forall w \in V $.)
2. The vocabulary $V$ is a proper subset of the set of word types in the training corpus. Any word token not in $V$ is replaced with a special symbol $\textrm {OOV}$. (This is colloquially called UNKing the corpus. This is necessary for any non-trivial, count-based language model.)

As a reminder, we need a fixed vocabulary $V$ of allowable words. These are the values that $w_i$ and $w_{i-1}$ may take on. Typically, we take this to be some subset of the set of word types in the training set. We replace the rest with a special symbol to designate ‘out-of-vocabulary’ (OOV). Sometimes this is instead called ‘unknown’ (UNK).

(I’ve been careless in my exposition about whether OOV is part of the vocabulary.)

---

The final piece of the puzzle is that the denominator can be replaced with a unigram count. $\sum_{w’} c(w_{i-1}w’) = c(w_{i-1})$.

Because of our initial assumptions, this unigram count can never be zero. If the word is a normal member of the vocabulary, this is because it was seen at least once in the training set. If it is not, then we use the special OOV symbol. By assumption 2 and the pigeonhole principle, the count of OOV in the training set is also nonzero. Consequently, in practice we can never divide by zero.

Answer 2

There are two things wrong with the accepted answer:

• First, while the unconditional counts are all positive, the conditional counts (count of word given context) can be zero.

• Second, the count of words given context is not equal to the unigram count! It is equal to the total number of n-grams that begin with that context. These are two completely different numbers.

I am not sure if this is truly a solved problem but I am very sure about those two points.