AUTHORS: Roark, Brian and Sproat, Richard TITLE: Computational Approaches to Morphology and Syntax SERIES: Oxford Surveys in Syntax and Morphology PUBLISHER: Oxford University Press YEAR: 2007
Xiaofei Lu, Department of Applied Linguistics, The Pennsylvania State University
SUMMARY This book provides a critical overview of the state-of-the-art computational techniques and algorithms for handling morphological and syntactic phenomena. Finite-state approaches to morphology and syntax figure prominently in the book, but context-free and context-sensitive approaches to syntax are also covered. The authors discuss the implications of the computational approaches for morphological and syntactical theories, their relation to formal mechanisms, and their applications in practical natural language processing tasks.
Chapter one, ''Introduction and Preliminaries'', delimits the scope of the book and reviews the basics of finite-state automata and transducers. The authors state that they intend to critically survey the key computational issues in the theoretical and applied domains of computational morphology and syntax, and to introduce some of the most effective approaches taken to address these issues, within the general class to which they belong to wherever possible. The bulk of the chapter comprises an overview of (weighted) finite-state automata and transducers and a synopsis of fundamental algorithmic issues that relate to composition, minimization, determinization, and epsilon removal. The chapter concludes with a discussion of the broad applicability of finite-state methods, their roles in computational approaches to morphology and syntax, and issues involved in building efficient and robust syntactic models.
The rest of the book is organized into two parts. Part one, ''Computational Approaches to Morphology'', consists of Chapters two through five. Chapter two, ''The Formal Characterization of Morphological Operations'', describes the formal devices used in different languages to encode information morphologically. The chapter first introduces the concepts of lemmatization and decomposition and the general goals of morphological analysis. It then demonstrates how a single computational operation, composition, can be used to describe both syntagmatic and paradigmatic aspects of morphology with finite-state devices. The authors draw upon examples from a variety of languages to illustrate a spectrum of syntagmatic variation, including simple concatenation, prosodically governed concatenation, phonological changes induced by affixation, subsegmental and subtractive morphology, extrametrical and positively circumscribed infixation, root-and-pattern morphology, and morphomic components. They then illustrate paradigmatic variation using Latin. The authors argue that the only morphological operation that cannot be handled elegantly by composition is reduplication, which seems to require a non-regular operation, namely copying.
Chapter three, ''The Relevance of Computational Issues for Morphological Theory'', establishes that from a computational perspective, the ''Item-and-Arrangement'' and ''Item-and-Process'' approaches that have often divided the field of theoretical morphology are of little difference. The chapter starts with an explanation of the properties of different languages that motivated these two approaches and a discussion of Stump's (2001) two-dimensional classification, namely, lexical versus inferential, and incremental versus realizational. It then delves into Stump's lexical-incremental and inferential-realization theories. The authors argue for the equivalence of the two approaches first in computational terms, with a computational analysis of Stump's data concerning stem alternations in Sanskrit, position classes in Swahili, and double plurals in Breton, and then in formal terms, with a formal analysis of the semantics of morphological operations.
Chapter four, ''A Brief History of Computational Morphology'', surveys the history of computational morphology, focusing on finite-state approaches. The core of the chapter is a review of Koskenniemi's (1983) two-level approach, implemented in the KIMMO two-level morphological analyzer. The review first discusses the key aspects of the system: the representation of dictionaries as tries, the representation of morphological concatenation via continuation lexica, and the finite-state transducers that implement the surface-lexical phonological correspondences. It then turns to intersection of finite-state transducers, providing proof that, although regular relations are not in general closed under intersection, k-length-difference-bounded regular relations are. Next, it explicates Koskenniemi's formalism for two-level rewrite rules that specify the transducers he built manually, and compares them with traditional generative phonological rules. The authors consider Koskenniemi's system as a historical accident, as it was motivated by the difficulty in compiling complex rule system with the insufficient speed and memory of the computers in the late 1970s. The chapter closes with a discussion of Karttunen's (1998) reductionist argument that Optimality Theory can be implemented via a cascade of transducers combined using lenient composition, which shows that radically different theoretical approaches may be computational equivalents of one another.
Chapter five, ''Machine Learning of Morphology'', reviews three influential studies on morphological induction. The authors begin with Goldsmith (2001), which they consider the gold standard for later work on unsupervised acquisition of morphology. Goldsmith's system derives a set of signatures, i.e., sets of affixes used with a given set of stems, along with words that belong to those signatures from a raw corpus. The review details Goldsmith's methods for candidate generation and evaluation, which are based on weighted mutual information and minimum description length respectively. The authors then move on to Schone and Jurafsky (2001), which differs from other approaches in that it uses not only orthographic, but also semantic and syntactic information derived from a raw corpus to analyze inflectional morphology, covering not only suffixes, but also prefixes and circumfixes. The review describes the method for finding affixes and for capturing pairs of potential morphological variants using a combination of semantic, orthographic, and syntactic environment-based probabilities. Finally, the authors examine Yarowsky and Wicentowski's (2001) lightly supervised method for inducing analyzers of inflectional morphology. The methods for producing a table of correspondences between roots and their inflected forms as well as for producing a morphological analyzer that can extend to new cases are discussed. The chapter concludes with a brief summary of other recent work in and relevant evidence for morphological induction.
Part two, ''Computational Approaches to Syntax'', consists of Chapters six through nine. Chapter six, ''Finite-state Approaches to Syntax'', introduces some of the most widely used syntactic models and several dynamic programming algorithms for efficient inference with weighted finite-state models. The chapter first describes various aspects of N-gram models, e.g., how they provide a probability distribution over strings in the language, how they can be encoded in a deterministic finite-state automaton, and how modeling on morphologically-rich languages can be improved using factored language models, among others. It then turns to class-based language models that alleviate the data sparseness problem by making generalizations about word behavior based on the behavior of similar words. The Markov assumption and the forward algorithm are detailed. Next, the chapter discusses approaches to part-of-speech tagging, focusing on HMM models and log-linear models. The Viterbi and Forward-backward algorithms are presented, so are Maximum Entropy models, Conditional Random Fields, and the Perceptron algorithm. The chapter then touches upon how sequence tagging models can be applied to NP chunking and shallow parsing, before concluding with the comment that while finite-state models may not be adequate in the eyes of syntacticians, they are efficient in practice.
Chapter seven, ''Basic Context-free Approaches to Syntax'', focuses on approaches to syntax using context-free grammars (CFGs). The chapter opens with an introduction to the definitions and properties of CFGs, derivations, and trees. It then describes algorithms for annotating strings using different kinds of CFGs. For deterministic parsing algorithms, the authors cover shift-reduce parsing, pushdown automata, and top-down and left-corner parsing; for non-deterministic parsing algorithms, they cover re-analysis and beam-search, CYK parsing, Earley parsing, inside-outside algorithms, and labeled recall parsing.
Chapter eight, ''Enriched Context-free Approaches to Syntax'', discusses the incorporation of corpus-derived statistical information within CFGs. The chapter first describes techniques for estimating probabilistic and lexicalized CFGs from treebanks and presents two well-known statistical parsers: Collin's parser and Charniak parser. It then moves away from constituent structure to lexical dependencies, and introduces dependency parsing. Next, the chapter details language models based on probabilistic CFGs, including the Structured Language Model, the top-down approach, and the Charniak model. The chapter also touches upon unsupervised grammar induction and reviews recent progress on learning syntactic structure from unannotated language samples. It closes with a discussion on methods for finite-state approximations. The authors emphasize the point that processing with context-free models comes at a large computational cost relative to finite-state models, and it is therefore useful to start with a context-free model and modify it to make it finite-state equivalent.
Chapter nine, ''Context-sensitive Approaches to Syntax'', reviews computational approaches to syntax that go beyond the context-free models to describe more complicated syntactic phenomena, albeit at an efficiency cost. Three families of grammars are presented. The authors begin with unification grammars, focusing in particular on Lexical-Functional Grammar. They then introduce several lexicalized grammar formalisms, including Tree-Adjoining Grammars (TAG), Combinatory Categorical Grammars (CCG), and two other mildly context-sensitive approaches, namely Multicomponent TAG and Minimalist Grammars. A discussion on finite-state and context-free approximations to a CCG is also included. The third family of grammars presented is transduction grammars that allow for the parsing of two or more related strings simultaneously. The authors also examine the task of parse selection, focusing on methods for defining a distribution for unification grammars and their usage for re-ranking the output of context-free parsers.
EVALUATION This book should undoubtedly be of great interest to students and researchers of morphology, syntax, computational linguistics, and natural language processing. To students of computational linguistics who want to learn more about computational morphology and syntax, the book provides an excellent systematic overview of the current state-of-the-art of the field. They will walk away with a good understanding of the key issues involved in computational modeling of morphology and syntax as well as some of the most widely used approaches to handling these issues. The book will also prove a handy and useful reference for researchers of computational linguistics and natural language processing.
One distinct feature of the book is the authors' clear effort in relating computational models of morphological and syntactic processing to issues of interest to theoretical linguistics and natural language processing. The book includes extensive descriptions of the formal characterization of morphological operations as well as a wide range of grammar formalisms, using multilingual data to illustrate these operations and formalisms wherever necessary. The theory-minded reader will appreciate the book's insightful discussion on the implications of computational modeling for theories of morphology and models of syntax, while the application-minded reader will appreciate its constant emphasis on the application of the models and algorithms introduced in practical natural language processing tasks.
Finite-state methods figure fairly prominently throughout the book. In particular, the computational approaches to morphology discussed in the book are primarily finite-state approaches, while other approaches, such as work on inflectional morphology in the DATR framework (e.g., Corbett and Fraser, 1993), are only mentioned in passing. The authors well justify their omission of these approaches with the argument that they do not add to the formal power of finite-state approaches described. Such choices are of course often necessary. However, it is useful for the potential reader to be aware of the authors' chosen focus, especially if they are looking for a book that covers all different approaches to computational morphology.
Finally, the book does a great job explaining complicated formal and algorithmic issues in an accessible way. Nevertheless, depending on background and training, the reader may find the formal mechanisms, pseudo code algorithms, or complex notation intimidating. As the authors suggest, the reader should prepare to get his or her hands dirty.
REFERENCES Corbett, G., and Fraser, N. (1993). Network morphology: A DATR account of Russian nominal inflection. _Journal of Linguistics_ 29, 113-142.
Goldsmith, J. (2001). Unsupervised acquisition of the morphology of a natural language. _Computational Linguistics_ 27(2), 153-198.
Karttunen, L. (1998). The proper treatment of optimality in computational phonology. In _Proceedings of the 2nd International Workshop on Finite-State Methods in Natural Language Processing_, pp. 1-12.
Koskenniemi, K. (1983). _Two-Level Morphology: A General Computational Model for Word-Form Recognition and Production_. Ph.D. thesis, University of Helsinki, Helsinki.
Schone, P., and Jurafsky, D., (2000). Knowledge-free induction of morphology using latent semantic analysis. In _Proceedings of the 4th Conference on Computational Natural Language Learning_, pp. 578-583.
Stump, G. (2001). _Inflectional Morphology: A Theory of Paradigm Structure_. Cambridge, UK: Cambridge University Press.
Yarowsky, D., and Wicentowski, R. (2001). Minimally supervised morphological analysis by multimodal alignment. In _Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing_, pp. 160-167.
ABOUT THE REVIEWER Xiaofei Lu is currently Assistant Professor of Applied Linguistics in the Department of Applied Linguistics at The Pennsylvania State University. His research interests are primarily in computational linguistics, corpus linguistics, and intelligent computer-assisted language learning. |