Foreword
Preface
About the Authors
1 Introduction
1.1 Knowledge in Speech and Language Processing
1.2 Ambiguity
1.3 Models and Algorithms
1.4 Language, Thought, and Understanding
1.5 The State of the Art
1.6 Some Brief History
1.6.1 Foundational Insights: 1940s and 1950s
1.6.2 The Two Camps: 1957-1970
1.6.3 Four Paradigms: 1970-1983
1.6.4 Empiricism and Finite State Models Redux: 1983-1993
1.6.5 The Field Comes Together: 1994-1999
1.6.6 The Rise of Machine Learning: 2000-2008
1.6.7 On Multiple Discoveries
1.6.8 A Final Brief Note on Psychology
1.7 Summary
Bibliographical and Historical Notes
Part I Words
2 Regular Expressions and Automata
2.1 Regular Expressions
2.1.1 Basic Regular Expression Patterns
2.1.2 Disjunction, Grouping, and Precedence
2.1.3 A Simple Example
2.1.4 A More Complex Example
2.1.5 Advanced Operators
2.1.6 Regular Expression Substitution, Memory, and ELIZA
2.2 Finite-State Automata
2.2.1 Using an FSA to Recognize Sheeptalk
2.2.2 Formal Languages
2.2.3 Another Example
2.2.4 Non-Deterministic FSAs
2.2.5 Using an NFSA to Accept Strings
2.2.6 Recognition as Search
2.2.7 Relating Deterministic and Non-Deterministic Automata
2.3 Regular Languages and FSAs
2.4 Summary
Bibliographical and Historical Notes
Exercises
3 Words and Transducers
3.1 Survey of (Mostly) English Morphology
3.1.1 Inflectional Morphology
3.1.2 Derivational Morphology
3.1.3 Cliticization
3.1.4 Non-Concatenative Morphology
3.1.5 Agreement
3.2 Finite-State Morphological Parsing
3.3 Construction of a Finite-State Lexicon
3.4 Finite-State Transducers
3.4.1 Sequential Transducers and Determinism
3.5 FSTs for Morphological Parsing
3.6 Transducers and Orthographic Rules
3.7 The COmbination of an FST Lexicon and Rules
3.8 Lexicon-Free FSTs: The Porter Stemmer
3.9 Word and Sentence Tokenization
3.9.1 Segmentation in Chinese
3.10 Detection and Correction of Spelling Errors
3.11 Minimum Edit Distance
3.12 Human Morphological Processing
3.13 Summary
Bibliographical and Historical Notes
Exercises
4 N-grams
4.1 Word Counting in Corpora
4.2 Simple (Unsmoothed) N-grams
4.3 Training and Test Sets
4.3.1 N-gram Sensitivity to the Training Corpus
4.3.2 Unknown Words: Open Versus Closed Vocabulary Tasks
4.4 Evaluating N-grams: Perplexity
4.5 Smoothing
4.5.1 Laplace Smoothing
4.5.2 Good-Turing Discounting
4.5.3 Some Advanced Issues in Good-Turing Estimation
4.6 Interpolation
4.7 Backoff
4.7.1 Advanced: Details of Computing Katz Backoff a and P?
4.8 Practical Issues: Toolkits and Data Formats
4.9 Advanced Issues in Language Modeling
4.9.1 Advanced Smoothing Methods: Kneser-Ney Smoothing
4.9.2 Class-Based N-grams
4.9.3 Language Model Adaptation and Web Use
4.9.4 Using Longer Distance Information: A Brief Summary
4.10 Advanced: Information Theory Background
4.10.1 Cross-Entropy for Comparing Models
4.11 Advanced: The Entropy of English and Entropy Rate Constancy
4.12 Summary
Bibliographical and Historical Notes
Exercises
5 Part-of-Speech Tagging
5.1 (Mostly) English Word Classes
5.2 Tagsets for English
5.3 Part-of-Speech Tagging
5.4 Rule-Based Part-of-Speech Tagging
5.5 HMM Part-of-Speech Tagging
5.5.1 Computing the Most-Likely Tag Sequence: An Example
5.5.2 Formalizing Hidden Markov Model Taggers
5.5.3 Using the Viterbi Algorithm for HMM Tagging
5.5.4 Extending the HMM Algorithm to Trigrams
5.6 Transformation-Based Tagging
5.6.1 How TBL Rules Are Applied
5.6.2 How TBL Rules Are Learned
5.7 Evaluation and Error Analysis
5.7.1 Error Analysis
5.8 Advanced Issues in Part-of-Speech Tagging
5.8.1 Practical Issues: Tag Indeterminacy and Tokenization
5.8.2 Unknown Words
5.8.3 Part-of-Speech Tagging for Other Languages
5.8.4 Tagger Combination
5.9 Advanced: The Noisy Channel Model for Spelling
5.9.1 Contextual Spelling Error Correction
5.10 Summary
Bibliographical and Historical Notes
Exercises
6 Hidden Markov and Maximum Entropy Models
6.1 Markov Chains
6.2 The Hidden Markov Model
6.3 Likelihood Computation: The Forward Algorithm
6.4 Decoding: The Viterbi Algorithm
6.5 HMM Training: The Forward-Backward Algorithm
6.6 Maximum Entropy Models: Background
6.6.1 Linear Regression
6.6.2 Logistic Regression
6.6.3 Logistic Regression: Classification
6.6.4 Advanced: Learning in Logistic Regression
6.7 Maximum Entropy Modeling
6.7.1 Why We Call it Maximum Entropy
6.8 Maximum Entropy Markov Models
6.8.1 Decoding and Learning in MEMMs
6.9 Summary
Bibliographical and Historical Notes
Exercises
Part II Speech
7 Phonetics
7.1 Speech Sounds and Phonetic Transcription
7.2 Articulatory Phonetics
7.2.1 The Vocal Organs
7.2.2 Consonants: Place of Articulation
7.2.3 Consonants: Manner of Articulation
7.2.4 Vowels
7.2.5 Syllables
7.3 Phonological Categories and Pronunciation Variation
7.3.1 Phonetic Features
7.3.2 Predicting Phonetic Variation
7.3.3 Factors Influencing Phonetic Variation
7.4 Acoustic Phonetics and Signals
7.4.1 Waves
7.4.2 Speech Sound Waves
7.4.3 Frequency and Amplitude; Pitch and Loudness
7.4.4 Interpretation of Phones from a Waveform
7.4.5 Spectra and the Frequency Domain
7.4.6 The Source-Filter Model
7.5 Phonetic Resources
7.6 Advanced: Articulatory and Gestural Phonology
7.7 Summary
Bibliographical and Historical Notes
Exercises
8 Speech Synthesis
8.1 Text Normalization
8.1.1 Sentence Tokenization
8.1.2 Non-Standard Words
8.1.3 Homograph Disambiguation
8.2 Phonetic Analysis
8.2.1 Dictionary Lookup
8.2.2 Names
8.2.3 Grapheme-to-Phoneme Conversion
8.3 Prosodic Analysis
8.3.1 Prosodic Structure
8.3.2 Prosodic Prominence
8.3.3 Tune
8.3.4 More Sophisticated Models: ToBI
8.3.5 Computing Duration from Prosodic Labels
8.3.6 Computing F0 from Prosodic Labels
8.3.7 Final Result of Text Analysis: Internal Representation
8.4 Diphone Waveform synthesis
8.4.1 Steps for Building a Diphone Database
8.4.2 Diphone Concatenation and TD-PSOLA for Prosody
8.5 Unit Selection (Waveform) Synthesis
8.6 Evaluation
Bibliographical and Historical Notes
Exercises
9 Automatic Speech Recognition
9.1 Speech Recognition Architecture
9.2 Applying the Hidden Markov Model to Speech
9.3 Feature Extraction: MFCC vectors
9.3.1 Preemphasis
9.3.2 Windowing
9.3.3 Discrete Fourier Transform
9.3.4 Mel Filter Bank and Log
9.3.5 The Cepstrum: Inverse Discrete Fourier Transform
9.3.6 Deltas and Energy
9.3.7 Summary: MFCC
9.4 Acoustic Likelihood Computation
9.4.1 Vector Quantization
9.4.2 Gaussian PDFs
9.4.3 Probabilities, Log Probabilities and Distance Functions
9.5 The Lexicon and Language Model
9.6 Search and Decoding
9.7 Embedded Training
9.8 Evaluation: Word Error Rate
9.9 Summary
Bibliographical and Historical Notes
Exercises
10 Speech Recognition: Advanced Topics
10.1 Multipass Decoding: N-best Lists and Lattices
10.2 A? ('Stack') Decoding
10.3 Context-Dependent Acoustic Models: Triphones
10.4 Discriminative Training
10.4.1 Maximum Mutual Information Estimation
10.4.2 Acoustic Models Based on Posterior Classifiers
10.5 Modeling Variation
10.5.1 Environmental Variation and Noise
10.5.2 Speaker Variation and Speaker Adaptation
10.5.3 Pronunciation Modeling: Variation Due to Genre
10.6 Metadata: Boundaries, Punctuation, and Disfluencies
10.7 Speech Recognition by Humans
10.8 Summary
Bibliographical and Historical Notes
Exercises
11 Computational Phonology
11.1 Finite-State Phonology
11.2 Advanced Finite-State Phonology
11.2.1 Harmony
11.2.2 Templatic Morphology
11.3 Computational Optimality Theory
11.3.1 Finite-State Transducer Models of Optimality Theory
11.3.2 Stochastic Models of Optimality Theory
11.4 Syllabification
11.5 Learning Phonology and Morphology
11.5.1 Learning Phonological Rules
11.5.2 Learning Morphology
11.5.3 Learning in Optimality Theory
11.6 Summary
Bibliographical and Historical Notes
Exercises
Part III Syntax
12 Formal Grammars of English
12.1 Constituency
12.2 Context-Free Grammars
12.2.1 Formal definition of Context-Free Grammar
12.3 Some Grammar Rules for English
12.3.1 Sentence-Level Constructions
12.3.2 Clauses and Sentences
12.3.3 The Noun Phrase
12.3.4 Agreement
12.3.5 The Verb Phrase and Subcategorization
12.3.6 Auxiliaries
12.3.7 Coordination
12.4 Treebanks
12.4.1 Example: The Penn Treebank Project
12.4.2 Treebanks as Grammars
12.4.3 Treebank Searching
12.4.4 Heads and Head Finding
12.5 Grammar Equivalence and Normal Form
12.6 Finite-State and Context-Free Grammars
12.7 Dependency Grammars
12.7.1 The Relationship Between Dependencies and Heads
12.7.2 Categorial Grammar
12.8 Spoken Language Syntax
12.8.1 Disfluencies and Repair
12.8.2 Treebanks for Spoken Language
12.9 Grammars and Human Processing
12.10 Summary
Bibliographical and Historical Notes
Exercises
13 Syntactic Parsing
13.1 Parsing as Search
13.1.1 Top-Down Parsing
13.1.2 Bottom-Up Parsing
13.1.3 Comparing Top-Down and Bottom-Up Parsing
13.2 Ambiguity
13.3 Search in the Face of Ambiguity
13.4 Dynamic Programming Parsing Methods
13.4.1 CKY Parsing
13.4.2 The Earley Algorithm
13.4.3 Chart Parsing
13.5 Partial Parsing
13.5.1 Finite-State Rule-Based Chunking
13.5.2 Machine Learning-Based Approaches to Chunking
13.5.3 Evaluating Chunking Systems
13.6 Summary
Bibliographical and Historical Notes
Exercises
14 Statistical Parsing
14.1 Probabilistic Context-Free Grammars
14.1.1 PCFGs for Disambiguation
14.1.2 PCFGs for Language Modeling
14.2 Probabilistic CKY Parsing of PCFGs
14.3 Learning PCFG Rule Probabilities
14.4 Problems with PCFGs
14.4.1 Independence Assumptions Miss Structural Dependencies Between Rules
14.4.2 Lack of Sensitivity to Lexical Dependencies
14.5 Improving PCFGs by Splitting Non-Terminals
14.6 Probabilistic Lexicalized CFGs
14.6.1 The Collins Parser
14.6.2 Advanced: Further Details of the Collins Parser
14.7 Evaluating Parsers
14.8 Advanced: Discriminative Reranking
14.9 Advanced: Parser-Based Language Modeling
14.10 Human Parsing
14.11 Summary
Bibliographical and Historical Notes
Exercises
15 Features and Unification
15.1 Feature Structures
15.2 Unification of Feature Structures
15.3 Feature Structures in the Grammar
15.3.1 Agreement
15.3.2 Head Features
15.3.3 Subcategorization
15.3.4 Long-Distance Dependencies
15.4 Implementation of Unification
15.4.1 Unification Data Structures
15.4.2 The Unification Algorithm
15.5 Parsing with Unification Constraints
15.5.1 Integration of Unification into an Earley Parser
15.5.2 Unification-Based Parsing
15.6 Types and Inheritance
15.6.1 Advanced: Extensions to Typing
15.6.2 Other Extensions to Unification
15.7 Summary
Bibliographical and Historical Notes
Exercises
16 Language and Complexity
16.1 The Chomsky Hierarchy
16.2 Ways to Tell if a Language Isn't Regular
16.2.1 The Pumping Lemma
16.2.2 Proofs That Various Natural Languages Are Not Regular
16.3 Is Natural Language Context-Free?
16.4 Complexity and Human Processing
16.5 Summary
Bibliographical and Historical Notes
Exercises
Part IV Semantics and Pragmatics
17 The Representation of Meaning
17.1 Computational Desiderata for Representations
17.1.1 Verifiability
17.1.2 Unambiguous Representations
17.1.3 Canonical Form
17.1.4 Inference and Variables
17.1.5 Expressiveness
17.2 Model-Theoretic Semantics
17.3 First-Order Logic
17.3.1 Basic Elements of First-Order Logic
17.3.2 Variables and Quantifiers
17.3.3 Lambda Notation
17.3.4 The Semantics of First-Order Logic
17.3.5 Inference
17.4 Event and State Representations
17.4.1 Representing Time
17.4.2 Aspect
17.5 Description Logics
17.6 Embodied and Situated Approaches to Meaning
17.7 Summary
Bibliographical and Historical Notes
Exercises
18 Computational Semantics
18.1 Syntax-Driven Semantic Analysis
18.2 Semantic Augmentations to Syntactic Rules
18.3 Quantifier Scope Ambiguity and Underspecification
18.3.1 Store and Retrieve Approaches
18.3.2 Constraint-Based Approaches
18.4 Unification-Based Approaches to Semantic Analysis
18.5 Integration of Semantics into the Earley Parser
18.6 Idioms and Compositionality
18.7 Summary
Bibliographical and Historical Notes
Exercises
19 Lexical Semantics
19.1 Word Senses
19.2 Relations Between Senses
19.2.1 Synonymy and Antonymy
19.2.2 Hyponymy
19.2.3 Semantic Fields
19.3 WordNet: A Database of Lexical Relations
19.4 Event Participants
19.4.1 Thematic Roles
19.4.2 Diathesis Alternations
19.4.3 Problems with Thematic Roles
19.4.4 The Proposition Bank
19.4.5 FrameNet
19.4.6 Selectional Restrictions
19.5 Primitive Decomposition
19.6 Advanced: Metaphor
19.7 Summary
Bibliographical and Historical Notes
Exercises
20 Computational Lexical Semantics
20.1 Word Sense Disambiguation: Overview
20.2 Supervised Word Sense Disambiguation
20.2.1 Feature Extraction for Supervised Learning
20.2.2 Naive Bayes and Decision List Classifiers
20.3 WSD Evaluation, Baselines, and Ceilings
20.4 WSD: Dictionary and Thesaurus Methods
20.4.1 The Lesk Algorithm
20.4.2 Selectional Restrictions and Selectional Preferences . . . . 684
20.5 Minimally Supervised WSD: Bootstrapping
20.6 Word Similarity: Thesaurus Methods
20.7 Word Similarity: Distributional Methods
20.7.1 Defining a Word's Co-Occurrence Vectors
20.7.2 Measuring Association with Context
20.7.3 Defining Similarity Between Two Vectors
20.7.4 Evaluating Distributional Word Similarity
20.8 Hyponymy and Other Word Relations
20.9 Semantic Role Labeling
20.10 Advanced: Unsupervised Sense Disambiguation
20.11 Summary
Bibliographical and Historical Notes
Exercises
21 Computational Discourse
21.1 Discourse Segmentation
21.1.1 Unsupervised Discourse Segmentation
21.1.2 Supervised Discourse Segmentation
21.1.3 Discourse Segmentation Evaluation
21.2 Text Coherence
21.2.1 Rhetorical Structure Theory
21.2.2 Automatic Coherence Assignment
21.3 Reference Resolution
21.4 Reference Phenomena
21.4.1 Five Types of Referring Expressions
21.4.2 Information Status
21.5 Features for Pronominal Anaphora Resolution
21.6 Three Algorithms for Pronominal Anaphora Resolution
21.6.1 Pronominal Anaphora Baseline: The Hobbs Algorithm
21.6.2 A Centering Algorithm for Anaphora Resolution
21.6.3 A Log-Linear Model for Pronominal Anaphora Resoluton
21.6.4 Features for Pronominal Anaphora Resoluton
21.7 Coreference Resolution
21.8 Evaluation of Coreference Resolution
21.9 Advanced: Inference-Based Coherence Resolution
21.10 Psycholinguistic Studies of Reference
21.11 Summary
Bibliographical and Historical Notes
Exercises
Part V Applications
22 Information Extraction
22.1 Named Entity Recognition
22.1.1 Ambiguity in Named Entity Recognition
22.1.2 NER as Sequence Labeling
22.1.3 Evaluation of Named Entity Recognition
22.1.4 Practical NER Architectures
22.2 Relation Detection and Classification
22.2.1 Supervised Learning Approaches to Relation Analysis
22.2.2 Lightly Supervised Approaches to Relation Analysis
22.2.3 Evaluation of Relation Analysis Systems
22.3 Temporal and Event Processing
22.3.1 Temporal Expression Recognition
22.3.2 Temporal Normalization
22.3.3 Event Detection and Analysis
22.3.4 TimeBank
22.4 Template-Filling
22.4.1 Statistical Approaches to Template-Filling
22.4.2 Finite-State Template-Filling Systems
22.5 Advanced: Biomedical Information Extraction
22.5.1 Biological Named Entity Recognition
22.5.2 Gene Normalization
22.5.3 Biological Roles and Relations
22.6 Summary
Bibliographical and Historical Notes
Exercises
23 Question Answering and Summarization
23.1 Information Retrieval
23.1.1 The Vector Space Model
23.1.2 Term Weighting
23.1.3 Term Selection and Creation
23.1.4 Evaluation of Information-Retrieval Systems
23.1.5 Homonymy, Polysemy, and Synonymy
23.1.6 Ways to Improve User Queries
23.2 Factoid Question Answering
23.2.1 Question Processing
23.2.2 Passage Retrieval
23.2.3 Answer Processing
23.2.4 Evaluation of Factoid Answers
23.3 Summarization
23.4 Single Document Summarization
23.4.1 Unsupervised Content Selection
23.4.2 Unsupervised Summarization Based on Rhetorical Parsing
23.4.3 Supervised Content Selection
23.4.4 Sentence Simplification
23.5 Multi-Document Summarization
23.5.1 Content Selection in Multi-Document Summarization
23.5.2 Information Ordering in Multi-Document Summarization
23.6 Focused Summarization and Question Answering
23.7 Summarization Evaluation
23.8 Summary
Bibliographical and Historical Notes
Exercises
24 Dialogue and Conversational Agents
24.1 Properties of Human Conversations
24.1.1 Turns and Turn-Taking
24.1.2 Language as Action: Speech Acts
24.1.3 Language as Joint Action: Grounding
24.1.4 Conversational Structure
24.1.5 Conversational Implicature
24.2 Basic Dialogue Systems
24.2.1 ASR component
24.2.2 NLU component
24.2.3 Generation and TTS components
24.2.4 Dialogue Manager
24.2.5 Dealing with Errors: Confirmation and Rejection
24.3 VoiceXML
24.4 Dialogue System Design and Evaluation
24.4.1 Designing Dialogue Systems
24.4.2 Evaluating Dialogue Systems
24.5 Information-State and Dialogue Acts
24.5.1 Using Dialogue Acts
24.5.2 Interpreting Dialogue Acts
24.5.3 Detecting Correction Acts
24.5.4 Generating Dialogue Acts: Confirmation and Rejection
24.6 Markov Decision Process Architecture
24.7 Advanced: Plan-Based Dialogue Agents
24.7.1 Plan-Inferential Interpretation and Production
24.7.2 The Intentional Structure of Dialogue
24.8 Summary
Bibliographical and Historical Notes
Exercises
25 Machine Translation
25.1 Why Machine Translation Is Hard
25.1.1 Typology
25.1.2 Other Structural Divergences
25.1.3 Lexical Divergences
25.2 Classical MT and the Vauquois Triangle
25.2.1 Direct Translation
25.2.2 Transfer
25.2.3 Combined Direct and Tranfer Approaches in Classic MT
25.2.4 The Interlingua Idea: Using Meaning
25.3 Statistical MT
25.4 P(F|E): the Phrase-Based Translation Model
25.5 Alignment in MT
25.5.1 IBM Model 1
25.5.2 HMM Alignment
25.6 Training Alignment Models
25.6.1 EM for Training Alignment Models
25.7 Symmetrizing Alignments for Phrase-Based MT
25.8 Decoding for Phrase-Based Statistical MT
25.9 MT Evaluation
25.9.1 Using Human Raters
25.9.2 Automatic Evaluation: BLEU
25.10 Advanced: Syntactic Models for MT
25.11 Advanced: IBM Model 3 and Fertitlity
25.11.1 Training for Model 3
25.12 Advanced: Log-linearModels for MT . . . . . . . . . . . . . . . . 903
25.13 Summary
Bibliographical and Historical Notes
Exercises
Bibliography
Author Index
Subject Index
