Computational Approaches to Morphology and Syntax / Edition 1

Computational Approaches to Morphology and Syntax / Edition 1

5.0 1
by Brian Roark, Richard Sproat, Richard Sproat
     
 

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

See more details below

Overview

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.

Product Details

ISBN-13:
9780199274789
Publisher:
Oxford University Press, USA
Publication date:
09/07/2007
Series:
Oxford Surveys in Syntax & Morphology Series, #4
Edition description:
New Edition
Pages:
320
Product dimensions:
9.60(w) x 6.70(h) x 0.70(d)

Table of Contents

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

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >