计算机科学与语音和语言处理,语音与语言处理:自然语言处理、计算语言学和语音识别导论:第2版:英文(全面系统地介绍了计算机自然语言处理)...

Summary of Contents

Foreword 23

Preface 25

About the Authors 31

1 Introduction 35

I Words

2 Regular Expressions and Automata 51

3 Words and Transducers 　　 79

4 N-Grams 117

5 Part-of-Speech Tagging 　　 157

6 Hidden Markov and Maximum Entropy Models 207

7 Phonetics 249

8 Speech Synthesis 283

9 Automatic Speech Recognition 319

10 Speech Recognition: Advanced Topics 369

11 Computational Phonology 　　 395

12 Formal Grammars of English 　 419

13 Syntactic Parsing 461

14 Statistical Parsing 493

15 Features and Uni?cation 　　 523

16 Language and Complexity 　　 563

IV Semantics and Pragmatics

17 The Representation ofMeaning　 579

18 Computational Semantics 　　 617

19 Lexical Semantics　 645

20 Computational Lexical Semantics　 671

21 Computational Discourse 　　 715

V Applications

22 Information Extraction 　　 759

23 Question Answering and Summarization 799

24 Dialogue and Conversational Agents 847

25 Machine Translation 　　 895

Bibliography 945

Author Index 995

Subject Index 1007

Contents

Foreword 23

Preface 25

About the Authors 31

1 Introduction 35

1.1 Knowledge in Speech and Language Processing 　 36

1.2 Ambiguity 38

1.3 Models andAlgorithms 39

1.4 Language, Thought, and Understanding 　　 40

1.5 TheState of theArt 42

1.6 SomeBriefHistory 43

1.6.1 Foundational Insights: 1940s and 1950s 　 43

1.6.2 The Two Camps: 1957–1970 　　 44

1.6.3 Four Paradigms: 1970–1983 　　 45

1.6.4 Empiricism and Finite-State Models Redux: 1983–1993 　 46

1.6.5 The Field Comes Together: 1994–1999　 46

1.6.6 The Rise of Machine Learning: 2000–2008 　 46

1.6.7 On Multiple Discoveries 　 47

1.6.8 A Final Brief Note on Psychology 　　 48

1.7 Summary 　 48

Bibliographical and Historical Notes 　 49

I Words

2 Regular Expressions and Automata　 51

2.1 RegularExpressions 　 51

2.1.1 Basic Regular Expression Patterns 　　 52

2.1.2 Disjunction, Grouping, and Precedence　 55

2.1.3 ASimpleExample　 56

2.1.4 A More Complex Example　 57

2.1.5 AdvancedOperators 　 58

2.1.6 Regular Expression Substitution, Memory, and ELIZA 　 59

2.2 Finite-StateAutomata 　 60

2.2.1 Use of an FSA to Recognize Sheeptalk 　 61

2.2.2 Formal Languages　 64

2.2.3 Another Example 　 65

2.2.4 Non-Deterministic FSAs . 66

2.2.5 Use of an NFSA to Accept Strings 　 67

2.2.6 Recognition as Search 69

2.2.7 Relation of Deterministic and Non-Deterministic Automata 　 72

Foreword 　 23

Preface 　 25

About the Authors　 31

1 Introduction 　 35

1.1 Knowledge in Speech and Language Processing　 36

1.2 Ambiguity 　 38

1.3 Models andAlgorithms 　 39

1.4 Language, Thought, and Understanding 　　　40

1.5 TheState of theArt . 42

1.6 SomeBriefHistory . 43

1.6.1 Foundational Insights: 1940s and 1950s 43

1.6.2 The Two Camps: 1957–1970 　　 44

1.6.3 Four Paradigms: 1970–1983 　　 45

1.6.4 Empiricism and Finite-State Models Redux: 1983–1993 46

1.6.5 The Field Comes Together: 1994–1999 46

1.6.6 The Rise of Machine Learning: 2000–2008 46

1.6.7 On Multiple Discoveries 47

1.6.8 A Final Brief Note on Psychology 　　 48

1.7 Summary 　 48

Bibliographical and Historical Notes 49

I Words

2 Regular Expressions and Automata 51

2.1 RegularExpressions 51

2.1.1 Basic Regular Expression Patterns 　　 52

2.1.2 Disjunction, Grouping, and Precedence　 55

2.1.3 ASimpleExample　 56

2.1.4 A More Complex Example 　 57

2.1.5 AdvancedOperators 　 58

2.1.6 Regular Expression Substitution, Memory, and ELIZA　 59

2.2 Finite-StateAutomata　 60

2.2.1 Use of an FSA to Recognize Sheeptalk　 61

2.2.2 Formal Languages　 64

2.2.3 Another Example 　 65

2.2.4 Non-Deterministic FSAs 　 66

2.2.5 Use of an NFSA to Accept Strings 　　 67

2.2.6 Recognition as Search　 69

2.2.7 Relation of Deterministic and Non-Deterministic Automata　 72

2.3 Regular Languages and FSAs　 72

2.4 Summary 　 75

Bibliographical and Historical Notes 76

Exercises 76

3 Words and Transducers 79

3.1 Survey of (Mostly) English Morphology 　 81

3.1.1 In?ectional Morphology 　 82

3.1.2 Derivational Morphology　 84

3.1.3 Cliticization 　 85

3.1.4 Non-Concatenative Morphology 　　 85

3.1.5 Agreement 　 86

3.2 Finite-State Morphological Parsing　 86

3.3 Construction of a Finite-State Lexicon 　　 88

3.4 Finite-StateTransducers 　 91

3.4.1 Sequential Transducers and Determinism 　 93

3.5 FSTs for Morphological Parsing 　 94

3.6 Transducers and Orthographic Rules 　　 96

3.7 The Combination of an FST Lexicon and Rules 　 99

3.8 Lexicon-Free FSTs: The Porter Stemmer 　　 102

3.9 Word and Sentence Tokenization　 102

3.9.1 Segmentation in Chinese　 104

3.10 Detection and Correction of Spelling Errors 　 106

3.11 MinimumEditDistance 　 107

3.12 Human Morphological Processing 　 111

3.13 Summary 　 113

Bibliographical and Historical Notes 　 114

Exercises 115

4 N-Grams 　 117

4.1 WordCounting inCorpora　 119

4.2 Simple (Unsmoothed) N-Grams　 120

4.3 Training andTestSets 　 125

4.3.1 N-Gram Sensitivity to the Training Corpus　 126

4.3.2 Unknown Words: Open Versus Closed Vocabulary Tasks 　 129

4.4 Evaluating N-Grams: Perplexity 　 129

4.5 Smoothing 　 131

4.5.1 LaplaceSmoothing 　 132

4.5.2 Good-Turing Discounting　 135

4.5.3 Some Advanced Issues in Good-Turing Estimation 　 136

4.6 Interpolation 　 138

4.7 Backoff 　 139

4.7.1 Advanced: Details of Computing Katz Backoff α and P 141

4.8 Practical Issues: Toolkits and Data Formats 　　 142

4.9 Advanced Issues in Language Modeling 　　 143

4.9.1 Advanced Smoothing Methods: Kneser-Ney Smoothing 　 143

4.9.2 Class-Based N-Grams　 145

4.9.3 Language Model Adaptation and Web Use　 146

4.9.4 Using Longer-Distance Information: A Brief Summary 　 146

4.10 Advanced: Information Theory Background 　　148

4.10.1 Cross-Entropy for Comparing Models 　　 150

4.11 Advanced: The Entropy of English and Entropy Rate Constancy 152

4.12 Summary 　 153

Bibliographical and Historical Notes 154

Exercises 155

5 Part-of-Speech Tagging 　 157

5.1 (Mostly) English Word Classes　 158

5.2 Tagsets forEnglish 　 164

5.3 Part-of-Speech Tagging 　 167

5.4 Rule-Based Part-of-Speech Tagging 　169

5.5 HMM Part-of-Speech Tagging　 173

5.5.1 Computing the Most Likely Tag Sequence: An Example　 176

5.5.2 Formalizing Hidden Markov Model Taggers　 178

5.5.3 Using the Viterbi Algorithm for HMM Tagging 　 179

5.5.4 Extending the HMM Algorithm to Trigrams 　 183

5.6 Transformation-Based Tagging 　 185

5.6.1 How TBL Rules Are Applied 　　 186

5.6.2 How TBL Rules Are Learned 　　 186

5.7 Evaluation and Error Analysis 　 187

5.7.1 ErrorAnalysis　 190

5.8 Advanced Issues in Part-of-Speech Tagging 　　 191

5.8.1 Practical Issues: Tag Indeterminacy and Tokenization 　 191

5.8.2 Unknown Words . 192

5.8.3 Part-of-Speech Tagging for Other Languages　 194

5.8.4 Tagger Combination 197

5.9 Advanced: The Noisy Channel Model for Spelling 　 197

5.9.1 Contextual Spelling Error Correction 　　 201

5.10 Summary 　 202

Bibliographical and Historical Notes 203

Exercises 205

6 Hidden Markov and Maximum Entropy Models 207

6.1 MarkovChains 　 208

6.2 TheHiddenMarkovModel 　 210

6.3 Likelihood Computation: The Forward Algorithm 　 213

6.4 Decoding: The Viterbi Algorithm　 218

6.5 HMM Training: The Forward-Backward Algorithm 　 220

6.6 Maximum Entropy Models: Background 　 227

6.6.1 LinearRegression 　 228

6.6.2 Logistic Regression 231

6.6.3 Logistic Regression: Classi?cation 　　233

6.6.4 Advanced: Learning in Logistic Regression 　 234

6.7 Maximum Entropy Modeling 　 235

6.7.1 Why We Call It Maximum Entropy 　　 239

6.8 Maximum Entropy Markov Models 241

6.8.1 Decoding and Learning in MEMMs 　　 244

6.9 Summary 　 245

Bibliographical and Historical Notes 246

Exercises 247

II Speech

7 Phonetics 　 249

7.1 Speech Sounds and Phonetic Transcription　 250

7.2 Articulatory Phonetics 　 251

7.2.1 TheVocalOrgans 　 252

7.2.2 Consonants: Place of Articulation 　　254

7.2.3 Consonants: Manner of Articulation 　　 255

7.2.4 Vowels 256

7.2.5 Syllables 257

7.3 Phonological Categories and Pronunciation Variation 259

7.3.1 Phonetic Features . 261

7.3.2 Predicting Phonetic Variation 　　 . 262

7.3.3 Factors In?uencing Phonetic Variation 　　 263

7.4 Acoustic Phonetics and Signals 264

7.4.1 Waves 　 264

7.4.2 Speech Sound Waves 　 265

7.4.3 Frequency and Amplitude; Pitch and Loudness 　 267

7.4.4 Interpretation of Phones from a Waveform　 270

7.4.5 Spectra and the Frequency Domain 　 270

7.4.6 The Source-Filter Model 　　274

7.5 Phonetic Resources 　 275

7.6 Advanced: Articulatory and Gestural Phonology 　 278

7.7 Summary 　 279

Bibliographical and Historical Notes　 280

Exercises 　 281

8 Speech Synthesis 　283

8.1 TextNormalization 　 285

8.1.1 Sentence Tokenization 　 285

8.1.2 Non-Standard Words 　 286

8.1.3 Homograph Disambiguation 　　290

8.2 Phonetic Analysis 　 291

8.2.1 Dictionary Lookup 　 291

8.2.2 Names 　 292

8.2.3 Grapheme-to-Phoneme Conversion 　　 293

8.3 ProsodicAnalysis 　 296

8.3.1 ProsodicStructure　 296

8.3.2 Prosodic Prominence 　 297

8.3.3 Tune 　 299

8.3.4 More Sophisticated Models: ToBI 　 300

8.3.5 Computing Duration from Prosodic Labels 　302

8.3.6 Computing F0 from Prosodic Labels 　　303

8.3.7 Final Result of Text Analysis: Internal Representation　 305

8.4 Diphone Waveform Synthesis 　 306

8.4.1 Steps for Building a Diphone Database 306

8.4.2 Diphone Concatenation and TD-PSOLA for Prosody 　308

8.5 Unit Selection (Waveform) Synthesis　 310

8.6 Evaluation 　 314

Bibliographical and Historical Notes 　 315

Exercises 　 318

9 Automatic Speech Recognition 　　319

9.1 Speech Recognition Architecture 　 321

9.2 The Hidden Markov Model Applied to Speech 　 325

9.3 Feature Extraction: MFCC Vectors　 329

9.3.1 Preemphasis　 330

9.3.2 Windowing 　 330

9.3.3 Discrete Fourier Transform 　 332

9.3.4 Mel Filter Bank and Log 　 333

9.3.5 The Cepstrum: Inverse Discrete Fourier Transform　 334

9.3.6 Deltas andEnergy　 336

9.3.7 Summary:MFCC 　 336

9.4 Acoustic Likelihood Computation　 337

9.4.1 Vector Quantization 　 337

9.4.2 GaussianPDFs 　 340

9.4.3 Probabilities, Log-Probabilities, and Distance Functions　 347

9.5 The Lexicon and Language Model 　 348

9.6 Search andDecoding 　 348

9.7 EmbeddedTraining 　 358

9.8 Evaluation: Word Error Rate 362

9.9 Summary 　 364

Bibliographical and Historical Notes 　 365

Exercises 　 367

10 Speech Recognition: Advanced Topics　 369

10.1 Multipass Decoding: N-Best Lists and Lattices 　　 369

10.2 A? (“Stack”)Decoding　 375

10.3 Context-Dependent Acoustic Models: Triphones 　 379

10.4 DiscriminativeTraining　 383

10.4.1 Maximum Mutual Information Estimation　 384

10.4.2 Acoustic Models Based on Posterior Classi?ers 385

10.5 ModelingVariation 　 386

10.5.1 Environmental Variation and Noise 　　386

10.5.2 Speaker Variation and Speaker Adaptation 　 387

10.5.3 Pronunciation Modeling: Variation Due to Genre 388

10.6 Metadata: Boundaries, Punctuation, and Dis?uencies 　 390

10.7 Speech Recognition by Humans　 392

10.8 Summary 　 393

Bibliographical and Historical Notes 　 393

Exercises 　 394

11 Computational Phonology 　 395

11.1 Finite-State Phonology 　 395

11.2 Advanced Finite-State Phonology 　 399

11.2.1 Harmony 　 399

11.2.2 Templatic Morphology　 400

11.3 Computational Optimality Theory 　 401

11.3.1 Finite-State Transducer Models of Optimality Theory 　 403

11.3.2 Stochastic Models of Optimality Theory　 404

11.4 Syllabi?cation 　 406

11.5 Learning Phonology and Morphology 　 409

11.5.1 Learning Phonological Rules 　 409

11.5.2 Learning Morphology 411

11.5.3 Learning in Optimality Theory 　　414

11.6 Summary 415

Bibliographical and Historical Notes 　 415

Exercises 417

III Syntax

12 Formal Grammars of English 419

12.1 Constituency 420

12.2 Context-FreeGrammars 421

12.2.1 Formal De?nition of Context-Free Grammar 425

12.3 Some Grammar Rules for English 　 426

12.3.1 Sentence-Level Constructions 　　426

12.3.2 Clauses and Sentences 　 428

12.3.3 The Noun Phrase　 428

12.3.4 Agreement 　 432

12.3.5 The Verb Phrase and Subcategorization　 434

12.3.6 Auxiliaries 　 436

12.3.7 Coordination　 437

12.4 Treebanks 438

12.4.1 Example: The Penn Treebank Project 　　 438

12.4.2 Treebanks as Grammars 　 440

12.4.3 Treebank Searching　 442

12.4.4 Heads and Head Finding 　443

12.5 Grammar Equivalence and Normal Form　 446

12.6 Finite-State and Context-Free Grammars 　 447

12.7 DependencyGrammars 448

12.7.1 The Relationship Between Dependencies and Heads 449

12.7.2 Categorial Grammar 451

12.8 Spoken Language Syntax 　 451

12.8.1 Dis?uencies andRepair 　 452

12.8.2 Treebanks for Spoken Language 　　453

12.9 Grammars and Human Processing 　 454

12.10 Summary 455

Bibliographical and Historical Notes 　456

Exercises 　 458

13 Syntactic Parsing 　 461

13.1 Parsing asSearch 　 462

13.1.1 Top-DownParsing 　 463

13.1.2 Bottom-UpParsing　 464

13.1.3 Comparing Top-Down and Bottom-Up Parsing 465

13.2 Ambiguity 466

13.3 Search in the Face of Ambiguity . 468

13.4 Dynamic Programming Parsing Methods 　　 469

13.4.1 CKYParsing 470

13.4.2 The Earley Algorithm 477

13.4.3 ChartParsing 482

13.5 PartialParsing . 484

13.5.1 Finite-State Rule-Based Chunking 　　 486

13.5.2 Machine Learning-Based Approaches to Chunking 486

13.5.3 Chunking-System Evaluations 　　 . 489

13.6 Summary 　490

Bibliographical and Historical Notes 　 491

Exercises 　 492

14 Statistical Parsing 　　493

14.1 Probabilistic Context-Free Grammars 　 494

14.1.1 PCFGs for Disambiguation 　 495

14.1.2 PCFGs for Language Modeling 　 497

14.2 Probabilistic CKY Parsing of PCFGs 　 498

14.3 Ways to Learn PCFG Rule Probabilities 　 501

14.4 ProblemswithPCFGs 　502

14.4.1 Independence Assumptions Miss Structural Dependencies BetweenRules　 502

14.4.2 Lack of Sensitivity to Lexical Dependencies　 503

14.5 Improving PCFGs by Splitting Non-Terminals 　 505

14.6 Probabilistic Lexicalized CFGs 　507

14.6.1 The Collins Parser 　509

14.6.2 Advanced: Further Details of the Collins Parser 　 511

14.7 EvaluatingParsers 　513

14.8 Advanced: Discriminative Reranking 　 515

14.9 Advanced: Parser-Based Language Modeling 　　 516

14.10 HumanParsing 　517

14.11 Summary 　519

Bibliographical and Historical Notes 　 520

Exercises 522

15 Features and Uni?cation　 523

15.1 FeatureStructures 　524

15.2 Uni?cation of Feature Structures 　 526

15.3 Feature Structures in the Grammar 　531

15.3.1 Agreement 　532

15.3.2 HeadFeatures 　534

15.3.3 Subcategorization 　535

15.3.4 Long-Distance Dependencies 　　 540

15.4 Implementation of Uni?cation　 541

15.4.1 Uni?cation Data Structures 　 541

15.4.2 The Uni?cationAlgorithm 　 543

15.5 Parsing with Uni?cation Constraints 　 547

15.5.1 Integration of Uni?cation into an Earley Parser 　548

15.5.2 Uni?cation-Based Parsing 　 553

15.6 Types and Inheritance 　 555

15.6.1 Advanced: Extensions to Typing 　 558

15.6.2 Other Extensions to Uni?cation 　 559

15.7 Summary 　 559

Bibliographical and Historical Notes　 560

Exercises 561

16 Language and Complexity 　 563

16.1 TheChomskyHierarchy 　 564

16.2 Ways to Tell if a Language Isn’t Regular 　　 566

16.2.1 The Pumping Lemma 567

16.2.2 Proofs that Various Natural Languages Are Not Regular　 569

16.3 Is Natural Language Context Free?　 571

16.4 Complexity and Human Processing 　 573

16.5 Summary 576

Bibliographical and Historical Notes 577

Exercises 578

17 The Representation of Meaning 579

17.1 Computational Desiderata for Representations 　 581

17.1.1 Veri?ability 581

17.1.2 Unambiguous Representations 　582

17.1.3 Canonical Form 　 583

17.1.4 Inference and Variables　 584

17.1.5 Expressiveness 　585

17.2 Model-Theoretic Semantics　 586

17.3 First-OrderLogic 　 589

17.3.1 Basic Elements of First-Order Logic 　　 589

17.3.2 Variables and Quanti?ers . 591

17.3.3 LambdaNotation . 593

17.3.4 The Semantics of First-Order Logic 　594

17.3.5 Inference 　 595

17.4 Event and State Representations　 597

17.4.1 RepresentingTime　 600

17.4.2 Aspect 　 603

17.5 DescriptionLogics 　 606

17.6 Embodied and Situated Approaches to Meaning 　 612

17.7 Summary 　 614

Bibliographical and Historical Notes 　 614

Exercises 616

18 Computational Semantics　 617

18.1 Syntax-Driven Semantic Analysis 　 617

18.2 Semantic Augmentations to Syntactic Rules 　 619

18.3 Quanti?er Scope Ambiguity and Underspeci?cation 　 626

18.3.1 Store and Retrieve Approaches 　　 626

18.3.2 Constraint-Based Approaches 　　 629

18.4 Uni?cation-Based Approaches to Semantic Analysis 　 632

18.5 Integration of Semantics into the Earley Parser 　 638

18.6 Idioms and Compositionality 　 639

18.7 Summary 　 641

Bibliographical and Historical Notes　 641

Exercises 　 643

19 Lexical Semantics 　645

19.1 WordSenses 　 646

19.2 Relations Between Senses 　 649

19.2.1 Synonymy and Antonymy 　 649

19.2.2 Hyponymy 　 650

19.2.3 SemanticFields 　 651

19.3 WordNet: A Database of Lexical Relations 　　 651

19.4 EventParticipants　 653

19.4.1 ThematicRoles 　 654

19.4.2 Diathesis Alternations 　656

19.4.3 Problems with Thematic Roles 　　 657

19.4.4 The Proposition Bank　 658

19.4.5 FrameNet 　 659

19.4.6 Selectional Restrictions 　 661

19.5 Primitive Decomposition 　 663

19.6 Advanced: Metaphor 665

19.7 Summary 　 666

Bibliographical and Historical Notes 　 667

Exercises 　 668

20 Computational Lexical Semantics 　 671

20.1 Word Sense Disambiguation: Overview 　　 672

20.2 Supervised Word Sense Disambiguation 　　 673

20.2.1 Feature Extraction for Supervised Learning　 674

20.2.2 Naive Bayes and Decision List Classi?ers 　 675

20.3 WSD Evaluation, Baselines, and Ceilings 　 678

20.4 WSD: Dictionary and Thesaurus Methods 　　680

20.4.1 The Lesk Algorithm 　 680

20.4.2 Selectional Restrictions and Selectional Preferences 　 682

20.5 Minimally Supervised WSD: Bootstrapping 　　 684

20.6 Word Similarity: Thesaurus Methods 　　 686

20.7 Word Similarity: Distributional Methods 　　 692

20.7.1 De?ning a Word’s Co-Occurrence Vectors 　 693

20.7.2 Measuring Association with Context 　　695

20.7.3 De?ning Similarity Between Two Vectors　 697

20.7.4 Evaluating Distributional Word Similarity 　 701

20.8 Hyponymy and Other Word Relations 　 701

20.9 SemanticRoleLabeling 　 704

20.10 Advanced: Unsupervised Sense Disambiguation　 708

20.11 Summary 709

Bibliographical and Historical Notes 710

Exercises 713

21 Computational Discourse　 715

21.1 DiscourseSegmentation　 718

21.1.1 Unsupervised Discourse Segmentation 　718

21.1.2 Supervised Discourse Segmentation 　　720

21.1.3 Discourse Segmentation Evaluation 　 722

21.2 TextCoherence　 723

21.2.1 Rhetorical Structure Theory 　 724

21.2.2 Automatic Coherence Assignment 　 726

21.3 ReferenceResolution 　 729

21.4 ReferencePhenomena 　 732

21.4.1 Five Types of Referring Expressions 　　 732

21.4.2 Information Status 　 734

21.5 Features for Pronominal Anaphora Resolution 　　 735

21.5.1 Features for Filtering Potential Referents　 735

21.5.2 Preferences in Pronoun Interpretation 　 736

21.6 Three Algorithms for Anaphora Resolution 　 738

21.6.1 Pronominal Anaphora Baseline: The Hobbs Algorithm 　 738

21.6.2 A Centering Algorithm for Anaphora Resolution 　 740

21.6.3 A Log-Linear Model for Pronominal Anaphora Resolution 　 742

21.6.4 Features for Pronominal Anaphora Resolution 　743

21.7 Coreference Resolution 　 744

21.8 Evaluation of Coreference Resolution 　 746

21.9 Advanced: Inference-Based Coherence Resolution 　 747

21.10 Psycholinguistic Studies of Reference 　 752

21.11 Summary 　753

Bibliographical and Historical Notes 　 754

Exercises　 756

V Applications

22 Information Extraction 　 759

22.1 Named Entity Recognition 　 761

22.1.1 Ambiguity in Named Entity Recognition 　 763

22.1.2 NER as Sequence Labeling 　 763

22.1.3 Evaluation of Named Entity Recognition　 766

22.1.4 Practical NER Architectures 　　 768

22.2 Relation Detection and Classi?cation 　　 768

22.2.1 Supervised Learning Approaches to Relation Analysis 769

22.2.2 Lightly Supervised Approaches to Relation Analysis . 772

22.2.3 Evaluation of Relation Analysis Systems . 776

22.3 Temporal and Event Processing 777

22.3.1 Temporal Expression Recognition 　　 777

22.3.2 Temporal Normalization 　 780

22.3.3 Event Detection and Analysis 　　 783

22.3.4 TimeBank 　784

22.4 Template Filling 　786

22.4.1 Statistical Approaches to Template-Filling 　 786

22.4.2 Finite-State Template-Filling Systems 　　 788

22.5 Advanced: Biomedical Information Extraction 　　 791

22.5.1 Biological Named Entity Recognition 　　 792

22.5.2 Gene Normalization　 793

22.5.3 Biological Roles and Relations 　 794

22.6 Summary 　 796

Bibliographical and Historical Notes　 796

Exercises 　 797

23 Question Answering and Summarization　 799

23.1 InformationRetrieval 　 801

23.1.1 The Vector Space Model 　 802

23.1.2 TermWeighting 　 804

23.1.3 Term Selection and Creation 　 806

23.1.4 Evaluation of Information-Retrieval Systems 806

23.1.5 Homonymy, Polysemy, and Synonymy 　 810

23.1.6 Ways to Improve User Queries 　　810

23.2 Factoid Question Answering　 812

23.2.1 Question Processing 　 813

23.2.2 PassageRetrieval　 815

23.2.3 AnswerProcessing　 817

23.2.4 Evaluation of Factoid Answers 　　 821

23.3 Summarization 　 821

23.4 Single-Document Summarization 　 824

23.4.1 Unsupervised Content Selection 　　 824

23.4.2 Unsupervised Summarization Based on Rhetorical Parsing 　 826

23.4.3 Supervised Content Selection 　　 828

23.4.4 Sentence Simpli?cation 　 829

23.5 Multi-Document Summarization　 830

23.5.1 Content Selection in Multi-Document Summarization　 831

23.5.2 Information Ordering in Multi-Document Summarization 　 832

23.6 Focused Summarization and Question Answering 　 835

23.7 Summarization Evaluation 　 839

23.8 Summary 　 841

Bibliographical and Historical Notes 　 842

Exercises 844

24 Dialogue and Conversational Agents 　847

24.1 Properties of Human Conversations 　849

24.1.1 Turns and Turn-Taking 　849

24.1.2 Language as Action: Speech Acts 　　 851

24.1.3 Language as Joint Action: Grounding 　 852

24.1.4 Conversational Structure 　 854

24.1.5 Conversational Implicature　 855

24.2 Basic Dialogue Systems 　 857

24.2.1 ASR Component　 857

24.2.2 NLU Component 　 858

24.2.3 Generation and TTS Components 　 861

24.2.4 Dialogue Manager 　 863

24.2.5 Dealing with Errors: Con?rmation and Rejection 867

24.3 VoiceXML 868

24.4 Dialogue System Design and Evaluation 　　 872

24.4.1 Designing Dialogue Systems 　　 872

24.4.2 Evaluating Dialogue Systems 　 872

24.5 Information-State and Dialogue Acts 　 874

24.5.1 Using Dialogue Acts 　 876

24.5.2 Interpreting Dialogue Acts　 877

24.5.3 Detecting Correction Acts　 880

24.5.4 Generating Dialogue Acts: Con?rmation and Rejection 　881

24.6 Markov Decision Process Architecture 　　 882

24.7 Advanced: Plan-Based Dialogue Agents 　　 886

24.7.1 Plan-Inferential Interpretation and Production　 887

24.7.2 The Intentional Structure of Dialogue 　 889

24.8 Summary 　891

Bibliographical and Historical Notes 　 892

Exercises 　 894

25 Machine Translation　 895

25.1 Why Machine Translation Is Hard 　 898

25.1.1 Typology 　 898

25.1.2 Other Structural Divergences 　　 900

25.1.3 LexicalDivergences 　 901

25.2 Classical MT and the Vauquois Triangle 903

25.2.1 Direct Translation 　 904

25.2.2 Transfer 　 906

25.2.3 Combined Direct and Transfer Approaches in Classic MT　 908

25.2.4 The Interlingua Idea: Using Meaning 　　 909

25.3 StatisticalMT 　 910

25.4 P(F E): The Phrase-Based Translation Model　　 913

25.5 Alignment inMT 　 915

25.5.1 IBMModel 1 　 916

25.5.2 HMMAlignment 　　919

25.6 Training Alignment Models　 921

25.6.1 EM for Training Alignment Models 　　922

25.7 Symmetrizing Alignments for Phrase-Based MT　 924

25.8 Decoding for Phrase-Based Statistical MT 　　 926

25.9 MTEvaluation 　 930

25.9.1 Using Human Raters 　 930

25.9.2 Automatic Evaluation: BLEU 　　 931

25.10 Advanced: Syntactic Models for MT 　　 934

25.11 Advanced: IBM Model 3 and Fertility 　　935

25.11.1 Training forModel 3 　939

25.12 Advanced: Log-Linear Models for MT 　　 939

25.13 Summary 　940

Bibliographical and Historical Notes 　 941

Exercises 943

Bibliography 　 945

Author Index　 995

Subject Index 　 1007