Computational Approaches to Morphology and Syntax

by Roark, Brian; Sproat, Richard

• ISBN13: 9780199274772
• ISBN10: 0199274770
• Format: Hardcover
• Copyright: 2007-09-27
• Publisher: Oxford University Press

Summary

The book will appeal to scholars and advanced students of morphology, syntax, computational linguistics and natural language processing (NLP). It provides a critical and practical guide to computational techniques for handling morphological and syntactic phenomena, showing how these techniques have been used and modified in practice. The authors discuss the nature and uses of syntactic parsers and examine the problems and opportunities of parsing algorithms for finite-state, context-free and various context-sensitive grammars. They relate approaches for describing syntax and morphology to formal mechanisms and algorithms, and present well-motivated approaches for augmenting grammars with weights or probabilities.

Author Biography

Brian E. Roark is Assistant Professor in the Department of Computer Science & Electrical Engineering and the Center for Spoken Language Understanding at Oregon Health & Science University. He has published papers in Computer Speech and Language, Speech Communication, Natural Language Engineering and Computational Linguistics.
Richard Sproat is Professor of Linguistics and Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign and also holds an appointment at the Beckman Institute for Advanced Science and Technology. His most recent book is A Computational Theory of Writing Systems (CUP, 2000).

Table of Contents

General preface	p. ix
Preface	p. x
List of Figures	p. xii
List of Tables	p. xv
Abbreviations	p. xvii
Introduction and Preliminaries	p. 1
Introduction	p. 1
Finite-State Automata and Transducers	p. 2
Weights and Probabilities	p. 8
Weighted Finite-State Automata and Transducers	p. 9
A Synopsis of Algorithmic Issues	p. 13
Computational Approaches to Morphology and Syntax	p. 16
Computational Approaches to Morphology
The Formal Characterization of Morphological Operations	p. 23
Introduction	p. 24
Syntagmatic Variation	p. 27
Simple Concatenation	p. 27
Interlude: Prosodic Circumscription	p. 29
Prosodically Governed Concatenation	p. 31
Phonological Changes Induced by Affixation	p. 35
Subsegmental Morphology	p. 36
Subtractive Morphology	p. 37
Extrametrical Infixation	p. 39
Positively Circumscribed Infixation	p. 40
Root-and-Pattern Morphology	p. 41
Morphomic Components	p. 46
Paradigmatic Variation	p. 49
The Remaining Problem: Reduplication	p. 53
Summary	p. 61
The Relevance of Computational Issues for Morphological Theory	p. 62
Introduction: Realizational versus Incremental Morphology	p. 62
Stump's Theory	p. 66
Computational Implementation of Fragments	p. 67
Stem Alternations in Sanskrit	p. 68
Position Classes in Swahili	p. 73
Double Plurals in Breton	p. 79
Equivalence of Inferential-Realizational and Lexical-Incremental Approaches: A Formal Analysis	p. 83
Conclusions	p. 85
Lextools	p. 86
XFST Implementation of Sanskrit	p. 95
A Brief History of Computational Morphology	p. 100
Introduction	p. 100
The KIMMO Two-Level Morphological Analyzer	p. 102
KIMMO Basics	p. 103
FST Intersection	p. 105
Koskenniemi's Rule Types	p. 109
Koskenniemi's System as a Historical Accident	p. 110
Summary	p. 113
Machine Learning of Morphology	p. 116
Introduction	p. 116
Goldsmith, 2001	p. 119
Candidate Generation	p. 121
Candidate Evaluation	p. 122
Schone and Jurafsky, 2001	p. 124
Yarowsky and Wicentowski, 2001	p. 129
Discussion	p. 132
Computational Approaches to Syntax
Finite-state Approaches to Syntax	p. 139
N-gram Models	p. 139
Background	p. 139
Basic Approach	p. 141
Smoothing	p. 143
Encoding	p. 148
Factored Language Models	p. 150
Class-based Language Models	p. 151
Forward Algorithm	p. 154
Part-of-Speech Tagging	p. 159
Viterbi Algorithm	p. 160
Efficient N-best Viterbi Decoding	p. 162
Forward-backward Algorithm	p. 164
Forward-backward Decoding	p. 168
Log-linear Models	p. 170
NP Chunking and Shallow Parsing	p. 173
Summary	p. 174
Basic Context-free Approaches to Syntax	p. 176
Grammars, Derivations and Trees	p. 176
Deterministic Parsing Algorithms	p. 180
Shift-reduce Parsing	p. 181
Pushdown Automata	p. 182
Top-down and Left-corner Parsing	p. 184
Non-deterministic Parsing Algorithms	p. 189
Re-analysis and Beam-search	p. 191
CYK Parsing	p. 193
Earley Parsing	p. 201
Inside-outside Algorithm	p. 203
Labeled Recall Parsing	p. 206
Summary	p. 208
Enriched Context-free Approaches to Syntax	p. 209
Stochastic CFG-based Parsing	p. 209
Treebanks and PCFGs	p. 210
Lexicalized Context-free Grammars	p. 221
Collins Parser	p. 226
Charniak Parser	p. 230
Dependency Parsing	p. 234
PCFG-based Language Models	p. 238
Unsupervised Grammar Induction	p. 240
Finite-state Approximations	p. 244
Summary	p. 246
Context-sensitive Approaches to Syntax	p. 248
Unification Grammars and Parsing	p. 248
Lexicalized Grammar Formalisms and Parsing	p. 257
Tree-adjoining Grammars	p. 258
Combinatory Categorial Grammars	p. 265
Other Mildly Context-sensitive Approaches	p. 270
Finite-state and Context-free Approximations	p. 271
Parse Selection	p. 273
Stochastic Unification Grammars	p. 273
Data-oriented Parsing	p. 275
Context-free Parser Re-ranking	p. 277
Transduction Grammars	p. 279
Summary	p. 283
References	p. 285
Name Index	p. 307
Language Index	p. 312
Index	p. 313
Table of Contents provided by Ingram. All Rights Reserved.