Automatic Acquisition of Two-Level Morphological Rules

Automatic Acquisition of Two-Level Morphological Rules Pieter Theron Dept. of Computer Science Stellenbosch University Stellenbosch 7600, South Africa ptheron@cs, sun. ac. za Ian Cloete Dept. of Computer Science Stellenbosch University Stellenbosch 7600~ South Africa ia/~@cs, sun. ac. za Abstract We describe and experimentally evaluate a complete method for the automatic ac- quisition of two-level rules for morphologi- cal analyzers/generators. The input to the system is sets of source-target word pairs, where the target is an inflected form of the source. There are two phases in the acquisi- tion process: (1) segmentation of the target into morphemes and (2) determination of the optimal two-level rule set with minimal discerning contexts. In phase one, a mini- mal acyclic finite state automaton (AFSA) is constructed from string edit sequences of the input pairs. Segmentaiion of the words into morphemes is achieved through view- ing the AFSA as a directed acyclic graph (DAG) and applying heuristics using prop- erties of the DAG as well as the elemen- tary edit operations. For phase two, the determination of the optimal rule set is made possible with a novel representation of rule contexts, with morpheme bound- aries added, in a new DAG. We introduce the notion of a delimiter edge. Delimiter edges are used to select the correct two- level rule type as well as to extract minimal discerning rule contexts from the DAG. Re- sults are presented for English adjectives, Xhosa noun locatives and Afrikaans noun plurals. 1 Introduction Computational systems based on the two-level model of morphology (Koskenniemi, 1983) have been remarkably successful for many languages (Sproat, 1992). The language specific information of such a system is stored as 1. a morphotactic description of the words to be processed as well as 2. a set of two-level morphonological (or spelling) rules. Up to now, these two components had to be coded largely by hand, since no automated method existed to acquire a set of two-level rules for input source- target word pairs. To hand-code a 100% correct rule set from word pairs becomes almost impossi- ble when a few hundred pairs are involved. Fur- thermore, there is no guarantee that such a hand coded lexicon does not contain redundant rules or rules with too large contexts. The usual approach is rather to construct general rules from small sub- sets of the input pairs. However, these general rules usually allow overrecognition and overgeneration -- even on the subsets from which they were inferred. Simons (Simons, 1988) describes methods for studying morphophonemic alternations (using anno- tated interlinear text) and Grimes (Grimes, 1983) presents a program for discovering affix posi- tions and cooccurrence restrictions. Koskenniemi (Koskenniemi, 1990) provides a sketch of a discovery procedure for phonological two-level rules. Golding and Thompson (Golding and Thompson, 1985) and Wothke (Wothke, 1986) present systems to automat- icaily calculate a set of word-formation rules. These rules are, however, ordered one-level rewrite rules and not unordered two-level rules, as in our system. Kuusik (Kuusik, 1996) also acquires ordered one- level rewrite rules, for …

Content truncated to 500 words