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 stateoftheart computational techniques and algorithms for handling morphological and syntactic phenomena. Finitestate approaches to morphology and syntax figure prominently in the book, but contextfree and contextsensitive 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 finitestate 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) finitestate 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 finitestate 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 finitestate 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, rootandpattern 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 nonregular operation, namely copying.
Chapter three, ''The Relevance of Computational Issues for Morphological Theory'', establishes that from a computational perspective, the ''ItemandArrangement'' and ''ItemandProcess'' 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) twodimensional classification, namely, lexical versus inferential, and incremental versus realizational. It then delves into Stump's lexicalincremental and inferentialrealization 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 finitestate approaches. The core of the chapter is a review of Koskenniemi's (1983) twolevel approach, implemented in the KIMMO twolevel 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 finitestate transducers that implement the surfacelexical phonological correspondences. It then turns to intersection of finitestate transducers, providing proof that, although regular relations are not in general closed under intersection, klengthdifferencebounded regular relations are. Next, it explicates Koskenniemi's formalism for twolevel 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 environmentbased 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, ''Finitestate Approaches to Syntax'', introduces some of the most widely used syntactic models and several dynamic programming algorithms for efficient inference with weighted finitestate models. The chapter first describes various aspects of Ngram models, e.g., how they provide a probability distribution over strings in the language, how they can be encoded in a deterministic finitestate automaton, and how modeling on morphologicallyrich languages can be improved using factored language models, among others. It then turns to classbased 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 partofspeech tagging, focusing on HMM models and loglinear models. The Viterbi and Forwardbackward 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 finitestate models may not be adequate in the eyes of syntacticians, they are efficient in practice.
Chapter seven, ''Basic Contextfree Approaches to Syntax'', focuses on approaches to syntax using contextfree 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 shiftreduce parsing, pushdown automata, and topdown and leftcorner parsing; for nondeterministic parsing algorithms, they cover reanalysis and beamsearch, CYK parsing, Earley parsing, insideoutside algorithms, and labeled recall parsing.
Chapter eight, ''Enriched Contextfree Approaches to Syntax'', discusses the incorporation of corpusderived statistical information within CFGs. The chapter first describes techniques for estimating probabilistic and lexicalized CFGs from treebanks and presents two wellknown 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 topdown 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 finitestate approximations. The authors emphasize the point that processing with contextfree models comes at a large computational cost relative to finitestate models, and it is therefore useful to start with a contextfree model and modify it to make it finitestate equivalent.
Chapter nine, ''Contextsensitive Approaches to Syntax'', reviews computational approaches to syntax that go beyond the contextfree 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 LexicalFunctional Grammar. They then introduce several lexicalized grammar formalisms, including TreeAdjoining Grammars (TAG), Combinatory Categorical Grammars (CCG), and two other mildly contextsensitive approaches, namely Multicomponent TAG and Minimalist Grammars. A discussion on finitestate and contextfree 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 reranking the output of contextfree 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 stateoftheart 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 theoryminded reader will appreciate the book's insightful discussion on the implications of computational modeling for theories of morphology and models of syntax, while the applicationminded reader will appreciate its constant emphasis on the application of the models and algorithms introduced in practical natural language processing tasks.
Finitestate methods figure fairly prominently throughout the book. In particular, the computational approaches to morphology discussed in the book are primarily finitestate 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 finitestate 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, 113142.
Goldsmith, J. (2001). Unsupervised acquisition of the morphology of a natural language. _Computational Linguistics_ 27(2), 153198.
Karttunen, L. (1998). The proper treatment of optimality in computational phonology. In _Proceedings of the 2nd International Workshop on FiniteState Methods in Natural Language Processing_, pp. 112.
Koskenniemi, K. (1983). _TwoLevel Morphology: A General Computational Model for WordForm Recognition and Production_. Ph.D. thesis, University of Helsinki, Helsinki.
Schone, P., and Jurafsky, D., (2000). Knowledgefree induction of morphology using latent semantic analysis. In _Proceedings of the 4th Conference on Computational Natural Language Learning_, pp. 578583.
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. 160167.
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 computerassisted language learning.
