nltk/nltk — Issue #175: SimpleGoodTuringProbDist is buggy
Author: alexrudnick
Created: 2012-01-17 06:27:48+00:00
State: open

I was working with SimpleGoodTuringProbDist and found that it doesn't seem to work correctly for unseen items.

Here's how to reproduce the bug:

1. Download the reference implementation of the Simple Good Turing estimation technique from Geoffrey Sampson's website (http://grsampson.net/D_SGT.c) and compile it (gcc -lm -o sgt D_SGT.c)

2. Give it an input file that contains frequencies and frequencies of frequencies. Here's the example file that i used

1 2
2 1
3 1
4 3
5 2
6 3
7 2
8 1
9 1
10 1

3. Run ./sgt < test.input. It will output the following smoothed probabilities:

0	0.02273
1	0.01765
2	0.02728
3	0.03682
4	0.04634
5	0.05584
6	0.06534
7	0.07484
8	0.08433
9	0.09382
10	0.1033

4. Now let's replicate this in nltk:

>>> from nltk import SimpleGoodTuringProbDist, FreqDist
>>> fd = FreqDist({'a':1, 'b':1, 'c': 2, 'd': 3, 'e': 4, 'f': 4, 'g': 4, 'h': 5, 'i': 5, 'j': 6, 'k': 6, 'l': 6, 'm': 7, 'n': 7, 'o': 8, 'p': 9, 'q': 10})
>>> p = SimpleGoodTuringProbDist(fd)
>>> p.prob('a') # matches about sgt output
0.017649766667026317
>>> p.prob('o') # matches above sgt output
0.08433050215340411
>>> p.prob('z') # unseen, does not match above sgt output for 0
0.0
>>> p.prob('foobar') # unseen, does not match above sgt output for 0
0.0

So it seems to correctly discount seen items from the vocabulary but does not seem to assign the probability mass Could this be related to issue 26 (already closed)? In any case, I haven't had a chance to figure out exactly where the trouble is but I might look at it over the weekend.

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

earlier comments

nmadnani said, at 2011-08-15T22:36:11.000Z:

Okay, I figured it out. It looks like you explicitly need to specify the number of bins (event types) to include the 'unseen' event. So, from the above example:

>>> from nltk import SimpleGoodTuringProbDist, FreqDist
>>> fd = FreqDist({'a':1, 'b':1, 'c': 2, 'd': 3, 'e': 4, 'f': 4, 'g': 4, 'h': 5, 'i': 5, 'j': 6, 'k': 6, 'l': 6, 'm': 7, 'n': 7, 'o': 8, 'p': 9, 'q': 10})
>>> p = SimpleGoodTuringProbDist(fd, 18) # 17 seen + 1 unseen event
>>> p.prob('a') # matches about sgt output
0.017649766667026317
>>> p.prob('o') # matches above sgt output
0.08433050215340411
>>> p.prob('z') # unseen, matches above sgt output for 0
0.022727272727272728
>>> p.prob('foobar') # unseen, matches above sgt output for 0
0.022727272727272728

However, that seems silly. The whole point of the smoothing is to discount probability mass of seen events and assign to the unseen event so that should be included in the bins by default.

I can fix this unless someone has an idea of why this should be the default.

nmadnani said, at 2011-08-26T17:15:22.000Z:

To be clear, I believe the fix is as simple as this:

1) When instantiating a SimpleGoodTuringProbDist, if the number of bins is unspecified, then set them to be 1 + the number of seen events, or, 1 + the number of bins in the input FreqDist.

2) In the prob() method for SimpleGoodTuringProbDist, if count is 0, no need to return 0 at all, just return the smoothed probabilities.

Steven has suggested, that I write some regression tests (perhaps based on examples from Jurfasky & Martin). I think that's a good idea and I will work on that next week.