Graph parsing with s-graph grammars

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1481–1490, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Graph parsing with s-graph grammars Jonas Groschwitz and Alexander Koller and Christoph Teichmann Department of Linguistics University of Potsdam firstname.lastname@uni-potsdam.de Abstract A key problem in semantic parsing with graph-based semantic representations is graph parsing, i.e. computing all pos- sible analyses of a given graph accord- ing to a grammar. This problem arises in training synchronous string-to-graph grammars, and when generating strings from them. We present two algorithms for graph parsing (bottom-up and top-down) with s-graph grammars. On the related problem of graph parsing with hyperedge replacement grammars, our implementa- tions outperform the best previous system by several orders of magnitude. 1 Introduction The recent years have seen an increased interest in semantic parsing, the problem of deriving a se- mantic representation for natural-language expres- sions with data-driven methods. With the recent availability of graph-based meaning banks (Ba- narescu et al., 2013; Oepen et al., 2014), much work has focused on computing graph-based se- mantic representations from strings (Jones et al., 2012; Flanigan et al., 2014; Martins and Almeida, 2014). One major approach to graph-based semantic parsing is to learn an explicit synchronous gram- mar which relates strings with graphs. One can then apply methods from statistical parsing to parse the string and read off the graph. Chiang et al. (2013) and Quernheim and Knight (2012) rep- resent this mapping of a (latent) syntactic struc- ture to a graph with a grammar formalism called hyperedge replacement grammar (HRG; (Drewes et al., 1997)). As an alternative to HRG, Koller (2015) introduced s-graph grammars and showed that they support linguistically reasonable gram- mars for graph-based semantics construction. One problem that is only partially understood in the context of semantic parsing with explicit grammars is graph parsing, i.e. the computation of the possible analyses the grammar assigns to an input graph (as opposed to string). This prob- lem arises whenever one tries to generate a string from a graph (e.g., on the generation side of an MT system), but also in the context of extracting and training a synchronous grammar, e.g. in EM train- ing. The state of the art is defined by the bottom- up graph parsing algorithm for HRG by Chiang et al. (2013), implemented in the Bolinas tool (An- dreas et al., 2013). We present two graph parsing algorithms (top- down and bottom-up) for s-graph grammars. S- graph grammars are equivalent to HRGs, but em- ploy a more fine-grained perspective on graph- combining operations. This simplifies the parsing algorithms, and facilitates reasoning about them. Our bottom-up algorithm is similar to Chiang et al.’s, and derives the same asymptotic number of rule instances. The top-down algorithm is novel, and achieves the same asymptotic runtime as the bottom-up algorithm by reasoning about the bi- connected components of the graph. Our eval- uation on the “Little Prince” graph-bank shows that …

Content truncated to 500 words