An Introduction to Language Processing with Perl and Prolog: An Outline of Theories, Implementation, and Application with Special Consideration of English, French, and German (Cognitive Technologies)

This book teaches the principles of natural language processing and covers linguistics issues. It also details the language-processing functions involved, including part-of-speech tagging using rules and stochastic techniques. A key feature of the book is the author's hands-on approach throughout, with extensive exercises, sample code in Prolog and Perl, and a detailed introduction to Prolog. The book is suitable for researchers and students of natural language processing and computational linguistics. Contents......Page 8 1.1 Linguistics and Language Processing......Page 20 1.2 Applications of Language Processing......Page 21 1.3 The Different Domains of Language Processing......Page 22 1.4 Phonetics......Page 23 1.5 Lexicon and Morphology......Page 25 1.6.1 Syntax as Defined by Noam Chomsky......Page 27 1.6.2 Syntax as Relations and Dependencies......Page 29 1.7 Semantics......Page 30 1.9 Why Speech and Language Processing Are Difficult......Page 33 1.9.1 Ambiguity......Page 34 1.9.2 Models and Their Implementation......Page 35 1.10.1 Overview of Persona......Page 36 1.10.2 The Persona's Modules......Page 37 1.11 Further Reading......Page 38 2.1.1 Types of Corpora......Page 42 2.1.2 Corpora and Lexicon Building......Page 43 2.1.3 Corpora as Knowledge Sources for the Linguist......Page 45 2.2.1 A Description......Page 46 2.2.2 Mathematical Definition of Finite-State Automata......Page 47 2.2.3 Finite-State Automata in Prolog......Page 48 2.2.4 Deterministic and Nondeterministic Automata......Page 49 2.2.6 Searching a String with a Finite-State Automaton......Page 50 2.2.7 Operations on Finite-State Automata......Page 52 2.3 Regular Expressions......Page 54 2.3.1 Repetition Metacharacters......Page 55 2.3.2 The Longest Match......Page 56 2.3.3 Character Classes......Page 57 2.3.4 Nonprintable Symbols or Positions......Page 58 2.3.6 Operator Combination and Precedence......Page 60 2.4.2 Matching......Page 61 2.4.3 Substitutions......Page 62 2.4.5 String Operators......Page 63 2.4.6 Back References......Page 64 2.5.1 Concordances in Prolog......Page 65 2.5.2 Concordances in Perl......Page 67 2.6.1 Edit Operations......Page 69 2.6.2 Minimum Edit Distance......Page 70 2.6.3 Searching Edits in Prolog......Page 73 2.7 Further Reading......Page 74 3.1 Encoding Texts......Page 77 3.2.1 Representing Characters......Page 78 3.2.2 Unicode......Page 79 3.2.3 The Unicode Encoding Schemes......Page 81 3.3.1 Presenting Time, Numerical Information, and Ordered Words......Page 84 3.3.2 The Unicode Collation Algorithm......Page 85 3.4.2 An Outline of XML......Page 87 3.4.3 Writing a DTD......Page 89 3.4.4 Writing an XML Document......Page 92 3.4.5 Namespaces......Page 93 3.5.1 Entropy......Page 94 3.5.2 Huffman Encoding......Page 95 3.5.3 Cross Entropy......Page 98 3.5.4 Perplexity and Cross Perplexity......Page 99 3.6.2 Inducing Decision Trees Automatically......Page 100 3.7 Further Reading......Page 102 4.2.1 What Is a Word?......Page 104 4.2.2 Breaking a Text into Words: Tokenization......Page 105 4.3.1 Tokenizing Texts in Prolog......Page 106 4.3.2 Tokenizing Texts in Perl......Page 108 4.4.1 Some Definitions......Page 109 4.4.3 Counting Unigrams with Perl......Page 110 4.5.1 The Maximum Likelihood Estimation......Page 112 4.5.2 Using ML Estimates with Nineteen Eighty-Four......Page 114 4.6.1 Sparse Data......Page 116 4.6.2 Laplace's Rule......Page 117 4.6.3 Good–Turing Estimation......Page 118 4.7 Using N-grams of Variable Length......Page 119 4.7.1 Linear Interpolation......Page 120 4.8.1 Intuitive Presentation......Page 121 4.8.3 Cross Entropy......Page 122 4.9 Collocations......Page 123 4.9.1 Word Preference Measurements......Page 124 4.9.2 Extracting Collocations with Perl......Page 125 4.10 Application: Retrieval and Ranking of Documents on the Web......Page 126 4.11 Further Reading......Page 128 5.1.1 Parts of Speech......Page 130 5.1.2 Features......Page 131 5.1.3 Two Signifficant Parts of Speech: The Noun and the Verb......Page 132 5.2 Lexicons......Page 134 5.2.1 Encoding a Dictionary......Page 136 5.2.2 Building a Trie in Prolog......Page 138 5.3.1 Morphemes......Page 140 5.3.2 Morphs......Page 141 5.3.3 Inffection and Derivation......Page 142 5.3.4 Language Differences......Page 146 5.4.1 Two-Level Model of Morphology......Page 147 5.4.3 Finite-State Transducers......Page 148 5.4.4 Conjugating a French Verb......Page 150 5.4.5 Prolog Implementation......Page 151 5.4.6 Ambiguity......Page 153 5.4.7 Operations on Finite-State Transducers......Page 154 5.5.1 Two-Level Rules......Page 155 5.5.2 Rules and Finite-State Transducers......Page 156 5.5.3 Rule Composition: An Example with French Irregular Verbs......Page 158 5.7 Further Reading......Page 159 6.1.2 Which Method to Use to Automatically Assign Parts of Speech......Page 163 6.2.1 Brill's Tagger......Page 165 6.2.2 Implementation in Prolog......Page 167 6.2.3 Deriving Rules Automatically......Page 169 6.3 Unknown Words......Page 170 6.4.1 Multilingual Part-of-Speech Tags......Page 172 6.4.2 Parts of Speech for English......Page 174 6.4.3 An Annotation Scheme for Swedish......Page 176 6.5 Further Reading......Page 178 7.1.1 Presentation......Page 179 7.1.2 The N-gram Approximation......Page 180 7.1.3 Tagging a Sentence......Page 181 7.1.4 The Viterbi Algorithm: An Intuitive Presentation......Page 182 7.2.1 Markov Chains......Page 183 7.2.2 Hidden Markov Models......Page 185 7.2.3 Three Fundamental Algorithms to Solve Problems with HMMs......Page 186 7.2.4 The Forward Procedure......Page 187 7.2.5 Viterbi Algorithm......Page 189 7.2.6 The Backward Procedure......Page 190 7.2.7 The Forward–Backward Algorithm......Page 191 7.3 Tagging with Decision Trees......Page 193 7.5 An Application of the Noisy Channel Model: Spell Checking......Page 195 7.6.1 Parallel Corpora......Page 196 7.6.2 Alignment......Page 197 7.6.3 Translation......Page 199 7.7 Further Reading......Page 200 8.2.1 Constituents......Page 201 8.2.2 Tree Structures......Page 202 8.2.3 Phrase-Structure Rules......Page 203 8.2.4 The Definite Clause Grammar (DCG) Notation......Page 204 8.3.1 Translating DCGs into Prolog Clauses......Page 206 8.3.2 Parsing and Generation......Page 208 8.3.3 Left-Recursive Rules......Page 209 8.4 Parsing Ambiguity......Page 210 8.5.1 Gender and Number Agreement......Page 212 8.5.2 Obtaining the Syntactic Structure......Page 214 8.6.1 Word Breaking......Page 216 8.6.2 Recognition of Sentence Boundaries......Page 217 8.7.1 λ-Calculus......Page 218 8.7.2 Embedding λ-Expressions into DCG Rules......Page 219 8.7.3 Semantic Composition of Verbs......Page 221 8.8 An Application of Phrase-Structure Grammars and a Worked Example......Page 222 8.9 Further Reading......Page 226 9.2.1 ELIZA......Page 228 9.2.2 Word Spotting in Prolog......Page 229 9.3.2 A Standard Multiword Annotation......Page 232 9.3.4 The Longest Match......Page 234 9.3.5 Running the Program......Page 235 9.4 Noun Groups and Verb Groups......Page 237 9.4.2 DCG Rules to Detect Noun Groups......Page 238 9.4.3 DCG Rules to Detect Verb Groups......Page 240 9.4.4 Running the Rules......Page 241 9.5.1 Tagging Gaps......Page 242 9.5.2 Tagging Words......Page 243 9.5.4 Using Statistical Tagging......Page 244 9.6 Cascading Partial Parsers......Page 245 9.7.1 Main Functions......Page 246 9.7.2 Extracting Other Groups......Page 247 9.8 An Annotation Scheme for Groups in French......Page 250 9.9.1 The Message Understanding Conferences......Page 252 9.9.2 The Syntactic Layers of the FASTUS System......Page 253 9.9.3 Evaluation of Information Extraction Systems......Page 254 9.10 Further Reading......Page 255 10.1 Introduction......Page 258 10.2.1 Constituency: A Formal Definition......Page 259 10.2.2 Transformations......Page 261 10.2.4 Gap Threading......Page 263 10.2.5 Gap Threading to Parse Relative Clauses......Page 265 10.3 Standardized Phrase Categories for English......Page 267 10.4.1 Features......Page 269 10.4.2 Representing Features in Prolog......Page 270 10.4.3 A Formalismfor Features and Rules......Page 272 10.4.4 Features Organization......Page 273 10.4.5 Features and Unification......Page 275 10.4.6 A Unification Algorithm for Feature Structures......Page 276 10.5.1 Presentation......Page 278 10.5.2 Properties of a Dependency Graph......Page 281 10.5.3 Valence......Page 283 10.5.4 Dependencies and Functions......Page 285 10.6 Further Reading......Page 288 11.1 Introduction......Page 291 11.2.1 The Shift–Reduce Algorithm......Page 292 11.2.2 Implementing Shift–Reduce Parsing in Prolog......Page 293 11.2.3 Differences Between Bottom-up and Top-down Parsing......Page 295 11.3.2 Structure of a Chart......Page 296 11.3.3 The Active Chart......Page 297 11.3.4 Modules of an Earley Parser......Page 299 11.3.5 The Earley Algorithm in Prolog......Page 302 11.3.6 The Earley Parser to Handle Left-Recursive Rules and Empty Symbols......Page 307 11.5 A Description of PCFGs......Page 308 11.5.1 The Bottom-up Chart......Page 311 11.5.2 The Cocke–Younger–Kasami Algorithm in Prolog......Page 312 11.5.3 Adding Probabilities to the CYK Parser......Page 314 11.6.1 Constituency-Based Evaluation......Page 315 11.6.3 Performance of PCFG Parsing......Page 316 11.7 Parsing Dependencies......Page 317 11.7.1 Dependency Rules......Page 318 11.7.2 Extending the Shift–Reduce Algorithm to Parse Dependencies......Page 319 11.7.3 Nivre's Parser in Prolog......Page 320 11.7.4 Finding Dependencies Using Constraints......Page 323 11.7.5 Parsing Dependencies Using Statistical Techniques......Page 324 11.8 Further Reading......Page 327 12.2 Language Meaning and Logic: An Illustrative Example......Page 330 12.4 First-Order Predicate Calculus to Represent the State of Affairs......Page 332 12.4.2 Predicates......Page 333 12.6 Mapping Phrases onto Logical Formulas......Page 335 12.6.1 Representing Nouns and Adjectives......Page 336 12.6.3 Representing Verbs and Prepositions......Page 337 12.7.1 Determiners and Logic Quantifiers......Page 338 12.7.2 Translating Sentences Using Quantifiers......Page 339 12.7.3 A General Representation of Sentences......Page 340 12.8.1 Translating the Noun Phrase......Page 342 12.8.2 Translating the Verb Phrase......Page 343 12.9 Augmenting the Database and Answering Questions......Page 344 12.9.2 Questions with Existential and Universal Quantifiers......Page 345 12.9.3 Prolog and Unknown Predicates......Page 347 12.10.1 Translating Spoken Sentences......Page 348 12.10.2 Compositional Semantics......Page 349 12.10.3 Semantic Representation Transfer......Page 351 12.11 Further Reading......Page 353 13.1.2 Language and the Structure of the World......Page 355 13.2.2 Ontological Organization......Page 356 13.2.3 Lexical Classes and Relations......Page 357 13.3 Building a Lexicon......Page 359 13.3.1 The Lexicon and Word Senses......Page 361 13.3.2 Verb Models......Page 362 13.3.3 Definitions......Page 363 13.4 An Example of Exhaustive Lexical Organization: WordNet......Page 364 13.4.1 Nouns......Page 365 13.4.2 Adjectives......Page 366 13.4.3 Verbs......Page 367 13.5.1 Senses as Tags......Page 368 13.5.3 Guessing the Topic......Page 369 13.5.4 Naïve Bayes......Page 370 13.5.6 Using Dictionary Definitions......Page 371 13.5.7 An Unsupervised Algorithm to Tag Senses......Page 372 13.5.8 Senses and Languages......Page 374 13.6.1 Cases in Latin......Page 375 13.6.2 Cases and Thematic Roles......Page 376 13.6.3 Parsing with Cases......Page 377 13.6.4 Semantic Grammars......Page 378 13.7.1 FrameNet......Page 379 13.7.2 A Statistical Method to Identify Semantic Roles......Page 380 13.8.1 EVAR's Ontology and Syntactic Classes......Page 383 13.9 Further Reading......Page 385 14.1 Introduction......Page 388 14.2.2 Discourse Entities......Page 389 14.3.1 References and Noun Phrases......Page 390 14.3.2 Finding Names – Proper Nouns......Page 391 14.4.1 Anaphora......Page 392 14.4.2 Solving Coreferences in an Example......Page 393 14.4.3 A Standard Coreference Annotation......Page 394 14.5.1 Generating Discourse Entities: The Existential Quantifier......Page 395 14.5.2 Retrieving Discourse Entities: Definite Descriptions......Page 396 14.5.3 Generating Discourse Entities: The Universal Quantifier......Page 397 14.6 Centering: A Theory on Discourse Structure......Page 398 14.7 Solving Coreferences......Page 399 14.7.1 A Simplistic Method: Using Syntactic and Semantic Compatibility......Page 400 14.7.2 Solving Coreferences with Shallow Grammatical Information......Page 401 14.7.4 Using a Machine-Learning Technique to Resolve Coreferences......Page 402 14.8 Discourse and Rhetoric......Page 407 14.8.2 Rhetorical Structure Theory......Page 408 14.8.3 Types of Relations......Page 410 14.8.4 Implementing Rhetorical Structure Theory......Page 411 14.9 Events and Time......Page 412 14.9.1 Events......Page 414 14.9.3 Temporal Representation of Events......Page 415 14.9.4 Events and Tenses......Page 417 14.10 TimeML, an Annotation Scheme for Time and Events......Page 418 14.11 Further Reading......Page 420 15.2 Why a Dialogue?......Page 422 15.3.1 Dialogue Systems Based on Automata......Page 423 15.3.2 Dialogue Modeling......Page 424 15.4 Speech Acts: A Theory of Language Interaction......Page 425 15.5.1 Speech Acts as a Tagging Model......Page 428 15.5.2 Speech Acts Tags Used in the SUNDIAL Project......Page 429 15.5.3 Dialogue Parsing......Page 430 15.5.4 Interpreting Speech Acts......Page 432 15.5.5 EVAR: A Dialogue Application Using Speech Acts......Page 433 15.6 Taking Beliefs and Intentions into Account......Page 434 15.6.1 Representing Mental States......Page 436 15.6.2 The STRIPS Planning Algorithm......Page 438 15.6.3 Causality......Page 440 15.7 Further Reading......Page 441 A.1 A Short Background......Page 443 A.2.1 Facts......Page 444 A.2.2 Terms......Page 445 A.2.4 Logical Variables......Page 447 A.2.5 Shared Variables......Page 448 A.2.6 Data Types in Prolog......Page 449 A.2.7 Rules......Page 450 A.3 Running a Program......Page 452 A.4.1 Substitution and Instances......Page 453 A.4.2 Terms and Unification......Page 454 A.4.4 Example......Page 455 A.4.5 The Occurs-Check......Page 456 A.5.2 A Resolution Algorithm......Page 457 A.5.3 Derivation Trees and Backtracking......Page 458 A.6 Tracing and Debugging......Page 460 A.7.1 Cuts......Page 462 A.7.2 Negation......Page 463 A.7.3 The once/1 Predicate......Page 464 A.8 Lists......Page 465 A.9.1 The member/2 Predicate......Page 466 A.9.2 The append/3 Predicate......Page 467 A.9.4 The intersection/3 Predicate......Page 468 A.9.6 The Mode of an Argument......Page 469 A.10.2 Arithmetic Operations......Page 470 A.10.3 Comparison Operators......Page 472 A.10.5 Lists and Comparison: The quicksort/2 Predicate......Page 473 A.11.1 Type Predicates......Page 474 A.11.2 Term Manipulation Predicates......Page 475 A.12 Handling Run-Time Errors and Exceptions......Page 476 A.13.1 Accessing a Clause: The clause/2 Predicate......Page 477 A.13.3 Adding a Clause: The asserta/1 and assertz/1 Predicates......Page 478 A.13.4 Removing Clauses: The retract/1 and abolish/2 Predicates......Page 479 A.14 All-Solutions Predicates......Page 480 A.15 Fundamental Search Algorithms......Page 481 A.15.1 Representing the Graph......Page 482 A.15.2 Depth-First Search......Page 483 A.15.3 Breadth-First Search......Page 484 A.15.4 A* Search......Page 485 A.16.2 Reading and Writing Terms with Edinburgh Prolog......Page 486 A.16.3 Opening and Closing Files with Edinburgh Prolog......Page 487 A.16.4 Reading and Writing Characters with Standard Prolog......Page 488 A.16.6 Opening and Closing Files with Standard Prolog......Page 489 A.16.7 Writing Loops......Page 490 A.17.1 Presentation Style......Page 491 A.17.2 Improving Programs......Page 492 B......Page 497 C......Page 498 F......Page 499 J......Page 500 M......Page 501 P......Page 502 R......Page 503 T......Page 504 X......Page 505 Z......Page 506 References......Page 507 The Areas Of Natural Language Processing And Computational Linguistics Have Continued To Grow In Recent Years, Driven By The Demand To Automatically Process Text And Spoken Data. With The Processing Power And Techniques Now Available, Research Is Scaling Up From Lab Prototypes To Real-world, Proven Applications. This Book Teaches The Principles Of Natural Language Processing, First Covering Linguistics Issues Such As Encoding, Entropy, And Annotation Schemes; Defining Words, Tokens And Parts Of Speech; And Morphology. It Then Details The Language-processing Functions Involved, Including Part-of-speech Tagging Using Rules And Stochastic Techniques; Using Prolog To Write Phase-structure Grammars; Parsing Techniques And Syntactic Formalisms; Semantics, Predicate Logic And Lexical Semantics; And Analysis Of Discourse, And Applications In Dialog Systems. The Key Feature Of The Book Is The Author's Hands-on Approach Throughout, With Extensive Exercises, Sample Code In Prolog And Perl, And A Detailed Introduction To Prolog. The Reader Is Supported With A Companion Website That Contains Teaching Slides, Programs, And Additional Material. The Book Is Suitable For Researchers And Students Of Natural Language Processing And Computational Linguistics. An Overview Of Language Processing -- Corpus Processing Tools -- Encoding, Entropy, And Annotation Schemes -- Counting Words -- Words, Parts Of Speech, And Morphology -- Part-of-speech Tagging Using Rules -- Part-of-speech Tagging Using Stochastic Techniques -- Phrase-structure Grammars In Prolog -- Partial Parsing -- Syntactic Formalisms -- Parsing Techniques -- Semantics And Predicate Logic -- Lexical Semantics -- Discourse -- Dialogue -- An Introduction To Prolog. By Pierre M. Nugues.

The areas of natural language processing and computational linguistics have continued to grow in recent years, driven by the demand to automatically process text and spoken data. With the processing power and techniques now available, research is scaling up from lab prototypes to real-world, proven applications.

This book teaches the principles of natural language processing, first covering linguistics issues such as encoding, entropy, and annotation schemes; defining words, tokens and parts of speech; and morphology. It then details the language-processing functions involved, including part-of-speech tagging using rules and stochastic techniques; using Prolog to write phase-structure grammars; parsing techniques and syntactic formalisms; semantics, predicate logic and lexical semantics; and analysis of discourse, and applications in dialog systems. The key feature of the book is the author's hands-on approach throughout, with extensive exercises, sample code in Prolog and Perl, and a detailed introduction to Prolog. The reader is supported with a companion website that contains teaching slides, programs, and additional material.

The book is suitable for researchers and students of natural language processing and computational linguistics.