nltk/nltk — Issue #142: clarifying n-gram tagger memory requirements, section 5.5
Author: alexrudnick
Created: 2012-01-17 06:27:02+00:00
State: open

Comment for: June 2009 first edition, section 5.5

First off, I liked the approach in your discussion of the limits of what you call n-gram tagging. It's interesting to see how many times tag[n-2], tag[n-1], word[n] lead to different tag[n]. This still won't give you a lower bound on held-out error, as there's no reason to believe there won't be sampling error in the original corpus -- thus held-out performance will likely be worse than estimated by your method.

At first I thought you were doing something like an HMM, where you actually use the following tags as context implicitly when you condition tag[n+1] on tag[n] and so on. So this isn't an upper bound on models that use n-gram statistics -- you can do better with an HMM because of the overlaps in the prediction contexts and outcomes.

Second, the storage isn't as bad as you make out for the key reason that it's limited by the size of training corpora. If you use Brown, there's 1M tokens, so you need to store at most 1M n-grams. So I don't think we'll be faced with the "hundreds of millions of entries" you suggest on page 208. (Of course, you could get there if you use some kind of semi-supervised learning.)

Thus I don't understand why you say "it is simply impractical for n-gram models to be conditioned on the identities of the words in context". This will again be limited by the training set size. You actually see all kinds of conditioning on the words these days in conditional random fields (CRFs). You also see conditioning on words in an HMM-like model in the old BBN approach to named entities in Nymble (which I adopted for the first tagger I implemented in LingPipe 1). You see it in Collins' parser for PCFGs.

I don't know if you've seen the Ratinov and Roth paper on
features for tagging, but it's very interesting. They actually
found a MEMM-type approach with very very little backtracking
could perform very well with unbounded context-length predictive features.

Ratinov, Lev and Dan Roth. 2009. Design Challenges and Misconceptions in Named Entity Recognition. In CoNLL.
http://www.aclweb.org/anthology/W/W09/W09-1119.pdf

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