SPEECH and LANGUAGE PROCESSING

Table of Contents

1 Introduction

The Role of Knowledge in Speech and Language Processing
Models and Algorithms
Language, Thought, and Understanding
The Turing Test
The State of the Art and the Near-Term Future
A Short History of Speech and Language Processing
Foundational Insights: 1940s and 1950s
The Two Camps: 1957-1971
Natural Language Processing: 1972-1983
Generation and Finite-State Models: 1983-1993
The Field Comes Together: 1994-1999
A Brief Note on Psychology
Summary
Bibliographical And Historical Notes
Exercises

PART I: Words

2 Regular Expressions and Finite Automata

Regular Expressions
Basic Regular Expression Patterns
Disjunction, Grouping and Precedence
Memory
Advanced Operators
Finite State Automata
Using an FSA to Recognize Sheeptalk
Formal Languages
Nondeterministic FSAs
Using and NFSA to Recognize Strings
Recognition as Search
Relating Deterministic and Nondeterministic Automata
Regular Languages and FSAs
Summary
Bibliographical And Historical Notes
Exercises

3 Morphology and Finite State Transducers

Summary of (Mostly) English Morphology
Inflectional Morphology
Derivational Morphology
Finite-State Morphological Parsing
The Lexicon and Morphotactics
Morphological Parsing with Finite-State Transducers
Orthographic Rules and Finite-State Transducers
Combining an FST Lexicon and Rules
Lexicon-Free FSTs: The Porter Stemmer
Human Morphological Processing
Summary
Bibliographical and Historical Notes
Exercises

4 Computational Phonology and Pronunciation Modeling

Speech Sounds and Phonetic Transcription
The Vocal Organs
Consonants: Places of Articulation
Consonants: Manner of Articulation
Vowels
The Phoneme and Phonological Rules
Phonological Rules and Transducers
Mapping Text to Phones for TTS
Pronunciation Dictionaries
Beyond Dictionary Lookup: Text Analysis
An FSA-Based Pronunciation Lexicon
English Pronunciation Variation
Summary
Bibliographical And Historical Notes
Exercises

5 Probabilistic Models of Pronunciation and Spelling

Introduction to Spell Checking
Spelling Error Patterns
Detecting Non-word Errors
Probabilistic Models
Applying the Bayesian Method to Spelling Correction
Minimum Edit Distance
The Bayesian Method for Pronunciation
Decision Tree Models of Pronunciation Variation
Weighted Automata
Computing Likelihoods: The Forward Algorithm
Decoding: The Viterbi Algorithm
Weighted Automata and Segmentation
Summary
Bibliographical And Historical Notes
Exercises

PART II: Syntax

6 N-grams Models of Syntax

Counting Words in Corpora
Simple (Unsmoothed) N-grams
Smoothing
Add-One Discounting
Witten-Bell DIscounting
Good-Turing Discounting
Backoff
Combining Backoff with Discounting
Deleted Interpolation
N-grams for Spelling and Pronunciation
Real Word Spelling Errors
N-grams for Pronunciation Modeling
Entropy
Cross Entropy for Comparing Models
The Entropy of English
Summary
Bibliographical And Historical Notes
Exercises

7 HMMs and Speech Recognition

Introduction to Speech Recognition
Overview of a Speech Recognition Architecture
Overview of Hidden Markov Models
The Viterbi Algorithms Revisited
Advanced Methods of Decoding
A* Decoding
Acoustic Processing of Speech
Sound Waves
How to Interpret a Waveform
Spectra
Feature Extraction
Computing Acoustic Probabilities
Training a Recognizer
Summary
Bibliographical And Historical Notes
Exercises

8 Word Classes and Part-of-Speech Tagging

(Mostly) English Word Classes
Tagsets for English
Part of Speech Tagging
Rule-Based Part of Speech Tagging
Stochastic Part of Speech Tagging
The Actual Algorithm for HMM Tagging
Transformation-Based Tagging
How TBL Rules are Applied
How TBL Rules are Learned
Other Issues
Multiple Tags and Multiple-Words
Unknown Words
Class-based N-grams
Summary
Bibliographical And Historical Notes
Exercises

9 Context Free Grammars for English Syntax

Constituency
Context-Free Rules and Trees
Sentence-Level Constructions
The Noun Phrase
Before the Head Noun
After the Noun
Coordination
Conjunction
Agreement
The Verb Phrase and Subcategorization
Spoken Language Syntax
Disfluencies
Prosody
Grammar Equivalence and Normal Form
Finite-State Grammars and Context-Free Grammars
Grammars and Human Processing
Summary
Bibliographical And Historical Notes
Exercises

10 Parsing with Context Free Grammars

Parsing as Search
Top-down Parsing
Bottom-Up Parsing
Comparing Top-down and Bottom-up parsing
A Basic Top-Down Parser
Adding Bottom-up Filtering
Problems with the Simple Top-Down Parser
Left-recursion
Ambiguity
Repeated Parsing of Subtrees
The Earley Algorithm
The Algorithm
Dynamic Programming and its Relation to Chart Parsing and Viterbi
Finite-State Parsing Methods
Summary
Bibliographical And Historical Notes
Exercises

11 Features and Unification

Feature Structures
Unification of Feature Structures
Feature Structures in the Grammar
Agreement
Head Features
Subcategorization
Long Distance Dependencies
Implementing Unification
Unification Data Structures
The Unification Algorithm
Unification Parsing
Integrating Unification into an Earley Parser
Types and Inheritance
Extensions to Typing
Other Extensions to Unification
Summary
Bibliographical And Historical Notes
Exercises

12 Lexicalized and Probablistic Parsing

Probabilistic Context-Free Grammars
Probabilistic CYK Parsing of PCFGs
Learning PCFG Probabilities
Problems with PCFGs
Probabilistic Lexicalized CFGs
Dependency Grammars
Human Parsing
Summary
Bibliographical And Historical Notes
Exercises

13 Language and Complexity

The Chomsky Hierarchy
How to tell if a language isn't regular
 Pumping Lemma
 Are English and other Natural Languages Regular?
Is Natural Language Context-Free
Complexity and Human Processing
Summary
Bibliographical And Historical Notes
Exercises

PART III: Semantics

14 Representing Meaning

Introduction
 Computational Requirements for Representations
Meaning Structure of Language
Predicate Argument Structure
First Order Predicate Calculus
Elements of FOPC
The Semantics of FOPC
Variables and Quantifiers
Inference
Representing Linguistically Relevent Concepts
Categories
Events
Representing Time
Representing Beliefs
Related Representational Approaches
Alternative Conceptions of Meaning
Meaning as Action
Meaning and Truth
Summary
Bibliographical And Historical Notes

Exercises

15 Semantic Analysis

 Introduction
 Syntax-Driven Semantic Analysis
Semantic Augmentations to CFG Rules
Simple Semantic Attachments
Lambda Notation
Complex Terms
Quantifier Scoping and Complex Terms
Semantic Attachments for a Fragment of English
The Design of a Syntax-Driven Analyzer
Integrating Semantics into the Earley Algorithm
Idioms and Compositionality
Robust Analysis
Information Extraction
Basic Assumptions
Various Tasks
Entity Recognition
Topic Spotting
Slot Filling
Layered Finite State Methods
Summary
Bibliographical And Historical Notes
Exercises

16 Lexical Semantics

Introduction
Relations among Lexemes and Their Senses
Homonymy
Polysemy
Synonymy
Hyponymy
WordNet: A Database of Lexical Relations
The Internal Structure of Words
Thematic Roles
Selection Restrictions
Primitive Decomposition
Word Sense Disambiguation
Simple Constraint-Based Disambiguation
Robust Word-Sense Disambiguation
Other Issues
Discovering Senses
Information Retrieval
Representing Documents
Representing Users Needs
Retrieving Documents
Other Issues
Query Term Disambiguation
Query Expansion
Summary
Bibliographical And Historical Notes
Exercises

17 Word Sense Disambiguation and Information Retrieval

Selectional Restriction-Based Approaches

Limitations of Selectional Restrictions

Robust Word Sense Disambiguation

Machine Learning Approaches
Dictionary-Based Approaches

Information Retrieval

The Vector Space Model
Term Weighting
Term Selection and Creation
Homonymy, Polysemy and Synonymy
Improving User Queries

Other Information Retrieval Tasks
Summary

Bibliographical And Historical Notes

Exercises

PART IV: Discourse

18 Discourse (Written by Andy Kehler)

Introduction
Reference Resolution
Reference Phenomena
Syntactic and Semantic Constraints on Co-reference

Preferences in Pronoun Interpretation
An Algorithm for Pronoun Resolution
Text Coherence
The Phenomenon
An Inference-Based Resolution Algorithm
Discourse Structure
Summary
Bibliographical And Historical Notes
Exercises

19 Dialog and Conversational Agents

What Makes Dialog Different?
Turns and Utterances
Backchannels and Grounding
Conversational Implicature
Dialog Acts
Augmentations to Speech Acts
Automatic Interpretation of Dialog Acts
Plan-Inferential Interpretation of Dialog Acts
Cue-Based Interpretation of Dialog Acts
Summary
Dialog Structure and Coherence
Dialog Managers and Conversational Agents
Summary
Bibliographical And Historical Notes
Exercises

20 Generation (Written by Keith Vander Linden)

Introduction to Language Generation
An Architecture for Generation
Surface Realizations
Systemic Grammar
Functional Unification Grammar
Discourse Planning
Text Schemata
Rhetorical Structure Theory
Other Issues
Microplanning
Lexical Selection
Summary
Bibliographical And Historical Notes
Exercises

PART V: Multilingual Processing

21 Machine Translation (Written by Nigel Ward)

Language Similarities and Differences
The Transfer Metaphor
Syntactic Transformations
Lexical Transfer
The Interlingua Idea: Using Meaning
Direct Translation
Using Statistical Techniques
Quantifying Fluency
Quantifying Faithfulness
Search
Usability and System Development
Summary
Bibliographical And Historical Notes
Exercises

Appendices

A  Regular Expression Operators

B  The Porter Stemming Algorithm

C  CLAWS Tagsets

D  Training HMMs: The Forward Backward Algorithm