Parsing Discontinuous Structures

Abstract

The development of frameworks that allow to state grammars for natural languages in a mathematically precise way is a core task of the field of computational linguistics. The same holds for the development of techniques for finding the syntactic structure of a sentence given a grammar, parsing. The focus of this thesis lies on data-driven parsing. In this area, one uses probabilistic grammars that are extracted from manually analyzed sentences coming from a treebank. The probability model can be used for disambiguation, i.e., for finding the best analysis of a sentence.

In the last decades, enormous progress has been achieved in the domain of data-driven parsing. Many current parsers are nevertheless still limited in an important aspect: They cannot handle discontinuous structures, a phenomenon which occurs especially frequently in languages with a free word order. This is due to the fact that those parsers are based on Probabilistic Context-Free Grammar (PCFG), a framework that cannot model discontinuities.

In this thesis, I propose the use of Probabilistic Simple Range Concatenation Grammar (PSRCG), a natural extension of PCFG, for data-driven parsing. Thereby, I bring together developments from different areas, namely research on parsing German, on the quantification of discontinuity in treebanks, and on formalisms which can model discontinuous structures. Not only theoretical aspects are treated. For the first time, all techniques for direct data-driven parsing of discontinuities have been implemented and tested in a real-world data-driven parsing setting. The parser output quality and the parsing speed are encouraging and prove the point of this work: An exploration of the landscape of formal grammars beyond Context-Free Grammar with regard to data-driven parsing is worth the effort for data-driven parsing and opens the way for many new developments in the future, both in parsing and beyond.

Die Entwicklung formaler Systeme für die mathematisch präzise Formulierung einer Grammatik der natürlichen Sprache ist eine Kernaufgabe der Computerlinguistik. Dasselbe gilt für die Entwicklung von Techniken für die Berechnung der syntaktischen Struktur eines Satzes auf Basis einer Grammatik, Parsing. In dieser Dissertation steht das datengetriebene Parsing im Vordergrund. Dabei werden von den manuell annotierten Sätzen einer Baumbank extrahierte probabilistische Grammatiken benutzt. Das Wahrscheinlichkeitsmodell kann zur Disambiguierung benutzt werden, d.h. zur Berechnung der besten Analyse für einen gegebenen Satz.

In den vergangenen Jahrzehnten wurden in der Forschung zu datengetriebenem Parsing enorme Fortschritte erzielt. Nichtsdestotrotz sind viele aktuelle Parser weiterhin in einem wichtigen Aspekt beschränkt: Sie können nicht mit diskontinuierlichen Strukturen umgehen, einer Art von Strukturen die besonders in Sprachen mit freier Wortstellung häufig auftritt. Der Grund hierfür ist, dass diese Parser auf Probabilistischer Kontextfreier Grammatik aufbauen, welche Diskontinuitäten nicht modellieren kann.

In dieser Dissertation plädiere ich für die Benutzung von Probabilistic Simple Range Concatenation Grammar, einer natürlichen Erweiterung der Probabilistischen Kontextfreien Grammatik, für datengetriebenes Parsing. Ich führe damit Entwicklungen aus verschiedenen Bereichen zusammen: Forschung zum Parsing des Deutschen, zur Quantifizierung von Diskontinuität in Baumbanken, und zu Formalismen, die diskontinuierliche Strukturen modellieren können. Nicht nur theoretische Aspekte werden behandelt. Zum ersten Mal wurden alle Techniken, die für direktes datengetriebenes Parsing von Diskontinuitäten benötigt werden, implementiert und auf einem realistisch großen Datensatz getestet. Die Qualität der Parserausgabe und die Parsinggeschwindigkeit sind ermutigend und sprechen für den Ansatz dieser Arbeit: Eine Erforschung der Landschaft der formalen Grammatiken jenseits der Kontextfreien Grammatik lohnt sich für das datengetriebene Parsing und ebnet den Weg für viele Entwicklungen in der Zukunft, im Parsing, und darüber hinaus.