5.6.2 How TBL Rules Are Learned

Brill's TBL algorithm has three major stages. It first labels every word with its most-likely tag. It then examines every possible transformation, and selects the one that results in the most improved tagging. Finally, it then re-tags the data according to this rule. The last two stages are repeated until some stopping criterion is reached, such as insufficient improvement over the previous pass. Note that stage two requires that TBL knows the correct tag of each word; that is, TBL is a supervised learning algorithm.

The output of the TBL process is an ordered list of transformations; these then constitute a “tagging procedure” that can be applied to a new corpus. In principle the set of possible transformations is infinite, since we could imagine transformations such as “transform NN to VB if the previous word was “IBM” and the word “the” occurs between 17 and 158 words before that”. But TBL needs to consider every possible transformation, in order to pick the best one on each pass through the algorithm. Thus the algorithm needs a way to limit the set of transformations. This is done by designing a small set of templates (abstracted transformations). Every allowable transformation

is an instantiation of one of the templates. Brill's set of templates is listed in Fig. 5.20. Fig. 5.21 gives the details of this algorithm for learning transformations.

At the heart of Fig. 5.21 are the two functions GET_BEST_TRANSFORMATION and GET_BEST_INSTANCE. GET_BEST_TRANSFORMATION is called with a list of potential templates; for each template, it calls GET_BEST_INSTANCE. GET_BEST_INSTANCE iteratively tests every possible instantiation of each template by filling in specific values for the tag variables a, b, z, and w.

In practice, there are a number of ways to make the algorithm more efficient. For example, templates and instantiated transformations can be suggested in a data-driven manner; a transformation-instance might only be suggested if it would improve the tagging of some specific word. The search can also be made more efficient by pre-indexing the words in the training corpus by potential transformation. Roche and Schabes (1997) show how the tagger can also be speeded up by converting each rule into a finite-state transducer and composing all the transducers.

Fig. 5.22 shows a few of the rules learned by Brill's original tagger.

5.7 EVALUATION AND ERROR ANALYSIS

The probabilities in a statistical model like an HMM POS-tagger come from the corpus it is trained on. We saw in Sec. ?? that in order to train statistical models like taggers or N-grams, we need to set aside a training set. The design of the training set or training corpus needs to be carefully considered. If the training corpus is too specific to the task or domain, the probabilities may be too narrow and not generalize well to tagging sentences in very different domains. But if the training corpus is too general, the probabilities may not do a sufficient job of reflecting the task or domain.

For evaluating N-grams models, we said in Sec. ?? that we need to divide our corpus into a distinct training set, test set, and a second test set called a development test set. We train our tagger on the training set. Then we use the development test set (also called a devtest set) to perhaps tune some parameters, and in general decide what the best model is. Then once we come up with what we think is the best model, we run it on the (hitherto unseen) test set to see its performance. We might use 80% of our data for training, and save 10% each for devtest and test. Why do we need a development test set distinct from the final test set? Because if we used the final test

function TBL(corpus) returns transforms-queue

INITIALIZE-WITH-MOST-LIKELY-TAGS(corpus)

until end condition is met do

templates ← GENERATE-POTENTIAL-RELEVANT-TEMPLATES

best-transform ← GET-BEST-TRANSFORM(corpus, templates)

APPLY-TRANSFORM(best-transform, corpus)

ENQUEUE(best-transform-rule, transforms-queue)

end

return(transforms-queue)

function GET-BEST-TRANSFORM(corpus, templates) returns transform

for each template in templates

(instance, score) ← GET-BEST-INSTANCE(corpus, template)

if (score > best-transform.score) then best-transform ← (instance, score)

return(best-transform)

function GET-BEST-INSTANCE(corpus, template) returns transform

for from-tag ← from tag₁ to tagₙ do

for to-tag ← from tag₁ to tagₙ do

for pos ← from 1 to corpus-size do

if (correct-tag(pos) == to-tag && current-tag(pos) == from-tag)

num-good-transforms(current-tag(pos-1))++

else if (correct-tag(pos) == from-tag && current-tag(pos) == from-tag)

num-bad-transforms(current-tag(pos-1))++

end

best-Z ← ARGMAXₜ(num-good-transforms(t) - num-bad-transforms(t))

if (num-good-transforms(best-Z) - num-bad-transforms(best-Z) > best-instance.score) then

best-rule ← “Change tag from from-tag to to-tag if prev tag is best-Z”

best-score ← num-good-transforms(best-Z) - num-bad-transforms(best-Z)

return(best)

procedure APPLY-TRANSFORM(transform, corpus)

for pos ← from 1 to corpus-size do

if (current-tag(pos) == best-rule-from)

&&(current-tag(pos-1)) == best-rule-prev))

current-tag(pos) ← best-rule-to

Figure 5.21 The TBL algorithm for learning to tag. GET_BEST_INSTANCE would have to change for transformation templates other than “Change tag from X to Y if previous tag is Z”. After Brill (1995).

set to compute performance for all our experiments during our development phase, we would be tuning the various changes and parameters to this set. Our final error rate on the test set would then be optimistic: it would underestimate the true error rate.

| # | Change tags | Condition | Example | | |

| --- | --- | --- | --- | --- | --- |

| From | To | | | | |

| 1 | NN | VB | Previous tag is TO | to/TO race/NN $ \rightarrow $ VB | |

| 2 | VBP | VB | One of the previous 3 tags is MD | might/MD vanish/VBP $ \rightarrow $ VB | |

| 3 | NN | VB | One of the previous 2 tags is MD | might/MD not reply/NN $ \rightarrow $ VB | |

| 4 | VB | NN | One of the previous 2 tags is DT | | |

| 5 | VBD | VBN | One of the previous 3 tags is VBZ | | |

The problem with having a fixed training set, devset, and test set is that in order to save lots of data for training, the test set might not be large enough to be representative. Thus a better approach would be to somehow use all our data both for training and test. How is this possible? The idea is to use crossvalidation. In crossvalidation, we randomly choose a training and test set division of our data, train our tagger, and then compute the error rate on the test set. Then we repeat with a different randomly selected training set and test set. We do this sampling process 10 times, and then average these 10 runs to get an average error rate. This is called 10-fold crossvalidation.

The only problem with cross-validation is that because all the data is used for testing, we need the whole corpus to be blind; we can't examine any of the data to suggest possible features, and in general see what's going on. But looking at the corpus is often important for designing the system. For this reason it is common to create a fixed training set and test set, and then to do 10-fold crossvalidation inside the training set, but compute error rate the normal way in the test set.

Once we have a test set, taggers are evaluated by comparing their labeling of the test set with a human-labeled Gold Standard test set, based on accuracy: the percentage of all tags in the test set where the tagger and the Gold standard agree. Most current tagging algorithms have an accuracy of around 96–97% for simple tagsets like the Penn Treebank set. These accuracies are for words and punctuation; the accuracy for words only would be lower.

How good is 97%? Since tagsets and tasks differ, the performance of tags can be compared against a lower-bound baseline and an upper-bound ceiling. One way to set a ceiling is to see how well humans do on the task. Marcus et al. (1993), for example, found that human annotators agreed on about 96–97% of the tags in the Penn Treebank version of the Brown corpus. This suggests that the Gold Standard may have a 3-4% margin of error, and that it is meaningless to get 100% accuracy, (modeling the last 3% would just be modeling noise). Indeed Ratnaparkhi (1996) showed that the tagging ambiguities that caused problems for his tagger were exactly the ones that humans had labeled inconsistently in the training set. Two experiments by Voutilainen (1995, p. 174), however, found that when humans were allowed to discuss tags, they reached consensus on 100% of the tags.

Human Ceiling: When using a human Gold Standard to evaluate a classification algorithm, check the agreement rate of humans on the standard.

The standard baseline, suggested by Gale et al. (1992) (in the slightly different context of word-sense disambiguation), is to choose the unigram most-likely tag for

PAIRED TESTS

WILCOXON

SIGNED-RANK TEST

PAIRED T:TESTS

MAPSSWE

MCNEMAR TEST

each ambiguous word. The most-likely tag for each word can be computed from a hand-tagged corpus (which may be the same as the training corpus for the tagger being evaluated).

Most Frequent Class Baseline: Always compare a classifier against a baseline at least as good as the most frequent class baseline (assigning each token to the class it occurred in most often in the training set).

Tagging algorithms since Harris (1962) incorporate this tag frequency intuition. Charniak et al. (1993) showed that this baseline algorithm achieves an accuracy of 90–91% on the 87-tag Brown tagset; Toutanova et al. (2003) showed that a more complex version, augmented with an unknown word model, achieved 93.69% on the 45-tag Treebank tagset.

When comparing models it is important to use statistical tests (introduced in any statistics class or textbook for the social sciences) to determine if the difference between two models is significant. Cohen (1995) is a useful reference which focuses on statistical research methods for artificial intelligence. Dietterich (1998) focuses on statistical tests for comparing classifiers. When statistically comparing sequence models like part-of-speech taggers, it is important to use paired tests. Commonly used paired tests for evaluating part-of-speech taggers include the Wilcoxon signed-rank test, paired t-tests, versions of matched t-tests such as the Matched-Pair Sentence Segment Word Error (MAPSSWE) test originally applied to speech recognition word error rate, and the McNemar test.