Speech and Language Processing

speech and language processing mechanisms in verbal serial recall and speech and language processing problems. speech and language processing for assistive technologies
RyanCanon Profile Pic
RyanCanon,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
Speech and Language ProcessingPRENTICE HALL SERIES IN ARTIFICIAL INTELLIGENCE A AI I Stuart Russell and Peter Norvig, Editors GRAHAM ANSI Common Lisp MUGGLETON Logical Foundations of Machine Learning RUSSELL & NORVIG Artificial Intelligence: A Modern Approach JURAFSKY & MARTIN Speech and Language ProcessingSpeech and Language Processing An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition Daniel Jurafsky and James H. Martin Draft of September 28, 1999. Do not cite without permission. Contributing writers: Andrew Kehler, Keith Vander Linden, Nigel Ward Prentice Hall, Englewood Cliffs, New Jersey 07632Library of Congress Cataloging-in-Publication Data Jurafsky, Daniel S. (Daniel Saul) Speech and Langauge Processing / Daniel Jurafsky, James H. Martin. p. cm. Includes bibliographical references and index. ISBN Publisher: Alan Apt c 2000 by Prentice-Hall, Inc. A Simon & Schuster Company Englewood Cliffs, New Jersey 07632 The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs. All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 Prentice-Hall International (UK) Limited, London Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall Canada, Inc., Toronto Prentice-Hall Hispanoamericana, S.A., Mexico Prentice-Hall of India Private Limited, New Delhi Prentice-Hall of Japan, Inc., Tokyo Simon & Schuster Asia Pte. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de JaneiroFor my parents — D.J. For Linda — J.M.Summary of Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 I Words 19 2 Regular Expressions and Automata. . . . . . . . . . . . . . . . . . . . . . 21 3 Morphology and Finite-State Transducers . . . . . . . . . . . . . . . 57 4 Computational Phonology and Text-to-Speech . . . . . . . . . . . 91 5 Probabilistic Models of Pronunciation and Spelling . . . . . . 139 6 N-grams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7 HMMs and Speech Recognition . . . . . . . . . . . . . . . . . . . . . . . . . 233 II Syntax 283 8 Word Classes and Part-of-Speech Tagging . . . . . . . . . . . . . . . 285 9 Context-Free Grammars for English . . . . . . . . . . . . . . . . . . . . 319 10 Parsing with Context-Free Grammars . . . . . . . . . . . . . . . . . . . 353 11 Features and Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 12 Lexicalized and Probabilistic Parsing . . . . . . . . . . . . . . . . . . . . 443 13 Language and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 III Semantics 495 14 Representing Meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 15 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 16 Lexical Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 17 Word Sense Disambiguation and Information Retrieval . . 627 IV Pragmatics 661 18 Discourse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 19 Dialogue and Conversational Agents. . . . . . . . . . . . . . . . . . . . . 715 20 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759 21 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797 A Regular Expression Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 829 B The Porter Stemming Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 831 C C5 and C7 tagsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835 D Training HMMs: The Forward-Backward Algorithm . . . . 841 Bibliography 851 Index 923 viiContents 1 Introduction 1 1.1 Knowledge in Speech and Language Processing . . . . . . 2 1.2 Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Models and Algorithms . . . . . . . . . . . . . . . . . . . 5 1.4 Language, Thought, and Understanding . . . . . . . . . . . 6 1.5 The State of the Art and The Near-Term Future . . . . . . . 9 1.6 Some Brief History . . . . . . . . . . . . . . . . . . . . . 10 Foundational Insights: 1940’s and 1950’s . . . . . . . . . . 10 The Two Camps: 1957–1970 . . . . . . . . . . . . . . . . 11 Four Paradigms: 1970–1983 . . . . . . . . . . . . . . . . . 13 Empiricism and Finite State Models Redux: 1983-1993 . . 14 The Field Comes Together: 1994-1999 . . . . . . . . . . . 14 A Final Brief Note on Psychology . . . . . . . . . . . . . . 15 1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 16 I Words 19 2 Regular Expressions and Automata 21 2.1 Regular Expressions . . . . . . . . . . . . . . . . . . . . . 22 Basic Regular Expression Patterns . . . . . . . . . . . . . 23 Disjunction, Grouping, and Precedence . . . . . . . . . . . 27 A simple example . . . . . . . . . . . . . . . . . . . . . . 28 A More Complex Example . . . . . . . . . . . . . . . . . 29 Advanced Operators . . . . . . . . . . . . . . . . . . . . . 30 Regular Expression Substitution, Memory, and ELIZA . . . 31 2.2 Finite-State Automata . . . . . . . . . . . . . . . . . . . . 33 Using an FSA to Recognize Sheeptalk . . . . . . . . . . . 34 Formal Languages . . . . . . . . . . . . . . . . . . . . . . 38 Another Example . . . . . . . . . . . . . . . . . . . . . . 39 Nondeterministic FSAs . . . . . . . . . . . . . . . . . . . 40 Using an NFSA to accept strings . . . . . . . . . . . . . . 42 Recognition as Search . . . . . . . . . . . . . . . . . . . . 44 Relating Deterministic and Non-deterministic Automata . . 48 2.3 Regular Languages and FSAs . . . . . . . . . . . . . . . . 49 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 ixx Contents Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 52 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3 Morphology and Finite-State Transducers 57 3.1 Survey of (Mostly) English Morphology . . . . . . . . . . 59 Inflectional Morphology . . . . . . . . . . . . . . . . . . . 61 Derivational Morphology . . . . . . . . . . . . . . . . . . 63 3.2 Finite-State Morphological Parsing . . . . . . . . . . . . . 65 The Lexicon and Morphotactics . . . . . . . . . . . . . . . 66 Morphological Parsing with Finite-State Transducers . . . 71 Orthographic Rules and Finite-State Transducers . . . . . . 76 3.3 Combining FST Lexicon and Rules . . . . . . . . . . . . . 79 3.4 Lexicon-free FSTs: The Porter Stemmer . . . . . . . . . . 82 3.5 Human Morphological Processing . . . . . . . . . . . . . 84 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 87 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4 Computational Phonology and Text-to-Speech 91 4.1 Speech Sounds and Phonetic Transcription . . . . . . . . . 92 The Vocal Organs . . . . . . . . . . . . . . . . . . . . . . 94 Consonants: Place of Articulation . . . . . . . . . . . . . . 97 Consonants: Manner of Articulation . . . . . . . . . . . . 98 Vowels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.2 The Phoneme and Phonological Rules . . . . . . . . . . . 102 4.3 Phonological Rules and Transducers . . . . . . . . . . . . 104 4.4 Advanced Issues in Computational Phonology . . . . . . . 109 Harmony . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Templatic Morphology . . . . . . . . . . . . . . . . . . . 111 Optimality Theory . . . . . . . . . . . . . . . . . . . . . . 112 4.5 Machine Learning of Phonological Rules . . . . . . . . . . 117 4.6 Mapping Text to Phones for TTS . . . . . . . . . . . . . . 119 Pronunciation dictionaries . . . . . . . . . . . . . . . . . . 119 Beyond Dictionary Lookup: Text Analysis . . . . . . . . . 121 An FST-based pronunciation lexicon . . . . . . . . . . . . 124 4.7 Prosody in TTS . . . . . . . . . . . . . . . . . . . . . . . 129 Phonological Aspects of Prosody . . . . . . . . . . . . . . 129 Phonetic or Acoustic Aspects of Prosody . . . . . . . . . . 131 Prosody in Speech Synthesis . . . . . . . . . . . . . . . . 131Contents xi 4.8 Human Processing of Phonology and Morphology . . . . . 133 4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 135 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5 Probabilistic Models of Pronunciation and Spelling 139 5.1 Dealing with Spelling Errors . . . . . . . . . . . . . . . . 141 5.2 Spelling Error Patterns . . . . . . . . . . . . . . . . . . . . 142 5.3 Detecting Non-Word Errors . . . . . . . . . . . . . . . . . 144 5.4 Probabilistic Models . . . . . . . . . . . . . . . . . . . . . 144 5.5 Applying the Bayesian method to spelling . . . . . . . . . 147 5.6 Minimum Edit Distance . . . . . . . . . . . . . . . . . . . 151 5.7 English Pronunciation Variation . . . . . . . . . . . . . . . 154 5.8 The Bayesian method for pronunciation . . . . . . . . . . . 161 Decision Tree Models of Pronunciation Variation . . . . . 166 5.9 Weighted Automata . . . . . . . . . . . . . . . . . . . . . 167 Computing Likelihoods from Weighted Automata: The For- ward Algorithm . . . . . . . . . . . . . . . . . . . 169 Decoding: The Viterbi Algorithm . . . . . . . . . . . . . . 174 Weighted Automata and Segmentation . . . . . . . . . . . 178 5.10 Pronunciation in Humans . . . . . . . . . . . . . . . . . . 180 5.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 184 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6 N-grams 189 6.1 Counting Words in Corpora . . . . . . . . . . . . . . . . . 191 6.2 Simple (Unsmoothed) N-grams . . . . . . . . . . . . . . . 194 More on N-grams and their sensitivity to the training corpus 199 6.3 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Add-One Smoothing . . . . . . . . . . . . . . . . . . . . . 205 Witten-Bell Discounting . . . . . . . . . . . . . . . . . . . 208 Good-Turing Discounting . . . . . . . . . . . . . . . . . . 212 6.4 Backoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Combining Backoff with Discounting . . . . . . . . . . . . 215 6.5 Deleted Interpolation . . . . . . . . . . . . . . . . . . . . 217 6.6 N-grams for Spelling and Pronunciation . . . . . . . . . . 218 Context-Sensitive Spelling Error Correction . . . . . . . . 219 N-grams for Pronunciation Modeling . . . . . . . . . . . . 220xii Contents 6.7 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Cross Entropy for Comparing Models . . . . . . . . . . . . 224 The Entropy of English . . . . . . . . . . . . . . . . . . . 225 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 228 6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 7 HMMs and Speech Recognition 233 7.1 Speech Recognition Architecture . . . . . . . . . . . . . . 235 7.2 Overview of Hidden Markov Models . . . . . . . . . . . . 239 7.3 The Viterbi Algorithm Revisited . . . . . . . . . . . . . . 242 7.4 Advanced Methods for Decoding . . . . . . . . . . . . . . 250 A Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 252 7.5 Acoustic Processing of Speech . . . . . . . . . . . . . . . 258 Sound Waves . . . . . . . . . . . . . . . . . . . . . . . . . 258 How to Interpret a Waveform . . . . . . . . . . . . . . . . 259 Spectra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . 264 7.6 Computing Acoustic Probabilities . . . . . . . . . . . . . . 265 7.7 Training a Speech Recognizer . . . . . . . . . . . . . . . . 270 7.8 Waveform Generation for Speech Synthesis . . . . . . . . 272 Pitch and Duration Modification . . . . . . . . . . . . . . 273 Unit Selection . . . . . . . . . . . . . . . . . . . . . . . . 274 7.9 Human Speech Recognition . . . . . . . . . . . . . . . . . 275 7.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 278 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 II Syntax 283 8 Word Classes and Part-of-Speech Tagging 285 8.1 (Mostly) English Word Classes . . . . . . . . . . . . . . . 286 8.2 Tagsets for English . . . . . . . . . . . . . . . . . . . . . . 294 8.3 Part of Speech Tagging . . . . . . . . . . . . . . . . . . . 296 8.4 Rule-based Part-of-speech Tagging . . . . . . . . . . . . . 298 8.5 Stochastic Part-of-speech Tagging . . . . . . . . . . . . . . 300 A Motivating Example . . . . . . . . . . . . . . . . . . . . 301 The Actual Algorithm for HMM tagging . . . . . . . . . . 303 8.6 Transformation-Based Tagging . . . . . . . . . . . . . . . 304Contents xiii How TBL rules are applied . . . . . . . . . . . . . . . . . 306 How TBL Rules are Learned . . . . . . . . . . . . . . . . 307 8.7 Other Issues . . . . . . . . . . . . . . . . . . . . . . . . . 308 Multiple tags and multiple words . . . . . . . . . . . . . . 308 Unknown words . . . . . . . . . . . . . . . . . . . . . . . 310 Class-based N-grams . . . . . . . . . . . . . . . . . . . . 312 8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 315 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 9 Context-Free Grammars for English 319 9.1 Constituency . . . . . . . . . . . . . . . . . . . . . . . . . 321 9.2 Context-Free Rules and Trees . . . . . . . . . . . . . . . . 322 9.3 Sentence-Level Constructions . . . . . . . . . . . . . . . . 328 9.4 The Noun Phrase . . . . . . . . . . . . . . . . . . . . . . . 330 Before the Head Noun . . . . . . . . . . . . . . . . . . . . 331 After the Noun . . . . . . . . . . . . . . . . . . . . . . . . 333 9.5 Coordination . . . . . . . . . . . . . . . . . . . . . . . . . 335 9.6 Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 336 9.7 The Verb Phrase and Subcategorization . . . . . . . . . . . 337 9.8 Auxiliaries . . . . . . . . . . . . . . . . . . . . . . . . . . 340 9.9 Spoken Language Syntax . . . . . . . . . . . . . . . . . . 341 Disfluencies . . . . . . . . . . . . . . . . . . . . . . . . . 342 9.10 Grammar Equivalence & Normal Form . . . . . . . . . . . 343 9.11 Finite State & Context-Free Grammars . . . . . . . . . . . 344 9.12 Grammars & Human Processing . . . . . . . . . . . . . . 346 9.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 349 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 10 Parsing with Context-Free Grammars 353 10.1 Parsing as Search . . . . . . . . . . . . . . . . . . . . . . 355 Top-Down Parsing . . . . . . . . . . . . . . . . . . . . . 356 Bottom-Up Parsing . . . . . . . . . . . . . . . . . . . . . 357 Comparing Top-down and Bottom-up Parsing . . . . . . . 359 10.2 A Basic Top-down Parser . . . . . . . . . . . . . . . . . . 360 Adding Bottom-up Filtering . . . . . . . . . . . . . . . . . 365 10.3 Problems with the Basic Top-down Parser . . . . . . . . . 366 Left-Recursion . . . . . . . . . . . . . . . . . . . . . . . . 367xiv Contents Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . 368 Repeated Parsing of Subtrees . . . . . . . . . . . . . . . . 373 10.4 The Earley Algorithm . . . . . . . . . . . . . . . . . . . . 375 10.5 Finite-State Parsing Methods . . . . . . . . . . . . . . . . 383 10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 388 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 11 Features and Unification 391 11.1 Feature Structures . . . . . . . . . . . . . . . . . . . . . . 393 11.2 Unification of Feature Structures . . . . . . . . . . . . . . 396 11.3 Features Structures in the Grammar . . . . . . . . . . . . 401 Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 403 Head Features . . . . . . . . . . . . . . . . . . . . . . . . 406 Subcategorization . . . . . . . . . . . . . . . . . . . . . . 407 Long Distance Dependencies . . . . . . . . . . . . . . . . 413 11.4 Implementing Unification . . . . . . . . . . . . . . . . . . 414 Unification Data Structures . . . . . . . . . . . . . . . . . 415 The Unification Algorithm . . . . . . . . . . . . . . . . . 419 11.5 Parsing with Unification Constraints . . . . . . . . . . . . 423 Integrating Unification into an Earley Parser . . . . . . . . 424 Unification Parsing . . . . . . . . . . . . . . . . . . . . . 431 11.6 Types and Inheritance . . . . . . . . . . . . . . . . . . . . 433 Extensions to Typing . . . . . . . . . . . . . . . . . . . . 436 Other Extensions to Unification . . . . . . . . . . . . . . . 438 11.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 438 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 439 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 12 Lexicalized and Probabilistic Parsing 443 12.1 Probabilistic Context-Free Grammars . . . . . . . . . . . . 444 Probabilistic CYK Parsing of PCFGs . . . . . . . . . . . . 449 Learning PCFG probabilities . . . . . . . . . . . . . . . . 450 12.2 Problems with PCFGs . . . . . . . . . . . . . . . . . . . . 451 12.3 Probabilistic Lexicalized CFGs . . . . . . . . . . . . . . . 454 12.4 Dependency Grammars . . . . . . . . . . . . . . . . . . . 459 Categorial Grammar . . . . . . . . . . . . . . . . . . . . . 462 12.5 Human Parsing . . . . . . . . . . . . . . . . . . . . . . . . 463 12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 468Contents xv Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 470 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 13 Language and Complexity 473 13.1 The Chomsky Hierarchy . . . . . . . . . . . . . . . . . . . 474 13.2 How to tell if a language isn’t regular . . . . . . . . . . . . 477 The Pumping Lemma . . . . . . . . . . . . . . . . . . . . 478 Are English and other Natural Languges Regular Languages?481 13.3 Is Natural Language Context-Free? . . . . . . . . . . . . . 485 13.4 Complexity and Human Processing . . . . . . . . . . . . . 487 13.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 493 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 III Semantics 495 14 Representing Meaning 497 14.1 Computational Desiderata for Representations . . . . . . . 500 Verifiability . . . . . . . . . . . . . . . . . . . . . . . . . 500 Unambiguous Representations . . . . . . . . . . . . . . . 501 Canonical Form . . . . . . . . . . . . . . . . . . . . . . . 502 Inference and Variables . . . . . . . . . . . . . . . . . . . 504 Expressiveness . . . . . . . . . . . . . . . . . . . . . . . . 505 14.2 Meaning Structure of Language . . . . . . . . . . . . . . . 506 Predicate-Argument Structure . . . . . . . . . . . . . . . . 506 14.3 First Order Predicate Calculus . . . . . . . . . . . . . . . . 509 Elements of FOPC . . . . . . . . . . . . . . . . . . . . . . 509 The Semantics of FOPC . . . . . . . . . . . . . . . . . . . 512 Variables and Quantifiers . . . . . . . . . . . . . . . . . . 513 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 14.4 Some Linguistically Relevant Concepts . . . . . . . . . . . 518 Categories . . . . . . . . . . . . . . . . . . . . . . . . . . 518 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 Representing Time . . . . . . . . . . . . . . . . . . . . . . 523 Aspect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Representing Beliefs . . . . . . . . . . . . . . . . . . . . . 530 Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 14.5 Related Representational Approaches . . . . . . . . . . . . 534 14.6 Alternative Approaches to Meaning . . . . . . . . . . . . . 535xvi Contents Meaning as Action . . . . . . . . . . . . . . . . . . . . . . 535 Meaning as Truth . . . . . . . . . . . . . . . . . . . . . . 536 14.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 536 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 537 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 15 Semantic Analysis 543 15.1 Syntax-Driven Semantic Analysis . . . . . . . . . . . . . . 544 Semantic Augmentations to Context-Free Grammar Rules . 547 Quantifier Scoping and the Translation of Complex Terms . 555 15.2 Attachments for a Fragment of English . . . . . . . . . . . 556 Sentences . . . . . . . . . . . . . . . . . . . . . . . . . . 556 Noun Phrases . . . . . . . . . . . . . . . . . . . . . . . . 559 Verb Phrases . . . . . . . . . . . . . . . . . . . . . . . . . 562 Prepositional Phrases . . . . . . . . . . . . . . . . . . . . 565 15.3 Integrating Semantic Analysis into the Earley Parser . . . . 567 15.4 Idioms and Compositionality . . . . . . . . . . . . . . . . 569 15.5 Robust Semantic Analysis . . . . . . . . . . . . . . . . . . 571 Semantic Grammars . . . . . . . . . . . . . . . . . . . . . 571 Information Extraction . . . . . . . . . . . . . . . . . . . . 575 15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 581 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 582 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 16 Lexical Semantics 587 16.1 Relations Among Lexemes and Their Senses . . . . . . . . 590 Homonymy . . . . . . . . . . . . . . . . . . . . . . . . . 590 Polysemy . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 Synonymy . . . . . . . . . . . . . . . . . . . . . . . . . . 596 Hyponymy . . . . . . . . . . . . . . . . . . . . . . . . . . 599 16.2 WordNet: A Database of Lexical Relations . . . . . . . . . 600 16.3 The Internal Structure of Words . . . . . . . . . . . . . . . 605 Thematic Roles . . . . . . . . . . . . . . . . . . . . . . . 606 Selection Restrictions . . . . . . . . . . . . . . . . . . . . 613 Primitive Decomposition . . . . . . . . . . . . . . . . . . 618 Semantic Fields . . . . . . . . . . . . . . . . . . . . . . . 620 16.4 Creativity and the Lexicon . . . . . . . . . . . . . . . . . . 621 16.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 623Contents xvii Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 17 Word Sense Disambiguation and Information Retrieval 627 17.1 Selection Restriction-Based Disambiguation . . . . . . . . 628 Limitations of Selection Restrictions . . . . . . . . . . . . 630 17.2 Robust Word Sense Disambiguation . . . . . . . . . . . . 632 Machine Learning Approaches . . . . . . . . . . . . . . . 632 Dictionary-Based Approaches . . . . . . . . . . . . . . . . 641 17.3 Information Retrieval . . . . . . . . . . . . . . . . . . . . 642 The Vector Space Model . . . . . . . . . . . . . . . . . . . 643 Term Weighting . . . . . . . . . . . . . . . . . . . . . . . 647 Term Selection and Creation . . . . . . . . . . . . . . . . 650 Homonymy, Polysemy and Synonymy . . . . . . . . . . . 651 Improving User Queries . . . . . . . . . . . . . . . . . . . 652 17.4 Other Information Retrieval Tasks . . . . . . . . . . . . . . 654 17.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 656 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 IV Pragmatics 661 18 Discourse 663 18.1 Reference Resolution . . . . . . . . . . . . . . . . . . . . 665 Reference Phenomena . . . . . . . . . . . . . . . . . . . . 667 Syntactic and Semantic Constraints on Coreference . . . . 672 Preferences in Pronoun Interpretation . . . . . . . . . . . . 675 An Algorithm for Pronoun Resolution . . . . . . . . . . . 678 18.2 Text Coherence . . . . . . . . . . . . . . . . . . . . . . . 689 The Phenomenon . . . . . . . . . . . . . . . . . . . . . . 689 An Inference Based Resolution Algorithm . . . . . . . . . 691 18.3 Discourse Structure . . . . . . . . . . . . . . . . . . . . . 699 18.4 Psycholinguistic Studies of Reference and Coherence . . . 701 18.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 706 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 707 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709 19 Dialogue and Conversational Agents 715 19.1 What Makes Dialogue Different? . . . . . . . . . . . . . . 716 Turns and Utterances . . . . . . . . . . . . . . . . . . . . 717xviii Contents Grounding . . . . . . . . . . . . . . . . . . . . . . . . . . 720 Conversational Implicature . . . . . . . . . . . . . . . . . 722 19.2 Dialogue Acts . . . . . . . . . . . . . . . . . . . . . . . . 723 19.3 Automatic Interpretation of Dialogue Acts . . . . . . . . . 726 Plan-Inferential Interpretation of Dialogue Acts . . . . . . 729 Cue-based interpretation of Dialogue Acts . . . . . . . . . 734 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 740 19.4 Dialogue Structure and Coherence . . . . . . . . . . . . . 740 19.5 Dialogue Managers in Conversational Agents . . . . . . . 746 19.6 summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 753 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 755 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756 20 Generation 759 20.1 Introduction to Language Generation . . . . . . . . . . . . 761 20.2 An Architecture for Generation . . . . . . . . . . . . . . . 763 20.3 Surface Realization . . . . . . . . . . . . . . . . . . . . . 764 Systemic Grammar . . . . . . . . . . . . . . . . . . . . . 765 Functional Unification Grammar . . . . . . . . . . . . . . 770 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 775 20.4 Discourse Planning . . . . . . . . . . . . . . . . . . . . . 775 Text Schemata . . . . . . . . . . . . . . . . . . . . . . . . 776 Rhetorical Relations . . . . . . . . . . . . . . . . . . . . . 779 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 784 20.5 Other Issues . . . . . . . . . . . . . . . . . . . . . . . . . 785 Microplanning . . . . . . . . . . . . . . . . . . . . . . . . 785 Lexical Selection . . . . . . . . . . . . . . . . . . . . . . 786 Evaluating Generation Systems . . . . . . . . . . . . . . . 786 Generating Speech . . . . . . . . . . . . . . . . . . . . . . 787 20.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 788 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 789 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792 21 Machine Translation 797 21.1 Language Similarities and Differences . . . . . . . . . . . 800 21.2 The Transfer Metaphor . . . . . . . . . . . . . . . . . . . 805 Syntactic Transformations . . . . . . . . . . . . . . . . . . 806 Lexical Transfer . . . . . . . . . . . . . . . . . . . . . . . 808 21.3 The Interlingua Idea: Using Meaning . . . . . . . . . . . . 809Contents xix 21.4 Direct Translation . . . . . . . . . . . . . . . . . . . . . . 813 21.5 Using Statistical Techniques . . . . . . . . . . . . . . . . . 816 Quantifying Fluency . . . . . . . . . . . . . . . . . . . . . 818 Quantifying Faithfulness . . . . . . . . . . . . . . . . . . 819 Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820 21.6 Usability and System Development . . . . . . . . . . . . . 820 21.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 823 Bibliographical and Historical Notes . . . . . . . . . . . . . . . . 824 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 A Regular Expression Operators 829 B The Porter Stemming Algorithm 831 C C5 and C7 tagsets 835 D Training HMMs: The Forward-Backward Algorithm 841 Continuous Probability Densities . . . . . . . . . . . . . . 847 Bibliography 851 Index 923

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.