Foundations of Statistical Natural Language Processing

Cover......Page 1
Title Page......Page 5
Brief Contents......Page 7
Contents......Page 9
List of Tables......Page 17
List of Figures......Page 23
Table of Notations......Page 27
Preface......Page 31
Road Map......Page 37
Part I: Preliminaries......Page 41
1 Introduction......Page 43
1.1 Rationalist and Empiricist Approaches to Language......Page 44
1.2 Scientific Content......Page 47
1.2.1 Questions that linguistics should answer......Page 48
1.2.2 Non-categorical phenomena in language......Page 51
1.2.3 Language and cognition as probabilistic phenomena......Page 55
1.3 The Ambiguity of Language: Why NLP Is Difficult......Page 57
1.4.1 Lexical resources......Page 59
1.4.2 Word counts......Page 60
1.4.3 Zipf’s laws......Page 63
1.4.4 Collocations......Page 69
1.4.5 Concordances......Page 71
1.5 Further Reading......Page 74
1.6 Exercises......Page 75
2 Mathematical Foundations......Page 79
2.1.1 Probability spaces......Page 80
2.1.2 Conditional probability and independence......Page 82
2.1.3 Bayes’ theorem......Page 83
2.1.4 Random variables......Page 85
2.1.5 Expectation and variance......Page 86
2.1.6 Notation......Page 87
2.1.8 Determining P......Page 88
2.1.9 Standard distributions......Page 90
2.1.10 Bayesian statistics......Page 94
2.1.11 Exercises......Page 99
2.2 Essential Information Theory......Page 100
2.2.1 Entropy......Page 101
2.2.2 Joint entropy and conditional entropy......Page 103
2.2.3 Mutual information......Page 106
2.2.4 The noisy channel model......Page 108
2.2.5 Relative entropy or Kullback-Leibler divergence......Page 112
2.2.6 The relation to language: Cross entropy......Page 113
2.2.7 The entropy of English......Page 116
2.2.9 Exercises......Page 118
2.3 Further Reading......Page 119
3.1 Parts of Speech and Morphology......Page 121
3.1.1 Nouns and pronouns......Page 123
3.1.2 Words that accompany nouns: Determiners and adjectives......Page 127
3.1.3 Verbs......Page 128
3.1.4 Other parts of speech......Page 131
3.2 Phrase Structure......Page 133
3.2.1 Phrase structure grammars......Page 136
3.2.2 Dependency: Arguments and adjuncts......Page 141
3.2.3 X' theory......Page 146
3.2.4 Phrase structure ambiguity......Page 147
3.3 Semantics and Pragmatics......Page 149
3.4 Other Areas......Page 152
3.5 Further Reading......Page 153
3.6 Exercises......Page 154
4 Corpus-Based Work......Page 157
4.1.2 Corpora......Page 158
4.1.3 Software......Page 160
4.2.1 Low-level formatting issues......Page 163
4.2.2 Tokenization: What is a word?......Page 164
4.2.3 Morphology......Page 171
4.2.4 Sentences......Page 174
4.3 Marked-up Data......Page 176
4.3.1 Markup schemes......Page 177
4.3.2 Grammatical tagging......Page 179
4.4 Further Reading......Page 185
4.5 Exercises......Page 187
Part II: Words......Page 189
5 Collocations......Page 191
5.1 Frequency......Page 193
5.2 Mean and Variance......Page 197
5.3 Hypothesis Testing......Page 202
5.3.1 The t test......Page 203
5.3.2 Hypothesis testing of differences......Page 206
5.3.3 Pearson’s chi-square test......Page 209
5.3.4 Likelihood ratios......Page 212
5.4 Mutual Information......Page 218
5.5 The Notion of Collocation......Page 223
5.6 Further Reading......Page 227
6 Statistical Inference: n-gram Models over Sparse Data......Page 231
6.1.2 n-gram models......Page 232
6.1.3 Building n-gram models......Page 235
6.2 Statistical Estimators......Page 236
6.2.1 Maximum Likelihood Estimation (MLE)......Page 237
6.2.2 Laplace’s law, Lidstone’s law and the Jeffreys-Perks law......Page 242
6.2.3 Held out estimation......Page 245
6.2.4 Cross-validation (deleted estimation)......Page 250
6.2.5 Good-Turing estimation......Page 252
6.2.6 Briefly noted......Page 256
6.3 Combining Estimators......Page 257
6.3.1 Simple linear interpolation......Page 258
6.3.2 Katz’s backing-off......Page 259
6.3.3 General linear interpolation......Page 260
6.3.4 Briefly noted......Page 262
6.3.5 Language models for Austen......Page 263
6.4 Conclusions......Page 264
6.6 Exercises......Page 265
7 Word Sense Disambiguation......Page 269
7.1.1 Supervised and unsupervised learning......Page 272
7.1.3 Upper and lower bounds on performance......Page 273
7.2.1 Bayesian classification......Page 275
7.2.2 An information-theoretic approach......Page 279
7.3 Dictionary-Based Disambiguation......Page 281
7.3.1 Disambiguation based on sense definitions......Page 282
7.3.2 Thesaurus-based disambiguation......Page 284
7.3.3 Disambiguation based on translations in a second-language corpus......Page 287
7.3.4 One sense per discourse, one sense per collocation......Page 289
7.4 Unsupervised Disambiguation......Page 292
7.5 What Is a Word Sense?......Page 296
7.6 Further Reading......Page 300
7.7 Exercises......Page 302
8 Lexical Acquisition......Page 305
8.1 Evaluation Measures......Page 307
8.2 Verb Subcategorization......Page 311
8.3 Attachment Ambiguity......Page 318
8.3.1 Hindle and Rooth (1993)......Page 320
8.3.2 General remarks on PP attachment......Page 324
8.4 Selectional Preferences......Page 328
8.5 Semantic Similarity......Page 334
8.5.1 Vector space measures......Page 336
8.5.2 Probabilistic measures......Page 343
8.6 The Role of Lexical Acquisition in Statistical NLP......Page 348
8.7 Further Reading......Page 352
Part III: Grammar......Page 355
9 Markov Models......Page 357
9.1 Markov Models......Page 358
9.2 Hidden Markov Models......Page 360
9.2.1 Why use HMMs?......Page 362
9.2.2 General form of an HMM......Page 364
9.3 The Three Fundamental Questions for HMMs......Page 365
9.3.1 Finding the probability of an observation......Page 366
9.3.2 Finding the best state sequence......Page 371
9.3.3 The third problem: Parameter estimation......Page 373
9.4.1 Implementation......Page 376
9.4.2 Variants......Page 377
9.4.3 Multiple input observations......Page 378
9.5 Further Reading......Page 379
10 Part-of-Speech Tagging......Page 381
10.1 The Information Sources in Tagging......Page 383
10.2.1 The probabilistic model......Page 385
10.2.2 The Viterbi algorithm......Page 389
10.2.3 Variations......Page 391
10.3 Hidden Markov Model Taggers......Page 396
10.3.1 Applying HMMs to POS tagging......Page 397
10.3.2 The effect of initialization on HMM training......Page 399
10.4 Transformation-Based Learning of Tags......Page 401
10.4.1 Transformations......Page 402
10.4.2 The learning algorithm......Page 404
10.4.3 Relation to other models......Page 405
10.4.4 Automata......Page 407
10.4.5 Summary......Page 409
10.5.1 Other approaches to tagging......Page 410
10.6.1 Tagging accuracy......Page 411
10.6.2 Applications of tagging......Page 414
10.7 Further Reading......Page 417
10.8 Exercises......Page 419
11 Probabilistic Context Free Grammars......Page 421
11.1 Some Features of PCFGs......Page 426
11.2 Questions for PCFGs......Page 428
11.3.1 Using inside probabilities......Page 432
11.3.2 Using outside probabilities......Page 434
11.3.3 Finding the most likely parse for a sentence......Page 436
11.3.4 Training a PCFG......Page 438
11.4 Problems with the Inside-Outside Algorithm......Page 441
11.5 Further Reading......Page 442
11.6 Exercises......Page 444
12 Probabilistic Parsing......Page 447
12.1.1 Parsing for disambiguation......Page 448
12.1.2 Treebanks......Page 452
12.1.3 Parsing models vs. language models......Page 454
12.1.4 Weakening the independence assumptions of PCFGs......Page 456
12.1.5 Tree probabilities and derivational probabilities......Page 461
12.1.6 There’s more than one way to do it......Page 463
12.1.7 Phrase structure grammars and dependency grammars......Page 468
12.1.8 Evaluation......Page 471
12.1.9 Equivalent models......Page 477
12.1.10 Building parsers: Search methods......Page 479
12.1.11 Use of the geometric mean......Page 482
12.2.1 Non-lexicalized treebank grammars......Page 483
12.2.2 Lexicalized models using derivational histories......Page 488
12.2.3 Dependency-based models......Page 491
12.2.4 Discussion......Page 494
12.3 Further Reading......Page 496
12.4 Exercises......Page 498
Part IV: Applications and Techniques......Page 501
13 Statistical Alignment and Machine Translation......Page 503
13.1 Text Alignment......Page 506
13.1.1 Aligning sentences and paragraphs......Page 507
13.1.2 Length-based methods......Page 511
13.1.3 Offset alignment by signal processing techniques......Page 515
13.1.4 Lexical methods of sentence alignment......Page 518
13.2 Word Alignment......Page 524
13.3 Statistical Machine Translation......Page 526
13.4 Further Reading......Page 532
14 Clustering......Page 535
14.1 Hierarchical Clustering......Page 540
14.1.1 Single-link and complete-link clustering......Page 543
14.1.2 Group-average agglomerative clustering......Page 547
14.1.3 An application: Improving a language model......Page 549
14.1.4 Top-down clustering......Page 552
14.2 Non-Hierarchical Clustering......Page 554
14.2.1 K-means......Page 555
14.2.2 The EM algorithm......Page 558
14.3 Further Reading......Page 567
14.4 Exercises......Page 568
15 Topics in Information Retrieval......Page 569
15.1 Some Background on Information Retrieval......Page 570
15.1.1 Common design features of IR systems......Page 572
15.1.2 Evaluation measures......Page 574
15.1.3 The probability ranking principle (PRP)......Page 578
15.2 The Vector Space Model......Page 579
15.2.1 Vector similarity......Page 580
15.2.2 Term weighting......Page 581
15.3 Term Distribution Models......Page 584
15.3.1 The Poisson distribution......Page 585
15.3.2 The two-Poisson model......Page 588
15.3.3 The K mixture......Page 589
15.3.4 Inverse document frequency......Page 591
15.3.5 Residual inverse document frequency......Page 593
15.4 Latent Semantic Indexing......Page 594
15.4.1 Least-squares methods......Page 597
15.4.2 Singular Value Decomposition......Page 598
15.4.3 Latent Semantic Indexing in IR......Page 604
15.5 Discourse Segmentation......Page 606
15.5.1 TextTiling......Page 607
15.6 Further Reading......Page 610
15.7 Exercises......Page 613
16 Text Categorization......Page 615
16.1 Decision Trees......Page 618
16.2 Maximum Entropy Modeling......Page 629
16.2.1 Generalized iterative scaling......Page 631
16.2.2 Application to text categorization......Page 634
16.3 Perceptrons......Page 637
16.4 k Nearest Neighbor Classification......Page 644
16.5 Further Reading......Page 647
Tiny Statistical Tables......Page 649
A......Page 651
B......Page 653
C......Page 658
D......Page 661
E......Page 663
F......Page 664
G......Page 665
H......Page 668
J......Page 671
K......Page 673
L......Page 675
M......Page 678
N......Page 681
P......Page 682
R......Page 683
S......Page 686
T......Page 691
W......Page 692
Z......Page 694
A......Page 697
B......Page 698
C......Page 699
D......Page 701
F......Page 703
G......Page 704
H......Page 705
I......Page 706
K......Page 707
L......Page 708
M......Page 709
O......Page 711
P......Page 712
Q......Page 713
S......Page 714
T......Page 717
V......Page 718
Y......Page 719
Z......Page 720