nltk/nltk — pull request #468 by Tahnan (2013-08-26 17:55:22+00:00)
Title: Correction to _expected_values of ngrams

The formula for the expected values, across n_all k-grams, for n_1 n_2 ... n_k
is:

n_all * p(n_1) * ... * p(n_k)

where p(n) is (number of occurrences of n) / n_all. The previous code's thus
had the formula wrong in two ways.

First, the denominator will be (n_all ** k), which when multiplied by n_all
gives (n_all ** (k - 1)). The previous code had (n_all ** 2), which is right
only in the case of trigrams. Since only bigrams and trigrams were created as
subclasses of NgramAssocMeasures, and the bigram object overrides this method,
the incorrect denominator probably didn't affect many people, so it was easy to
miss.

Second, for "number of occurrences of n", the code previously used the same
code that was used for bigram calculation, cont[i] + cont[i ^ j], for each j
in [1, 2, ..., 2 ** (k - 1)]. However, it's a happy accident that this works
for the bigram case. In the trigram case, the contingency table is 2x2x2:

w3 ~w3
w1 ~w1 w1 ~w1
------- ------- ------- -------
w2 | n_iii | n_oii | w2 | n_iio | n_oio |
------- ------- ------- -------
~w2 | n_ioi | n_ooi | ~w2 | n_ioo | n_ooo |
------- ------- ------- -------

The "cont[i] + cont[i ^ j]" trick takes, for each cell, the row, column, and
"pillar" (i.e. the line along the z axis) containing that cell. But only in the
bigram case is that the number of occurrences of n. Considering the first cell,
n_iii, in the trigram case, this gives (n_iii + n_oii), (n_iii + n_ioi), and
(n_iii + n_iio), which for a trigram ABC counts the occurrences of xBC, AxC,
and ABx, instead of the occurrences of Axx, xBx, and xxC. The correct number
for occurrences of w1 is the entire "left side of the cube": n_iii + n_ioi +
n_iio + n_ioo. Similarly, occurrences of w2 is the entire "back side of the
cube", and w3 is the entire "bottom of the cube" (assuming that the right
square is stacked on top of the left one).

What's actually wanted is code that says "sum the entire line/plane/hyper-plane
containing this cell, along each axis". The new code does this by finding all
cells in the same "first bit" plane, all cells in the same "second bit" plane,
etc, and summing those.

It's not a wholly intuitive formula, so I wanted to put some of this into a
comment in the method, but I wasn't able to coherently boil it down into
anything that would fit. Hopefully this commit message will be enough to,
first, convince people that the new math is correct, and second, inspire
someone to write that clarifying comment.