A Course in Natural Language Processing

Natural Language Processing is the branch of Artificial Intelligence involving language, be it in spoken or written modality. Teaching Natural Language Processing (NLP) is difficult because of its inherent connections with other disciplines, such as Linguistics, Cognitive Science, Knowledge Representation, Machine Learning, Data Science, and its latest avatar: Deep Learning. Most introductory NLP books favor one of these disciplines at the expense of others. Based on a course on Natural Language Processing taught by the author at IMT Atlantique for over a decade, this textbook considers three points of view corresponding to three different disciplines, while granting equal importance to each of them. As such, the book provides a thorough introduction to the topic following three main threads: the fundamental notions of Linguistics, symbolic Artificial Intelligence methods (based on knowledge representation languages), and statistical methods (involving both legacy machine learning and deep learning tools). Complementary to this introductory text is teaching material, such as exercises and labs with hints and expected results. Complete solutions with Python code are provided for educators on the SpringerLink webpage of the book. This material can serve for classes given to undergraduate and graduate students, or for researchers, instructors, and professionals in computer science or linguistics who wish to acquire or improve their knowledge in the field. The book is suitable and warmly recommended for self-study. Preface From ELIZA to ChatGPT Pedagogical Objectives For Whom Is This Book Written, and How To Read It Acknowledgments Contents Chapter 1 Introduction 1.1 What Is Language in the First Place? 1.2 Principles of Linguistics and of Language 1.2.1 Signifier and Signified 1.2.2 Opposition, Etics and Emics 1.2.3 Paradigmatic Axis and Syntagmatic Axis 1.2.4 Compositionality 1.2.5 Modalities of Language 1.2.6 Functions of Language 1.2.7 Sapir-Whorf and the Eskimo Vocabulary Hoax 1.3 A Terminological Issue: Data–Information–Knowledge 1.4 Notations 1.5 Exercises and Hints 1.6 Resources and Errata References Part I Linguistics Chapter 2 Phonetics/Phonology 2.1 Articulatory Phonetics 2.1.1 (Pulmonic) Consonants 2.1.2 Vowels 2.2 Acoustic Phonetics 2.3 From Phonetics to Phonemics 2.3.1 Features 2.3.2 Phonemes 2.4 Phonological Rules 2.4.1 Underlying Representation 2.5 Suprasegmental Aspects 2.5.1 Syllables 2.5.2 Stress and Foot 2.5.3 Mora 2.5.4 Tone 2.5.5 Prosody 2.6 iPA Phonetics, an App for Learning Phonetics 2.7 Psycholinguistic Aspects, Perceptual Phonetics 2.8 Further Reading 2.8.1 Literature 2.8.2 LATEX 2.8.3 Science Fiction 2.9 Exercises Exercise 1-1: English Accents Exercise 1-2: Phonotactics of English Exercise 1-3: Tonotactics of Vietnamese Exercise 1-4: Classification of Voice Files References Chapter 3 Graphetics/Graphemics 3.1 Graphetics 3.1.1 Descriptive Graphetics 3.1.1.1 Cheirographetics, or the Study of Handwriting 3.1.1.2 Typographetics 3.1.1.3 Descriptive Levels 3.1.1.4 Kerning and Ligatures 3.1.1.5 Typographetic Functions and Connotations 3.2 Graphemics 3.2.1 Writing Systems and Scripts 3.2.2 Pictography, Emoji 3.2.3 Orthography 3.2.4 Hyphenation and Non-breakability 3.2.5 Graphemic Gender-neutral Methods 3.2.6 Sinographemics 3.3 Psycholinguistic Aspects of Reading 3.4 Further Reading 3.4.1 Literature 3.4.2 LATEX 3.4.3 Science Fiction 3.5 Exercises Exercise 2-1: Evaluating ALA-LC Transcriptions of Arabic and Greek Exercise 2-2: Graphotactics of English Exercise 2-3: Greek Car License Plate and Signs Exercise 2-4: Predictability of New Sinograms Exercise 2-5: Exotype Classification References Chapter 4 Morphemes, Words, Terms 4.1 Words 4.2 Lexemes 4.3 Parts of Speech 4.4 Morphemes 4.5 Inflection 4.6 Derivation 4.7 Compounding 4.8 Astonishing Morphologies: Semitic Languages and Lojban 4.8.1 Semitic Languages 4.8.2 Lojban 4.9 Terms and Collocations 4.10 Psycholinguistic Aspects Finding Words Building Words Phonological Encoding Keylogs 4.11 Further Reading 4.11.1 Literature 4.11.2 Science Fiction Orwell’s Newspeak Time Travel and Verb Morphology The Golem 4.12 Exercises Exercise 3-1: English and French Verb Conjugation Compared Exercise 3-2: Jules Verne and French Verbs Exercise 3-3: The Combinatorics of Neoclassical Morphemes Exercise 3-4: The Morphology of Lojban Exercise 3-5: Long and Round Ess in German References Chapter 5 Syntax 5.1 Constituents and Clauses 5.1.1 Constituency Tests 5.1.2 Agreement 5.1.3 Clauses 5.1.4 Topology 5.1.5 Ambiguity 5.2 Syntax Theories 5.3 Chomsky’s Context-Free Phrase Structure Grammar 5.3.1 Parsing Context-Free Phrase Structure Grammar in Python 5.4 Chomsky’s Transformational Grammar 5.5 Binding Theory 5.5.1 Domination 5.5.2 Precedence 5.5.3 C-command 5.5.4 Referring Expressions, Anaphors, Binding 5.6 X Theory 5.6.1 Tense Phrases 5.7 Head-Driven Phrase Structure Grammars 5.8 Combinatory Categorial Grammars 5.8.1 From Phrase-Structure Grammars to Categorial Grammars 5.8.2 Conjunction 5.8.3 Composition, Bluebird 5.8.4 Type Raising, Thrush 5.8.5 A Python Parser for CCGs 5.9 Dependency Syntax 5.9.1 Some History 5.9.2 Strings and Catenae 5.9.3 Types of Dependency Relations 5.9.4 From Constituents to Dependencies 5.9.5 Parsing Dependency Grammars in Python 5.9.6 Surface-Syntactic Universal Dependencies 5.10 Psycholinguistic Aspects 5.11 Further Reading 5.11.1 Literature 5.11.2 LATEX 5.11.3 Science Fiction 5.12 Exercises Exercise 4-1: Constituency parser comparison Exercise 4-2: How well do stanza and spacy parse Yoda? Exercise 4-3: The Syntax of Lojban Exercise 4-4: Find Perfectly Ambiguous Sentences in English Exercise 4-5: Find emoji that behave like noun phrases References Chapter 6 Semantics (and Pragmatics) 6.1 Sense Relations 6.2 Structuralist Approaches to Semantics 6.2.1 Lexical Field Theory 6.2.2 Componential Analysis, Formal Concept Analysis 6.2.3 Relational Semantics 6.2.4 WordNet 6.3 Neostructuralist Approaches to Semantics 6.3.1 Wierzbicka’s Natural Semantic Metalanguage 6.3.2 Conceptual Semantics 6.3.3 Generative Lexicon 6.4 Cognitive Semantics 6.4.1 Prototype Theory 6.4.2 Fillmore’s Frames 6.4.3 FrameNet 6.4.4 Minsky’s Frames 6.4.5 Frames and Humor 6.4.6 Idealized Cognitive Models and Conceptual Theory of Metaphor 6.4.7 MetaNet 6.5 Formal Semantics 6.5.1 Frege, Sense, Denotation, and Truth 6.5.2 Montague Formal Semantics 6.5.2.1 Python Implementation of Formal Semantics 6.5.2.2 Formal Semantics through CCGs 6.6 Discourse Semantics 6.6.1 Rhetorical Structure Theory 6.6.2 Discourse Representation Theory 6.7 Implicatures and Conversation Maxims 6.8 Psycholinguistic Aspects 6.8.1 Independence of Syntactic and Semantic Processing 6.8.2 Architecture of the Language Processing System 6.9 Further Reading 6.9.1 Literature 6.9.2 Science Fiction 6.10 Exercises Exercise 5-1: Find faux amis words in French, German, Italian, Spanish, and English Exercise 5-2: FCA Exercise 5-3: The semantics of Lojban References Chapter 7 Controlled Natural Languages 7.1 Simplifications of English: Basic English, Simple English, and Caterpillar English 7.2 Formalizable Controlled Languages: Attempto Controlled English, PENG 7.3 A CNL for Mathematics: ForTheL 7.4 Exercises Exercise 6-1: Discovery of Attempto Controlled English Exercise 6-2: How simple is Simple English Wikipedia? Exercise 6-3: Write haikus inspired by themes by Emily Dickinson in Python Exercise 6-4: Do Daleks use a controlled language? References Part II Mathematical Tools Chapter 8 Graphs 8.1 Definitions 8.1.1 Trees 8.2 Basic Graph Algorithms 8.2.1 Search in a Graph 8.2.2 Shortest Paths 8.2.3 An Example: Word Ladders 8.2.4 Processing WordNet as a Graph 8.3 Vertex Centrality 8.3.1 Degree Centrality Degree Centrality in WordNet 8.3.2 Closeness Centrality Closeness Centrality in WordNet 8.3.3 Betweenness Centrality Betweenness Centrality in WordNet 8.4 Community Detection 8.4.1 Two Examples Based on Shakespeare's Night’s Dream 8.4.1.1 The Co-presence on Stage Graph 8.4.1.2 Doubling in MND 8.4.1.3 Centralities of MND Characters in the Co-presence on Stage Graph 8.4.1.4 Communities of MND Characters in the Co-presence on Stage Graph 8.4.1.5 The Vocative Graph 8.4.1.6 Centralities of MND Characters in the Vocative Graph 8.4.1.7 Communities of MND Characters in the Vocative Graph 8.4.1.8 Possible Improvements 8.5 Further Reading 8.5.1 Literature 8.5.2 LATEX 8.5.3 Science Fiction 8.6 Exercises Exercise 7-1: Using WordNet for disambiguation Exercise 7-2: Find the most central word of the Quran and the Bible Exercise 7-3: Assortativity of Chinese Hyperonyms Exercise 7-4: Productivity of sinographic component base References Chapter 9 Formal Languages 9.1 Background 9.2 Basic Definitions 9.3 Formal Grammars 9.3.1 The Chomsky Hierarchy 9.4 Regular Languages 9.4.1 Regular Expressions 9.4.1.1 Abstract Syntax 9.4.1.2 POSIX Syntax 9.4.1.3 Lazy Quantifiers 9.4.1.4 Regular Expressions in Python 9.4.1.5 Regular Expressions and ELIZA 9.4.1.6 Regular Expressions, Gender-Neutral Methods, and Poetry 9.4.2 Finite-State Automata and Transducers 9.4.2.1 Finite-State Automata in Python 9.4.2.2 Transducers 9.4.2.3 Transducers in Python 9.5 Context-Free Grammars 9.5.1 Context-Free Grammars in Python 9.5.2 Feature-Based Context-Free Grammars in Python 9.6 Grammatical Inference 9.7 Further Reading 9.7.1 Literature 9.7.2 LATEX 9.8 Exercises Exercise 8-1: an, anbn, anbncn, etc. Exercise 8-2: How many formal languages can there be? Exercise 8-3: The complementary of a regular language Exercise 8-4: Implement French and German gender-neutral language References Chapter 10 Logic 10.1 First-Order Logic 10.1.1 Formal Theory 10.1.2 Model Theory 10.1.3 Propositional Logic 10.1.4 Natural Language Formalization 10.1.4.1 An Example: The Barber’s (Pseudo-)Paradox 10.1.5 Knowledge Bases and Queries 10.1.5.1 Resolution 10.2 Extensions of First-Order Logic 10.2.1 Temporal Logic: Event Calculus 10.2.2 Modal Logic 10.2.2.1 Alethic Logic 10.2.2.2 Epistemic Logic 10.2.2.3 Deontic Logic 10.2.2.4 Other Modal Logics 10.3 Description Logics 10.3.1 Definitions 10.3.2 An Example: DL Formulas for AWO Plants are disjoint from animals Branches are parts of trees, leaves are parts of branches Carnivores are exactly those animals that eat only animals Herbivores are exactly those animals that eat only plants or parts of plants Lions are animals that eat only herbivores, giraffes eat only leaves 10.3.3 Role Properties 10.3.4 A Naming Scheme for Description Logics 10.4 Further Reading 10.4.1 Literature 10.4.2 LATEX 10.4.3 Science Fiction 10.4.3.1 Mr Spock 10.4.3.2 Predestination 10.5 Exercises Exercise 9-1: Socrates’ “I know that I know nothing” Exercise 9-2: Use Prolog for Formal Semantics Exercise 9-3: Prove that Curiosity killed the Cat using Attempto Controlled English, gkc, and RACE Exercise 9-4: The “logical proof of the existence of God” fallacy References Chapter 11 Ontologies and Conceptual Graphs 11.1 The Semantic Web 11.1.1 The Origins 11.1.2 The Semantic Web Cake 11.1.3 The Lower Levels: Unicode Literals, URIs, XML 11.1.4 RDF, SPARQL, and RDFS 11.1.5 OWL Ontologies 11.1.5.1 Prefixes, Ontology 11.1.5.2 Classes, Roles, Individuals 11.1.5.3 Subsumptions, Restrictions 11.1.5.4 Domain, Range, Identity 11.1.5.5 Role properties 11.1.5.6 Datatypes 11.1.5.7 Example 11.1.6 Protégé 11.1.7 Using Description Logic Reasoners with Python 11.1.7.1 All Men Are Mortal, in FACT++ 11.1.7.2 Pizzas and Pepper Allergy, in HermiT 11.2 Conceptual Graphs 11.2.1 Definitions 11.2.2 Subsumption 11.2.3 Queries 11.2.4 Beyond CGs: SGs, Models, Translation into FOL 11.2.4.1 Models 11.2.4.2 Translation into FOL 11.3 Exercises Exercise 10-1: Translate DL formulas into Attempto Controlled English and find counterexamples Exercise 10-2: Write a Q&A system for the Wildlife Ontology References Part III Data Formats Chapter 12 Unicode 12.1 What Is a Character? 12.2 Unicode Structure and Terminology 12.3 UTF-8 12.4 Combining Characters and Normalization 12.5 ZWJ and ZWNJ 12.6 Collation 12.7 Language Tags 12.8 Unicode and Python 12.9 What To Do When a Glyph Is Missing 12.10 Further Reading 12.10.1 Literature 12.10.2 LATEX 12.11 Exercises Exercise 11-1: Steganography Using Unicode Combining Characters Tasks Questions Exercise 11-2: Southeast-Asian Scripts Implementations in Unicode Exercise 11-3: How do Unicode and Wikipedia deal with simplified and traditional Chinese? Exercise 11-4: Unicode and political correctness in the processing of emoji Exercise 11-5: Curiosa Unicodensis References Chapter 13 XML, TEI, CDL 13.1 XML 13.1.1 XML Names 13.1.2 Markup Types 13.1.3 Abstract Syntax Tree Structure 13.1.4 XML Compositionality 13.1.5 XML Schemas 13.1.5.1 Validation in Python 13.1.6 Parsing XML Documents 13.1.6.1 SAX 13.1.6.2 XPath 13.1.6.3 DOM 13.2 TEI 13.2.1 The Header 13.2.2 The Common Core 13.2.3 Linguistic Corpora 13.2.4 Linguistic Annotation 13.2.5 Transcriptions of Speech 13.2.6 Verses and Alignment 13.2.7 Dictionaries 13.3 CDL 13.4 Exercises Exercise 12-1: Jerome K. Jerome’s Three Men on the Bummel in TEI Exercise 12-2: Find the subject occurrences in Bach’s Fugue BWV 846 Exercise 12-3: Document conversion from HTML to TEI using SAX and DOM References Part IV Statistical Methods Chapter 14 Counting Words 14.1 Tokenization and Segmentation 14.2 Zipf’s Law 14.3 Stop Words and tfidf 14.4 Collocations 14.5 N-grams 14.6 Vector Semantics 14.6.1 LSA and ESA 14.7 Skip-gram Embeddings 14.7.1 Theory 14.7.2 Word Analogies 14.7.3 Visualization 14.7.4 FastText 14.8 Further Reading 14.8.1 Literature 14.9 Exercises Exercise 13-1: Exploring the Anthology of the Association for Computational Linguistics Exercise 13-2: Find a Cornelian play among nine Racinian plays Exercise 13-3: Test properties of GloVe embeddings References Chapter 15 Going Neural 15.1 Feedforward Neural Networks 15.1.1 Doing It Manually 15.1.2 Batches and Epochs 15.1.3 How To Read Graphical Illustrations of Neural Networks 15.1.4 An Example in Python 15.2 Recurrent Neural Networks 15.2.1 An Example in Python 15.3 Encoder-Decoder Networks and Attention 15.4 Transformers and Self-Attention 15.4.1 Implementations of Transformers 15.5 Further Reading 15.5.1 Literature 15.5.2 Science Fiction References Chapter 16 Hints and Expected Results for Exercises 16.1 Chapter 1: Phonetics/Phonology Hints for Exercise 1-1: English Accents Expected Results Hints for Exercise 1-2: Phonotactics of English Expected Results Hints for Exercise 1-3: Tonotactics of Vietnamese Expected Results Hints for Exercise 1-4: Classification of Voice Files Expected Results 16.2 Chapter 2: Graphetics/Graphemics Hints for Exercise 2-1: Evaluating ALA-LC Transcriptions of Arabic and Greek Expected Results Hints for Exercise 2-2: Graphotactics of English Expected Results Hints for Exercise 2-3: Greek Car License Plate and Signs Expected Results Hints for Exercise 2-4: Predictability of New Sinograms Expected Results Hints for Exercise 2-5: Exotype Classification Expected Results 16.3 Chapter 3: Morphemes, Words, Terms Hints for Exercise 3-1: English and French Verb Conjugation Compared Expected Results Hints for Exercise 3-2: Jules Verne and French Verbs Expected Results Hints for Exercise 3-3: The Combinatorics of Neoclassical Morphemes Expected Results Hints for Exercise 3-4: The Morphology of Lojban Expected Results Hints for Exercise 3-5: Long and Round Ess in German Expected Results 16.4 Chapter 4: Syntax Hints for Exercise 4-1: Constituency parser comparison Expected Results Hints for Exercise 4-2: How well do stanza and spacy parse Yoda? Expected Results Hints for Exercise 4-3: The Syntax of Lojban Expected Results Hints for Exercise 4-4: Find Perfectly Ambiguous Sentences in English Expected Results Hints for Exercise 4-5: Find emoji that behave like noun phrases Expected Results 16.5 Chapter 5: Semantics (and Pragmatics) Hints for Exercise 5-1: Find faux amis words in French, German, Italian, Spanish, and English Expected Results Hints for Exercise 5-2: FCA Expected Results Hints for Exercise 5-3: The semantics of Lojban Expected Results 16.6 Chapter 6: Controlled Natural Languages Hints for Exercise 6-1: Discovery of Attempto Controlled English Expected Results Hints for Exercise 6-2: How simple is Simple English Wikipedia? Expected Results Hints for Exercise 6-3: Write haikus inspired by themes by Emily Dickinson in Python Expected Results Hints for Exercise 6-4: Do Daleks use a controlled language? Expected Results 16.7 Chapter 7: Graphs Hints for Exercise 7-1: Using WordNet for disambiguation Expected Results Hints for Exercise 7-2: Find the most central word of the Quran and of the Bible Expected Results Hints for Exercise 7-3: Assortativity of Chinese Hyperonyms Expected Results Hints for Exercise 7-4: Productivity of sinographic component base Expected Results 16.8 Chapter 8: Formal Languages Hints for Exercise 8-1: an, anbn, anbncn, etc. Hints for Exercise 8-2: How many formal languages can there be? Expected Results Hints for Exercise 8-3: The complementary of a regular language Hints for Exercise 8-4: Implement French and German gender-neutral language 16.9 Chapter 9: Logic Hints for Exercise 9-1: Socrates’ “I know that I know nothing” Hints for Exercise 9-2: Use Prolog for Formal Semantics Expected Results Hints for Exercise 9-3: Prove that Curiosity killed the Cat using Attempto Controlled English, gkc, and RACE Expected Results Hints for Exercise 9-4: The “logical proof of the existence of God” fallacy 16.10 Chapter 10: Ontologies and Conceptual Graphs Hints for Exercise 10-1: Translate DL formulas into Attempto and find counterexamples Expected Results Hints for Exercise 10-2: Write a Q&A system for the Wildlife Ontology Expected Results 16.11 Chapter 11: Unicode Hints for Exercise 11-1: Steganography Using Unicode Combining Characters Expected Results Hints for Exercise 11-2: Southeast-Asian Scripts Implementations in Unicode Expected Results Hints for Exercise 11-3: How do Unicode and Wikipedia deal with simplified and traditional Chinese? Expected Results Hints for Exercise 11-4: Unicode and political correctness in the processing of emoji Expected Results Hints for Exercise 11-5: Curiosa Unicodensis Expected Results 16.12 Chapter 12: XML, TEI, CDL Hints for Exercise 12-1: Jerome K. Jerome’s Three Men on the Bummel in TEI Hints for Exercise 12-2: Find the subject occurrences in Bach’s Fugue BWV 846 Expected Results Discussion of the result Hints for Exercise 12-3: Document conversion from HTML to TEI using SAX and DOM 16.13 Chapter 13: Counting Words Hints for Exercise 13-1: Exploring the Anthology of the Association for Computational Linguistics Expected Results Hints for Exercise 13-2: Find a Cornelian play among nine Racinian plays Expected Results Hints for Exercise 13-3: Test properties of GloVe embeddings Expected Results References Acronyms Index