Handbook of natural language processing

Contents......Page 6
List of Figures......Page 8
List of Tables......Page 12
Editors......Page 13
Board of Reviewers......Page 14
Contributors......Page 16
Preface......Page 18
Part I: Classical Approaches......Page 21
1.1 Context......Page 22
1.2 The Classical Toolkit......Page 23
Lexical Analysis......Page 24
1.3 Conclusions......Page 25
Reference......Page 26
2.1 Introduction......Page 27
2.2 Challenges of Text Preprocessing......Page 28
Character-Set Dependence......Page 29
Language Dependence......Page 31
Application Dependence......Page 32
2.3 Tokenization......Page 33
Tokenization in Space-Delimited Languages......Page 34
Tokenization in Unsegmented Languages......Page 37
2.4 Sentence Segmentation......Page 40
Sentence Boundary Punctuation......Page 41
The Importance of Context......Page 42
Traditional Rule-Based Approaches......Page 43
Trainable Algorithms......Page 44
2.5 Conclusion......Page 45
References......Page 46
3.1 Introduction......Page 49
3.2 Finite State Morphonology......Page 51
3.3 Finite State Morphology......Page 55
Disjunctive Affixes, Inflectional Classes, and Exceptionality......Page 57
3.4 \"Difficult\" Morphology and Lexical Analysis......Page 60
Isomorphism Problems......Page 61
Contiguity Problems......Page 62
Paradigmatic Relations and Generalization......Page 65
The Role of Defaults......Page 69
Paradigm-Based Accounts of Difficult Morphology......Page 70
Further Remarks on Paradigm-Based Approaches......Page 71
3.6 Concluding Remarks......Page 72
References......Page 73
4.1 Introduction......Page 77
Context-Free Grammars......Page 79
Syntax Trees......Page 80
Other Grammar Formalisms......Page 81
Basic Concepts in Parsing......Page 82
4.3 The Cocke–Kasami–Younger Algorithm......Page 83
Example Session......Page 84
4.4 Parsing as Deduction......Page 85
Chart Parsing......Page 86
Example Session......Page 88
Dynamic Filtering......Page 89
Storing and Retrieving Parse Results......Page 90
The LR(0) Table......Page 91
Deterministic LR Parsing......Page 92
Generalized LR Parsing......Page 93
Overview......Page 95
Unification......Page 96
Robustness......Page 97
Disambiguation......Page 99
Efficiency......Page 100
4.9 Historical Notes and Outlook......Page 101
References......Page 102
5. Semantic Analysis......Page 110
5.1 Basic Concepts and Issues in Natural Language Semantics......Page 111
Logical Approaches......Page 112
Discourse Representation Theory......Page 114
Pustejovsky\'s Generative Lexicon......Page 115
Natural Semantic Metalanguage......Page 117
Object-Oriented Semantics......Page 119
Sense Relations and Ontologies......Page 120
Roles......Page 122
Emotional Meanings: \"Sadness\" and \"Worry\" in English and Chinese......Page 124
Ethnogeographical Categories: \"Rivers\" and \"Creeks\"......Page 126
Functional Macro-Categories......Page 128
5.5 Prospectus and \"Hard Problems\"......Page 130
References......Page 131
6.1 Introduction......Page 138
Complex......Page 141
Simple......Page 142
6.3 The Components of a Generator......Page 143
Components and Levels of Representation......Page 144
The Function of the Speaker......Page 146
Pushing vs. Pulling......Page 148
Planning by Progressive Refinement of the Speaker\'s Message......Page 149
Text Schemas......Page 150
Surface Realization Components......Page 151
Assembling vs. Navigating......Page 152
Systemic Grammars......Page 153
Functional Unification Grammars......Page 154
Story Generation......Page 155
Personality-Sensitive Generation......Page 156
6.7 Conclusions......Page 157
References......Page 158
Part II: Empirical and Statistical Approaches......Page 162
7.1 Introduction......Page 163
7.2 Corpus Size......Page 164
7.3 Balance, Representativeness, and Sampling......Page 165
7.4 Data Capture and Copyright......Page 169
7.5 Corpus Markup and Annotation......Page 171
7.6 Multilingual Corpora......Page 175
7.8 Conclusions......Page 177
References......Page 178
8.1 Introduction......Page 182
8.2 Corpus Annotation Types......Page 183
Motivation and Definition......Page 184
An Example: The Penn Treebank......Page 185
Annotation and Linguistic Theory......Page 186
Going Beyond the Surface Shape of the Sentence......Page 189
8.5 The Process of Building Treebanks......Page 191
8.6 Applications of Treebanks......Page 192
8.7 Searching Treebanks......Page 195
8.8 Conclusions......Page 196
References......Page 197
9.1 Binary Linear Classification......Page 204
9.2 One-versus-All Method for Multi-Category Classification......Page 208
9.4 Generative and Discriminative Models......Page 209
Naive Bayes......Page 210
Logistic Regression......Page 211
9.5 Mixture Model and EM......Page 213
Hidden Markov Model......Page 215
Local Discriminative Model for Sequence Prediction......Page 217
Global Discriminative Model for Sequence Prediction......Page 218
References......Page 219
Parts of Speech......Page 220
Part-of-Speech Problem......Page 221
10.2 The General Framework......Page 223
Rule-Based Approaches......Page 224
Markov Model Approaches......Page 229
Maximum Entropy Approaches......Page 234
10.4 Other Statistical and Machine Learning Approaches......Page 237
Methods and Relevant Work......Page 238
Combining Taggers......Page 239
Chinese......Page 240
Korean......Page 242
10.6 Conclusion......Page 243
References......Page 244
11.1 Introduction......Page 251
Syntactic Representations......Page 252
Parser Evaluation......Page 254
Basic Definitions......Page 255
PCFGs as Statistical Parsing Models......Page 256
Learning and Inference......Page 257
11.4 Generative Models......Page 258
History-Based Models......Page 259
PCFG Transformations......Page 261
Data-Oriented Parsing......Page 262
11.5 Discriminative Models......Page 263
Local Discriminative Models......Page 264
Global Discriminative Models......Page 266
Unsupervised Parsing......Page 269
11.7 Summary and Conclusions......Page 271
References......Page 272
12.1 Introduction......Page 281
Idiomaticity......Page 283
Other Properties of MWEs......Page 285
Testing an Expression for MWEhood......Page 286
Collocations and MWEs......Page 287
Nominal MWEs......Page 288
Verbal MWEs......Page 289
Prepositional MWEs......Page 292
12.4 MWE Classification......Page 293
Identification......Page 294
Extraction......Page 295
Internal Syntactic Disambiguation......Page 297
MWE Interpretation......Page 298
References......Page 299
13.1 Introduction......Page 307
Association Measures......Page 309
Latent Semantic Analysis......Page 310
13.3 Background of the NWD Method......Page 311
13.4 Brief Introduction to Kolmogorov Complexity......Page 312
13.5 Information Distance......Page 314
Normalized Compression Distance......Page 315
13.6 Word Similarity: Normalized Web Distance......Page 316
Hierarchical Clustering......Page 318
Classification......Page 322
Systematic Comparison with WordNet Semantics......Page 324
13.8 Conclusion......Page 325
References......Page 326
14.1 Introduction......Page 329
Treatment of Part of Speech......Page 330
Sources of Sense Inventories......Page 331
Granularity of Sense Partitions......Page 332
Regular Polysemy......Page 333
Applications in Machine Translation......Page 334
Bar-Hillel: An Early Perspective on WSD......Page 335
Early AI Systems: Word Experts......Page 336
14.5 Supervised Approaches to Sense Disambiguation......Page 337
Training Data for Supervised WSD Algorithms......Page 338
Features for WSD Algorithms......Page 339
Supervised WSD Algorithms......Page 340
WSD via Word-Class Disambiguation......Page 341
WSD via Monosemous Relatives......Page 342
Iterative Bootstrapping Algorithms......Page 343
14.7 Unsupervised WSD and Sense Discovery......Page 345
References......Page 346
15.1 Introduction......Page 353
15.2 Major Architectural Components......Page 354
Acoustic Models......Page 355
Language Models......Page 357
Decoding......Page 360
15.3 Major Historical Developments in Speech Recognition......Page 364
15.4 Speech-Recognition Applications......Page 366
Mobile Applications......Page 368
Robustness against Acoustic Environments and a Multitude of Other Factors......Page 370
Capitalizing on Data Deluge for Speech Recognition......Page 372
Self-Learning and Adaptation for Speech Recognition......Page 373
Detection of Unknown Events in Speech Recognition......Page 374
Learning from Human Speech Perception and Production......Page 375
Embedding Knowledge and Parallelism into Speech-Recognition Decoding......Page 376
References......Page 377
16.1 Introduction......Page 381
Alignment......Page 383
Constraints and Correlations......Page 387
Length-Based Sentence Alignment......Page 392
Lexical Sentence Alignment......Page 397
Multifeature Sentence Alignment......Page 399
16.4 Character, Word, and Phrase Alignment......Page 400
Non-Monotonic Alignment for Single-Token Words......Page 401
Non-Monotonic Alignment for Multitoken Words and Phrases......Page 404
16.5 Structure and Tree Alignment......Page 405
Cost Functions......Page 406
Algorithms......Page 407
16.6 Biparsing and ITG Tree Alignment......Page 408
Inversion Transduction Grammars......Page 409
Cost Functions......Page 411
Algorithms......Page 412
Grammars for Biparsing......Page 414
Strengths and Weaknesses of Biparsing and ITG Tree Alignment Techniques......Page 415
16.7 Conclusion......Page 416
References......Page 417
17.1 Introduction......Page 423
17.2 Approaches......Page 424
17.3 Language Models......Page 425
17.5 Word Alignment......Page 426
17.7 Translation Models......Page 427
Phrase-Based Systems......Page 428
Syntax-Based Systems for Machine Translation......Page 429
Direct Translation Models......Page 431
17.8 Search Strategies......Page 433
Acknowledgment......Page 434
References......Page 435
Part III: Applications......Page 437
18.1 Introduction......Page 439
18.2 Preprocessing—What Is a Chinese Word?......Page 440
The Maximum Entropy Framework for Word Segmentation......Page 441
Translation-Driven Word Segmentation......Page 443
18.3 Phrase-Based SMT—From Words to Phrases......Page 444
18.4 Example-Based MT—Translation by Analogy......Page 445
18.5 Syntax-Based MT—Structural Transfer......Page 446
18.6 Semantics-Based SMT and Interlingua......Page 450
Word Sense Translation......Page 451
Semantic Role Labels......Page 452
Chinese Term and Named Entity Translation......Page 456
Chinese Spoken Language Translation......Page 460
18.8 Conclusion and Discussion......Page 461
References......Page 462
19.1 Introduction......Page 468
19.2 Indexing......Page 469
Indexing Dimensions......Page 470
Indexing Process......Page 471
Classical Boolean Model......Page 473
Vector-Space Models......Page 474
Probabilistic Models......Page 476
Query Expansion and Relevance Feedback......Page 479
Advanced Models......Page 480
19.4 Evaluation and Failure Analysis......Page 482
Evaluation Campaigns......Page 483
Evaluation Measures......Page 484
Failure Analysis......Page 486
19.5 Natural Language Processing and Information Retrieval......Page 487
Morphology......Page 488
Syntax......Page 490
Semantics......Page 491
Related Applications......Page 492
19.6 Conclusion......Page 493
References......Page 494
20.1 Introduction......Page 498
20.2 Historical Context......Page 500
Question Analysis......Page 501
Document or Passage Selection......Page 504
Answer Extraction......Page 505
20.4 Evaluation of QA Systems......Page 510
Evolution of the TREC QA Track......Page 511
Evaluation Metrics......Page 513
20.5 Multilinguality in Question Answering......Page 514
20.6 Question Answering on Restricted Domains......Page 516
20.7 Recent Trends and Related Work......Page 517
Acknowledgment......Page 518
References......Page 519
21.1 Introduction......Page 524
Unstructured vs. Semi-Structured Text......Page 526
Single-Document vs. Multi-Document IE......Page 527
Assumptions about Incoming Documents......Page 528
Complex Words......Page 529
Basic Phrases......Page 530
Complex Phrases......Page 531
Domain Events......Page 532
Template Generation: Merging Structures......Page 534
Supervised Learning of Extraction Patterns and Rules......Page 535
Supervised Learning of Sequential Classifier Models......Page 536
Weakly Supervised and Unsupervised Approaches......Page 537
21.5 How Good Is Information Extraction?......Page 538
References......Page 539
22.1 Introduction......Page 546
What Makes a Text a Report?......Page 547
Report as Text Genre......Page 548
Characteristic Features of Report Generation......Page 549
Data and Knowledge Sources......Page 550
Data Assessment and Interpretation......Page 552
Content Selection......Page 553
22.5 Linguistic Realization for Report Generation......Page 554
Input and Levels of Linguistic Representation......Page 555
Tasks of Linguistic Realization......Page 556
22.6 Sample Report Generators......Page 557
22.8 Conclusions: The Present and the Future of RG......Page 564
References......Page 565
23.1 Introduction......Page 569
23.2 Multimedia Presentation Generation......Page 570
23.3 Language Interfaces for Intelligent Tutoring Systems......Page 574
CIRCSIM-Tutor......Page 576
ATLAS-ANDES, WHY2-ATLAS, and WHY2-AUTOTUTOR......Page 577
Briefly Noted......Page 579
23.4 Argumentation for Health-Care Consumers......Page 580
References......Page 582
24.1 Introduction......Page 588
24.2 Ontology and Ontologies......Page 590
Anatomy of an Ontology......Page 591
Ontology Languages......Page 592
Ontologies and Natural Language......Page 595
24.3 Ontology Engineering......Page 596
Methodologies......Page 597
24.4 Ontology Learning......Page 603
State of the Art......Page 604
Acknowledgments......Page 607
References......Page 608
25.1 Introduction......Page 616
Biological/Genomic NLP......Page 617
Model Organism Databases, and the Database Curator as a Canonical User......Page 618
BioNLP in the Context of Natural Language Processing and Computational Linguistics......Page 619
25.3 Just Enough Biology......Page 620
Named Entity Recognition......Page 621
Named Entity Normalization......Page 623
Abbreviation Disambiguation......Page 625
Named Entity Recognition 2: Collier, Nobata, and GENIA......Page 626
Corpora 1: PubMed/MEDLINE......Page 627
Lexical Resources 1: The Gene Ontology......Page 628
Tokenization......Page 629
Full Parsers......Page 630
User Interface Design......Page 631
The Difference between an Application That Will Relieve Pain and Suffering and an Application That Will Get You Published at ACL......Page 632
References......Page 633
26. Sentiment Analysis and Subjectivity......Page 637
26.1 The Problem of Sentiment Analysis......Page 639
Document-Level Sentiment Classification......Page 647
Sentence-Level Subjectivity and Sentiment Classification......Page 650
Opinion Lexicon Generation......Page 651
Feature Extraction......Page 654
Opinion Orientation Identification......Page 658
Basic Rules of Opinions......Page 659
Problem Definition......Page 660
Comparative Sentence Identification......Page 662
Preferred Object Identification......Page 663
26.5 Opinion Search and Retrieval......Page 664
26.6 Opinion Spam and Utility of Opinions......Page 666
Opinion Spam......Page 667
26.7 Conclusions......Page 670
References......Page 671