Language Processing
with Perl and Prolog

Book description

Table of contents [pdf]

Index [pdf]

Slides, programs, and links

Sample chapters

Additional chapter

Errata

The EDAN20 course at Lund University--LTH

Language technology at LTH

Language Processing with Perl and Prolog

by Pierre Nugues
Second edition: August 2014
Pages: 662
Published by Springer

Slides, Programs, and Links

Table of contents

Ch. 1: An overview of language processing Ch. 2: Corpus processing tools Ch. 3: Encoding and annotation schemes Ch. 4: Topics in information theory and machine learning Ch. 5: Counting words Ch. 6: Words, parts of speech, and morphology Ch. 7: Part-of-speech tagging using rules Ch. 8: Part-of-speech tagging using stochastic techniques Ch. 9: Phrase-structure grammars in Prolog

Ch. 10: Partial parsing Ch. 11: Syntactic formalisms Ch. 12: Constituent parsing Ch. 13: Dependency parsing Ch. 14: Semantics and predicate logic Ch. 15: Lexical semantics Ch. 16: Discourse Ch. 17: Dialogue App. A: An introduction to Prolog

^Chapter 1: An overview of language processing [pdf]

• Contents: Presentation of language processing, applications, disciplines of linguistics
• Chapter slides: [pdf].
• Application examples:
  • Watson from IBM: Question answering on Jeopardy!, a footage from the show, and an overview.
  • Carsim from LTH
  • Direkt Profil from Lund university
  • The Persona project from Microsoft Research
  • A video of Higgins
  • a video of Ulysse.
• General resources:
  • Wikipedia
  • ACL anthology
  • Natural language software registry
• Research opportunities:
  • Companies: Microsoft research, Research at Google, IBM research, Yahoo Research, Xerox research center.
  • Lists: Corpora, ELSNET, LN
• Associations: ACL, ATALA, GSCL.

^Chapter 2: Corpus processing tools [pdf]

• Contents:
  • Regular expressions
  • Automata
  • An introduction to Perl
  • Concordances
  • Approximate string matching
• Chapter slides [pdf].
• Programs:
  • An elementary automaton in Prolog [1]
  • Short programs in Perl to illustrate regular expressions and pattern matching [2] [3] [4] [5] [6] [7] [8] [9]
  • Concordances in Perl [10]
  • Minimum edit distance in Perl [11]
  • Searching edits in Prolog [12]
  • A concise and elegant spelling corrector in Python by Peter Norvig and a variation of it in Prolog: Spelling corrector in Prolog.
• Corpora:
  • Corpus thomisticum, the first electronic corpus compiled by Roberto Busa.
  • A modern concordance to the Clementine Vulgate.
  • The Oxford text archive, Centre National des Ressources Textuelles et Lexicales, Project Gutenberg, the Internet archive, the Runeberg project, Gallica.
• Demonstrations:
  • Regex 101, an online regex tester.
  • Concordances and collocations:
    • Corpus thomisticum
    • Many corpora from Brigham-Young, such as the corpus of contemporary American English, Språkbanken, CNRTL.
    • Google, one of the largest concordancers to date.
• Software:
  • FSA, finite state automata utilities in Prolog
  • OpenFst, a library for constructing weighted finite-state transducers in C++
  • FSM library from AT&T Labs
• Documents:
  • Interesting tutorials by Ken Church
  • Another interesting paper on an algorithm to align words for historical comparison by Michael Covington

^Chapter 3: Encoding and annotation schemes [pdf]

• Contents:
  • Character sets and Unicode
  • Mark-up languages and XML
• Chapter slides: [pdf].
• Resources:
  • Unicode: the Unicode consortium and international components for Unicode
  • XML: the XML site at W3C
  • XML in text processing: The Text encoding initiative, DocBook, the International Digital Publishing Forum.

^Chapter 4: Topics in information theory and machine learning [pdf]

• Contents:
  • Topics in information theory
  • Entropy and decision trees
  • Using Weka, a popular machine learning toolkit
• Chapter slides: [pdf].
• Resources:
  • Machine-learning software:
    • C4.5, ID3's successor, by Ross Quinlan
    • Weka, a comprehensive data mining software in Java
    • LIBSVM, an efficient implementation of support vector machines.
    • LIBLINEAR, a library for large linear classification.
  • Courses on machine learning:
    • At Stanford: CS229
    • At Carnegie Mellon: 10-701
    • An interesting blog: Mechanistician

^Chapter 5: Counting words [pdf]

• Contents:
  • Tokenization
  • N-grams
  • Counting words and N-grams
  • Probability of a word sequence
  • Smoothing
  • Collocations and other statistics
• Chapter slides: [pdf].
• Perl programs:
  • A simple tokenizer [1] and a more complex one by Gregory Grefenstette [2]
  • Another popular tokenizer by Robert MacIntyre, original version in sed [3] and its translation in Perl [4]
  • Counting unigrams [5] and bigrams [6]
  • Mutual information [7], t-scores [8], and the log-likelihood ratio [9].
• Demonstrations:
  • A collocation demo from from the Corpus Linguistics group at FAU Erlangen-Nürnberg.
• Software and resources:
  • N-grams at Google Research and N-grams at Microsoft Research.
  • A journalist's account from wired.com on how Google uses bigrams in its search engine.
  • The SRI language modeling toolkit
  • The CMU-Cambridge statistical language modeling toolkit

^Chapter 6: Words, parts of speech, and morphology [pdf]

• Contents:
  • Dictionaries
  • Morphology
  • Transducers
• Chapter slides: [pdf]
• Additional slides on the Prolog language [pdf].
• Prolog programs:
  • Building and searching a letter tree (trie) [1]
  • A transducer modeling the future tense of regular French verbs [2].
• Grammar resources and history:
  • Tecknè, the first grammar of Greek, by Dionysius Thrax, who created concepts we still use today
  • De partibus orationis ars minor , the most popular grammar in the west in the Middle ages by Aelius Donatus
  • An introduction to the grammar of English from University College London.
• Software:
  • PC-Kimmo, a morphological parser from the Summer Institute of Linguistics.
  • The Helsinki Finite-State Transducer software, a toolkit to implement morphological parsers based on weighted and unweigted finite-state transducers.
  • Unitex, a corpus processing system using automata and transducers from Université de Marne-la-Vallée
• Demonstrations:
  • The Xerox site on multilingual content analysis.
  • The Swedish morphological parser from Lingsoft
  • The German morphological parser from Canoo.

^Chapter 7: Part-of-speech tagging using rules [pdf]

• Contents:
  • Part-of-speech tagging with symbolic rules
  • Annotation standards for parts of speech (tagsets)
• Chapter slides: [pdf].
• Annotation manuals and corpora:
  • Manuals used by the Penn treebanks
  • BNC, the British national corpus, an annotated corpus in English following the text encoding initiative (TEI).
  • SUC, the Stockholm-Umeå corpus, an annotated corpus in Swedish
  • Negra, an annotated corpus in German
  • An inventory of available corpora compiled by a group at Stanford.
• Software:
  • The historical Brill's tagger in Lisp.
  • An implementation of Brill's tagger in C++ by Radu Florian.

^Chapter 8: Part-of-speech tagging using stochastic techniques [pdf]

• Contents:
  • Stochastic tagging
  • Markov models
  • Tagging with decision trees
  • Application: Language models for machine translation
• Chapter slides: [pdf].
• Demonstrations:
  • The Xerox site on multilingual content analysis.
  • Demonstrations from Universitat politècnica de Catalunya.
  • GRIM from the KTH.
• Software:
  • The historical Xerox tagger based on hidden Markov models in Lisp.
  • TreeTagger, a multiligual tagger using decision trees from Helmut Schmid.
  • MXPOST, an efficient tagger from Adwait Ratnaparkhi.
  • SVMTool, a tagger using support vector machines from Universitat politècnica de Catalunya.
  • A part-of-speech tagger and other tools for Swedish from KTH.
  • Stagger: another part-of-speech tagger for Swedish.
  • GIZA++, a software to train translation models from Franz Josef Och.

^Chapter 9: Phrase-structure grammars in Prolog [pdf]

• Contents:
  • Constituents, trees
  • Using Prolog to do natural language analysis, DCG rules, variables
  • Getting the syntactic structure
  • Compositional analysis to get the semantic structure
• Chapter slides: [pdf]
• Prolog programs:
  • Two small DCG grammars [1] [2]
  • A tokenizer using Prolog clauses [3] and another one using DCG rules [4].
  • A small interpreter of regular expressions in Prolog by Robert Cameron [5].
• Application examples:
  • The grammar checker in MS Word whose parser uses phrase-structure rules.
  • The natural language group at Microsoft Research.

^Chapter 10: Partial parsing [pdf]

• Contents:
  • ELIZA: word spotting and pattern matching
  • Multiwords and named entities
  • Noun groups and verb groups
  • Partial parsing: multiword and group detection in Prolog
  • Partial parsing: statistical techniques
  • Information extraction
  • Precision, recall, and F-measure (harmonic mean)
• Chapter slides: [pdf]
• Prolog programs:
  • Prolog predicates to write local DCG grammars with simple noun group and verb group rules [1].
• Documents:
  • Many interesting papers on partial parsing by Steven Abney;
  • An application example of information extraction: the FASTUS system from SRI.
  • Carsim, a system to generate animated 3D scenes from text that uses information extraction techniques.
• Annotated corpora and evaluation resources:
  • CoNLL-2002 and CoNLL-2003 on language-independent named entity recognition: Spanish, Dutch, English, and German.
  • CoNLL-2000 on chunking and CoNLL-1999 on noun phrase chunking
  • CoNLL-2001 on clause identification
• Demonstrations:
  • CiceroLite, a system to extract named entities
  • AlchemyAPI, a system to identify people, organizations, locations, and categorize text
  • Calais, an information extraction system
  • Visualizing and monitoring events and disasters on a map at EMM labs, part of the Europe media monitor. A key to the symbols used is available from this page. See also their name explorer.
• Software:
  • Yamcha, an efficient chunker
  • The Stanford named entity recognizer from Stanford University
  • The Illinois named entity tagger from the University of Illinois
• Annotation resources:
  • The MUC site;
  • PEAS, a group annotation scheme for French
  • TüPP-D/Z, Tübingen Partially Parsed Corpus of Written German

^Chapter 11: Syntactic formalisms [pdf]

• Contents:
  • Constituency and dependency
  • Phrase categories
  • Unification-based grammars
  • Dependency grammars
  • Valence and subcategorization frames
  • Functions
• Chapter slides: [pdf]
• Prolog programs:
  • Some simple DCG rules for German noun phrases [1]
  • The generalized unification [2].
  • Detection of nonprojective links in a dependency tree [3] and examples of graphs [4].
  • A program to convert the CONLL-X file format into a Prolog clause [5]. Useful with the nonprojectivity detection.
• Corpus and programming resources:
  • Four freely available annotated dependency corpora, Danish, Dutch, Portuguese, and Swedish, and links to seven others from the CONLL-X shared task.
  • The Susanne corpus, a free treebank for English.
  • A French treebank from Université Paris VII (Available with a license).
  • Tables lexique-grammaire , subcategorization frames in French available from Université de Marne-la-Vallée.
  • The LTH converter to convert constituent trees using the Penn Treebank annotation into dependency graphs.
• Lexical and grammar resources:
  • A grammar for Swedish from Gunilla Colliander.
  • The Oxford Advanced Learner's Dictionary, a dictionary listing valence patterns of English verbs.
• Annotation resources:
  • A dependency annotated corpus in Swedish from Joakim Nivre
  • What's wrong with my NLP, a visualizer of dependency graphs using the CoNLL formats.
  • A guide to annotate dependencies for Danish from Handelshøjskolen i København, (Copenhagen Business School).

^Chapter 12: Constituent parsing [pdf]

• Contents:
  • Top-down and bottom-up strategies
  • The shift-reduce algorithm
  • Earley's algorithm
  • Statistical parsing and PCFG
• Chapter slides: [pdf]
• Prolog programs:
  • A shift-reduce parser [1]
  • Earley's parser [2]
• Corpus resources:
  • The Susanne corpus, a free treebank for English
  • A French treebank from Université Paris VII (Available with a license)
• Parsers resources:
  • The Charniak parser (From Eugene Charniak's web page)
  • The Collins parser (Michael Collins' web page)
• On-line parsers:
  • The Berkeley parser
  • Stanford parser

^Chapter 13: Dependency parsing [pdf]

• Contents:
  • Dependency parsing
  • Nivre's parser
• Chapter slides: [pdf]
• Prolog programs:
  • Joakim Nivre's dependency parser [3].
  • Updates to the book:
    • Nivre's parser to parse an annotated corpus (gold standard parsing) [4] and an improved version of Nivre's parser [5].
    • Utilities to parse a CoNLL 2006 or 2007 corpus [6] [7] [8].
    • The Swedish corpus used in CoNLL 2006 and formatted as a Prolog clause. Training set [9] and test set [10].
• Corpus resources:
  • Four freely available annotated dependency corpora, Danish, Dutch, Portuguese, and Swedish, and links to 7 others from the CoNLL-X shared task. Seven other corpora with the same annotation, Basque, Catalan, Chinese, Greek, Hungarian, Italian, and Turkish, from the CoNLL 2007 shared task.
• Parsers resources:
  • Joakim Nivre's web page and the Malt parser
  • Ryan McDonald's web page
  • The CONLL-X and CONLL-2007 shared tasks on dependency parsing covering a total of 19 languages.
• On-line parsers:
  • Connexor
  • Lingsoft
  • Link grammar
  • Stanford parser

^Chapter 14: Semantics and predicate logic [pdf]

• Contents:
  • Formal semantics
  • λ-calculus
  • Compositionality: nouns, verbs, determiners
• Chapter slides: [pdf]
• Prolog programs:
  • A small grammar embedding compositionality [1]
• Corpus resources:
  • A corpus of logical forms from the natural language group at Microsoft research
• Application examples:
  • Semantic interpretation for speech recognition (SISR): A W3C recommendation to embed semantic annotation into grammar rules.
  • Translation projects by the natural language group at Microsoft Research.

^Chapter 15: Lexical semantics [pdf]

• Contents:
  • Words and meaning
  • Lexical semantics
  • Lexical networks
  • Word sense disambiguation
  • Case grammars
  • Frame semantics and semantic roles
  • Semantic grammars
• Chapter slides: [pdf]. Anders Björkelund's presentation of his thesis on semantic role labeling [pdf].
• Resources:
  • Lexical databases:
    • WordNet from Princeton.
    • Alexandria from Memodata.
  • Sense identification:
    • SemCor, the Brown corpus tagged with Wordnet senses. This was originally done at Princeton with WordNet 1.6. In the meantime, WordNet people reorganized the sense nomenclature. The different corpora are mappings according to WordNet sense versions
  • Semantic role labeling:
    • FrameNet from Berkeley.
    • The ACE project and the Propbank annotation guidelines.
    • The Unified verb index merging FrameNet, VerbNet, and PropBank from the University of Colorado.
    • CONLL-2004 and CONLL-2005 on semantic role labeling.
    • CONLL-2008 and CONLL-2009 on joint learning of syntactic and semantic dependencies.
  • Semantic role labeling software:
    • A demonstration of the LTH semantic parser and its source code. (CoNLL 2009 version).
    • The LTH semantic parser code with Propbank and Nombank predicates from Richard Johansson (CoNLL 2008 version).
    • The LTH semantic parser with the Framenet paradigm from Richard Johansson.
    • The ASSERT Automatic Statistical SEmantic Role Tagger from Sameer Pradhan.
    • Semantic role labeling by the University of Illinois at Urbana-Champaign.
    • Open information extraction, a system to extract predicate--argument structures from web pages.
    • The Senna semantic role-labeling tool from the NEC Laboratories America.

^Chapter 16: Discourse [pdf]

• Contents:
  • Discourse definition,
  • Discourse entities
  • Reference and anaphora
  • Rhetorical structure theory (RST)
  • Parsing a text
  • Machine learning to discover RST relations
  • TimeML
• Chapter slides: [pdf]
• Annotation and evaluation resources:
  • The coreference annotation manual used in MUC-7 by Hirschman and Chinchor.
  • A paper on coreference evaluation by Vilain et al. (1995).
  • An annotation manual for Rhetorical structure theory from the University of Southern California's Information Sciences Institute.
  • Another annotation manual for the Penn Discourse Treebank.
  • TimeML, markup language for temporal and event expressions.
• Corpus resources:
  • Entity databases: Freebase, DBpedia, and Yago
  • CONLL-2011 and CONLL-2012 on modeling unrestricted coreference in OntoNotes.
  • A RST annotated corpus in German from the University of Postdam. Available on request.
  • TimeBank, a TimeML annotated corpus.

^Chapter 17: Dialogue [pdf]

• Contents:
  • Dialogue automata
  • Pairs
  • Speech acts
  • Speech act recognition
• Chapter slides: [pdf]
• Resources:
  • DAMSL, Dialogue markup scheme from the University of Rochester.
  • Dialogue acts in Verbmobil and Verbmobil-2 [1] [2].
  • The TRAINS corpus and annotated files from the University of Rochester.
• VoiceXML, a markup framework to develop dialogue applications:
  • The VoiceXML official page
  • Java VoiceXML, an open source implementation of VoiceXML.
• Application examples:
  • TRAINS, TRIPS.
  • A train information system in Swedish from SJ. Call 0046 771-75-75-75.
  • A paper by Johan Boye, Mats Wirén, Manny Rayner, Ian Lewin, David Carter, and Ralph Becket, "Language-Processing Strategies and Mixed-Initiative Dialogues", IJCAI-99 Workshop on Knowledge and Reasoning in Practical Dialogue Systems, July 1999.

^Appendix A: An introduction to Prolog [pdf]

• The slides of this chapter [pdf].
• Documents:
  • Alain Colmerauer's web page with papers on Prolog and its history. The teaching section of his page includes an excellent tutorial to Prolog IV.
  • ISO Prolog.
• Prolog compilers and environments:
  • SWI Prolog, an outstanding free Prolog.
  • YAP, a high-performance Prolog.
  • tuProlog, a Java, Android compatible Prolog. [source]
  • SICSTUS Prolog, a commercial Prolog.

Institutionen för Datavetenskap 2014. Ansvarig: Pierre Nugues
Last update: Thursday, 17-Dec-2020 13:47:00 CET