Efficient Transformation-Based Parsing

Efficient Transformation-Based Parsing Giorgio Satta Eric Brill Dipartimento di Elettronica ed Informatica Department of Computer Science Universit£ di Padova Johns Hopkins University via Gradenigo, 6/A Baltimore, MD 21218-2694 2-35131 Padova, Italy brill©cs, jhu. edu satta@dei, unipd, it Abstract In transformation-based parsing, a finite sequence of tree rewriting rules are checked for application to an input structure. Since in practice only a small percentage of rules are applied to any particular structure, the naive parsing algorithm is rather ineffi- cient. We exploit this sparseness in rule applications to derive an algorithm two to three orders of magnitude faster than the standard parsing algorithm. 1 Introduction The idea of using transformational rules in natu- ral language analysis dates back at least to Chore- sky, who attempted to define a set of transfor- mations that would apply to a word sequence to map it from deep structure to surface structure (see (Chomsky, 1965)). Transformations have also been used in much of generative phonology to cap- ture contextual variants in pronunciation, start- ing with (Chomsky and Halle, 1968). More re- cently, transformations have been applied to a di- verse set of problems, including part of speech tagging, pronunciation network creation, preposi- tional phrase attachment disambiguation, and pars- ing, under the paradigm of transformation-based error-driven learning (see (Brill, 1993; Brill, 1995) and (Brill and Resnik, 1994)). In this paradigm, rules can be learned automatically from a training corpus, instead of being written by hand. Transformation-based systems are typically deter- ministic. Each rule in an ordered list of rules is ap- plied once wherever it can apply, then is discarded, and the next rule is processed until the last rule in the list has been processed. Since for each rule the application algorithm must check for a matching at all possible sites to see whether the rule can apply, these systems run in O(rrpn) time, where 7r is the number of rules, p is the cost of a single rule match- ing, and n is the size of the input structure. While this results in fast processing, it is possible to create much faster systems. In (Roche and Schabes, 1995), a method is described for converting a list of trans- formations that operates on strings into a determin- istic finite state transducer, resulting in an optimal tagger in the sense that tagging requires only one state transition per word, giving a linear time tag- ger whose run-time is independent of the number and size of rules. In this paper we consider transformation-based parsing, introduced in (Brill, 1993), and we im- prove upon the O(Trpn) time upper bound.. In transformation-based parsing, an ordered sequence of tree-rewriting rules (tree transformations) are ap- plied to an initial parse structure for an input sen- tence, to derive the final parse structure. We observe that in most transformation-based parsers, only a small percentage of rules are actually applied, for any particular input sentence. For example, in an application of the transformation-based parser de- scribed in (Brill, 1993), 7r = 300 rules …

Content truncated to 500 words