Dependency Parsing (Summer 2021)

General Information

Instructors: Kilian Evang
Jakub Waszczuk
Lectures: Tuesday, 14:30 – 16:00, online
Labs: Friday, 10:30 – 12:00, online
Rocket.Chat channel:
Course web page:
(This web page, which will be updated throughout the course.)
Languages: English and German

Course Description

The task of syntactic parsing consists in finding the structure of a natural language sentence. Just as there are two main approaches of representing such structures – namely, constituency- and dependency-based structures – there are also two main approaches of syntactic parsing, adapted to handle constituency trees and dependency graphs, respectively. Since dependency parsing adopts a different view on how structure of languages should be represented, the methods used for dependency parsing are often different from those used for constituency parsing.

Dependency parsing can be performed either using linguistic descriptions (grammars) or using machine learning (data driven). This course presents the methods used in data-driven dependency parsing. These methods fall in two main families, the first one being based on transition systems, the second one on graph theory.



Week 1 Introduction and overview
Exercises (latex template, annotations)
Week 2 Basics of dependency parsing (constituency to dependency conversion example; examples of dependency graph properties)
Exercises (latex template, solutions)
Week 3 Grammar-based approaches to dependency parsing (lecture notes)
Exercises (latex template, solutions)
Week 4 Introduction to data-driven dependency parsing
Exercises (.xlsx template, possible solution)
Week 5

Transition-based dependency parsing (part 1)

Projective shift-reduce (a.k.a. arc-standard) parsing; see also Nivre (2008) for correctness proofs and complexity analysis

Exercises (latex template, solutions)
Week 6

Transition-based dependency parsing (part 2)

Arc-eager parsing, non-projective parsing
Exercises (latex template, solutions)
Week 7

Transition-based dependency parsing (part 3)

Dynamic oracles

Exercises (latex template, solutions)

  • 28.05.2021: Shifted the deadline
Week 8 Implementation of a transition-based parser (part 1)
Exercises (blog post, source code, data, solution)
Week 9 Implementation of a transition-based parser (part 2)
Exercises (solution)
Week 10 Implementation of a transition-based parser (part 3)
Exercises (starter code, solution)
Week 11

Graph-based dependency parsing (part 1)

Chu-Liu-Edmonds’ algorithm
Exercises (solution)
Week 12

Graph-based dependency parsing (part 2)

Eisner algorithm
Exercises (latex source, solution)
Week 13

Graph-based dependency parsing (part 3)

Beyond arc-factored models Dependency parsing in the neural age
Exercises (solution)
Week 14 Revision for the exam
Exercises from previous years
Week 15 Mock exam
Online exam
Leitfaden zur Durchführung von Online-Klausuren
The exam is an open book exam, i.e., all course materials, published papers, textbooks, etc., may be used. It is not permitted for participants to communicate with each other during the exam. It is not permitted to use interactive resources such as online parsing GUIs.
The exam questions will be posed in English. You can answer them in English or German.
If you need a work station at uni for the online exam, please email me ASAP!


Thanks to Simon Petitjean, Andreas van Cranenburgh, and Rafael Ehren for providing their teaching materials, as well as to Sandra Kübler, Ryan McDonald, and Joakim Nivre, authors of the various tutorials (ACL 2006, ESSLLI 2007, EACL 2014) on which this course is based.