Table of Contents

I   Preliminaries

1   Introduction

1.1 Rationalist and Empiricist Approaches to Language

1.2 Scientific Content

1.3 The Ambiguity of Language: Why NLP Is Difficult

1.4 Dirty Hands

1.5 Further Reading

1.6 Exercises

2   Mathematical Foundations

2.1 Elementary Probability Theory

2.2 Essential Information Theory

2.3 Further Reading

3   Linguistics Essentials

3.1 Parts of Speech and Morphology

3.2 Phrase Structure

3.3 Semantics and Pragmatics

3.4 Other Areas

3.5 Further Reading

3.6 Exercises

4   Corpus-Based Work

4.1 Getting Set Up

4.2 Looking at Text

4.3 Marked-Up Data

4.4 Further Reading

4.5 Exercises

II   Words

5   Collocations

5.1 Frequency

5.2 Mean and Variance

5.3 Hypothesis Testing

5.4 Mutual Information

5.5 The Notion of Collocation

5.6 Further Reading

6   Statistical Inference: n-gram Models over Sparse Data

6.1 Bins: Forming Equivalence Classes

6.2 Statistical Estimators

6.3 Combining Estimators

6.4 Conclusions

6.5 Further Reading

6.6 Exercises

7   Word Sense Disambiguation

7.1 Methodological Preliminaries

7.2 Supervised Disambiguation

7.3 Dictionary-Based Disambiguation

7.4 Unsupervised Disambiguation

7.5 What Is a Word Sense?

7.6 Further Reading

7.7 Exercises

8   Lexical Acquisition

8.1 Evaluation Measures

8.2 Verb Subcategorization

8.3 Attachment Ambiguity

8.4 Selectional Preferences

8.5 Semantic Similarity

8.6 The Role of Lexical Acquisition in Statistical NLP

8.7 Further Reading

III   Grammar

9   Markov Models

9.1 Markov Models

9.2 Hidden Markov Models

9.3 The Three Fundamental Questions for HMMs

9.4 HMMs: Implementation, Properties, and Variants

9.5 Further Reading

10   Part-of-Speech Tagging

10.1 The Information Sources in Tagging

10.2 Markov Model Taggers

10.3 Hidden Markov Model Taggers

10.4 Transformation-Based Learning of Tags

10.5 Other Methods, Other Languages

10.6 Tagging Accuracy and Uses of Taggers

10.7 Further Reading

10.8 Exercises

11   Probabilistic Context Free Grammars

11.1 Some Features of PCFGs

11.2 Questions for PCFGs

11.3 The Probability of a String

11.4 Problems with the Inside-Outside Algorithm

11.5 Further Reading

11.6 Exercises

12   Probabilistic Parsing

12.1 Some Concepts

12.2 Some Approaches

12.3 Further Reading

12.4 Exercises

IV   Applications and Techniques

13   Statistical Alignment and Machine Translation

13.1 Text Alignment

13.2 Word Alignment

13.3 Statistical Machine Translation

13.4 Further Reading

14   Clustering

14.1 Hierarchical Clustering

14.2 Non-Hierarchical Clustering

14.3 Further Reading

14.4 Exercises

15   Topics in Information Retrieval

15.1 Some Background on Information Retrieval

15.2 The Vector Space Models

15.3 Term Distribution Models

15.4 Latent Semantic Indexing

15.5 Discourse Segmentation

15.6 Further Reading

15.7 Exercises

16   Text Categorization

16.1 Decision Trees

16.2 Maximum Entropy Modeling

16.3 Perceptrons

16.4 k Nearest Neighbor Classification

16.5 Further Reading