Learning compositional structures for semantic graph parsing (2021)

Abstract: AM dependency parsing is a method for neural semantic graph parsing that exploits the principle of compositionality. While AM dependency parsers have been shown to be fast and accurate across several graphbanks, they require explicit annotations of the compositional tree structures for training. In the past, these were obtained using complex graphbank-specific heuristics written by experts. Here we show how they can instead be trained directly on the graphs with a neural latent-variable model, drastically reducing the amount and complexity of manual heuristics. We demonstrate that our model picks up on several linguistic phenomena on its own and achieves comparable accuracy to supervised training, greatly facilitating the use of AM dependency parsing for new sembanks.

## introduction it is generally accepted in linguistic semantics that meaning is compositional, i.e. that the meaning representation for a sentence can be computed by evaluating a tree bottom-up. a compositional parsing model not only reflects this insight, but has practical advantages such as in compositional generalisation (e.g. herzig and berant 2020), i.e. systematically generalizing from limited data. however, in developing a compositional semantic parser, one faces the task of figuring out what exactly the compositional structures -i.e. the trees that link the sentence and the meaning representation -should look like. this is challenging even for expert linguists; for instance, @xcite report that 90% of the development time of the english resource grammar @xcite went into the development of the syntax-semantics interface. compositional semantic parsers which are learned from data face an analogous problem: to train a such a parser, the compositional structures must be made explicit. however, these structures are not annotated in most sembanks. for instance, the am (apply-modify) dependency parser of @xcite uses a neural model to predict am dependency trees, compositional structures that evaluate to semantic graphs. their parser achieves high accuracy @xcite and parsing speed @xcite across a variety of english semantic graphbanks. to obtain an am dependency tree for each graph in the corpus, they use hand-written graphbank-specific heuristics. these heuristics cost significant time and expert knowledge to create, limiting the ability of the am parser to scale to new sembanks. in this paper, we drastically reduce the need for hand-written heuristics for training the am dependency parser. we first present a graphbankindependent method to compactly represent the relevant compositional structures of a graph in a tree automaton. we then train a neural am dependency parser directly on these tree automata. our code is available at github.com/coli-saar/am-parser. we evaluate the consistency and usefulness of the learned compositional structures in two ways. we first evaluate the accuracy of the trained am dependency parsers, across four graphbanks, and find that it is on par with an am dependency parser that was trained on the hand-designed compositional structures of @xcite . we then analyze the compositional structures which our algorithm produced, and find that they are linguistically consistent and meaningful. we expect that our methods will facilitate the design of compositional models of semantics in the future. ## am dependency parsing compositional semantic graph parsing methods do not predict a graph directly, but rather predict a compositional structure which in turn determines the graph. @xcite represent the compositional structure of a graph with am dependency trees (am dep-trees for short) like the one in fig. 1a . it describes the way the meanings of the words -the graph fragments in fig. 2 -combine to form the semantic graph in fig. 1c , here an amr @xcite . the am dep-tree edges are labeled with graph-combining operations, taken from the apply-modify (am) algebra @xcite . graphs are built out of fragments called graph constants (fig. 2 ). each graph constant has a root, marked with a rectangular outline, and may have special node markers called sources @xcite , drawn in red, which mark the empty slots where other graphs will be inserted. in fig. 1a , the app o operation plugs the root of g-glow into the o source of g-begin. because g-begin and g-glow both have an s-source, app o merges these nodes, creating a reentrancy, i.e. an undirected cycle, and yielding fig. 1d , which is in turn attached at s to the root of g-fairy by mod s . app fills a source of a head with an argument while mod uses a source of a modifier to connect it to a head; both operations keep the root of the head. types the [s] annotation at the o-source of g-begin in fig. 2 is a request as to what the type of the o argument of g-begin should be. the type of a graph is the set of its sources with their request annotations, so the request [s] means that the source set of the argument must be {s}. because this is true of g-glow, the am dependency tree is well-typed; otherwise the tree could not be evaluated to a graph. thus, the graph constants lexically specify the semantic valency of each word as well as reentrancies due to e.g. control. if a graph has no sources, we say it has the empty type [ ]; if a source in a graph printed here has no annotation, it is assumed to have the empty request (i.e. its argument must have no sources). fairy p-fairy glow f arg0 p-glow tiny f mod-of p-tiny sparkle f arg1 p-sparkle and s op1 g op2 p-and figure 4: canonical constants. begin f arg0 g[f] ## decomposition algorithm the central challenge of compositional methods lies in the fact that the compositional structures are not provided in the graphbanks. existing am parsers @xcite @xcite use hand-built heuristics to extract am dep-trees for supervised training from the graphs in the graphbank. these heuristics require extensive expert work, including graphbank-specific decisions for source allocations and graphbank-and phenomenon-specific patterns to extract type requests for reentrancies. in this section we present a simpler yet more complete method for obtaining the basic structure of an am dep-tree for a given semantic graph g (for decomposing the graph), with much reduced reliance on heuristics. we will learn meaningful source names jointly with training the parser in §5 and §6. notation. we treat graphs as a quadruple @xmath0, r g , e g , l g , where the nodes n g are arbitrary objects (in the examples here we use lower- ## tree automata for source names we have now seen how, for any graph g, we obtain a unique am dependency tree t . this tree represents the compositional structure of g, but it still contains placeholder source names. we will now show how to automatically choose source names. these names should be consistent across the trees for different sentences; this yields reusable graph constants, which capture linguistic generalizations and permit more accurate parsing. but the source names must also remain consistent within each tree to ensure that the tree still evaluates correctly to g; for instance, if we replace the placeholder source f in p-glow in fig. 6e by o, but we replace f in p -and by s, then the am dep-tree would not be well-typed because the request is not satisfied. we therefore proceed in two steps. in this section, we represent all internally consistent source assignments compactly with a tree automaton. in §6, we then learn to select globally reusable source names jointly with training the neural parser. tree automata. a (bottom-up) tree automaton @xcite is a device for compactly describing a language (set) of trees. it processes a tree bottom-up, starting at the leaves, and nondeterministically assigns states from a finite set to the nodes. a rule in a tree automaton has the general shape f (q 1 , . . . , q n ) → q. if the automaton can assign the states q 1 , . . . , q n to the children of a node π with node label f , this rule allows it to assign the state q to π. the automaton accepts a tree if it can assign a final state to the root node. tree automata can be seens as generalisation of parse charts. ## joint learning of compositional structure and parser as a final step, we train the neural parser of @xcite directly on the tree automata. for each position i in the sentence, the parser predicts a score c (g, i) for each graph constant g, and for each pair i, j of positions and operation ℓ, it predicts an edge score c i ℓ -→ j . the tree automata are factored the same way, in that they have one rule per graph constant and per dependency edge. as a result, we get a oneto-one correspondence between parser scores and automaton rules when aligning automata rules to words via the words' alignments to graph nodes. we thus take the neural parser scores as rule weights c (r) for rules r in the automaton. in a weighted tree automaton, the weight of a tree is defined as the product of the weights of all rules that built it. the inside score i of the tree automaton is the sum of the weights of all the trees it accepts. computing this sum naively would be intractable, but the inside score can be computed efficiently with dynamic programming. our training objective is to maximize the sum of the log inside scores of all automata in the corpus. the arithmetic structure of computing the inside scores is complex and varies from automaton to automaton, which would make batching difficult. we solve this with the chain rule as follows: when a graph g is non-decomposable using our blob partition, i.e. if there is no well-typed am dep-tree t that evaluates to g, and so the condition of theorem 2 does not hold, then we remove that graph from the training set. (this does not affect coverage at evaluation time.) this occurs rarely, affecting e.g. about 1.6% of graphs in the psd training set. like @xcite , we use the heuristic amr alignments of @xcite . these alignments can yield multi-node constants. in those cases, we first run the algorithm of section 4 to obtain an am tree with placeholder source names, and then consolidate those constants that are aligned to the same word into one constant, effectively collapsing segments of the am tree into a single constant. we then construct the tree automata of section 5 as normal. ## linguistic analysis as am parsing is inherently interpretable, we can explore linguistic properties of the learned graph constants and trees. we find that the neural method makes use of both syntax and semantics. we compute for each sentence in the training set the best tree from its tree automaton, according to the neural weights of the best performing epoch. we then sample trees from this set for handanalysis (see appendix a), to examine whether the model learned consistent sources for subjects and objects. we find that while the em method uses highly consistent graph constants and am operations, the neural method, which has access to the strings, sacrifices some graph constant and operation consistency in favour of syntactic consistency. ## conclusion in this work, we presented a method to obtain the compositional structures for am dependency parsing that relies much less on graphbank-specific heuristics written by experts. our neural model learns linguistically meaningful argument slot names, as shown by our manual evaluation; in this regard, our model learns to do the job of the linguist. high parsing performance across graphbanks shows that the learned compositional structures are also well-suited for practical applications, promising easier adaptation of am dependency parsing to new graphbanks. learning compositional structures for semantic graph parsing supplementary materials jonas groschwitz saarland university jonasg@coli.uni-saarland.de meaghan fowlie utrecht university m.fowlie@uu.nl alexander koller saarland university koller@coli.uni-saarland.de