Seminar (Laura Kallmeyer)
Monday 10.30-12.00, room 23.11.03.22, Tuesday 10.30-12.00, room 23.21.HS 3F.
Start: 17.10.2016. Last session: 07.02.2017.
Course description:
Parsing is a central task in natural language processing. Its goal is to compute the syntactic structures of sentences. Such a syntactic structure could either be a constituency structure or a dependency structure. The former is in many cases taken to be generated by a context-free grammar (CFG). Consequently, constituency parsing amounts to a) implementing/inducing a context-free grammar and b) using this grammar for parsing. Dependency parsing, in contrast to this, is mostly grammar-less parsing using machine-learning techniques.
In this course, we will mainly concentrate on step b) of CFG-based constituency parsing. We will revise various symbolic parsing algorithms that yield, given a CFG and an input sentence, the set of all parse trees for this sentence. In the second half of the course, we will move on to probabilistic parsing, covering Viterbi parsing and weighted deductive parsing with A* estimates.
For references see the slides of the individual sessions.
Schedule and Slides
- 17.10.16 Introduction
- 18.10.16 Context-free grammars (CFG)
- 24.10.16 CFG II
- 25.10.16 Push-Down Automata (PDA) (Example)
- 31.10.16 Unger’s Parser (Example)
- 01.11.16 (holiday)
- 07.11.16 Unger’s Parser II (Example)
- 08.11.16 Top-down Parsing (LL-Parsing). (Example)
- 14.11.16 Parsing as Deduction
- 15.11.16 Parsing as Deduction. (Example)
- 21.11.16 CYK Parsing.
- 22.11.16 Shift Reduce Parsing.
- 28.11.16 LL(1) Parsing
- 29.11.16 LL(1) Parsing.
- 05.12.16 Preparation mid term exam. Sample exercises can be found here.
- 06.12.16 Mid term exam. Any non-electronic material (course slides etc.) is allowed.
- 12.12.16 Left Corner Parsing. (Example)
- 13.12.16 Earley Parsing
- 19.12.16 Earley Parsing II (Example)
- 20.12.16 LR Parsing
- 09.01.17 LR Parsing II. A further example can be found here.
- 10.01.17 Tomita. A further example can be found here.
- 16.01.17 PCFG, Inside and outside, Viterbi. An example for CYK viterbi chart parsing can be found here.
- 17.01.17 Treebank grammars
- 23.01.17 Weighted deductive parsing
- 24.01.17 Weighted deductive parsing (Example)
- 30.01.17 A* parsing
- 31.01.17 A* parsing. An example for computation of outside SX estimates can be found here.
- 06.02.17 Preparation final exam. For preparation, here is the final exam from 2013.
- 07.02.17 Final exam. Any non-electronic material (course slides etc.) is allowed.
Exercises
There are weekly exercises for the course. These exercises are not mandatory but but working on them is a good way to prepare for the exams. The solutions of the exercises will be discussed in the course.
The collection of homework exercises can be found here: Exercises.
Leistungsnachweise
AP: Für eine AP muss in einer Gruppe von zwei Studierenden ein Beispiel zu einem der mit (Example) gekennzeichneten Themen erklät und als Handout ausgearbeitet werden. Daneben ist die Teilnahme an beiden Klausuren Voraussetzung für eine AP. Die Note setzt sich zu gleichen Teilen aus den beiden Klausurnoten zusammen. Für das vorgetragene Beispiel gibt es max. 5 Punkte, die zusätzlich auf die Punkte aus den Klausuren (max. 50 pro Klausur) angerechnet werden können.
BN: Für einen BN muss in einer Gruppe von zwei Studierenden ein Beispiel zu einem der mit (Example) gekennzeichneten Themen erklät und als Handout ausgearbeitet werden. Daneben ist die Teilnahme an beiden Klausuren Voraussetzung, wobei mindestens 50% der Aufgaben sinnvoll bearbeitet werden müssen.