First and foremost, thank you for your reaction.

The transformation rules
I’m still working on the transformation rules and especially the relation between their frequency and error reduction score. I based my post on the 1992 article A simple rule-based part of speech tagger (bold is mine):

“The initial tagger was trained on 90% of the corpus (the training corpus). 5% was held back to be used for the patch acquisition procedure (the patch corpus) and 5% for testing. Once the initial tagger is trained, it is used to tag the patch corpus. A list of tagging errors is compiled by comparing the output of the tagger to the correct tagging of the patch corpus. This list consists of triples < taga, tagb, number >, indicating the number of times the tagger mistagged a word with taga when it should have been tagged with tagb in the patch corpus. Next, for each error triple, it is determined which instantation of a template from the prespecified set of patch templates results in the greatest error reduction.”

The initial tagger Brill refers to in the quote is the frequency-based tagger. Brill’s method differs from the one you (and I) use, but it seems quite clear that the list and score of the instantation rules is calculated using the patch corpus and not the original training corpus. This seems logical to me, because the rules have to correct the initial tagger and the mechanism of tagging unknown words as nouns. If you derive the rules from (tagging) the original training corpus, however, there will be no unknown words. Isn’t that a problem, even if the scoring function will select the most effective rules?

Unknown words
I have no problem whatsoever with tagging unknown words as “NN”. It’s an efficient and elegant solution. At http://www.nlpwp.org, however, you seem to do the following:

1. Train the tagger using a training corpus
2. Run the tagger on the training corpus
3. Tag unknown words as “NN”
4. Distil transformation rules from the tagged file.

My point is that step 3 is unnecessary, because there are no unknown words. Every word in the traing corpus is – by definition – in the initial tagger. I tried this (but didn’t publish the results) and calculating the transformation rules with or without your function backoffTagger will yield exactly the same result, i.e. the same list of rules, in the same order, with the same frequency.

One or two files?
I understand your decision to work with one corpus. But you do not create a set of rules that takes into account unknown words (cf. my previous point). I have no idea whether this influences the performance of the finished tagger, it’s something I could try to find out along the way. But maybe you could use 95% of the corpus as a training file and 5% as a patch file? I’m sure your readers won’t mind…

More recent research has shown that HMM, maxent, and SVM taggers outperform transformation-based tagging by a pretty wide margin. We chose to discuss a TBL tagger, because it is conceptually nice and simple, and allows us to show off some Haskell magic.

“This very simple algorithm has an error rate of about 7.9% when trained on 90% of the tagged Brown Corpus [...] The initial tagger was trained on 90% of the corpus (the training corpus).”

With respect to tagging unknown words in the initial tagging state in our examples: we do this, because the user could have trained the most-likely word tagger using another (large) corpus. In such a case you’d have to handle unknown words. If you use one training corpus for training the initial tagger and the contextual rules, that is obviously not necessary.

May be a bit too soon, but could you not persist the rules discovered by the Brill tagger so that he can reuse them in future. I would think that if you keep repeating that you should end up with a pretty strong tagger. Except that previously learned rules may not be entirely correct (or ideal) and start dominating later rules…

Anyway, those nlpwp guys should consider hiring you to write their book! ;-)

http://www.chrisdb.me.uk/redmine/projects/haskell-sound-change/repository

For the sake of clarity I would also stick to the normal sorting methods for the book. On the other hand, you could add a footnote with the information in your comment for the sake of completeness. That way, the reader has both a clear explanation and a pointer to a more efficient sorting method (in C).

http://www.cs.dartmouth.edu/~doug/sarray/

There is also more recent work, such as Kärkkainen et al., 2005.

For the book, when we have to choose between performance and clarity, the latter usually wins ;).