The u-TBL System: Logic Programming Tools for Transformation-Based Learning

The #-TBL System: Logic Programming Tools for Transformation-Based Learning TorbjSrn Lager Department of Linguistics Uppsala University Torbj orn. Lager~ling. uu. se Abstract The #u-TBL system represents an attempt to use the search and database capabilities of the Prolog pro- gramming language to implement a generalized form of transformation-based learning. In the true spirit of logic-programming, the implementation is 'derived' from a declarative, logical interpretation of transforma- tion rules. The #-TBL system recognizes four kinds of rules, that can be used to implement various kinds of disambiguators, including Constraint Grammar dis- ambiguators as well as more traditional 'Brill-taggers'. Results from a number of experiments and benchmarks are presented which show that the system is both flex- " ible and efficient. Introduction Since Eric Brill first introduced the method of Trans- formation-Based Learning (TBL) it has been used to learn rules for many natural language processing tasks, such as part-of-speech tagging [Brill, 1995], PP- attachment disambiguation [Brill and Resnik, 1994], text chunking [Ramshaw and Marcus, 1995], spell- ing correction [Mangu and Brill, 1997], dialogue act tagging [Samuel et al., 1998] and ellipsis resolution [Hardt, 1998]. Thus, TBL has proved very useful, in many different ways, and is likely to continue to do so in the future. Moreover, since Brill generously made his own TBL implementation publicly available, l many researchers in need of all off-the-shelf retrainable part-of-speech tag- ger have found what they were looking for. However, although very useful, Brill's original implementation is somewhat opaque, templates are not compositional, IThroughout this paper, when referring to Brill's TBL implementation, it is always his contextual-rule-learner - implemented in C - that I have in mind. "It is available from http://www, cs. jhu. edu/~brill/, along with ~veral other learners and utility programs. and they are hard-wired into the program. Therefore, the program is difficult to modify and extend. What is more, it is fairly slow. This paper is dedicated to the design and implemen- tation of an alternative transformation-based learner system, called "the #-TBL system" (pronounced "mu- table"). The p-TBL system is designed to be the- oretically transparent, flexible and efficient. Trans- parency is achieved by performing a 'logical reconstruc- tion' of TBL, and by deriving the system from there. Flexibility is achieved through the use of a composi- tional rule and template formalism, and 'pluggable' "al- gorithms. As for the implementation, it turns out that transformation-based learning can be implemented very straightforwardly in a logic programming language such as Prolog. Efficient indexing of data, unification and backtracking search, as well as established Prolog pro- gramming techniques for building rule compilers and meta-interpreters, contribute to the making of a logi- cally transparent, easily extendible, and fairly efficient system. 2 The content of the paper is presented in a bottom-up fashion, starting from the semantics of transformation rules. First, I show that, contrary to what is often as- sumed, transformation rules can be given a declarative, logical interpretation. I then introduce the IL-TBL sys- tem, which in a manner of speaking is derived from this …

Content truncated to 500 words