Computational Approaches to Morphology and Syntax by Brian Roark, Richard Sproat

General preface ix

Preface x

List of Figures xii

List of Tables xv

Abbreviations xvii

1 Introduction and Preliminaries 1

1.1 Introduction 1

1.2 Finite-State Automata and Transducers 2

1.3 Weights and Probabilities 8

1.4 Weighted Finite-State Automata and Transducers 9

1.5 A Synopsis of Algorithmic Issues 13

1.6 Computational Approaches to Morphology and Syntax 16

Part I Computational Approaches to Morphology

2 The Formal Characterization of Morphological Operations 23

2.1 Introduction 24

2.2 Syntagmatic Variation 27

2.2.1 Simple Concatenation 27

2.2.2 Interlude: Prosodic Circumscription 29

2.2.3 Prosodically Governed Concatenation 31

2.2.4 Phonological Changes Induced by Affixation 35

2.2.5 Subsegmental Morphology 36

2.2.6 Subtractive Morphology 37

2.2.7 Extrametrical Infixation 39

2.2.8 Positively Circumscribed Infixation 40

2.2.9 Root-and-Pattern Morphology 41

2.2.10 Morphomic Components 46

2.3 Paradigmatic Variation 49

2.4 The Remaining Problem: Reduplication 53

2.5 Summary 61

3 The Relevance of Computational Issues for Morphological Theory 62

3.1 Introduction: Realizational versus Incremental Morphology 62

3.2 Stump's Theory 66

3.3 Computational Implementation of Fragments 67

3.3.1 Stem Alternations in Sanskrit 68

3.3.2 Position Classes in Swahili 73

3.3.3 Double Plurals in Breton 79

3.4 Equivalence of Inferential-Realizational and Lexical-Incremental Approaches: A Formal Analysis 83

3.5 Conclusions 85

Appendix 3A Lextools 86

Appendix 3B XFST Implementation of Sanskrit 95

4 A Brief History of Computational Morphology 100

4.1 Introduction 100

4.2 The KIMMO Two-Level MorphologicalAnalyzer 102

4.2.1 KIMMO Basics 103

4.2.2 FST Intersection 105

4.2.3 Koskenniemi's Rule Types 109

4.2.4 Koskenniemi's System as a Historical Accident 110

4.3 Summary 113

5 Machine Learning of Morphology 116

5.1 Introduction 116

5.2 Goldsmith, 2001 119

5.2.1 Candidate Generation 121

5.2.2 Candidate Evaluation 122

5.3 Schone and Jurafsky, 2001 124

5.4 Yarowsky and Wicentowski, 2001 129

5.5 Discussion 132

Part II Computational Approaches to Syntax

6 Finite-state Approaches to Syntax 139

6.1 N-gram Models 139

6.1.1 Background 139

6.1.2 Basic Approach 141

6.1.3 Smoothing 143

6.1.4 Encoding 148

6.1.5 Factored Language Models 150

6.2 Class-based Language Models 151

6.2.1 Forward Algorithm 154

6.3 Part-of-Speech Tagging 159

6.3.1 Viterbi Algorithm 160

6.3.2 Efficient N-best Viterbi Decoding 162

6.3.3 Forward-backward Algorithm 164

6.3.4 Forward-backward Decoding 168

6.3.5 Log-linear Models 170

6.4 NP Chunking and Shallow Parsing 173

6.5 Summary 174

7 Basic Context-free Approaches to Syntax 176

7.1 Grammars, Derivations and Trees 176

7.2 Deterministic Parsing Algorithms 180

7.2.1 Shift-reduce Parsing 181

7.2.2 Pushdown Automata 182

7.2.3 Top-down and Left-corner Parsing 184

7.3 Non-deterministic Parsing Algorithms 189

7.3.1 Re-analysis and Beam-search 191

7.3.2 CYK Parsing 193

7.3.3 Earley Parsing 201

7.3.4 Inside-outside Algorithm 203

7.3.5 Labeled Recall Parsing 206

7.4 Summary 208

8 Enriched Context-free Approaches to Syntax 209

8.1 Stochastic CFG-based Parsing 209

8.1.1 Treebanks and PCFGs 210

8.1.2 Lexicalized Context-free Grammars 221

8.1.3 Collins Parser 226

8.1.4 Charniak Parser 230

8.2 Dependency Parsing 234

8.3 PCFG-based Language Models 238

8.4 Unsupervised Grammar Induction 240

8.5 Finite-state Approximations 244

8.6 Summary 246

9 Context-sensitive Approaches to Syntax 248

9.1 Unification Grammars and Parsing 248

9.2 Lexicalized Grammar Formalisms and Parsing 257

9.2.1 Tree-adjoining Grammars 258

9.2.2 Combinatory Categorial Grammars 265

9.2.3 Other Mildly Context-sensitive Approaches 270

9.2.4 Finite-state and Context-free Approximations 271

9.3 Parse Selection 273

9.3.1 Stochastic Unification Grammars 273

9.3.2 Data-oriented Parsing 275

9.3.3 Context-free Parser Re-ranking 277

9.4 Transduction Grammars 279

9.5 Summary 283

References 285

Name Index 307

Language Index 312

Index 313