Dynamic Oracle for the Arc-Standard Parser: from Approximation to Reinforcement Learning

Dependency parsing is one of the foundational tasks in Natural Language Pro- cessing and forms a backbone for syntactic analysis and language understand- ing. The Arc-Standard transition based parser has largely been adopted to solve this task, due to its simplicity and effectiveness, but the computational demands that are attached with its dynamic oracle present very crucial challenges when dealing with non-projective data. This thesis deals with the computational inefficiencies of the dynamic oracle for the Arc-Standard parser. Firstly, an overview is given of the main approaches to this task, then a more in depth analysis of transition-based parsers and their oracles follows, in particular detailing the motivations and strengths associated with the dynamic oracle. Moving on, our research follows the academic litera- ture reporting the arc decomposition property and its key role in deriving exact linear dynamic oracles: after explaining why the Arc-Standard parser doesn’t present this theoretical feature, an exact, but computationally expensive, dy- namic oracle is implemented. The thesis continues with the implementation of a linear approximate dynamic oracle, trying to cut down computational com- plexity while preserving parsing accuracy. Guided by these findings, this dissertation considers using the reinforcement learning approach in reformulating the dynamic oracle. Applying machine learning techniques to adapt parsing decisions dynamically, given a learned model, can increase both the efficiency and the accuracy of this process. In this direction, our contribution is a first attempt on reducing computational demands of the exact dynamic oracle to achieve performance comparable to those original formulations. The thesis presents a blend of theoretical discussions, empirical evaluations, and practical implementations for examining how well provided dynamic oracle optimizations work. Experimental results illuminate trade-offs of computational efficiency against parsing accuracy through the stages of our enhancement pro- cess. In addition, this research offers insights into the field of dependency pars- ing in that it suggests a reinforcement learning framework tailored specifically to address the challenges presented by the dynamic oracle of the Arc-Standard parser.

L’analisi delle dipendenze è uno dei compiti fondamentali nel Natural Language Processing e costituisce un pilastro per l’analisi sintattica e la comprensione del linguaggio. Il parser basato sulle transizioni Arc-Standard è stato ampiamente adottato per via della sua semplicità ed efficacia, ma le richieste computazionali che sono associate al suo oracolo dinamico presentano sfide molto importanti quando si ha a che fare con dati non proiettivi. Questa tesi riguarda le inefficienze computazionali dell’oracolo dinamico per il parser Arc-Standard. In primo luogo viene fornita una panoramica dei principali approcci a questo compito, segue un’analisi più approfondita dei parser basati su transizioni e dei loro oracoli, in particolare dettagliando le moti- vazioni e i punti di forza associati all’oracolo dinamico. Proseguendo, la nostra ricerca segue la letteratura accademica che riporta la proprietà di decompo- sizione dell’arco e il suo ruolo chiave nel derivare oracoli dinamici lineari esatti: dopo aver spiegato perché il parser Arc-Standard non presenta questa caratteris- tica teorica, viene implementato un oracolo dinamico esatto, ma computazional- mente costoso. La tesi continua con l’implementazione di un oracolo dinamico lineare approssimato, cercando di ridurre la complessità computazionale pur preservando l’accuratezza del parsing. A questo punto, la dissertazione considera l’utilizzo dell’approccio di ap- prendimento per rinforzo nella riformulazione dell’oracolo dinamico. Applicare tecniche di machine learning per adattare dinamicamente le decisioni di pars- ing, dato un modello appreso, può aumentare sia l’efficienza che l’accuratezza di questo processo. In questa direzione, il nostro contributo è un primo tentativo di ridurre le richieste computazionali dell’oracolo dinamico esatto per ottenere prestazioni paragonabili a quelle delle formulazioni originali. La tesi presenta una miscela di discussioni teoriche, valutazioni empiriche e implementazioni pratiche per esaminare quanto bene funzionino le ottimiz- zazioni dell’oracolo dinamico fornite. I risultati sperimentali mostrano i com- promessi tra efficienza computazionale e accuratezza del parsing attraverso le fasi del nostro processo di miglioramento. Inoltre, questa ricerca offre intu- izioni nel campo dell’analisi delle dipendenze in quanto suggerisce un frame- work di apprendimento per rinforzo su misura per affrontare le sfide presentate dall’oracolo dinamico del parser Arc-Standard.