nltk/nltk — pull request #800 by Copper-Head (2014-12-02 18:48:22+00:00)
Title: A stab at fixing the ngram model

The commit messages should give you a good idea of what I've done specifically, so I'm going to give a high-level overview here as well as ask some questions.

1. The goal of this PR isn't necessarily to fix **everything** wrong with the ngram and probability modules but to get started on that task by enabling basic ngram functionality.
2. I've implemented @bcroy's take on backoff from #367 and set Lidstone as the default estimator based on the discussion in #602. I suspect both of these changes have been expected by the community and shouldn't spark much discussion.
3. Here comes the controversial part. I think I've found the cause of the bugs @afourney pointed out in #367. The problem was that nltk's implementation of conditional probability distributions by default breaks up the training sample space into sample spaces for each condition/context. Thus, for every condition/context the denominator is *not* the **N** of the total number of outcomes *but* instead the **N** of outcomes observed given a condition/context. This means that as soon as we start summing over outcomes observed during training *but not* given a certain condition the result will be > 1! I have fixed this by computing an "override_N" value based on the **N** of the whole distribution and then passing that down to the estimator. As of this writing I am certain there's a more natural way to implement this given nltk's class topology. If folks are on board with the concept, I'd be willing to try out some alternative refactorings.
4. @kmike I know we went over this in #326, but I'm still very fuzzy on how testing works. I tried running "tox" from the root of my nltk repo even before I made any of my changes and got 3 to 5 errors right off the bat. I see myself working on the ngram and probability module for a while, so I might as well figure this testing stuff out now with this PR. Who knows, maybe we'll even solve #396!