Seminar "Parsingformalismen für natürliche Sprachen"

Karl-Michael Schneider

(Zeit, Raum)

Inhalt | Ausrichtung und Vorkenntnisse | Scheinerwerb | Themen für Referate | Bibliografie | Folien | Software und Links

Inhalt

Das Seminar "Parsingformalismen für natürliche Sprachen" behandelt Parsingverfahren für Grammatikformalismen und Grammatiktheorien, die im Bereich der natürlichen Sprache eine Rolle spielen. Diese stammen aus zwei Bereichen:

• linguistisch motivierte Grammatikformalismen, d.h. Grammatikformalismen und Grammatiktheorien, die in der Linguistik und theoretischen Computerlinguistik zur Beschreibung der syntaktischen Struktur von natürlichen Sprachen verwendet werden. Dazu gehören unter anderem:
  • unifikationsbasierte Grammatikformalismen: LFG, GPSG, HPSG, PATR
  • schwach kontextsensitive Grammatikformalismen: TAG, LIG, CCG
  • Prinzipien- und Paramtertheorien: GB
  • Minimalist Grammar
• Grammatikformalismen, die vorwiegend bei der maschinellen Sprachverarbeitung eingesetzt werden. Dies sind vor allem Grammatikformalismen, die eine Wahrscheinlichkeitsverteilung über der Menge der möglichen Satzstrukturen definieren, wie Probabilistic Context-Free Grammars (PCFG) und Probabilistic Dependency Grammars.

Zu Beginn des Seminars werden einige Grundlagen des Parsings behandelt (Chart-Parsing, Parsingschemata).

"Parsingformalismen für natürliche Sprachen" kann als Ergänzung des Seminars "Grammatikformalismen für natürliche Sprachen" vom WS 2001/2002 angesehen werden, in welchem die meisten der oben genannten Grammatikformalismen vorgestellt wurden.

Ausrichtung und Vorkenntnisse

Das Seminar richtet sich hauptsächlich an Studierende im Hauptstudium mit Hauptfach Informatik/Nebenfach Linguistik oder Hauptfach Linguistik (Magister)/Nebenfach Informatik. Informatikstudierende mit anderen Nebenfächern sowie Studierende anderer Fakultäten sind ebenfalls willkommen, sofern Sie einen gewissen Sinn für formale Methoden und algorithmische Verfahren besitzen.

Kenntnisse in linguistischen Grammatiktheorien (z.B. durch Besuch des Seminars "Grammatikformalismen für natürliche Sprachen") werden vorausgesetzt; Grundkenntnisse in formalen Sprachen (z.B. Grundlagen der Informatik I) sind vorteilhaft.

Scheinerwerb

Scheine (Leistungsnachweise) können durch Halten eines Referats und Anfertigen einer Hausarbeit über das Thema des Referats erworben werden. Referate müssen unter Angabe des Themas bei mir angemeldet werden (mündlich oder per E-Mail). Einzelne Themen können schon vergeben sein.

Themen für Referate

Als mögliche Themen kommen in Frage (Vorschläge für alternative Themen sind erlaubt):

• Parsingalgorithmen für Baumadjunktionsgrammatiken (TAG) [Bibliografie] und lineare Indexgrammatiken (LIG) [Bibliografie] (*) (**)
• Parsing von kombinatorischen Kategorialgrammatiken (CCG) [Bibliografie]
• Parsing von Minimalist Grammars [Bibliografie] (*)
• Parsing von Prinzipien- und Parametertheorien (prinzipienbasiertes Parsen, GB-Parsing) [Bibliografie]
• LFG-Parsing [Bibliografie]
• HPSG-Parsing [Bibliografie]
• Alternativen zu direktem HPSG-Parsing: Übersetzung in TAG, kontextfreie Approximation [Bibliografie]
• probabilistisches (PCFG-) Parsing [Bibliografie]

(*) Für die Beschreibung von Parsingalgorithmen für TAG, LIG und Minimalist Grammars werden Kenntnisse über Chart-Parsing (tabellenbasiertes Parsen) und Parsingschemata benötigt, die zu Beginn des Seminars vermittelt werden.

(**) TAG und LIG und deren Parsingalgorithmen hängen eng miteinander zusammen; dieses Thema kann auch von zwei Teilnehmern (als Team) behandelt werden.

Bibliografie

Die Bibliografie enthält nur solche Publikationen zu den einzelnen Grammatikformalismen, die sich mit Parsing befassen. Die meisten der angegebenen Veröffentlichungen sind im Internet verfügbar. Nicht parsingrelevante Veröffentlichungen finden sich in der Bibliografie zum Seminar Grammatikformalismen für natürliche Sprachen.

Folien

Zum Betrachten der PDF-Folien braucht man den Adobe Acrobat Reader. Zum Drucken sollten die PostScript-Folien verwendet werden, da die PDF-Folien viele Animationen verwenden. Einige (wenige) animierte Folien sind nicht als PostScript-Folien verfügbar.

• Inhalt [Druckversion]
• Teil 1: Einführung [Druckversion]
• Teil 2: Tabulares Parsen
  • Chart-Parsing [Druckversion]
  • Parsingschemata [Druckversion]
  • Earley-Parsing [Druckversion]
  • Left-Corner-Parsing [Druckversion]
  • Push-Down Automaten [Druckversion]
  • Zusammenfassung [Druckversion]
• Teil 3: TAG- und LIG-Parsing
  • MCSL, TAG, LIG, Kodierung von TAG in LIG [Druckversion]
  • Head-Corner-Parsing, Bottom-up LIG-Parsing, Bottom-up TAG-Parsing [Druckversion]
• Teil 4: Parsing von Unifikationsgrammatiken
  • Merkmalsstrukturen [Druckversion]
  • Constraints und Modelle [Druckversion]
  • Unifikationsgrammatiken [Druckversion]
  • Parsebäume und Sprache [Druckversion]
  • Parsing von Unifikationsgrammatiken [Druckversion]
• Teil 5: CCG-Parsing
  • Kombinatorische Kategorialgrammatiken (CCG) [Druckversion]
  • Bottom-up Parsing von CCG [Druckversion]
  • Kodierung von CCG in LIG [Druckversion]

Software und Links

Zu vielen der behandelten Grammatikformalismen existieren Implementationen von Entwicklungswerkzeugen und Parsern, die frei im Internet verfügbar sind. Teilnehmer des Seminars werden ausdrücklich ermuntert, sich diese Software zu besorgen und damit zu experimentieren, um ein besseres Verständnis für die Methoden und die praktische Anwendbarkeit zu bekommen. Hier sind einige relevante Links (Ergänzungen werden gerne entgegengenommen):

• Pstone, context-free parser package for education
• XTAG, lexicalized tree adjoining grammar development tools
• Grail, theorem prover for categorial logics
• PC-PATR
• Xerox LFG Grammar Writer's Workbench
• XLFG, LFG-parser
• Babel-System, HPSG-Implementation für das Deutsche
• PAPPI, parsing system for the principles-and-parameters framework
• LoPar, parser for head-lexicalised probabilistic context-free grammars
• NLTK (Natural Language Processing Toolkit), Pythonklassen und -module für NLP-Aufgaben
• Linguistic parsing software (principle-based parsers)
• Der Marcus Parser