nltk/nltk — pull request #549 by muneson (2013-11-17 12:44:06+00:00)
Title: update to nltk.tag.brill 

This is a proposed update to the brill tagger for nltk3, with
main differences with respect to the one of nltk2 as indicated below.

I realize this is a bit big for a pull request -- it is offered to nltk
much as an afterthought, or it would have been come in more
digestible pieces. Still, I tried to redo my successive refactorization
( the largest change), into the first few commits,
so that later changes are mostly incremental (and should "mostly"
work, too). It is a point of departure, anyway.

**Modularization and isolation of application-specific code**

PR is split into subpackages (its predecessor is thoroughly monolitic).
This should make it easier to implement new
alternative training algorithms and other extensions, of which there are many.
It is also not biased towards POS tagging, which is just a single thing
out of many that TBL is good for, and there should be natural homes
for future non-postagging applications.

Here is the present layout of the update:

brill/
__init__.py #desired exports

nltk2/ #(for backwards compatibility)
__init__.py
demo.py #demo
postagging #class ProximateTagsRule, ProximateWordsRule
template #class ProximateTokensTemplate,
# SymmetricProximateTokensTemplate,
# ProximateTokensRule

application/
__init__.py
postagging #class Word, Pos
... #future implementations of other applications

trainer/
__init__.py #desired exports and defaults for training algorithms
fast #class TaggerTrainer
brillorig #class TaggerTrainer
... #future implementations of alternative trainers
#(e.g Florian & Ngai, Samuel, Hepple, dos Santos ...)
#and other extensions (multidimensional TBL,
#probabilistic TBL, constraint-grammar-styled TBL,
#transformation-based regression, etc)
demo/
__init__.py
postagging #postagging demo
postagging_templates #predefined template sets (e.g., from publications)
... #future demos of other applications

tagger #class BrillTagger

rule #class BrillRule (abstract), Rule

template #class BrillTemplateI, Template, Feature (abstract)

erroranalysis #error_list
... #future additions -- export rules to FST, graphing, etc

**Feature specification**
Any number of features is allowed at any number of positions (not
necessarily contiguous). They are expressed so :

templates = [ # or start, end args (as in nltk2):
Template(Word([-3,-2,-1]), # Template(Word(-3, -1))
Template(Word([1,2,3]), # Template(Word(1, 3))
Template(Tag([-1]), Tag([1])),
Template(Tag([-1]), Word([1,2]))
]

**Feature- and Template-generating factory functions**
There is a Feature.expand(startat, winlen) which generates lists
of Features, and at Template.expand([Featurelists]) which basically builds
the Cartesian product of such lists (or manually specified ones),
with semantic duplicates removed. For instance,

wordtpls = Word.expand([-1,0,1], [1,2], excludezero=False)
tagtpls = Pos.expand([-2,-1,0,1], [1,2], excludezero=True)
templates = list(Template.expand([wordtpls, tagtpls, tagtpls], combinations=(1,3)))

will generate 53 unique templates with 1..3 features each (all non-empty combinations of
Word(wordpositions), Tag(...), Tag(...), where (for instance)
wordpositions contains all the ways of starting of one of
[-1, 0, 1] and looking at a window of length one of [1,2]).
See docstring for more.

**Feature computation**
The abstract extract_token() method takes the entire current token sequence
and the current index as input, instead of a single token; this makes it
possible to compute aggregate features (sequence length, say).

**Accuracy threshold**
Rules with lower accuracy than a threshold will be discarded. This may
hurt performance a bit, but will often produce rules which are more interesting
read to a human (which in some cases may be the main interest).

**String representations of rules**
A rule now knows what template it was created from, which is useful
for statistical analysis. repr(rule) looks so:

156 194 38 24 | Rule(029, 'NN', 'NNP', [(Pos([-2, -1]),'NNP')])
92 100 8 19 | Rule(018, 'NN', 'VB', [(Word([-1]),'to')])
51 53 2 1 | Rule(020, 'VBD', 'VBN', [(Pos([1]),'-NONE-'),
| (Pos([2]),'IN')])

str(rule) returns a compact, logic-based representation:

156 194 38 24 | NN->NNP if Pos:NNP@[-2,-1]
92 100 8 19 | NN->VB if Word:to@[-1]
51 53 2 1 | VBD->VBN if Pos:-NONE-@[1] & Pos:IN@[2]

The wordier str(rule) of nltk2 is also available

156 194 38 24 | NN -> NNP if the Pos of words i-2...i-1 is "NNP"
92 100 8 19 | NN -> VB if the Word of the preceding word is "to"
51 53 2 1 | VBD -> VBN if the Pos of the following word is "-NONE-",
| and the Pos of word i+2 is "IN"

**Template statistics**
There is a diagnostic tagger.print_template_statistics() method which ranks all
templates according to the total relative scores (in training or, optionally, testing)
they have been involved in (useful to speed up training and/or suggest new templates).

**Incremental tagging**
Statististics for individual rules is collected in training and can (optionally,
slow) also be collected in testing by batch_tag_incremental() method.
This gives statistics for individual rules which may be used to plot learning curves
such as

![learningcurve](https://f.cloud.github.com/assets/5937152/1558283/0f7c9d4e-4f7c-11e3-93be-31982989e1cb.png)

**A demo with a documented function for each of the above**
in the form of a postag() function with many default arguments,
and different named wrappers around it.