3
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ I have no idea what any of this stuff is, nor am I going to spend time to figure it out. Nevertheless, it appears that on the last equality of p. 39, terms which are zero divided by zero are evaluated as zero. i have no idea if that makes any sense. If that's the "correct" thing to do, you will have to implement a more complicated calculation to achieve that behavior (e.g., check if denominator is zero or "too close" to zero, and if so, set the whole term to zero if the numerator is zero). I have no idea whether you can ever get a non-zero divided by a zero, or what you should do in such case. $\endgroup$ Apr 17, 2016 at 1:12
  • 2
    $\begingroup$ Please try to make your question self-contained - could you at least include the formula and the relevant excerpt? $\endgroup$
    – Silverfish
    Apr 17, 2016 at 8:59
  • $\begingroup$ @Silverfish thanks for your suggestion I have expanded the question, hopefully it is clearer what I'm trying to understand. $\endgroup$ Apr 17, 2016 at 20:32
  • $\begingroup$ @MarkL.Stone, thanks for your input and sorry if my question was too vague, there is lots to read in that paper (or in any paper for that matter that explains NLP and Kneser-Ney). I have reformatted my question, hopefully it is clearer. I have to implement this formula for an assignment due very soon so I will have to check if the denominator is zero and amend the code accordingly that is no problem. However my question remains (and probably it is as much as a Math question as it is a Statistical one), how can a formula let in a 0 denominator without accounting for that eventuality? $\endgroup$ Apr 17, 2016 at 20:36

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.