Predictive Dependency Parsing

Abstract

This dissertation is concerned with analyzing the syntactic structure of dynamically evolving sentences before the sentences are complete. Human processing of both written and spoken language is inherently incremental, but most computational language processing happens under the assumption that all relevant data is available before processing begins. I discuss different approaches to build incremental processors and how to evaluate them.

I introduce two different approaches to incremental parsing. One performs restart-incremental parsing, obtaining very high accuracies. The other uses a novel transition system combined with a discriminative component; while it parses with lower accuracy, it can be trained on arbitrary dependency treebanks without any pre-processing and parses sentences at speeds of 3ms per word. Both approaches can be trained on existing treebanks and are language independent. Also, both try to provide as much information as possible by also predicting structure containing stand-ins for words not yet seen. To show that these structural predictions do provide non-trivial information, I demonstrate that n-gram language models benefit from incorporating these predictions, which is only possible if the predictions encode long-spanning information about the sentence structure.

Diese Dissertation befasst sich mit der Analyse syntaktischer Strukturen von noch unvollständigen Sätzen. Menschliche Sprachverarbeitung sowohl des geschriebenen als auch gesprochenen Wortes is inhärent inkrementell, während bei maschineller Verarbeitung meist davon ausgegangen wird, dass alle relevanten Informationen bereits zugreifbar sind bevor die Verarbeitung beginnt. Ich bespreche verschiedene Ansätze um inkrementelle Prozessoren zu bauen und diese zu evaluieren.

Ich stelle zwei verschiedene Ansätze für inkrementelles Parsing vor, die beide versuchen so viel Information wie möglich zu generieren indem sie Struktur vorhersagen die Platzhalter for noch nicht gesehene Worte enthält. Beide können auf existierenden Baumbanken trainiert werden und sind sprachunabhängig. Ein Ansatz ist restart-inkrementell, wodurch er sehr hohe Genauigkeiten erzielt. Der andere nutzt ein neuartiges Transitionssystem kombiniert mit einer diskriminativen Komponente; er parst mit geringerer Genauigkeit, kann aber ohne Vorverarbeitung auf beliebigen Dependenzbaumbanken trainiert werden und kann Sätze mit einer Geschwindigkeit von 3ms pro Wort parsen. Um zu zeigen, dass die strukturellen Vorhersagen tatsächlich nicht-triviale Information enthalten, zeige ich, dass n-gram-Sprachmodelle von diesen Informationen profitieren; dies ist nur möglich, da die Vorhersagen Informationen über die Satzstruktur kodieren, die über den begrenzenten Horizont der n-gram-Sprachmodelle hinausgehen.