A General Computational Model for Word-Form Recognition and Production

Kimmo KoskenniemiCOLING 1984

TL;DR

This paper introduces the "two-level model," a computational framework for analyzing and generating word forms that overcomes the limitations of traditional generative phonology. By representing morphological rules as finite state automata that directly map between lexical and surface forms, it enables efficient, bidirectional processing without the need for complex rule ordering or merging.

What Problem Does This Paper Address?

Traditional generative phonology describes word formation using rewriting rules that transform an underlying "lexical" representation into a "surface" form. While conceptually powerful, this approach is unidirectional and computationally challenging to implement efficiently. The authors highlight that practical morphological programs have found little use for it. An earlier attempt by Kay and Kaplan proposed representing these rules as finite state automata and merging them into a single, large automaton. While this approach is operational and bidirectional, it suffers from a critical drawback: the merged automaton can become prohibitively large for languages with complex morphology, like Finnish. The paper addresses the need for a computational model that is both theoretically sound, practically efficient, and capable of handling complex morphology bidirectionally.

Methods

The core of the paper is the "two-level model." Instead of abstract lexical representations, it uses concrete or natural morphology, meaning there's no need for intermediate stages between the lexical and surface forms. Morphological alternations are described by "two-level rules." These rules define a static, parallel, and nondirectional correspondence between segments at the lexical and surface levels. Each rule is implemented as a finite state automaton (FSA). The key innovation is that the entire morphological grammar is not a cascade of automata to be merged, but rather a set of parallel FSAs that all operate simultaneously. A word form is considered valid only if its configuration is accepted by each of these rule-automata. This parallel operation, unlike the cascaded approach, avoids the problem of excessively large merged automata. The model is inherently bidirectional, capable of both analyzing surface forms into their lexical representations and generating surface forms from lexical ones.

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and provides examples from Finnish morphology.

Key Insights and Ideas

  • Direct Lexical-to-Surface Mapping: The model eliminates intermediate representations, simplifying the computational process and directly linking the underlying form to its surface realization.
  • Parallel Rule Application: Instead of ordering rules sequentially (as in generative phonology) or merging them into one giant automaton (as in Kay and Kaplan's approach), the two-level model uses parallel, independent rule-automata. This is crucial for computational efficiency.
  • Bidirectionality as a Feature, Not a Bug: The model is designed from the ground up to work in both directions (analysis and synthesis), making it suitable for a wider range of NLP tasks.
  • Suppletion-like Variations Handled by Lexicon: Alternations that are too complex or unnatural to be described by simple segment-to-segment rules are treated as suppletion and handled within the lexicon system, rather than forcing complex rule structures.
  • Tabular Automata for Readability: While rules are conceptually FSAs, the paper notes that a tabular representation of these automata is more practical and readable, especially for linguists.

Key Results

The paper presents a theoretical model and its operational implementation. While specific quantitative results like accuracy percentages are not detailed, the key qualitative result is the demonstration of a computationally feasible and theoretically robust model for handling complex morphology. The authors state that the program is "fully operational and reasonably fast" (about 0.05 CPU seconds per word) and has been implemented in various programming languages and on different systems. They also list numerous ongoing and completed projects applying the model to various languages, indicating its broad applicability and success in practice.

Limitations and Future Work

The authors acknowledge that while the two-level rule formalism is readable, the actual implementation uses hand-compiled automata. They suggest that a compiler that accepts rules directly in a two-level rule formalism would be highly valuable, as it could automatically transform rules into finite state automata, facilitating the creation of new descriptions and further development. They also note that the lack of extrinsic rule ordering in the two-level rule component, while simplifying the model, might make it less powerful than generative phonology in certain theoretical contexts, though they argue this is not a significant issue in practical descriptions. Future work includes further development of the system and its application to more languages.

Summary updated

BibTeX
@inproceedings{koskenniemi1984general,
  author = {Kimmo Koskenniemi},
  title = {{A General Computational Model for Word-Form Recognition and Production}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure