Improvements in Transition Based Systems for Dependency Parsing

This thesis investigates transition based systems for parsing of natural language using dependency grammars. Dependency parsing provides a good and simple syntactic representation of the grammatical relations in a sentence. In the last years, this basic task has become a fundamental step in many applications that deal with natural language processing. Specifically, transition based systems have strong practical and psycholinguistic motivations. From a practical point of view, these systems are the only parsing systems that are fast enough to be used in web-scale applications. From a psycholinguistic point of view, they very closely resemble how humans incrementally process the language. However, these systems fall back in accuracy when compared with graph-based parsing, a family of parsing techniques that are based on a more traditional graph theoretic / dynamic programming approach, and that are more demanding on a computational perspective. Recently, some techniques have been developed in order to improve the accuracy of transition based systems. Most successful techniques are based on beam search or on the combination of the output of different parsing algorithms. However, all these techniques have a negative impact on parsing time. In this thesis, I will explore an alternative approach for transition based parsing, one that improves the accuracy without sacrificing computational efficiency. I will focus on greedy transition based systems and I will show how it is possible to improve the accuracy by using a dynamic oracle and a flexible parsing strategy. Dynamic oracles allow to reduce the error propagation at parsing time. Dynamic oracles may have some impact on training time, but there is no efficiency loss at parsing time. A flexible parsing strategy allows to reduce constraints over the parsing process and the time impact in both training and parsing time is almost negligible. Finally, these two techniques work really well when combined together, and they are orthogonal to previously explored proposals such as beam search or system combinations. As far as I know, the obtained experimental results are still state-of-the-art for greedy transition based parsing based on dependency grammars.

La tesi riguarda gli algoritmi incrementali per l'analisi del linguaggio (naturale) usando grammatiche alle dipendenze. Queste grammatiche permettono di dare una chiara rappresentazione delle relazioni sintattiche che intercorrono tra le varie parole della frase. Negli ultimi anni tali rappresentazioni hanno rivestito grande interesse, fino a diventare un passaggio fondamentale in moltissime applicazioni che trattano il linguaggio. I sistemi incrementali trovano forti motivazioni sia pratiche che psicolinguistiche. Da un punto di vista pratico, questi sistemi sono gli unici algoritmi in grado di processare velocemente grandi quantità di dati. Da un punto di vista psicolinguistico sono sistemi che simulano il modo in cui l'uomo elabora e capisce il linguaggio. Se in termini di velocità i sistemi incrementali sono i migliori, esistono sistemi basati sulla teoria dei grafi che ottengono una migliore precisione. Recentemente si è cercato di migliorare i sistemi incrementali con l'ausilio di tecniche più o meno elaborate di ``beam search'' o combinando i risultati provenienti da diversi algoritmi. Sebbene queste tecniche migliorino la precisione dei sistemi, hanno un impatto negativo sulla velocità degli algoritmi. Durante il mio lavoro di ricerca ho elaborato sistemi alternativi che migliorano la precisione senza sacrificare l'efficienza. In particolare nella tesi descriverò come sia possibile migliorare i sistemi incrementali agendo sulle funzioni oracolo e aumentando la flessibilità degli algoritmi. Agendo sulle funzioni oracolo, che guidano l'apprendimento dei modelli statistici usati in fase applicativa, è possibile ridurre la propagazione degli errori che tipicamente affligge gli algoritmi incrementali. Le nuove funzioni riducono leggermente la velocità della fase di apprendimento, ma non hanno alcun impatto sull'efficienza in fase applicativa. Invece, agendo sulla flessibilità degli algoritmi, è possibile creare sistemi incrementali con meno vincoli con un miglioramento della precisione a scapito di una praticamente trascurabile riduzione dell'efficienza. Concluderò mostrando come queste due nuove idee funzionino bene combinate l'una con l'altra raggiungendo risultati tuttora allo stato dell'arte.