Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Sartorio, Francesco (2015) Improvements in Transition Based Systems for Dependency Parsing. [Tesi di dottorato]

Questa è la versione più aggiornata di questo documento.

Full text disponibile come:

[img]
Anteprima
Documento PDF
1129Kb

Abstract (inglese)

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.

Abstract (italiano)

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.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Satta, Giorgio
Dottorato (corsi e scuole):Ciclo 26 > Scuole 26 > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:02 Febbraio 2015
Anno di Pubblicazione:02 Febbraio 2015
Parole chiave (italiano / inglese):parsing natural language processing
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:8004
Depositato il:23 Nov 2015 15:28
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record