Speech and Language Processing - deepsky.com

1 Speech and Language Processing PRENTICE HALL SERIES. AI IN ARTIFICIAL INTELLIGENCE. Stuart Russell and Peter Norvig, Editors G RAHAM ANSI Common Lisp M UGGLETON Logical Foundations of Machine Learning RUSSELL & N ORVIG Artificial Intelligence: A Modern Approach J URAFSKY & M ARTIN Speech and Language Processing Speech 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 07632. Library of Congress Cataloging-in-Publication Data Jurafsky, Daniel S.

2 (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.

3 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, , 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 Janeiro For my parents For Linda 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.

4 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.

5 835. D Training HMMs: The Forward-Backward Algorithm .. 841. Bibliography 851. Index 923. vii Contents 1 Introduction 1. Knowledge in Speech and Language Processing .. 2. Ambiguity .. 4. Models and Algorithms .. 5. Language , Thought, and Understanding .. 6. The State of the Art and The Near-Term Future .. 9. 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. Summary .. 15. Bibliographical and Historical Notes .. 16. I Words 19. 2 Regular Expressions and Automata 21. Regular Expressions.

6 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. 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. Regular Languages and FSAs .. 49. Summary .. 51. ix x Contents Bibliographical and Historical Notes .. 52. Exercises .. 53. 3 Morphology and Finite-State Transducers 57. Survey of (Mostly) English Morphology.

7 59. Inflectional Morphology .. 61. Derivational Morphology .. 63. Finite-State Morphological Parsing .. 65. The Lexicon and Morphotactics .. 66. Morphological Parsing with Finite-State Transducers .. 71. Orthographic Rules and Finite-State Transducers .. 76. Combining FST Lexicon and Rules .. 79. Lexicon-free FSTs: The Porter Stemmer .. 82. Human Morphological Processing .. 84. Summary .. 86. Bibliographical and Historical Notes .. 87. Exercises .. 89. 4 Computational Phonology and Text-to- Speech 91. Speech Sounds and Phonetic Transcription .. 92. The Vocal Organs .. 94. Consonants: Place of Articulation .. 97. Consonants: Manner of Articulation .. 98. Vowels .. 100. The Phoneme and Phonological Rules.

8 102. Phonological Rules and Transducers .. 104. Advanced Issues in Computational Phonology .. 109. Harmony .. 109. Templatic Morphology .. 111. Optimality Theory .. 112. Machine Learning of Phonological Rules .. 117. Mapping Text to Phones for TTS .. 119. Pronunciation dictionaries .. 119. Beyond Dictionary Lookup: Text Analysis .. 121. An FST-based pronunciation lexicon .. 124. Prosody in TTS .. 129. Phonological Aspects of Prosody .. 129. Phonetic or Acoustic Aspects of Prosody .. 131. Prosody in Speech Synthesis .. 131. Contents xi Human Processing of Phonology and Morphology .. 133. Summary .. 134. Bibliographical and Historical Notes .. 135. Exercises .. 136. 5 Probabilistic Models of Pronunciation and Spelling 139.

9 Dealing with Spelling Errors .. 141. Spelling Error Patterns .. 142. Detecting Non-Word Errors .. 144. Probabilistic Models .. 144. Applying the Bayesian method to spelling .. 147. Minimum Edit Distance .. 151. English Pronunciation Variation .. 154. The Bayesian method for pronunciation .. 161. Decision Tree Models of Pronunciation Variation .. 166. Weighted Automata .. 167. Computing Likelihoods from Weighted Automata: The For- ward Algorithm .. 169. Decoding: The Viterbi Algorithm .. 174. Weighted Automata and Segmentation .. 178. Pronunciation in Humans .. 180. Summary .. 183. Bibliographical and Historical Notes .. 184. Exercises .. 187. 6 N-grams 189. Counting Words in Corpora .. 191. Simple (Unsmoothed) N-grams.

10 194. More on N-grams and their sensitivity to the training corpus 199. Smoothing .. 204. Add-One Smoothing .. 205. Witten-Bell Discounting .. 208. Good-Turing Discounting .. 212. Backoff .. 214. Combining Backoff with Discounting .. 215. Deleted Interpolation .. 217. N-grams for Spelling and Pronunciation .. 218. Context-Sensitive Spelling Error Correction .. 219. N-grams for Pronunciation Modeling .. 220. xii Contents Entropy .. 221. Cross Entropy for Comparing Models .. 224. The Entropy of English .. 225. Bibliographical and Historical Notes .. 228. Summary .. 229. Exercises .. 230. 7 HMMs and Speech Recognition 233. Speech Recognition Architecture .. 235. Overview of Hidden Markov Models .. 239. The Viterbi Algorithm Revisited.