Semantic Composition with PSHRG for Derivation Tree Reconstruction from Graph-Based Meaning Representations (2022)

Abstract: We introduce a data-driven approach to generating derivation trees from meaning representation graphs with probabilistic synchronous hyperedge replacement grammar (PSHRG). SHRG has been used to produce meaning representation graphs from texts and syntax trees, but little is known about its viability on the reverse. In particular, we experiment on Dependency Minimal Recursion Semantics (DMRS) and adapt PSHRG as a formalism that approximates the semantic composition of DMRS graphs and simultaneously recovers the derivations that license the DMRS graphs. Consistent results are obtained as evaluated on a collection of annotated corpora. This work reveals the ability of PSHRG in formalizing a syntax–semantics interface, modelling compositional graph-to-tree translations, and channelling explainability to surface realization.

## introduction general graph-based meaning representations (mrs) that model sentence-level semantics aim to provide interpretable intermediate representations that are application-and domain-independent @xcite . recently, graph grammars and algebras that formalize semantic constructions were introduced to mr processing (for example: @xcite @xcite @xcite @xcite ). these formal grammars bridge between linguistic assumptions and data-driven parsing, and offer the benefit of cross-framework adaptability. for instance, the apply-modify algebra was adopted in parsing across 5 mr frameworks @xcite ) @xcite . another formalism that was adopted in generating semantic graphs from syntax trees is synchronous hyperedge replacement grammar (shrg) @xcite @xcite . the use of shrg in recovering syntax trees from mrs has however received scant research coverage. empirical results of pshrg's application are limited to @xcite 's work in semantic-based machine translation. an immediate application of mr-to-tree parsing is surface realization. previous data-driven approaches to it include rule-based @xcite @xcite and neural methods @xcite @xcite . all these methods do not generate syntactic analyses. in contrast, the answer constraint engine (ace; @xcite @xcite , an hpsg grammar-based parser, generates both derivations and sentences from minimal recursion semantics (mrs; @xcite . if we can induce an shrg from data, mrs can be translated into derivation trees without relying on a hand-engineered grammar, and natural language texts can be obtained by realizing the terminals. combining the strengths of rulebased systems and the data-driven paradigm, such an approach gives both linguistically-informed realization processes and explainable results, removes syntactic ambiguities that would otherwise exist in flattened surface strings, and provides potential usage for downstream tasks such as chunking. among the different mr frameworks, we investigate dependency minimal recursion semantics (dmrs; @xcite . dmrs are directed graphs derived losslessly from mrs, whereas an mrs structure with respect to a reading of an english sentence is composed along with a derivation tree using the english resource grammar (erg; @xcite , a broad-coverage handengineered hpsg grammar of english. dmrs encodes logical formulae with underspecified scopes (for an introduction, see @xcite . fig. 1 shows an example of an erg analysis. @xcite gave a compositional sethat licenses the dmrs by an erg analysis of the sentence some boys want to go, and a scope-resolved representation of the dmrs with variables (bottom). each dmrs node is aligned to the surface string as indicated by the colours. in the derivation, each preterminal is a lexical item, e.g., _go_v1, and each nonterminal above is labelled by a lexical or syntactic rule, e.g., hd-cmp_u_c denotes the head-complement construction. in a dmrs, each node is either a predicate corresponding to a lexeme (e.g., _boy_n_1) or a nonlexical predicate (e.g., loc_nonsp) (see fig. 4 ). for ease of exposition, node attributes (e.g., number and tense) are not shown. the primary edge labels (e.g., arg1) denote argument relationship, the secondary edge labels (e.g., /neq and /h) encode constraints on scopal relationships, and top specifies the top scopal non-quantifier node. based on the scopal information in the dmrs, the bottom scope is the only scope possible. in this paper, we shed light on the applicability of a succinct grammar formalism in approximating the semantic compositions of a graph-based mr. essentially, we capture the syntax-semantics interface of the erg by inducing a pshrg from an annotated treebank to provide generative models for both dmrs graphs and derivation trees. with the induced pshrg, derivation trees that license the dmrs graphs can be reconstructed through graph parsing. we describe the procedures and the relevant adaptations involved, from pshrg induction, parsing to generating derivation trees. finally, we present the empirical results on derivation trees and surface strings reconstruction from dmrs graphs under different configurations. the numbered rounded rectangles attached to each hyperedge denote the ordered collection of nodes the hyperedge connects to, each of which corresponds to a dmrs node. a labelled arrow is a terminal hyperedge that connects to exactly two nodes and that corresponds to a dmrs edge. in an hrg production 𝐴 → 𝑅, each external node of 𝑅 is mapped to a node of the same colour in 𝐴. h5 rewrites the start symbol to a hyperedge that connects to one node. note that all nodes of h4 are non-external nodes of the hypergraph fragment. ## probabilistic synchronous hyperedge replacement grammar hyperedge replacement grammar (hrg) is a context-free rewriting formalism for generating graphs @xcite . a synchronous hrg (shrg) defines mappings between languages of graphs, which in our context are an hrg and a context-free grammar (cfg) for strings. we give the definitions in this section. ## pshrg induction and parsing in this section, we describe how a pshrg is induced from training data and how a derivation tree is reconstructed from a dmrs of the test data with the induced grammar. we also describe two methods for modelling the semantics of lexical items. ## towards practical grammar approximation and modelling to approximate complex grammars or implicit relations established between trees and graphs by pshrg, we introduce extensions for improving on both the precision and generalizability of modelling. the application of most of the proposed techniques is not limited to the dmrs, but to general mr parsing by pshrg. ## experiments the main objective of the experiments is to assess the performance of pshrg models on simulating dmrs compositions and producing approximating derivation trees. specifically, we reconstruct a derivation tree for each dmrs whose nonterminals are aligned to dmrs subgraphs and labelled by an erg syntactic construction; the erg 1214 contains more than 210 fine-grained syntactic constructions that reflect the distinguishing properties of different syntactic constructions. as a secondary evaluation, we analyze our performance on the task of surface realization. the purpose of this is twofold: first, assessing the quality of the surface strings produced from the recon-2 each lexical entry in the erg is assigned to exactly one lexical type, which determines most of its syntactic and semantic properties. for example, inform, advise and remind share a lexical type because they all select a noun phrase and a sentential complement. the detailed lexical types interact with the highly generalized linguistic principles to produce precise linguistic interpretations. finally, we evaluate the significance of the two proposed adaptations, namely recovering words with empty semantics and incorporating framework-specific constraints to pshrg parsing. an instance of sample input and sample output are provided in appendix c. ## discussion the proposed frequency-based pshrg models are simple yet competitive data-driven baselines for recovering derivations of dmrs. they can be further combined with sophisticated machine learning methods for a more accurate parse ranking. more extensive features can also be included to enhance grammar approximation. for instance, the featurepaths of erg signs are shown to be helpful for pcfg approximation @xcite . language-specific knowledge about words with empty semantics is also critical for syntactic purposes. in terms of efficiency, @xcite showed that exact parsing can be very practical on elementary dependency structures (eds; @xcite , a close equivalent to dmrs that excludes scopal information. different from ye and sun (2020)'s implementation, we retain more than 210 erg syntactic constructions for precision and adopt delexicalization for generalization, both of which increase the search space of parsing and trade efficiency. we suggest that the described pshrg-based approach can be a potential alternative to the unification-based ace generator for surface realization from dmrs, whilst improving parsing coverage, accuracy and efficiency without sacrificing one another would be a critical problem for future research. in this paper, we report our findings with respect to the engineering decisions we investigated based on the data at hand. in principle, the application of the described pshrg-based approach is not limited to dmrs, but also to generic graph-to-tree translations that exhibit compositionality, if suitable data of aligned trees and graphs is available. if explicit associations do not exist between the trees and graphs, the induced grammar formalizes the underlying relations and patterns; otherwise, the induced grammar provides an approximation to such relations, which can be desirable for computation purposes. ## conclusion based on the experimental results, we can assess the contributions of this work from three perspectives: (1) pshrg with framework-specific adaptions as a formalism that approximates the semantic composition process of dmrs, (2) pshrg graph parsing with framework-independent extensions as a general approach to modelling compositional graph-to-tree translation, and (3) derivation reconstruction with a pshrg induced from data as a solution to surface realization from mrs that provides explainability, syntactic disambiguation, and syntactic variations. we hope that this work provides relevant and substantial empirical insights to stimulate more research on approaching mr processing with linguistically-motivated methods. erik velldal and stephan oepen. 2006. statistical ranking in tactical generation. in proceedings of the 2006 conference on empirical methods in natural language processing, pages 517-525, sydney, australia. association for computational linguistics. yajie ye and weiwei sun. 2020. exact yet efficient graph parsing, bi-directional locality and the constructivist hypothesis. in proceedings of the 58th annual meeting of the association for computational linguistics, pages 4100-4110, online. association for computational linguistics. yajie ye, weiwei sun, and xiaojun wan. 2018. language generation via dag transduction. in proceedings of the 56th annual meeting of the association for computational linguistics (volume 1: long papers), pages 1928-1937, melbourne, australia. association for computational linguistics. yi zhang and hans-ulrich krieger. 2011. large-scale corpus-driven pcfg approximation of an hpsg. in proceedings of the 12th international conference on parsing technologies, pages 198-208, dublin, ireland. association for computational linguistics.