Constraint-Erfüllung und -Optimierung mithilfe von endlichen Maschinen in der Anwendung des robusten Dependenzparsings

Abstract

Die Arbeit folgt der These, dass der Bereich der Constraint-Verarbeitung und der Bereich der endlichen Techniken ein großes Potenzial haben, sich gegenseitig mit neuen Perspektiven und Möglichkeiten zu bereichern und dass deren Kombination einen echten Mehrwert schafft. Dies betrifft insbesondere das dependenzorientierte Parsing, bei dem viele Forschungsarbeiten individuell auf beiden Seiten existieren.

Das Semiring-basierte Constraint-Erfüllungsproblem wird als Bindeglied zwischen den beiden Bereichen herangezogen. Es wird gezeigt, dass es auf natürliche Weise mithilfe von endlichen Maschinen repräsentiert und gelöst werden kann. Zudem wird es um drei wesentliche Aspekte erweitert: um einen unendlichen Wertebereich, um eine simultane Repräsentation und um globale Constraints. Aufseiten der endlichen Techniken steht hierdurch ein einheitlicher Formalismus zur Verfügung, um weiche Beschränkungen und Propagierungstechniken einzubeziehen. Für die Constraint-Verarbeitung existieren hingegen neue Möglichkeiten, bekannte oder neuartige Probleme anzugehen.

Hierauf aufbauend wird robustes Dependenzparsing im Stil der Weighted Constraint Dependency Grammar über einen erweiterten endlichen Ansatz umgesetzt: Es wird ein Problemzerlegungsansatz zur perfekten Relaxierung vorgestellt, für den verschiedene Problemzerlegungs- und Constraint-Anwendungsstrategien erarbeitet und mit Memoisation kombiniert werden. Es wird gezeigt, wie überlokale Constraints umgesetzt und sowohl Verletzungen als auch Präferenzen während des Problemlösens nachverfolgt werden können. Der Ansatz erlaubt die intensive Einbeziehung nichtprojektiver Strukturen und die Modellierung komplexer linguistischer Phänomene wie Struktur und Koordinationsellipsen, Valenzen und nichtlokale Abhängigkeiten.

Es wird eine handgeschriebene, abdeckungsreiche Grammatik für das Deutsche vorgestellt, die auf regulären prädikatenlogischen Formeln beruht und anhand einer Auswertung eine höhere Parsing-Qualität ermöglicht als die der Weighted Constraint Dependency Grammar. Unhandhabbare Zwischenergebnisse von enormer Größe sind beim Constraint- basierten Parsing mit endlichen Maschinen ein fundamentales Problem. Über Experimente wird dahingegen gezeigt, dass über die hier entwickelten Problemzerlegungs- und Constraint-Anwendungsstrategien zusammen mit der Memoisation eine kompakte Repräsentation von Zwischenergebnissen während des Problemlösens erreicht werden kann.

Der Ansatz bietet viele Anknüpfungspunkte und viel Spielraum für die Einbeziehung datengetriebener und neuronaler Methoden und komplexitätsreduzierender Approximationsstrategien. In diesem Rahmen ist ein leistungsstarkes hybrides neurosymbolisches Parsing-System somit in greifbarer Nähe.

This thesis follows the working hypothesis that the field of constraint processing and that of finite-state techniques have a strong potential to enrich each other with new perspectives and possibilities and that their combination provides a true added value. This is especially true for dependency-based parsing, where a lot of research exists on both sides individually.

The semiring-based constraint satisfaction problem is used to combine these two fields. It is shown that it can be represented and solved in a natural way using finite-state machines. Furthermore, it is extended by three essential aspects: an infinite domain, a simultaneous representation and global constraints. Hence, a unified formalism for finite techniques is available that incorporates soft constraints and propagation techniques. For constraint processing, on the other hand, new possibilities exist to tackle known or recent problems.

Based on this, robust dependency parsing in the style of the Weighted Constraint Dependency Grammar is implemented using an extended finite-state approach: A problem decomposition approach with perfect relaxation is presented, for which different problem decomposition and constraint application strategies are worked out and combined with memoization. It is demonstrated how supra-local constraints can be implemented and how both violations and preferences can be traced during problem solving. The approach allows the intensive inclusion of non-projective structures and the modelling of complex linguistic phenomena such as structural and coordination ellipses, valences and non-local dependencies.

A handwritten, high-coverage grammar for German is presented, which is based on regular predicate logic formulas. On the basis of an evaluation the Grammar achieves a higher parsing quality than that of the Weighted Constraint Dependency Grammar. Unmanageable intermediate results of enormous size are a fundamental problem in constraint-based parsing with finite-state machines. In contrast, experiments show that a compact representation of intermediate results during problem solving is possible. This is enabled by the problem decomposition and constraint application strategies developed here.

The approach provides many connecting points and wide scope for the inclusion of data-driven and neural methods and complexity-reducing approximation strategies. Thus, a powerful hybrid neurosymbolic parsing system is close at hand.