Foundations of Statistical Natural Language Processing Christopher D. Manning Hinrich The MIT Press Cambridge, Massachusetts London, England Second printing, 1999 Massachusetts Institute of Technology Second printing with corrections, 2000 All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or informa- tion storage and retrieval) without permission in writing from the publisher. Typeset in Bright by the authors using Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Information Manning, Christopher D. Foundations of statistical natural language processing Christopher D. Manning, Hinrich Schutze. Includes bibliographical references (p.
Computational linguistics-Statistical methods. 1999 99-21137 Brief Contents I Preliminaries 1 1 Introduction 3 2 Mathematical Foundations 39 3 Linguistic Essentials 81 4 Corpus-Based Work 117 II W o r d s 1 4 9 5 Collocations 151 6 Statistical Inference: n-gram Models over Sparse Data 191 7 Word Sense Disambiguation 229 8 Lexical Acquisition 265 III Grammar 315 9 Markov Models 317 10 Part-of-Speech Tagging 341 11 Probabilistic Context Free Grammars 381 12 Probabilistic Parsing 407 Iv Applications and Techniques 461 13 Statistical Alignment and Machine Translation 463 14 Clustering 495 15 Topics in Information Retrieval 529 16 Text Categorization 575 Contents List of Tables xv List of Figures xxi Table of Notations xxv Preface Road Map I Preliminaries 1 1 Introduction 3 1.1 Rationalist and Empiricist Approaches to Language 4 1.1 Questions that linguistics should answer 8 1.2 Non-categorical phenomena in language 11 1.3 Language and cognition as probabilistic phenomena 15 1.3 The Ambiguity of Language: Why NLP Is Difficult 17 1.5 Further Reading 34 Contents 1.6 Exercises 35 2 Mathematical Foundations 39 2.1 Elementary Probability Theory 40 2.2 Conditional probability and independence 42 2.5 Expectation and variance 46 2.7 Joint and conditional distributions 48 2.2 Essential Information Theory 60 2.2 Joint entropy and conditional entropy 63 2.4 The noisy channel model 68 2.5 Relative entropy or Kullback-Leibler divergence 72 2.6 The relation to language: Cross entropy 73 2.7 The entropy of English 76 2.3 Further Reading 79 3 Linguistic Essentials 8 1 3.1 Parts of Speech and Morphology 8 1 3.1 Nouns pronouns and 83 3.2 Words that accompany nouns: Determiners and adjectives 87 3.4 Other parts of speech 91 3.1 Phrase grammars structure 96 3.2 Dependency: Arguments and adjuncts 101 3.4 Phrase structure ambiguity 107 Contents ix 3.6 Exercises 114 4 Corpus-Based Work 117 4.1 Getting Set Up 118 4.2 Looking at Text 123 4.1 Low-level formatting issues 123 4.2 Tokenization: What is a word? 124 4.3 Marked-up Data 136 4.5 Exercises 147 II Words 149 5 Collocations 151 5.2 Mean and Variance 157 5.2 Hypothesis testing of differences 166 5.3 Pearson’s chi-square test 169 5.5 The Notion of Collocation 183 5.6 Further Reading 187 6 Statistical Inference: n -gram Models over Sparse Data 191 6.1 Bins: Forming Equivalence Classes 192 6.2 n-gram models 192 Contents 6.3 n-gram models Building 195 6.1 Maximum Likelihood Estimation 197 6.2 Laplace’s law, Lidstone’s law and the Jeffreys-Perks law 202 6.3 Held out estimation 205 6.5 Good-Turing estimation 212 6.1 Simple linear interpolation 218 6.2 Katz’s backing-off 219 6.3 General linear interpolation 220 6.5 Language models for Austen 223 6.6 Exercises 225 7 Word Sense Disambiguation 229 7.1 Supervised and unsupervised learning 232 7.3 Upper and lower bounds on performance 233 7.2 An information-theoretic approach 239 7.3 Dictionary-Based Disambiguation 241 7.1 Disambiguation based on sense definitions 242 7.2 Thesaurus-based disambiguation 244 7.3 Disambiguation based on translations in a second-language corpus 247 7.4 One sense per discourse, one sense per collocation 249 7.5 What Is a Word Sense? 256 7.7 Exercises 262 Contents xi 8 Lexical Acquisition 265 8.1 Hindle and Rooth (1993) 280 8.2 General remarks on PP attachment 284 8.1 Vector space measures 296 Probabilistic measures 303 8.6 The Role of Lexical Acquisition in Statistical NLP 308 8.7 Further Reading 312 III 315 9 Markov Models 317 9.2 Hidden Markov Models 320 9.2 General form of an HMM 324 9.3 The Three Fundamental Questions for 325 9.1 Finding the probability of an observation 326 9.2 Finding the best state sequence 331 9.3 The third problem: Parameter estimation 333 9.4 Implementation, Properties, and Variants 336 9.3 Multiple input observations 338 9.4 Initialization of parameter values 339 9.5 Further Reading 339 10 Part-of-Speech Tagging 341 10.1 The Information Sources in Tagging 343 10.2 Markov Model Taggers 345 10.1 The probabilistic model 345 10.2 The Viterbi algorithm 349 10.3 Hidden Markov Model Taggers 356 xii Contents 10.1 Applying to POS tagging 357 10.32 The effect of initialization on HMM training 359 10.4 Transformation-Based Learning of Tags 361 10.2 The learning algorithm 364 10.3 Relation to other models 365 10.5 Other Methods, Other Languages 370 10.1 Other approaches to tagging 370 10.2 Languages other than English 371 10.6 Tagging Accuracy and Uses of Taggers 371 10.2 Applications of tagging 374 10.8 E x e r c i s e s 3 7 9 11 Probabilistic Context Free Grammars 381 11.1 Some Features of PCFGs 3 8 6 11.2 Questions for PCFGs 388 11.3 The Probability of a String 392 11.1 Using inside probabilities 392 11.2 Using outside probabilities 394 11.3 Finding the most likely parse for a sentence 396 11.4 Problems with the Inside-Outside Algorithm 401 11.6 Exercises 404 12 Probabilistic Parsing 407 12.1 Parsing for disambiguation 408 12.3 Parsing models vs.4 Weakening the independence assumptions of PCFGs 416 12.5 Tree probabilities and derivational probabilities 421 12.6 There’s more than one way to do it 423 Contents 121.7 Phrase structure grammars and dependency grammars 428 12. 1 0 B u i l dparsers: ing Search methods 439 12.11 Use of the geometric mean 442 12.1 Non-lexicalized grammars 443 12.2 Lexicalized models using derivational histories 448 12.3 Dependency-based models 451 12.4 E x e r c i s e s 4 5 8 Applications and Techniques 461 13 Statistical Alignment and Machine Translation 463 13.1 Aligning sentences and paragraphs 467 13.2 Length-based methods 471 13.3 Offset alignment by signal processing techniques 475 13.4 Lexical methods of sentence alignment 478 13.3 Statistical Machine Translation 486 13.4 Further Reading 492 14 Clustering 495 14.1 Single-link and complete-link clustering 503 14.2 Group-average agglomerative clustering 507 14.3 An application: Improving a language model 509 14.4 Top-down clustering 512 14.2 Non-Hierarchical Clustering 514 14.2 The EM algorithm 518 14.3 Further Reading 527 xiv 14.4 Exercises 528 15 Topics in Information Retrieval 529 15.1 Some Background on Information Retrieval 530 15.1 Common design features of IR systems 532 15.3 The probability ranking principle 538 15.2 The Vector Space Model 539 15.3 Term Distribution Models 544 15.1 The Poisson distribution 545 15.2 The two-Poisson model 548 15.4 Inverse document frequency 551 Residual inverse document frequency 553 15.6 Usage of term distribution models 554 15.4 Latent Semantic Indexing 554 15.1 Least-squares methods 557 15.2 Singular Value Decomposition 558 15.3 Latent Semantic Indexing in IR 564 15.7 Exercises 573 16 Text Categorization 575 16.2 Maximum Entropy Modeling 589 16.1 Generalized iterative scaling 591 16.2 Application to text categorization 594 16.4 k Nearest Neighbor Classification 604 16.5 Further Reading 607 Tiny Statistical Tables 609 Bibliography 611 Index 657 List of Tables 1.1 Common words in Tom Sawyer.2 Frequency of frequencies of word types in Tom Sawyer.3 Empirical evaluation of Zipf’s law on Tom Sawyer.4 Commonest collocations in the New York Times.5 Frequent after filtering.1 Likelihood ratios between two theories.2 Statistical NLP problems as decoding problems.1 Common inflections of nouns.2 Pronoun forms in English.3 Features commonly marked on verbs.1 Major suppliers of electronic corpora with contact 119 4.2 Different formats for telephone numbers appearing in an issue of The Economist.3 Sentence lengths in text.4 Sizes of various tag sets.5 Comparison of different tag sets: adjective, adverb, conjunction, determiner, noun, and pronoun tags.6 Comparison of different tag sets: Verb, preposition, punctuation and symbol tags.1 Finding Collocations: Raw Frequency.2 Part of speech tag patterns for collocation filtering.3 Finding Collocations: Justeson and Katz’ part-of-speech filter. 15 5 xvi List of Tables 5.4 The nouns w occurring most often in the patterns ‘strong and ‘powerful 156 5.5 Finding collocations based on mean and variance.6 Finding collocations: The test applied to 10 that occur with frequency 20.7 Words that occur significantly more often with powerful (the first ten words) and strong (the last ten words).8 A 2-by-2 table showing the dependence of occurrences of new and companies.9 Correspondence of and cow in an aligned corpus.10 Testing for the independence of words in different corpora using 171 5.11 How to compute Dunning’s likelihood ratio test.12 of powerful with the highest scores according to Dunning’s likelihood ratio test.13 Damerau’s frequency ratio test.14 Finding collocations: Ten that occur with frequency 20, ranked according to mutual information.15 Correspondence of and house and and house in the aligned Hansard corpus.16 Problems for Mutual Information from data sparseness.17 Different definitions of mutual information in (Cover and Thomas 1991) and (Fano 1961).18 Collocations in the BBI Combinatory Dictionary of English for the words strength and power.1 Growth in number of parameters for n-gram models.2 Notation for the statistical estimation chapter.3 Probabilities of each successive word for a clause from Persuasion.4 Estimated frequencies for the AP data from Church and Gale 203 6.5 Expected Likelihood Estimation estimates for the word following was.6 Using the test for comparing the performance of two systems.7 Extracts from the frequencies of frequencies distribution for and in the Austen corpus.
214 List of Tables xvii 6.8 Good-Turing estimates for Adjusted frequencies and probabilities.9 Good-Turing frequency estimates for the clause from Persuasion.10 Back-off language models with Good-Turing estimation tested on Persuasion.11 Probability estimates of the test clause according to various language models.1 Notational conventions used in this chapter.2 Clues for two senses of drug used by a Bayesian classifier.3 Highly informative indicators for three ambiguous French words.4 Two senses of ash.5 Disambiguation of ash with Lesk’s algorithm.6 Some results of thesaurus-based disambiguation.7 How to disambiguate interest using a second-language corpus.8 Examples of the one sense per discourse constraint.9 Some results of unsupervised disambiguation.1 The measure and accuracy are different objective functions.2 Some subcategorization frames with example verbs and sentences.3 Some subcategorization frames learned by Manning’s system.4 An example where the simple model for resolving PP attachment ambiguity fails.5 Selectional Preference Strength (SPS).6 Association strength distinguishes a verb’s plausible and implausible objects.7 Similarity measures for binary vectors.8 The cosine as a measure of semantic similarity.9 Measures of between probability distributions.10 Types of words occurring in the LOB corpus that were not covered by the OALD dictionary.1 Notation used in the HMM chapter.2 Variable calculations for 0 = (lem, cola).1 Some part-of-speech tags frequently used for tagging English. 342 List of Tables 10.2 Notational conventions for tagging.3 Idealized counts of some tag transitions in the Brown Corpus.4 Idealized counts of tags that some words occur within the Brown Corpus.5 Table of probabilities for dealing with unknown words in tagging.6 Initialization of the parameters of an HMM.7 Triggering environments in Brill’s transformation-based tagger.8 Examples of some transformations learned in transformation-based tagging.9 Examples of frequent errors of probabilistic taggers.10 A portion of a confusion matrix for part of speech tagging.1 Notation for the PCFG chapter.2 A simple Probabilistic Context Free Grammar (PCFG).3 Calculation of inside probabilities.1 Abbreviations for phrasal categories in the Penn Treebank.2 Frequency of common subcategorization frames (local trees expanding VP) for selected verbs.3 Selected common expansions of NP as Subject vs. Object, ordered by log odds ratio.4 Selected common expansions of NP as first and second object inside VP.5 Precision and recall evaluation results for PP attachment errors for different styles of phrase structure.6 Comparison of some statistical parsing systems.1 Sentence alignment papers.1 A summary of the attributes of different clustering algorithms.2 Symbols used in the clustering chapter.3 Similarity functions used in clustering.4 An example of K-means clustering.5 An example of a Gaussian mixture.1 A small stop list for English.2 An example of the evaluation of rankings. 535 List of Tables xix 15.3 Three quantities that are commonly used in term weighting in information retrieval.