2
$\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$
  • 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$ – Mark L. Stone Apr 17 '16 at 1:12
  • 1
    $\begingroup$ Please try to make your question self-contained - could you at least include the formula and the relevant excerpt? $\endgroup$ – Silverfish Apr 17 '16 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$ – Giuseppe Romagnuolo Apr 17 '16 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$ – Giuseppe Romagnuolo Apr 17 '16 at 20:36

Your Answer

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

Browse other questions tagged or ask your own question.