Automatic Induction of Finite State Transducers for Simple Phonological Rules

Automatic Induction of Finite State Transducers for Simple Phonological Rules Daniel Gildea and Daniel Jurafsky International Computer Science Institute and University of California at Berkeley {gildea,jurafsky} @icsi.berkeley.edu Abstract This paper presents a method for learning phonological rules from sample pairs of un- derlying and surface forms, without negative evidence. The learned rules are represented as finite state transducers that accept underlying forms as input and generate surface forms as output. The algorithm for learning them is an extension of the OSTIA algorithm for learn- ing general subsequential finite state transduc- ers. Although OSTIA is capable of learning arbitrary s.-f.s.t's in the limit, large dictionaries of actual English pronunciations did not give enough samples to correctly induce phonolog- ical rules. We then augmented OSTIA with two kinds of knowledge specific to natural lan- guage phonology, biases from "universal gram- mar". One bias is that underlying phones are often realized as phonetically similar or iden- tical surface phones. The other biases phono- logical rules to apply across natural phonolog- ical classes. The additions helped in learning more compact, accurate, and general transduc- ers than the unmodified OSTIA algorithm. An implementation of the algorithm successfully learns a number of English postlexical rules. 1 Introduction Johnson (1972). first observed that traditional phonolog- ical rewrite rules can be expressed as regular relations if one accepts the constraint that no rule may reapply directly to its own output. This means that finite state transducers can be used to represent phonological rules, greatly simplifying the problem of parsing the output of phonological rules in order to obtain the underlying, lex- ical forms (Karttunen 1993). In this paper we explore an- other consequence of FST models of phonological rules: their weaker generative capacity also makes them easier to learn. We describe our preliminary algorithm for learn- ing rules from sample pairs of input and output strings, and the results we obtained. In order to take advantage of recent work in transducer induction, we have chosen to represent rules as subse- quential finite state transducers. Subsequential finite state transducers are a subtype of finite state transduc- ers with the following properties: 1. The transducer is deterministic, that is, there is only one arc leaving a given state for each input symbol. 2. Each time a transition is made, exactly one symbol of the input string is consumed. 3. A unique end of string symbol is introduced. At the end of each input string, the transducer makes an additional transition on the end of string symbol. 4. All states are accepting. The length of the output strings associated with a subse- quential transducer's transitions is not constrained. The subsequential transducer for the English flapping rule in 1 is shown in Figure 1; an underlying t is realized as a flap after a stressed vowel and any number of r's, and before an unstressed vowel. (1) t ~ dx / (r r* V 2 The OSTIA Algorithm Our phonological-rule induction algorithm is based on augmenting the Onward Subsequential Transducer Infer- ence …

Content truncated to 500 words