Computational approaches to morphology and syntax

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 Notes

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

General preface	p. ix
Preface	p. x
List of Figures	p. xii
List of Tables	p. xv
Abbreviations	p. xvii
1 Introduction and Preliminaries	p. 1
1.1 Introduction	p. 1
1.2 Finite-State Automata and Transducers	p. 2
1.3 Weights and Probabilities	p. 8
1.4 Weighted Finite-State Automata and Transducers	p. 9
1.5 A Synopsis of Algorithmic Issues	p. 13
1.6 Computational Approaches to Morphology and Syntax	p. 16
Part I Computational Approaches to Morphology
2 The Formal Characterization of Morphological Operations	p. 23
2.1 Introduction	p. 24
2.2 Syntagmatic Variation	p. 27
2.2.1 Simple Concatenation	p. 27
2.2.2 Interlude: Prosodic Circumscription	p. 29
2.2.3 Prosodically Governed Concatenation	p. 31
2.2.4 Phonological Changes Induced by Affixation	p. 35
2.2.5 Subsegmental Morphology	p. 36
2.2.6 Subtractive Morphology	p. 37
2.2.7 Extrametrical Infixation	p. 39
2.2.8 Positively Circumscribed Infixation	p. 40
2.2.9 Root-and-Pattern Morphology	p. 41
2.2.10 Morphomic Components	p. 46
2.3 Paradigmatic Variation	p. 49
2.4 The Remaining Problem: Reduplication	p. 53
2.5 Summary	p. 61
3 The Relevance of Computational Issues for Morphological Theory	p. 62
3.1 Introduction: Realizational versus Incremental Morphology	p. 62
3.2 Stump's Theory	p. 66
3.3 Computational Implementation of Fragments	p. 67
3.3.1 Stem Alternations in Sanskrit	p. 68
3.3.2 Position Classes in Swahili	p. 73
3.3.3 Double Plurals in Breton	p. 79
3.4 Equivalence of Inferential-Realizational and Lexical-Incremental Approaches: A Formal Analysis	p. 83
3.5 Conclusions	p. 85
Appendix 3A Lextools	p. 86
Appendix 3B XFST Implementation of Sanskrit	p. 95
4 A Brief History of Computational Morphology	p. 100
4.1 Introduction	p. 100
4.2 The KIMMO Two-Level Morphological Analyzer	p. 102
4.2.1 KIMMO Basics	p. 103
4.2.2 FST Intersection	p. 105
4.2.3 Koskenniemi's Rule Types	p. 109
4.2.4 Koskenniemi's System as a Historical Accident	p. 110
4.3 Summary	p. 113
5 Machine Learning of Morphology	p. 116
5.1 Introduction	p. 116
5.2 Goldsmith, 2001	p. 119
5.2.1 Candidate Generation	p. 121
5.2.2 Candidate Evaluation	p. 122
5.3 Schone and Jurafsky, 2001	p. 124
5.4 Yarowsky and Wicentowski, 2001	p. 129
5.5 Discussion	p. 132
Part II Computational Approaches to Syntax
6 Finite-state Approaches to Syntax	p. 139
6.1 N-gram Models	p. 139
6.1.1 Background	p. 139
6.1.2 Basic Approach	p. 141
6.1.3 Smoothing	p. 143
6.1.4 Encoding	p. 148
6.1.5 Factored Language Models	p. 150
6.2 Class-based Language Models	p. 151
6.2.1 Forward Algorithm	p. 154
6.3 Part-of-Speech Tagging	p. 159
6.3.1 Viterbi Algorithm	p. 160
6.3.2 Efficient N-best Viterbi Decoding	p. 162
6.3.3 Forward-backward Algorithm	p. 164
6.3.4 Forward-backward Decoding	p. 168
6.3.5 Log-linear Models	p. 170
6.4 NP Chunking and Shallow Parsing	p. 173
6.5 Summary	p. 174
7 Basic Context-free Approaches to Syntax	p. 176
7.1 Grammars, Derivations and Trees	p. 176
7.2 Deterministic Parsing Algorithms	p. 180
7.2.1 Shift-reduce Parsing	p. 181
7.2.2 Pushdown Automata	p. 182
7.2.3 Top-down and Left-corner Parsing	p. 184
7.3 Non-deterministic Parsing Algorithms	p. 189
7.3.1 Re-analysis and Beam-search	p. 191
7.3.2 CYK Parsing	p. 193
7.3.3 Earley Parsing	p. 201
7.3.4 Inside-outside Algorithm	p. 203
7.3.5 Labeled Recall Parsing	p. 206
7.4 Summary	p. 208
8 Enriched Context-free Approaches to Syntax	p. 209
8.1 Stochastic CFG-based Parsing	p. 209
8.1.1 Treebanks and PCFGs	p. 210
8.1.2 Lexicalized Context-free Grammars	p. 221
8.1.3 Collins Parser	p. 226
8.1.4 Charniak Parser	p. 230
8.2 Dependency Parsing	p. 234
8.3 PCFG-based Language Models	p. 238
8.4 Unsupervised Grammar Induction	p. 240
8.5 Finite-state Approximations	p. 244
8.6 Summary	p. 246
9 Context-sensitive Approaches to Syntax	p. 248
9.1 Unification Grammars and Parsing	p. 248
9.2 Lexicalized Grammar Formalisms and Parsing	p. 257
9.2.1 Tree-adjoining Grammars	p. 258
9.2.2 Combinatory Categorial Grammars	p. 265
9.2.3 Other Mildly Context-sensitive Approaches	p. 270
9.2.4 Finite-state and Context-free Approximations	p. 271
9.3 Parse Selection	p. 273
9.3.1 Stochastic Unification Grammars	p. 273
9.3.2 Data-oriented Parsing	p. 275
9.3.3 Context-free Parser Re-ranking	p. 277
9.4 Transduction Grammars	p. 279
9.5 Summary	p. 283
References	p. 285
Name Index	p. 307
Language Index	p. 312
Index	p. 313

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents