Accurate polyglot semantic parsing with DAG grammars (2020)

Abstract: Semantic parses are directed acyclic graphs (DAGs), but in practice most parsers treat them as strings or trees, mainly because models that predict graphs are far less understood. This simplification, however, comes at a cost: there is no guarantee that the output is a well-formed graph. A recent work by Fancellu et al. (2019) addressed this problem by proposing a graph-aware sequence model that utilizes a DAG grammar to guide graph generation. We significantly improve upon this work, by proposing a simpler architecture as well as more efficient training and inference algorithms that can always guarantee the well-formedness of the generated graphs. Importantly, unlike Fancellu et al., our model does not require language-specific features, and hence can harness the inherent ability of DAG-grammar parsing in multilingual settings. We perform monolingual as well as multilingual experiments on the Parallel Meaning Bank (Abzianidze et al., 2017). Our parser outperforms previous graph-aware models by a large margin, and closes the performance gap between string-based and DAG-grammar parsing.

## introduction semantic parsers map a natural language utterance into a machine-readable meaning representation, thus helping machines understand and perform inference and reasoning over natural language data. various semantic formalisms have been explored as the target meaning representation for semantic parsing, including dependency-based compositional semantics @xcite , abstract meaning representation @xcite , minimum recursion semantics (mrs, @xcite , and discourse representation theory (drt, @xcite . despite meaningful differences across formalisms or parsing models, a representation in any of these formalisms can be expressed as a directed acyclic graph (dag). consider for instance the sentence 'we barred the door and locked it', whose meaning representation as a discourse representation structure (drs) is shown in figure 1 . a drs is usually represented as a set of nested boxes (e.g. b 1 ), containing variable-bound discourse referents (e.g. 'lock(e 2 )'), semantic constants (e.g. 'speaker'), predicates (e.g. agent) expressing relations between variables and constants, and discourse relations between the boxes (e.g. continuation). this representation can be expressed as a dag by turning referents and constants into vertices, and predicates and discourse relations into connecting edges, as shown in figure 2 . how can we parse a sentence into a dag? commonly-adopted approaches view graphs as strings (e.g. van @xcite , or trees (e.g. @xcite , taking advantage of the linearized graph representations provided in annotated data (e.g. figure 3 , where the graph in figure 2 is represented in penman notation (goodman, 2020)). an advantage of these linearized representations is that they allow for the use of well-understood sequential decoders and provide a general framework to parse into any arbitrary formalism. however, these representations are unaware of the overall graph strucure they build as well as of reentrant semantic relations, such as coordination, coreference, and control, that are widespread in language. parsers such as @xcite although able to generate reentrancies in their output, they do so by simply predicting pointers back to already generated nodes. parsing directly into dags, although desirable, is less straightforward than string-based parsing. whereas probabilistic models of strings and trees are ubiquitous in nlp, at present, it is an active problem in modern formal language theory to develop formalisms that allow to define probability distributions over dags of practical interest. 1 a successful line of work derives semantic graphs using graph grammars that allow to generate a graph by rewriting non-terminal symbols with graph fragments. among these, hyperedge replacement grammar (hrg) has been explored for parsing into semantic graphs @xcite . however, parsing with hrgs is not practical due to its complexity and large number of possible derivations per graph @xcite . thus, work has looked at ways of constraining the space of possible derivations, usually in the form of align-1 see @xcite for an extensive review of the issue. ment or syntax @xcite . for example, @xcite and @xcite extracted fine-grained typed grammars whose productions are aligned to the input sentence and combined over a dependency-like structure. similarly, @xcite draw on constituent parses to combine together hrg fragments. @xcite show that there exists a restricted subset of hrgs, restricted dag grammar (rdg), that provides a unique derivation per graph. a unique derivation means that a graph is generated by a unique sequence of productions, which can then be predicted using sequential decoders, without the need of an explicit alignment model or an underlying syntactic structure. furthermore, the grammar places hard constraints on the rewriting process, which can be used to guarantee the well-formedness of output graphs during decoding. drawing on this result, a recent work by @xcite introduces recurrent neural network rdgs, a sequential decoder that models graph generation as a rewriting process with an underlying rdg. however, despite the promising framework the approach in fa19 foot_0 falls short in several aspects. in this paper, we address these shortcomings, and propose an accurate, efficient, polyglot model for neural rdg parsing. specifically, our contributions are as follows: grammar: in practice, rdgs extracted from training graphs can be large and sparse. we show a novel factorization of the rdg production rules that reduces the sparsity of the extracted grammars. furthermore, we make use of rdgs extracted on fully human annotated training data to filter out samples from a larger noisy machine-generated dataset that cannot be derived using such grammars. we find that this strategy not only drastically reduces the size of the grammar, but also improves the final performance. model: fa19 use a syntactic parsing inspired architecture, a stacklstm, trained on a gamut of syntactic and semantic features. we replace this with a novel architecture that allows for batched input, while adding a multilingual transformer encoder that relies on word-embedding features only. constrained decoding: we identify a limitation in the decoding algorithm presented by fa19, in that it only partially makes use of the well-formdness constraints of an rdg. we describe the source of this error, implement a correction and show that we can guarantee well-formed dags. multilinguality: training data in languages other than english is often small and noisy. fa19 addressed this issue with cross-lingual models using features available only for a small number of languages, but did not observe improvements over monolingual baselines in languages other than english. we instead demonstrate the flexibility of rdgs by extracting a joint grammar from graph annotations in different languages. at the same time, we make full use of our multilingual encoder to build a polyglot model that can accept training data in any language, allowing us to experiment with different combinations of data. our results tell a different story where models that use combined training data from multiple languages always substantially outperform monolingual baselines. we test our approach on the parallel meaning bank (pmb, @xcite , a multilingual graphbank. our experimental results demonstrate that our new model outperforms that of fa19 by a large margin on english while fully exploiting the power of rdgs to always guarantee a wellformed graph. we also show that the ability of simultaneously training on multiple languages substantially improves performance for each individual language. importantly, we close the performance gap between graph-aware parsing and state-of-theart string-based models. ## restricted dag grammar we model graph generation as a process of graph rewriting with an underlying grammar. our grammar is a restricted dag grammar @xcite , a type of context-free grammar designed to model linearized dags. for ease of understanding, we represent fragments in grammar productions as strings. this is shown in figure 4 , where the right-hand-side (rhs) fragment can be represented as its left-to-right linearization, with reentrant nodes flagged by a dedicated @xmath01, @xmath11, @xmath21, @xmath31, @xmath41, @xmath51) :theme t1(@xmath61, @xmath72)))) :cont t2(c, @xmath81. once this mapping is performed, all instances of @xmath92. all our fragments are delexicalized. this is achieved by the separate non-terminal l that at every step is rewritten in the corresponding terminal label (e.g. bar). delexicalization allows to reduce the size of grammar and factorize the prediction of fragments and labels separately. however, dag grammars can still be large due to the many combinations of how edge labels and their corresponding non-terminals can appear in a fragment. for this reason, we propose a further simplification where edge labels are replaced with placeholders ê1 ...ê |e| , which we exemplify using the production in figure 4 as follows: after a fragment is predicted, placeholders are then replaced with actual edge labels by a dedicated module (see § 3.2 for more details). groschwitz et al. (2018 the fine-grained thematic types in the am algebra add a level of linguistic sophistication that rdg lacks, in that fragments fully specify the roles a word is expected to fill. this ensures that the output graphs are always semantically well-formed; in that am algebra behaves very similar to ccg. however this sophistication not only requires adhoc heuristics that are tailored to a specific formalism (amr in this case) but also relies on alignment information with the source words. ## architecture our model is an encoder-decoder architecture that takes as input a sentence and generates a dag g as a sequence of fragments with their corresponding labels, using the rewriting system in § 2. in what follows we describe how we obtain the logits for each target prediction, all of which are normalized with the softmax function to yield probability distributions. a detailed diagram of our architecture is shown in figure 7 in appendix a. ## experimental results we first present results of ablation experiments to understand which model configuration performs best ( § 5.1). we then compare our bestperforming model with several existing semantic parsers ( § 5.2), and present our model's performance in multilingual settings ( § 5.3). ## conclusions in this paper, we have introduced a graph parser that can fully harness the power of dag grammars in a seq2seq architecture. our approach is efficient, fully multilingual, always guarantees well-formed graphs and can rely on small grammars, while outperforming previous graph-aware parsers in english, italian, german and dutch by large margin. at the same time, we close the gap between stringbased and rdg-based decoding. in the future, we are planning to extend this work to other semantic formalisms (e.g. amr, ucca) as well as test-ing on other languages, so to encourage work in languages other than english. t and information about the parent fragment u t (yellow edges). all other predictions are done using the hidden state of the decoder second layer (in red) along a separate context vector c l t . both context vectors are computed using soft attention over the input representations (top left). fragments predicted are used to substitute the leftmost non-terminal in the partial graph g (in pink), as shown at the top for g 2 ...g 5 . for g 1 the first fragment predicted initializes the graph (this corresponds to substituting the start symbol s). the edge labels in the fragments above are replaced with placeholders e 1 ...e |e| to display how edge factorization works. we assume here, for brevity, that g 5 is our final output graph and show the prediction of two edges that substitute in place of the placeholders (box at the bottom). for edge prediction, we use a bundle of features collected during decoding, namely the parent and children fragment embedding f t , the second layer hidden state (in red) and the context vector c l at time t.