From: Randall Eggert <randylinguistlist.org>
Subject: Review: Computational Linguistics: Roark & Sproat (2007)
E-mail this message to a friend
Announced at http://linguistlist.org/issues/18/18-2402.html
AUTHORS: Roark, Brian and Sproat, RichardTITLE: Computational Approaches to Morphology and SyntaxSERIES: Oxford Surveys in Syntax and MorphologyPUBLISHER: Oxford University PressYEAR: 2007
Xiaofei Lu, Department of Applied Linguistics, The Pennsylvania State University
SUMMARYThis book provides a critical overview of the state-of-the-art computationaltechniques 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 formorphological and syntactical theories, their relation to formal mechanisms, andtheir applications in practical natural language processing tasks.
Chapter one, ''Introduction and Preliminaries'', delimits the scope of the bookand reviews the basics of finite-state automata and transducers. The authorsstate that they intend to critically survey the key computational issues in thetheoretical and applied domains of computational morphology and syntax, and tointroduce some of the most effective approaches taken to address these issues,within the general class to which they belong to wherever possible. The bulk ofthe chapter comprises an overview of (weighted) finite-state automata andtransducers and a synopsis of fundamental algorithmic issues that relate tocomposition, minimization, determinization, and epsilon removal. The chapterconcludes with a discussion of the broad applicability of finite-state methods,their roles in computational approaches to morphology and syntax, and issuesinvolved in building efficient and robust syntactic models.
The rest of the book is organized into two parts. Part one, ''ComputationalApproaches to Morphology'', consists of Chapters two through five. Chapter two,''The Formal Characterization of Morphological Operations'', describes the formaldevices used in different languages to encode information morphologically. Thechapter first introduces the concepts of lemmatization and decomposition and thegeneral goals of morphological analysis. It then demonstrates how a singlecomputational operation, composition, can be used to describe both syntagmaticand paradigmatic aspects of morphology with finite-state devices. The authorsdraw upon examples from a variety of languages to illustrate a spectrum ofsyntagmatic variation, including simple concatenation, prosodically governedconcatenation, phonological changes induced by affixation, subsegmental andsubtractive morphology, extrametrical and positively circumscribed infixation,root-and-pattern morphology, and morphomic components. They then illustrateparadigmatic variation using Latin. The authors argue that the onlymorphological operation that cannot be handled elegantly by composition isreduplication, 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 oftheoretical morphology are of little difference. The chapter starts with anexplanation of the properties of different languages that motivated these twoapproaches and a discussion of Stump's (2001) two-dimensional classification,namely, lexical versus inferential, and incremental versus realizational. Itthen delves into Stump's lexical-incremental and inferential-realizationtheories. The authors argue for the equivalence of the two approaches first incomputational terms, with a computational analysis of Stump's data concerningstem alternations in Sanskrit, position classes in Swahili, and double pluralsin Breton, and then in formal terms, with a formal analysis of the semantics ofmorphological operations.
Chapter four, ''A Brief History of Computational Morphology'', surveys the historyof computational morphology, focusing on finite-state approaches. The core ofthe chapter is a review of Koskenniemi's (1983) two-level approach, implementedin the KIMMO two-level morphological analyzer. The review first discusses thekey aspects of the system: the representation of dictionaries as tries, therepresentation of morphological concatenation via continuation lexica, and thefinite-state transducers that implement the surface-lexical phonologicalcorrespondences. It then turns to intersection of finite-state transducers,providing proof that, although regular relations are not in general closed underintersection, k-length-difference-bounded regular relations are. Next, itexplicates Koskenniemi's formalism for two-level rewrite rules that specify thetransducers he built manually, and compares them with traditional generativephonological rules. The authors consider Koskenniemi's system as a historicalaccident, as it was motivated by the difficulty in compiling complex rule systemwith the insufficient speed and memory of the computers in the late 1970s. Thechapter closes with a discussion of Karttunen's (1998) reductionist argumentthat Optimality Theory can be implemented via a cascade of transducers combinedusing lenient composition, which shows that radically different theoreticalapproaches may be computational equivalents of one another.
Chapter five, ''Machine Learning of Morphology'', reviews three influentialstudies on morphological induction. The authors begin with Goldsmith (2001),which they consider the gold standard for later work on unsupervised acquisitionof morphology. Goldsmith's system derives a set of signatures, i.e., sets ofaffixes used with a given set of stems, along with words that belong to thosesignatures from a raw corpus. The review details Goldsmith's methods forcandidate generation and evaluation, which are based on weighted mutualinformation and minimum description length respectively. The authors then moveon to Schone and Jurafsky (2001), which differs from other approaches in that ituses not only orthographic, but also semantic and syntactic information derivedfrom a raw corpus to analyze inflectional morphology, covering not onlysuffixes, but also prefixes and circumfixes. The review describes the method forfinding affixes and for capturing pairs of potential morphological variantsusing a combination of semantic, orthographic, and syntactic environment-basedprobabilities. Finally, the authors examine Yarowsky and Wicentowski's (2001)lightly supervised method for inducing analyzers of inflectional morphology. Themethods for producing a table of correspondences between roots and theirinflected forms as well as for producing a morphological analyzer that canextend to new cases are discussed. The chapter concludes with a brief summary ofother recent work in and relevant evidence for morphological induction.
Part two, ''Computational Approaches to Syntax'', consists of Chapters six throughnine. Chapter six, ''Finite-state Approaches to Syntax'', introduces some of themost widely used syntactic models and several dynamic programming algorithms forefficient inference with weighted finite-state models. The chapter firstdescribes various aspects of N-gram models, e.g., how they provide a probabilitydistribution over strings in the language, how they can be encoded in adeterministic finite-state automaton, and how modeling on morphologically-richlanguages can be improved using factored language models, among others. It thenturns to class-based language models that alleviate the data sparseness problemby making generalizations about word behavior based on the behavior of similarwords. The Markov assumption and the forward algorithm are detailed. Next, thechapter discusses approaches to part-of-speech tagging, focusing on HMM modelsand log-linear models. The Viterbi and Forward-backward algorithms arepresented, so are Maximum Entropy models, Conditional Random Fields, and thePerceptron algorithm. The chapter then touches upon how sequence tagging modelscan be applied to NP chunking and shallow parsing, before concluding with thecomment that while finite-state models may not be adequate in the eyes ofsyntacticians, they are efficient in practice.
Chapter seven, ''Basic Context-free Approaches to Syntax'', focuses on approachesto syntax using context-free grammars (CFGs). The chapter opens with anintroduction to the definitions and properties of CFGs, derivations, and trees.It then describes algorithms for annotating strings using different kinds ofCFGs. For deterministic parsing algorithms, the authors cover shift-reduceparsing, pushdown automata, and top-down and left-corner parsing; fornon-deterministic parsing algorithms, they cover re-analysis and beam-search,CYK parsing, Earley parsing, inside-outside algorithms, and labeled recallparsing.
Chapter eight, ''Enriched Context-free Approaches to Syntax'', discusses theincorporation of corpus-derived statistical information within CFGs. The chapterfirst describes techniques for estimating probabilistic and lexicalized CFGsfrom treebanks and presents two well-known statistical parsers: Collin's parserand Charniak parser. It then moves away from constituent structure to lexicaldependencies, and introduces dependency parsing. Next, the chapter detailslanguage models based on probabilistic CFGs, including the Structured LanguageModel, the top-down approach, and the Charniak model. The chapter also touchesupon unsupervised grammar induction and reviews recent progress on learningsyntactic structure from unannotated language samples. It closes with adiscussion on methods for finite-state approximations. The authors emphasize thepoint that processing with context-free models comes at a large computationalcost relative to finite-state models, and it is therefore useful to start with acontext-free model and modify it to make it finite-state equivalent.
Chapter nine, ''Context-sensitive Approaches to Syntax'', reviews computationalapproaches to syntax that go beyond the context-free models to describe morecomplicated syntactic phenomena, albeit at an efficiency cost. Three families ofgrammars are presented. The authors begin with unification grammars, focusing inparticular on Lexical-Functional Grammar. They then introduce severallexicalized grammar formalisms, including Tree-Adjoining Grammars (TAG),Combinatory Categorical Grammars (CCG), and two other mildly context-sensitiveapproaches, namely Multicomponent TAG and Minimalist Grammars. A discussion onfinite-state and context-free approximations to a CCG is also included. Thethird family of grammars presented is transduction grammars that allow for theparsing of two or more related strings simultaneously. The authors also examinethe task of parse selection, focusing on methods for defining a distribution forunification grammars and their usage for re-ranking the output of context-freeparsers.
EVALUATIONThis book should undoubtedly be of great interest to students and researchers ofmorphology, syntax, computational linguistics, and natural language processing.To students of computational linguistics who want to learn more aboutcomputational morphology and syntax, the book provides an excellent systematicoverview of the current state-of-the-art of the field. They will walk away witha good understanding of the key issues involved in computational modeling ofmorphology and syntax as well as some of the most widely used approaches tohandling these issues. The book will also prove a handy and useful reference forresearchers of computational linguistics and natural language processing.
One distinct feature of the book is the authors' clear effort in relatingcomputational models of morphological and syntactic processing to issues ofinterest to theoretical linguistics and natural language processing. The bookincludes extensive descriptions of the formal characterization of morphologicaloperations as well as a wide range of grammar formalisms, using multilingualdata to illustrate these operations and formalisms wherever necessary. Thetheory-minded reader will appreciate the book's insightful discussion on theimplications of computational modeling for theories of morphology and models ofsyntax, while the application-minded reader will appreciate its constantemphasis on the application of the models and algorithms introduced in practicalnatural language processing tasks.
Finite-state methods figure fairly prominently throughout the book. Inparticular, the computational approaches to morphology discussed in the book areprimarily finite-state approaches, while other approaches, such as work oninflectional morphology in the DATR framework (e.g., Corbett and Fraser, 1993),are only mentioned in passing. The authors well justify their omission of theseapproaches with the argument that they do not add to the formal power offinite-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 alldifferent approaches to computational morphology.
Finally, the book does a great job explaining complicated formal and algorithmicissues in an accessible way. Nevertheless, depending on background and training,the reader may find the formal mechanisms, pseudo code algorithms, or complexnotation intimidating. As the authors suggest, the reader should prepare to gethis or her hands dirty.
REFERENCESCorbett, G., and Fraser, N. (1993). Network morphology: A DATR account ofRussian nominal inflection. _Journal of Linguistics_ 29, 113-142.
Goldsmith, J. (2001). Unsupervised acquisition of the morphology of a naturallanguage. _Computational Linguistics_ 27(2), 153-198.
Karttunen, L. (1998). The proper treatment of optimality in computationalphonology. In _Proceedings of the 2nd International Workshop on Finite-StateMethods in Natural Language Processing_, pp. 1-12.
Koskenniemi, K. (1983). _Two-Level Morphology: A General Computational Model forWord-Form Recognition and Production_. Ph.D. thesis, University of Helsinki,Helsinki.
Schone, P., and Jurafsky, D., (2000). Knowledge-free induction of morphologyusing latent semantic analysis. In _Proceedings of the 4th Conference onComputational 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 morphologicalanalysis by multimodal alignment. In _Proceedings of the 2003 Conference onEmpirical Methods in Natural Language Processing_, pp. 160-167.
ABOUT THE REVIEWERXiaofei Lu is currently Assistant Professor of Applied Linguistics in theDepartment of Applied Linguistics at The Pennsylvania State University. Hisresearch interests are primarily in computational linguistics, corpuslinguistics, and intelligent computer-assisted language learning.