String Transformation Learning

String Transformation Learning Giorgio Satta Dipartimento di Elettronica e Informatica Universith di Padova via Gradenigo, 6/A 1-35131 Padova, Italy satt a@dei, unipd, it John C. Henderson Department of Computer Science Johns Hopkins University Baltimore, MD 21218-2694 j hndrsn~cs, j hu. edu Abstract String transformation systems have been introduced in (Brill, 1995) and have sev- eral applications in natural language pro- cessing. In this work we consider the com- putational problem of automatically learn- ing from a given corpus the set of transfor- mations presenting the best evidence. We introduce an original data structure and efficient algorithms that learn some fam- ilies of transformations that are relevant for part-of-speech tagging and phonologi- cal rule systems. We also show that the same learning problem becomes NP-hard in cases of an unbounded use of don't care symbols in a transformation. 1 Introduction Ordered sequences of rewriting rules are used in several applications in natural language process- ing, including phonological and morphological sys- tems (Kaplan and Kay, 1994), morphological disam- biguation, part-of-speech tagging and shallow syn- tactic parsing (Brill, 1995), (Karlsson et ah, 1995). In (Brill, 1995) a learning paradigm, called error- driven learning, has been introduced for automatic induction of a specific kind of rewriting rules called transformations, and it has been shown that the achieved accuracy of the resulting transformation systems is competitive with that of existing systems. In this work we further elaborate on the error- driven learning paradigm. Our main contribution is summarized in what follows. We consider some families of transformations and design efficient al- gorithms for the associated learning problem that improve existing methods. Our results are achieved by exploiting a data structure originally introduced in this work. This allows us to simultaneously repre- sent and test the search space of all possible transfor- mations. The transformations we investigate make use of classes of symbols, in order to generalize regu- larities in rule applications. We also show that when an unbounded number of these symbol classes are al- lowed within a transformation, then the associated learning problem becomes NP-hard. The notation we use in the remainder of the paper is briefly introduced here. ~3 denotes a fixed, finite alphabet and e the null string. E* and E+ are the set of all strings and all non-null strings over E, re- spectively. Let w 6 E*. We denote by Iwl the length ofw. Let w = uxv; uis aprefix and v is a suf- fix of w; when x is non-null, it is called a factor of w. The suffix of w of length i is denoted suffi(w), for O < i _< Iwl. Assume that x is non-null, and w = uixsuffi(w ) for ~ > 0 different values of i but not for ~ + 1, or x is not a factor of w and ~ = 0. Then we say that ~ is the statistic of factor z in w. 2 The learning paradigm The learning paradigm we adopt is called error- driven learning and has …

Content truncated to 500 words