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.
|
