Strukturiertes Praktikum im Sommersemester 2020

​Aktuelle Hinweise: Aufgrund der Verschiebung des Beginns der Präsenzlehrveranstaltungen im Sommersemester 2020 werden die ersten beiden Tutorien (06. und 27. April) durch E-Learning ersetzt! Bitte tragen Sie sich zeitnah in den Opal-Kurs ein, damit wir Sie per E-Mail erreichen können.

Modus für Tutorien:

• Alle benötigten Lerninhalte werden für das Selbststudium aufbereitet auf dieser Seite (unter dem Punkt Materialien) zur Verfügung gestellt.
• An den Terminen der Tutorien wird eine Telefonkonferenz zur Klärung von Fragen durchgeführt.

Modus für die Bearbeitung der Aufgaben:

• Die Aufgaben werden bis zur jeweiligen Deadline zu Hause bearbeitet (die PC-Pools sind gesperrt).
• Fragen können telefonisch oder per E-Mail geklärt werden (siehe Kontakt).

Überblick

In der Vorlesung Formale Systeme wurden kontextfreie Grammatiken als Modell zur Beschreibung formaler Sprachen eingeführt. Ziel dieses Praktikums ist die Anwendung kontextfreier Grammatiken in der natürlichen Sprachverarbeitung. Dazu werden wir aus Trainingssätzen eine Grammatik für die englische Sprache induzieren und einen Parser implementieren, der mithilfe dieser Grammatik Eingabesätze in ihre syntaktische Struktur zerlegt. Weiterhin werden wir verschiedene Methoden zur Verbesserung der Genauigkeit und der Laufzeit des Parsers untersuchen. Am Ende werden die genauesten und schnellsten Parser der Praktikumsteilnehmer in einem Wettbewerb gekürt.

Das Praktikum bietet eine Möglichkeit, die in den Vorlesungen Maschinelles Übersetzen natürlicher Sprachen und Parsing von natürlichen Sprachen vermittelten Konzepte am praktischen Beispiel zu vertiefen.

Organisation

Es gibt keine Einschreibung. Der Ablaufplan enthält alle relevanten Informationen:

• Einbringungsmöglichkeiten des Praktikums und Voraussetzungen,
• Teilaufgaben und deren Aufgabenstellungen,
• Termine der Tutorien und Abgabetermine der Teilaufgaben sowie
• die Dokumentation der erwarteten Kommandozeilenschnittstelle.

Solange keine Präsenzlehrveranstaltungen stattfinden, erfolgt die Aneignung des benötigten Wissens im Selbststudium und die Bearbeitung der Aufgaben von zu Hause aus. Zu den Terminen der Tutorien wird eine Telefonkonferenz durchgeführt, in der Fragen zu den Lerninhalten und den Aufgaben besprochen werden können. Die Plattform wird im OPAL-Kurs (nur für Eingeschriebene!) bekannt gegeben. Individuelle Fragen zu Ihrer Implementierung können Sie telefonisch oder per E-Mail stellen (siehe Kontakt).

Nach Wiederaufnahme der Präsenzlehrveranstaltungen steht wöchentlich am Montag in der 3. und 4. Doppelstunde der Raum APB/E067 für die Bearbeitung der Aufgaben zur Verfügung. Fragen können Sie dann vor Ort oder weiterhin per E-Mail stellen. Das benötigte Wissen wird in den entsprechenden Tutorien vermittelt. Die Anwesenheit zu diesen Tutorien ist Pflicht.

Materialien

An dieser Stelle werden Ihnen die Materialien zum Selbststudium und weitere für das Praktikum benötigte Daten zur Verfügung gestellt. Der Zugriff auf die verlinkten Ressourcen ist ausschließlich im Netz der TU Dresden möglich. Informationen zur Verwendung von VPN finden Sie hier.

Sprachmodellierung mit probabilistischen kontextfreien Grammatiken (PCFG)

Als Grundlage für das Selbststudium dient folgendes Kapitel über PCFG (in englischer Sprache). Eine formale Einführung in die Modellierung natürlicher Sprache mit PCFG bieten die Seiten 69 bis 74.

Die folgende Skizze dient als Überblick über das im Verlauf des Praktikums entwickelte Tool und den Funktionsumfang der Teilaufgaben.

Aufgabe 1: Grammatikinduktion

Die Seiten 74 bis 76 geben zunächst eine formale Einführung in die Induktion einer PCFG aus einem Trainingskorpus. Dabei zeigt Abbildung 13.4 das Format eines annotierten Satzes im verwendeten Korpus. Bitte beachten Sie, dass in den Daten, die im Praktikum verwendet werden, ein annotierter Satz immer auf einer Zeile gespeichert wird.

Das algorithmische Vorgehen bei der Grammatikinduktion wird in einem Foliensatz (in englischer Sprache) veranschaulicht. Dieser gibt auch Hinweise für die Implementierung.

Aufgabe 2: Parser

Das Parsingproblem für PCFG wird formal auf Seite 80 definiert. Es besteht die Wahl, einen CYK-Parser (auch: CKY-Parser) oder einen deduktiven Parser zu implementieren. Der CYK-Algorithmus ist aus der Vorlesung Formale Systeme bekannt, für eine Wiederholung sei auf die Vorlesungsmaterialien verwiesen. Die Adaption des CYK-Algorithmus und deduktiven Parsings für unseren Anwendungsfall werden in einem Foliensatz (in englischer Sprache) illustriert.

Aufgabe 3: Korpustransformationen

In der dritten Aufgabe werden zwei praktische Probleme behandelt. Zum Einen kann der CYK-parser nur mit binarisierten Grammatiken parsen, unsere Trainingsdaten müssen also binarisiert werden. Zum Anderen kann der Parser aus Aufgabe 2 nicht mit unbekannten (d.h. während des Trainings nicht gesehenen) und seltenen Wörtern umgehen. Der Foliensatz (in englischer Sprache) illustriert die Probleme und zeigt Algorithmen in Pseudocode mit Beispieldurchläufen. Bitte beachten Sie, dass nicht alle aufgeführten Funktionen implementiert werden müssen, da einige in den Wahlpflichtbereich fallen.

Aufgabe 4: Parseroptimierungen

Der Foliensatz (in englischer Sprache) stellt zwei Möglichkeiten vor, die Laufzeit des Parsers zu verringern: Pruning und A★-Suche. Dabei ist A★-Suche allein nur für deduktive Parser anwendbar, bei CYK-Parsern ist sie nur in Kombination mit Pruning sinnvoll. Die Genauigkeit des Parsers wird durch k-best-Parsing adressiert, in dem nicht mehr nur der beste, sondern mehrere beste Parsebäume zurückgegeben werden. Bitte beachten Sie, dass alle drei Teilaufgaben Wahlpflicht sind. In Kombination mit den Wahlpflichtaufgaben aus Aufgabe 3 muss mindestens eine Parseroptimierung implementiert werden.

Korpora

Als Trainings- und Testkorpus dienen annotierte Sätze des Wall Street Journals aus der Penn Treebank. Diese werden hier in aufbereiteter Form zur Verfügung gestellt. Bitte beachten Sie, dass die Lizenz der TU Dresden über die Nutzung der Penn Treebank Sie nicht zur Weitergabe dieser Daten berechtigt.

Die Daten sind wie folgt unterteilt:

training.mrg

Trainingskorpus (annotierte Sätze) für die Grammatinduktion.

grammar.rules, grammar.lexicon, grammar.words

Beispielgrammatik (binarisiert) für den Parser.

testsentences

Beispielsätze (i.e., Testkorpus) für den Parser.

gold.mrg

Gold-Parsebäume = annotierte Sätze des Testkorpus (nicht binarisiert, können also nicht zur Parser-Ausgabe passen!).

gold_b.mrg

Binarisierte Gold-Parsebäume.

Evaluation des Parsers (F1-Score)

Die vom Parser ausgegebenen Bäume stimmen im Normalfall nicht mit den Goldbäumen überein. Die Güte des Parsers wird daher über den F1-Score bestimmt, der z.B. mit discodop bestimmt werden kann:

discodop eval --fmt=bracket <DATEI MIT GOLDBÄUMEN> <DATEI MIT PARSEBÄUMEN>

Arbeitsumgebung

Die Strukturierung der Implementierung und die Wahl der verwendeten Tools ist Ihnen freigestellt. Es gelten lediglich die folgenden Anforderungen, um ein automatisches Testen zu ermöglichen.

• Das Arbeitsverzeichnis enthält auf oberster Ebene eine Datei namens Makefile. Diese enthält ein Target, das eine ausführbare Datei pcfg_tool erstellt. Eine weitergehende Einführung in Make gibt es z.B. hier.
• Das Programm pcfg_tool enthält die Lösungen zu allen Teilaufgaben. Einzelne Funktionen werden über Subkommandos aufgerufen (wie bei git). Ist eine Funktion nicht implementiert, soll das Programm mit dem Statuscode 22 beendet werden. Alles weitere zur Kommandozeilenschnittstelle steht im Ablaufplan.
• Keine Datei auf der obersten Ebene des Arbeitsverzeichnisses beginnt mit .eval_.

Sie können selbst überprüfen, ob Ihre Implementierung die Spezifikationen hinsichtlich Ein- und Ausgabeformat erfüllt. Dazu entpacken Sie die folgende Testsuite in Ihr Arbeitsverzeichnis und rufen make -f tests.mk auf. Bitte stellen Sie vor Einreichung einer Teillösung sicher, dass diese Tests erfolgreich durchlaufen. Hinweis: die Tests überprüfen nicht die Korrektheit der Implementierung.

Kontakt

• Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
  Heiko Vogler
  Tel.: +49 (0) 351 463-38232
• Dipl.-Inf. Richard Mörbitz
  Tel.: +49 (0) 351 463-38487