Neural-Symbolic Inference for Robust Autoregressive Graph Parsing via Compositional Uncertainty Quantification (2022)

Abstract: Pre-trained seq2seq models excel at graph semantic parsing with rich annotated data, but generalize worse to out-of-distribution (OOD) and long-tail examples. In comparison, symbolic parsers under-perform on population-level metrics, but exhibit unique strength in OOD and tail generalization. In this work, we study compositionality-aware approach to neural-symbolic inference informed by model confidence, performing fine-grained neural-symbolic reasoning at subgraph level (i.e., nodes and edges) and precisely targeting subgraph components with high uncertainty in the neural parser. As a result, the method combines the distinct strength of the neural and symbolic approaches in capturing different aspects of the graph prediction, leading to well-rounded generalization performance both across domains and in the tail. We empirically investigate the approach in the English Resource Grammar (ERG) parsing problem on a diverse suite of standard in-domain and seven OOD corpora. Our approach leads to 35.26% and 35.60% error reduction in aggregated SMATCH score over neural and symbolic approaches respectively, and 14% absolute accuracy gain in key tail linguistic categories over the neural model, outperforming prior state-of-art methods that do not account for compositionality or uncertainty.

## introduction a structured account of compositional meaning has become a longstanding goal for natural language processing. to this end, a number of efforts have focused on encoding semantic relationships and attributes into graph-based meaning representations (mrs, see appendix a for details). in particular, graph semantic parsing has been an important task in almost every semantic evaluation (semeval) exercise since 2014. in recent years, we have witnessed the burgeoning of applying neural networks † co-senior authors. ‡ work done at google. to semantic parsing. pre-trained language modelbased approaches have led to significant improvements across different mrs @xcite . however, these models often generalize poorly to out-of-distribution (ood) and tail examples @xcite @xcite , while grammar or rule-based parser work relatively robustly across different linguistic phenomena and language domains @xcite . see section 6 for a review of related work. in this paper, we propose a novel compositional neural-symbolic inference for graph semantic parsing, which takes advantage of both uncertainty quantification from a seq2seq parser and prior knowledge from a symbolic parser at the subgraph level (i.e., nodes and edges). we take graph semantic parsing for english resource grammar (erg) as our case study. erg is a compositional semantic representation explicitly coupled with the syntactic structure. compared to other graph-based meaning representations like abstract meaning representation (amr), erg has high coverage of english text and strong transferability across domains, rendering itself as an attractive target formalism for automated semantic parsing. furthermore, many years of erg research has led to well-established symbolic parser and a rich set of carefully constructed corpus across different application domains and fine-grained linguistic phenomena, making it an ideal candidate for studying cross-domain generalization of neural-symbolic methods @xcite . we start with a novel investigation of the uncertainty calibration behaviour of a t5-based state-ofthe-art neural erg parser @xcite on the subgraph level (section 3), where we make some key observations: (1) the performance of the neural parser degrades when it becomes uncertain at the subgraph level, while (2) the symbolic parser works still robustly when the neural parser is uncertain at the subgraph level. this motivates us to develop a compositional neural-symbolic inference process where the neural and symbolic parser collaborates at a more fine-grained level and guided by model uncertainty, which is an aspect missing in the previous neural-symbolic and ensemble parsing literature (see @xcite . we then propose a decision-theoretic criteria to allow for neural-symbolic inference at subgraph level (i.e., nodes and edges) and incorporates the neural parser's fine-grained uncertainty for each graph component prediction (section 4.1). the key to this approach is a meta graph g m that enumerates possible candidates for each node/edge prediction, and is constructed by merging multiple beam predictions from the neural seq2seq model. the core challenge here is how to properly quantify compositional uncertainty using a seq2seq model, i.e., assigning model probability for a node or edge prediction. for example, our interest is to express the conditional probability of a graph node v with respect to its parent p(v|pa(v), x), rather than the likelihood of v conditioning on the previous tokens in the linearized string. as a result, it cannot be achieved by relying on the naive tokenlevel autoregressive probabilities from the beam search. to address this issue, we introduce a simple probabilistic formalism termed graph autoregressive process (gap) (section 4.2). gap adopts a dual representation of an autoregressive process and a probabilistic graphical model, and can serve as a powerful medium for expressing compositional uncertainty for seq2seq graph parsing. we demonstrate the effectiveness of our approach in experiments across a diverse suite of eight in-domain and ood evaluation datasets encompassing domains including wikipedia entries, news articles, email communications, etc (section 5). we achieve the best results on the overall performance across the eight domains, attaining 35.26% and 35.60% error reduction in the aggre-gated smatch score over the neural and symbolic parser, respectively. our approach also exhibits significantly stronger robustness in generalization to ood datasets and long-tail linguistic phenomena than previous work, while maintaining the stateof-the-art performance on in-domain test. further study also shows that the compositionality aspects of neural-symbolic inference helps the model to assemble novel graph solution that the original inference process (e.g., beam search or symbolic parse) fails to provide (section 5.4). in summary, our contributions are four-fold: • we present a novel investigation of neural graph parser's uncertainty calibration performance at subgraph level (section 3). our study confirms the seq2seq uncertainty is effective for detecting model error even out-of-distribution, establishing the first empirical basis for the utility of compositional uncertainty in seq2seq graph parsing. our code is available on github: https://github.com/google/ uncertainty-baselines/tree/main/ baselines/t5/data/deepbank . ## motivation: subgraph-level uncertainty in seq2seq graph parsing we hypothesize that when the neural seq2seq model is uncertain at the subgraph level, it is more likely to make mistakes. assuming the symbolic parser performs more robustly in these situations, we can then design a procedure to ask the symbolic parser for help when the model is uncertain. to validate this hypothesis, we conduct experiments to empirically explore the following two questions: in figure 2 , we plot the bar charts compare the neural and symbolic performance in different bucket of seq2seq model uncertainties on the two largest datasets (e.g., tanaka and brown, see appendix g). results on other datasets can be found in the appendix k. as shown in the figure, low model probability generally corresponds to low t5 performance, while the corresponding ace parser's accuracies spread relatively stably (e.g., it @xmath0, while t5 accuracy @xmath1. this implies that when the model is uncertain, the accuracy of the neural model tend to be low, while the ace parser still performs well. this has motivated us to develop a compositional neural-symbolic inference procedure guided the model's subgraph level uncertainty, such that the t5 and ace parser can collaborate at a more fine-grained level via compostional uncertainty quantification (section 4). ## methods notation & problem statement. for graph semantic parsing, the input is a natural language utterance x, and the output is a directed acyclic graph (dag) @xmath2, e⟩, where n is the set of nodes and @xmath3.g., figure 1(a) ). in the case of seq2seq parsing, g is represented as a linearized graph string @xmath4.g., figure 1(b) ). as the graph prediction is probabilistic, each of the graph element @xmath5, leading to marginal probabilities p(@xmath6 to this end, our goal is to produce a principled inference procedure for graph prediction accounting for model uncertainty on predicting graph elements @xmath7. in the sequel, section 4.1 presents a decision-theoretic criterion that leverages the graphical model likelihood p(g|x) to conduct compositional neural-symbolic inference for graph prediction. to properly express the graphic model likelihood p(g|x) = @xmath8, x) using a learned seq2seq model, section 4.2 introduces a simple probabilistic formalism termed graph autoregressive process (gap) to translate the autoregressive sequence probability from the seq2seq model to graphical model probability. appendix e discusses some additional extensions. ## related work in this section we introduce related work for neuralsymbolic and ensemble learning for graph semantic ## conclusions we have shown how to perform accurate and robust semantic parsing across a diverse range of genres and linguistic categories for english resource grammar. we achieve this by taking the advantage of both the symbolic parser (ace) and the neural parser (t5) at a fine-grained subgraph level using compositional uncertainty, an aspect missing in the previous neural-symbolic or ensemble parsing work. our approach attains the best known result on the aggregated smatch score across eight evaluation corpus from redwoods treebank, attaining 35.26% and 35.60% error reduction over the neural and symbolic parser, respectively.