Linköping: Cubic-Time Graph Parsing with a Simple Scoring Scheme

Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014), pages 395–399, Dublin, Ireland, August 23-24, 2014. Linköping: Cubic-Time Graph Parsing with a Simple Scoring Scheme Marco Kuhlmann Dept. of Computer and Information Science Linköping University, Sweden marco.kuhlmann@liu.se Abstract We turn the Eisner algorithm for parsing to projective dependency trees into a cubic- time algorithm for parsing to a restricted class of directed graphs. To extend the algo- rithm into a data-driven parser, we combine it with an edge-factored feature model and online learning. We report and discuss re- sults on the SemEval-2014 Task 8 data sets (Oepen et al., 2014). 1 Introduction This paper describes the system that we submit- ted to the closed track of the SemEval-2014 Task on Broad-Coverage Semantic Dependency Parsing (Oepen et al., 2014).1 However, the main contribu- tion of the paper is not the system as such (which had the lowest score among all systems submitted to the task), but the general approach for which it is a proof of concept. Graphs support natural representations of lin- guistic structure. For this reason, algorithms that can learn, process and transform graphs are of cen- tral importance to language technology. Yet, most of the algorithms that are used in natural language processing today focus on the restricted case of trees, and do so for a reason: Computation on gen- eral graphs is hard or even intractable, and efficient processing is possible only for restricted classes (cf. Courcelle and Engelfriet (2012)). The task then is to identify classes of graphs that are both ex- pressive enough to cover the linguistic data, and restricted enough to facilitate efficient processing. This work is licensed under a Creative Commons At- tribution 4.0 International Licence. Page numbers and pro- ceedings footer are added by the organisers. Licence details: http://creativecommons.org/licenses/by/4.0/ 1https://github.com/liu-nlp/gamma This paper shows that there are graphs that sat- isfy both of these desiderata. Our system is based on a new algorithm for parsing to a restricted class of directed graphs (Section 2). This class is re- stricted in so far as our algorithm runs in cubic time with respect to the length of the sentence; it thus has the same asymptotic complexity as parsing with context-free phrase structure grammars. The class of graphs defined by our algorithm is also expressive, in so far that it covers more than 98% of the SemEval data. To demonstrate that our parsing algorithm can be turned into a practical system, we combine it with two techniques taken straight from the literature on data-driven syntactic dependency parsing: � an edge-factored scoring model, as it has been used as the core of practical parsers since the seminal work of McDonald et al. (2005), and � online learning using the structured percep- tron, in the style of Collins (2002). State-of-the-art parsers use considerably more ad- vanced (and computationally more demanding) techniques, and therefore our system cannot be expected to deliver competitive results. (Its results on the SemEval data are reported in Section 4.) Instead, the main …

Content truncated to 500 words