nltk/nltk — Issue #158: NgramModel.prob bug
Author: alexrudnick
Created: 2012-01-17 06:27:23+00:00
State: open

I am using 2.0.1 nltk version

I am using NgramModel(2,train_set)
in case the tuple is no in the _ngrams, backoff Model is invoked.
In our case it is Unigram Model.
Ngram.prob doesn't know to treat unseen words using Unigram Model, and it will raise an exception.

the original code:

def prob(self, word, context):
"""
Evaluate the probability of this word in this context.
"""

context = tuple(context)
if context + (word,) in self._ngrams:
return self[context].prob(word)
elif self._n > 1:
return self._alpha(context) * self._backoff.prob(word, context[1:])
else:
raise RuntimeError("No probability mass assigned to word %s in " +
"context %s" % (word, ' '.join(context)))
)

i propose to replace the exception with the call to calculate the prob of the unseen word:

prob(self, word, context):
"""
Evaluate the probability of this word in this context.
"""

context = tuple(context)
if context + (word,) in self._ngrams:
return self[context].prob(word)
elif self._n > 1:
return self._alpha(context) * self._backoff.prob(word, context[1:])
else:
return self[context].prob(word)

if it is for example a LidstoneProbDist estimator which sent as an argument to the NgramModel, it will know how to treat the unseen word.

After the fix it works fine.

Migrated from http://code.google.com/p/nltk/issues/detail?id=673

earlier comments

SilaiSantai said, at 2011-07-29T12:19:56.000Z:

The fix written here seem to also solve this issue:

http://code.google.com/p/nltk/issues/detail?id=694&can=1&q=ngrammodel

StevenBird1 said, at 2011-08-07T11:56:01.000Z:

Why should we do smoothing instead of backoff when self._n == 0?

smgorelik said, at 2011-08-07T12:04:21.000Z:

when self._n==0 we don't have to do smoothing and usually if the smoothing Technic is good enough self._n==1 will always return a proper answer. I proposed a solution for the case of unigram smoothing where self_n==1 (it was not covered in a previous version)

dan.blanchard said, at 2011-08-15T02:12:49.000Z:

The fix here is certainly more intuitive than the current case where unseen unigrams cause an exception even when you're using an estimator that can handle them (e.g., LidstoneProbDist). Any chance of this fix being accepted?

dan.blanchard said, at 2011-08-16T02:39:49.000Z:

I've attached a modified version of ngram.py that incorporates the previously proposed fix (albeit in a slightly cleaner fashion), adds the ability to pass optional arguments on to the estimator (instead of always passing the number of bins), and contains comments describing what the arguments of many of the functions were (since those were previously omitted). Oh, and it also removes imports that weren't being used (e.g., random).

joel.nothman said, at 2011-08-16T07:09:38.000Z:

I am not sure to what extent the following is a related issue, but it is not resolved in patched version Dan has offered. Unknown contexts (at least those found in the first n-1 tokens) produce entropies less than 0, implying probabilities greater than 1:

from nltk.corpus import brown, treebank
from nltk.probability import LidstoneProbDist, WittenBellProbDist
estimator = lambda fdist, bins: LidstoneProbDist(fdist, 0.2)
lm = NgramModel(3, treebank.words(), estimator)
print lm.entropy(['asdfsa', 'asfsf', ','])
print lm.entropy(['Vinken', 'Vinken', ',', '61'])

output:

-0.977147035825
-1.58496250072

Is problematic that the probability of the first n-1 tokens is not directly calculated in the entropy function?

dan.blanchard said, at 2011-08-24T16:57:27.000Z:

You're right that the entropy calculation was incorrect. I've gone ahead and fixed that too (assuming we wanted cross-entropy, since that's how most people evaluate language models). The main changes were that I added self._prefix to the front of the text so that the first n-1 words are properly handled, and I divided the sum of the log probabilities by the length sample text.

Since we're calculating the cross-entropy, I also added a function to calculate the perplexity as well.

nmadnani said, at 2011-08-25T14:59:01.000Z:

Steven, if we use this fix and then SimpleGoodTuringProbDist that I proposed in issue 674, then NgramModel should work much better. Please let me know if you want me to work on this.

rmyeid said, at 2011-10-02T16:39:34.000Z:

After replacing the old ngram modules with the new posted on Aug 25, I get a new error.

*Code:*
estimator = lambda fdist, bins: GoodTuringProbDist(fdist, 2*fdist.N())
model = nltk.NgramModel(3, words, estimator)
model.prob('lol', ('this', 'is'))

Traceback (most recent call last):
File "", line 1, in
File "/usr/local/lib/python2.7/dist-packages/nltk/model/ngram.py", line 96, in prob
return self._alpha(context) * self._backoff.prob(word, context[1:])
File "/usr/local/lib/python2.7/dist-packages/nltk/model/ngram.py", line 96, in prob
return self._alpha(context) * self._backoff.prob(word, context[1:])
File "/usr/local/lib/python2.7/dist-packages/nltk/model/ngram.py", line 99, in _alpha
return self._beta(tokens) / self._backoff._beta(tokens[1:])
File "/usr/local/lib/python2.7/dist-packages/nltk/model/ngram.py", line 103, in _beta
return self[tokens].discount()
File "/usr/local/lib/python2.7/dist-packages/nltk/probability.py", line 1345, in discount
return 1.0 * self._freqdist.Nr(1) / self._freqdist.N()
ZeroDivisionError: float division by zero

dan.blanchard said, at 2011-10-02T17:59:34.000Z:

Nitin, I believe you meant issue 710, not 674.

rmyeid, could you please tell me what you set "words" to in your example? When I use the brown corpus with the same estimator you're using like this:

model = NgramModel(3, brown.words(categories='news'), estimator)

I don't encounter the same problem. There is a different issue because GoodTuringProbDist is currently broken (see issue 710), so model.prob('lol', ('this', 'is')) returns 0, but I don't get a division by zero error.

StevenBird1 said, at 2011-12-01T01:53:17.000Z:

Apologies for the delay. Dan's new version of ngram.py is adopted in the source tree, with tweaks to the documentation for Sphinx compatibility.
https://github.com/nltk/nltk/commit/80a6603364b81297bda034725493913649be1bbd

rmyeid said, at 2011-12-01T07:22:28.000Z:

Is this expected ?
m = ngram.NgramModel(1, [str(i) for i in [1,2,32,43,54,5,1,1,1,1,1,2,3,4,7]])
m.prob("99", [])
# OUT: 0.4666666666666667
m.prob("99", ["1"])
# OUT: 1.0

StevenBird1 said, at 2012-01-06T19:09:15.000Z:

Right, there's clearly something going wrong here.

>>> m = ngram.NgramModel(1, [str(i) for i in [1,2,3,4,5]])
>>> m.prob("1", [])
0.0
>>> m.prob("0", [])
1.0

dan.blanchard said, at 2012-01-06T19:48:01.000Z:

I believe that's a bug in SimpleGoodTuringProbDist, and not in NgramModel. If I use an estimator with an MLEProbDist, I get the expected results:

>>> from nltk.probability import MLEProbDist
>>> def estimator(fdist, bins):
... return MLEProbDist(fdist)
...
>>> m = ngram.NgramModel(1, [str(i) for i in [1,2,3,4,5]], estimator)
>>> m.prob("99", [])
0.0
>>> m.prob("1", [])
0.2
>>> m.prob("2", [])
0.2
>>> m.prob("3", [])
0.2
>>> m.prob("4", [])
0.2
>>> m.prob("5", [])
0.2

dan.blanchard said, at 2012-01-06T19:53:08.000Z:

It also works if you use LaplaceProbDist. It is my understanding that issue 710 is still present, and SimpleGoodTuringProbDist (which is what NgramModel uses by default) is still broken.

>>> def estimator(fdist, bins):
... return LaplaceProbDist(fdist)
...
>>> m = ngram.NgramModel(1, [str(i) for i in [1,2,3,4,5]], estimator)
>>> m.prob("99", [])
0.1
>>> m.prob("1", [])
0.2
>>> m.prob("2", [])
0.2
>>> m.prob("3", [])
0.2
>>> m.prob("4", [])
0.2
>>> m.prob("5", [])
0.2

rmyeid said, at 2012-01-06T21:50:01.000Z:

@dan
It does not look from your example that LaplaceProbDist actually works, the summation of the probabilities is greater than one!

dan.blanchard said, at 2012-01-06T21:56:31.000Z:

LaplaceProbDist is only guaranteed to sum to 1 when you pass the number of possible outcomes as the "bins" keyword argument when creating the distribution. For a case like the example above, where there are more possible outcomes than in the initial sample, it will not sum to one.