A robust transformation-based learning approach using ripple down rules for part-of-speech tagging

1. Introduction

POS tagging is one of the most important tasks in Natural Language Processing (NLP) that assigns a tag to each word in a text, which the tag represents the word’s lexical category [26]. After the text has been tagged or annotated, it can be used in many applications such as machine translation, information retrieval, information extraction and the like.

Recently, statistical and machine learning-based POS tagging methods have become the mainstream ones obtaining state-of-the-art performance. However, the learning process of many of them is time-consuming and requires powerful computers for training. For example, for the task of combined POS and morphological tagging, as reported by Mueller et al. [43], the taggers SVMTool [25] and CRFSuite [52] took 2454 min (about 41 h) and 9274 min (about 155 h) respectively to train on a corpus of 38,727 Czech sentences (652,544 words), using a machine with two Hexa-Core Intel Xeon X5680 CPUs with 3.33 GHz and 144 GB of memory. Therefore, such methods might not be reasonable for individuals having limited computing resources. In addition, the tagging speed of many of those systems is relatively slow. For example, as reported by Moore [42], the SVMTool, the COMPOST tagger [71] and the UPenn bidirectional tagger [66] respectively achieved the tagging speed of 7700, 2600 and 270 English word tokens per second, using a Linux workstation with Intel Xeon X5550 2.67 GHz processors. So these methods may not be adaptable to the recent large-scale data NLP tasks where the fast tagging speed is necessary.

Turning to the rule-based POS tagging methods, the most well-known method proposed by Brill [10] automatically learns transformation-based error-driven rules. In the Brill’s method, the learning process selects a new rule based on the temporary context which is generated by all the preceding rules; the learning process then applies the new rule to the temporary context to generate a new context. By repeating this process, a sequentially ordered list of rules is produced, where a rule is allowed to change the outputs of all the preceding rules, so a word could be relabeled multiple times. Consequently, the Brill’s method is slow in terms of training and tagging processes [27,46].

In this paper, we present a new error-driven approach to automatically restructure transformation rules in the form of a Single Classification Ripple Down Rules (SCRDR) tree [15,57]. In the SCRDR tree, a new rule can only be added when the tree produces an incorrect output. Therefore, our approach allows the interaction between the rules, where a rule can only change the outputs of some preceding rules in a controlled context. To sum up, our contributions are:

The paper is organized as follows: Sections 2 and 3 present the SCRDR methodology and our new approach, respectively. Section 4 details the experimental results while Section 5 outlines the related work. Finally, Section 6 provides the concluding remarks and future work.

OPEN IN VIEWER

Fig. 1.

An example of a SCRDR tree for English POS tagging.

A SCRDR tree [15,48,57] is a binary tree with two distinct types of edges. These edges are typically called except and if-not edges. Associated with each node in the tree is a rule. A rule has the form: if α then β where α is called the condition and β is called the conclusion.

Cases in SCRDR are evaluated by passing a case to the root of the tree. At any node in the tree, if the condition of the rule at a node η is satisfied by the case (so the node η fires), the case is passed on to the except child node of the node η using the except edge if it exists. Otherwise, the case is passed on to the if-not child node of the node η. The conclusion of this process is given by the node which fired last.

For example, with the SCRDR tree in Fig. 1, given a case of 5-word window context “as/IN investors/NNS anticipate/VB a/DT recovery/NN” where “anticipate/VB” is the current word and POS tag pair, the case satisfies the conditions of the rules at nodes (0), (1) and (4), then it is passed on to node (5), using except edges. As the case does not satisfy the condition of the rule at node (5), it is passed on to node (8) using the if-not edge. Also, the case does not satisfy the conditions of the rules at nodes (8) and (9). So we have the evaluation path (0)–(1)–(4)–(5)–(8)–(9) with the last fired node (4). Thus, the POS tag for “anticipate” is concluded as “VBP” produced by the rule at node (4).

A new node containing a new exception rule is added to an SCRDR tree when the evaluation process returns an incorrect conclusion. The new node is attached to the last node in the evaluation path of the given case with the except edge if the last node is the fired node; otherwise, it is attached with the if-not edge.

To ensure that a conclusion is always given, the root node (called the default node) typically contains a trivial condition which is always satisfied. The rule at the default node, the default rule, is the unique rule which is not an exception rule of any other rule.

In the SCRDR tree in Fig. 1, rule (1) – the rule at node (1) – is an exception rule of the default rule (0). As node (2) is the if-not child node of node (1), rule (2) is also an exception rule of rule (0). Likewise, rule (3) is an exception rule of rule (0). Similarly, both rules (4) and (10) are exception rules of rule (1) whereas rules (5), (8) and (9) are exception rules of rule (4), and so on. Therefore, the exception structure of the SCRDR tree extends to four levels: rules (1), (2) and (3) at layer 1; rules (4), (10), (11), (12) and (14) at layer 2; rules (5), (8), (9), (13) and (15) at layer 3; and rules (6) and (7) at layer 4 of the exception structure.

3. Our approach

In this section, we present a new error-driven approach to automatically construct a SCRDR tree of transformation rules for POS tagging. The learning process in our approach is described in Fig. 2.

OPEN IN VIEWER

Fig. 2.

The diagram of our learning process.

The initialized corpus is generated by using an initial tagger to perform POS tagging on the raw corpus which consists of the raw text extracted from the gold standard training corpus, excluding POS tags.

Our initial tagger uses a lexicon to assign a tag for each word. The lexicon is constructed from the gold standard corpus, where each word type is coupled with its most frequent associated tag in the gold standard corpus. In addition, the character 2-, 3-, 4- and 5-gram suffixes of word types are also included in the lexicon. Each suffix is coupled with the most frequent2

To handle unknown words in English, our initial tagger uses regular expressions to capture the information about capitalization and word suffixes.3

By comparing the initialized corpus with the gold standard corpus, an object-driven dictionary of Object and correctTag pairs is produced. Each Object captures a 5-word window context of a word and its current initialized tag in the format of (previous 2nd word, previous 2nd tag, previous 1st word, previous 1st tag, word, current tag, next 1st word, next 1st tag, next 2nd word, next 2nd tag, last-2-characters, last-3-characters, last-4-characters), extracted from the initialized corpus.4

The rule selector is responsible for selecting the most suitable rules to build the SCRDR tree. To generate concrete rules, the rule selector uses rule templates. The examples of our rule templates are presented in Table 1, where the elements in bold will be replaced by specific values from the Object and correctTag pairs in the object-driven dictionary. Short descriptions of the rule templates are shown in Table 2.

The SCRDR rule tree is initialized with the default rule if True then tag = “” as shown in Fig. 1.5

This section presents the experiments validating our proposed approach in 13 languages. We also compare our approach with the TnT6

We run all experiments on a computer of Intel Core i5-2400 3.1 GHz CPU and 8 GB of memory. Experiments on English use the Penn WSJ Treebank [40] Sections 0–18 (38,219 sentences – 912,344 words) for training, Sections 19–21 (5527 sentences – 131,768 words) for validation, and the Sections 22–24 (5462 sentences – 129,654 words) for testing. The proportion of unknown words in the test set is 2.81% (3649 unknown words). We also conduct experiments on 12 other languages. The experimental datasets for those languages are described in Table 3.

Apart from English, it is difficult to compare the results of previously published works because each of them have used different experimental setups and data splits. Thus, it is difficult to create the same evaluation settings used in the previous works. So we perform 10-fold cross validation8

Our approach: In training phase, all words appearing only once time in the training set are initially treated as unknown words and tagged as described in Section 3. This strategy produces tagging models containing transformation rules learned on error contexts of unknown words. The threshold parameters were tuned on the English validation set. The best value pair (3, 2) was then used in all experiments for all languages.

TnT & MarMoT: We used default parameters for training TnT and MarMoT.

From early POS tagging approaches the rule-based Brill’s tagger [10] is the most well-known. The key idea of the Brill’s method is to compare a manually annotated gold standard corpus with an initialized corpus which is generated by executing an initial tagger on the corresponding unannotated corpus. Based on the predefined rule templates, the method then automatically produces a list of concrete rules to correct wrongly assigned POS tags. For example, the template “transfer tag of current word from A to B if the next word is W ” can produce concrete rules such as “transfer tag of current word from JJ to NN if the next word is of ” or “transfer tag of current word from VBD to VBN if the next word is by .”

At each training iteration, the Brill’s tagger generates a set of all possible rules and chooses the ones that help to correct the incorrectly tagged words in the whole corpus. Thus, the Brill’s training process takes a significant amount of time. To prevent that, Hepple [27] presented an approach with two assumptions for disabling interactions between rules to reduce the training time while sacrificing a small amount of accuracy. Ngai and Florian [46] proposed another method to reduce the training time by recalculating the scores of rules while obtaining similar accuracy result.

The main difference between our approach and the Brill’s method is that we construct transformation rules in the form of a SCRDR tree where a new transformation rule is produced only based on a subset of tagging errors. So our approach is faster in term of training speed. In the conference publication version of our approach [49], we reported an improvement up to 33 times in training speed against the Brill’s method. In addition, the Brill’s method enables each subsequent rule to change the outputs of all preceding rules, thus a word can be tagged multiple times in the tagging process, each time by a different rule. This is different from our approach where each word is tagged only once. Consequently, our approach also achieves a faster tagging speed.

In addition to our research, there is only one work that applies Ripple Down Rules method for POS tagging proposed by Xu and Hoffmann [79]. Though Xu and Hoffmann’s method obtained a very competitive accuracy, it is a hand-crafted approach taking about 60 h to manually build a SCRDR tree model for English POS tagging.

Turning to statistical and machine learning methods for POS tagging, these methods can be listed as various Hidden Markov model-based methods [9,20,73], maximum entropy-based methods [12,56,74,75,77], perceptron algorithm-based approaches [13,66,71], neural network-based approaches [11,14,33,38,59,60,80], Conditional Random Fields [34,35,37,43,44], Support Vector Machines [25,31,63,69] and other approaches including decision trees [61,62] and hybrid methods [19,36]. Overview about the POS tagging task can be found in [26,28].

6. Conclusion and future work

In this paper, we propose a new error-driven method to automatically construct a Single Classification Ripple Down Rules tree of transformation rules for POS and morphological tagging. Our method allows the interaction between rules where a rule only changes the results of a limited number of other rules. Experimental evaluations for POS tagging and the combined POS and morphological tagging on 13 languages show that our method obtains very promising accuracy results. In addition, we successfully achieve fast training and tagging processes for all experimental languages. This could help to significantly reduce time and effort for the machine learning tasks on big data, employing POS and morphological information as learning features.

An important point is that our approach is suitable to involve domain experts to add new exception rules given concrete cases that are misclassified by the tree model. This is especially important for under-resourced languages where obtaining a large annotated corpus is difficult. In future work, we plan to build tagging models for other languages such as Russian, Arabic, Latin, Hungarian, Chinese and so forth.

Bibliographic note

This paper extends the work published in our conference publications [47,49]. We make minor revisions to our published approach to yield improved accuracy results on English and Vietnamese, and we conduct new extensive empirical study on 11 other languages.