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
· · · · · · (
收起)
