On Compositional Uncertainty Quantification for Seq2seq Graph Parsing
Authors: Zi Lin
Du Phan
Panupong Pasupat
Jeremiah Zhe Liu
Jingbo Shang
Venue: ICLR 2023 poster (2023)
Keywords: Uncertainty Quantification
Seq2seq Graph Parsing

Abstract: Recent years have witnessed the success of applying seq2seq models to graph parsing tasks, where the outputs are compositionally structured (e.g., a graph or a tree). However, these seq2seq approaches pose a challenge in quantifying the model’s compositional uncertainty on graph structures due to the gap between seq2seq output probability and structural probability on the graph. This work is the first to quantify and evaluate compositional uncertainty for seq2seq graph parsing tasks. First, we proposed a generic, probabilistically interpretable framework that allows correspondences between seq2seq output probability to structural probability on the graph. This framework serves as a powerful medium for quantifying a seq2seq model's compositional uncertainty on graph elements (i.e., nodes or edges). Second, to evaluate uncertainty quality in terms of calibration, we propose a novel metric called Compositional Expected Calibration Error (CECE) which can measure a model’s calibration behavior in predicting graph structures. By a thorough evaluation for compositional uncertainty on three different tasks across ten domains, we demonstrate that CECE is a better reflection for distributional shift compared to vanilla sequence ECE. Finally, we validate the effectiveness of compositional uncertainty considering the task of collaborative semantic parsing, where the model is allowed to send limited subgraphs for human review. The results show that the collaborative performance based on uncertain subgraph selection consistently outperforms random subgraph selection (30% average error reduction rate) and performs comparably to oracle subgraph selection (only 0.33 difference in average prediction error), indicating that compositional uncertainty is an ideal signal for model errors and can benefit various downstream tasks.

Published as a conference paper at ICLR 2023
ON COMPOSITIONAL UNCERTAINTY QUANTIFICATION FOR SEQ2SEQ GRAPH PARSING
Zi L2+ Du Phan2 Panupong Pasupat² Jeremiah Liu
Jingbo Shang"
'CC San Diego "Google Research Haarardd University {lzi, jshang (acang)uucsae recsd.edu
{phandu, ppasupat, jerelin
ABSTRACT
Recent years have witnessed the success of applying seq2seq models to graph parsing tasks, where the outputs are compositionally structured (e.g.. a graph or tree). However, these seq2seq approaches pose challenge in quantifying the model's compositional uncertainty on graph structures due to the gap between seq2seq output probability and structural probability the graph. This work is the first to quantify and evaluate compositional uncertainty for seq2seq graph parsing tasks. First, proposed generic, probabilisticall) interpretable frame- work that allows correspondences between seq2seq output probability to structural probability the graph. This framework serves powerful medium for quanti- fying seq2seq model's compositional uncertainty on graph elements (i.e., nodes edges). Second, to evaluate uncertainty quality in terms of calibration, we pro- pose a novel metric called Compositional Expected Calibration Error (CECE) which can measure model's calibration behavior in predicting graph structures. By thorough evaluation for compositional uncertainty on three different tasks across ten domains, we demonstrate that CECE better reflection for distribu- tional shift compared to vanilla sequence ECE. Finally, we validate the effective- ness of compositional uncertainty considering the task collaborative semantic parsing, where the model is allowed to send limited subgraphs for human review. The results show that the collaborative performance based on uncertain subgraph selection consistently outperforms random subgraph selection (30% average error reduction rate) and performs comparably to oracle subgraph selection (only 0.33 difference in average prediction error), indicating that compositional uncertainty is an ideal signal for model errors and can benefit various downstream tasks. |
INTRODUCTION
Parsing a natural language sentence into compositional graph structure, i.e., graph parsing, is an important task of natural language understanding beyond simple classification or text generation tasks. has been broadly applied applications like semantic parsing, code generation and knowl- edge graph generation. Recently, line of research has successfully applied sequence-to-sequeee (seq2seq) approaches to these graph parsing tasks (Vinyals et al., 2015; Xu et 2020 Orhan [021] Cui et al. 2022 Lin et al.) 2022b). Despite achieving impressive results, these approaches pose challenge in quantilying the model's predictive uncertainty on graph structures, making it hard to ensure trustworthy and reliable deployment of NLP systems such voice assistants (see
ample in Figure D.. Meanwhile, most existing work on uncertainty estimation for seq2seq models focused on classification language generation tasks (Kumar & Sarawagi 2019 Vasudevan al., 2019 Malinin & Gales 2020, Jiang et al.) 2021] Shelmanov et al. 2021 Wang et al.) 2022. Pei al. 2022). However, how to quantify and evaluate compositional uncertainty, the predictive un- certainty over compositional graph elements (i.e.. nodes or edges), remains unresolved for seq2seq graph parsing (see related work Appendix A.2). this paper, we aim answer these questions by proposing a simple probabilistic framework and rigorous evaluation metrics.
"Work done while interning at Google Research. CCo-senior authors.
Open-source code may he found at htantt/ttt///sssshhooooooooooo/a ines

---

Published as a conference paper at ICLR 2023
What time on Tuesday my planning meeting?
Lineerized Graph (Actual Output)
Graph Structure
(findRvent Riventaped
stact
SindEvent
EventSpec
ylanning""
(veelcday
"planning"
Pinespoo
weakdaay
"tuesday"
Uncorlan
Uncertein
Just to make sure. We ore looking for a meeting that's on Tuesday right?
Asdistant
An example for graph semantic parsing in dialogue system. The output of the model is a linearized semantic graph (left) that corresponds to the graph structure (right). The dotted square indicates the uncertain part, based on which the model can ask clarification question.
Figure I:
Quantifying compositional uncertainty for seq2seq graph parsing is inherently more difficult than other seq2seq tasks like machine translation speech recognition, since there is a gap between seq2seq output probabilities and conditional probabilities on the graph. Specifically, our interest is to express the conditional probability of graph node concerning its parent pa(v). i.e., p(v) pa(v), xv), rather than the likelihood u conditioning on the previous tokens in the lincarized string. For ex- ample, in the graph structure of Figure I the subgraph rooted with node TimeSpec (in the dotted square) depends on its parent node EventSpect while in the linearized graph, the parent node is cannot not necessarily the previous token to the subgraph (the shaded spans). Consequently, directly quantify compositional uncertainty without bridging this gap between different probabilis- tic representations. To address this challenge, we propose generic, probabilistic framework called Graph Autoregressive Process (GAP) (e.ction2.1] 2.1 that allows the correspondence between seq2seq output probability to graphical probability, i.e., assigning model probability for node or edge on the graph. Thus, GAP can be used as powerful medium for quantifying a seq2seq model's 's compo- sitional uncertainty. Furthermore, to evaluate uncertainty quality, we propose a novel metric called Compositional Expected Calibration Error (CECH) to measure the model's behavior in predicting compositional graph structures (Section? 2.2
Taking semantic parsing as canonical application, in Section 3 we build large benchmark con- sisting of semantic parsing tasks across 10 different domains, based on which we comprehensively evaluate compositional uncertainty under distributional shift and validate its effectiveness on prac- tical downstream task (collaborative semantic parsing).
First, in Section 3.1 we report different calibration metrics for state-of-the-arr seq2seq parser (Lin ct al.] 2022b) based on TS (Raffel et al.) (020)) as well as its different advanced uncertainty vari- ants on the benchmark. We demonstrate that compared to vanilla ECE based sequence accuracy, CECE is a better metric for reflecting distributional shift, i.e., task difficulty and domain general- ization. We also notice that, despite the strong performance brought by those advanced uncertainty baselines on classification tasks, in the settings of graph parsing, the absolute advantage of these methods no longer holds when predicting graph edges. This suggests that developing uncertainty methods focused on compositional uncertainty can be a fruitful avenue for future research.
we validate the practical effectiveness of compositional uncertainty consid- cring the problem of collaborative semantic parsing. In this setting, the model is allowed to send a limited number of uncertain subgraphs for human review (see Figure for an example). We test the collaborative performance on the benchmark, and find that using uncertain subgraph selection consistently outperforms random subgraph selection (selecting random subgraphs on the predicted graph) with an average егror reduction rate of 30%, and performs fairly close to oracle subgraph selection (selecting incorrect subgraphs on the predicted graph) with an small difference in predic- tion error 0.33. This indicates that compositional uncertainty is an ideal signal for the likelihood on model eиror over graph elements, and can benefit various downstream tasks, e.g., human-AI collaborative parsing and neural-symbolic parsing (Lin et al. 2022a
Second, in Section 3.2
In summary, our work makes the following contributions:
New Framework for Compositional Uncertainty Quantification. We are the first to propose a simple and general probabilistic framework (GAP) that can quantify compositional uncertainty for seq2seq graph parsing. GAP allows us go beyond the conventional autoregressive sequence
2

---

Published as a conference paper at ICLR 2023
probability and express parent-child conditional probability the graph, which is compatible with any graph parsing problem and autoresgressive model.
Rigorous Metrics for Compositional Uncertainty Calibration. We introduce novel quality measurement for compositional uncertainty (CECE) which can evaluate the model's calibration on graph elements and provide better interpretation of the model's behavior in predicting graph structures under distributional shift.
Practical Effectiveness. We comprehensively evaluate the calibration behavior of modern pre- trained large language models, i.e., T5 (Raffel et al. 2020), in compositional uncertainty quan- tification on broad range of semantic parsing tasks of varying complexity (Redwoods, SNIPS, and SMCalFlow). We further evaluate the benefit of compositional uncertainty quantification in enabling new capacity (e.g, fine-grained collaborative prediction for complex semantic parsing) in downstream applications. Specifically, our results show that compositional uncertainty can signif- icantly benefit collaborative parsing performance, with only a 0.33 difference in prediction error compared to the headroom.
2 QUANTIFYING AND EVALUATING COMPOSITIONAL UNCERTAINTY
Problem Formulation. In this work, we interpret the term graph parsing as mapping from surface strings (usually natural language sentences) to target representations that are explicitly or implicitly graph-structured. Formally, the input is natural language utterance and the output is a DAG G= E), where N the set of nodes and E E N N is the set of edges. In the case of seq2seq parsing, G is represented In the experiment, we use PENMAN notation (Kasper 1989) to linearize all the formalism, which serialization format for the directed, rooted graphs used encode semantic dependencies (more details are available in Appendix B
linearized graph string g $1$2 SL consists of symbols {s:)
To this end, our goal is to quantify the graph-level uncertainty p(G[z) from the sequence-level probability p(g[z) generated by seq2seq model, which we term the compositional uncertainty. For example, our interest express the conditional probability of graph node with respect to its parent pa(v), i.e., p(ul pa()),z), rather than the likelihood of u conditioning on the previous tokens the linearized string. In the following sections, we will introduce how quantify (Section 2.1 and evaluate (Section 2.2 this compositional uncertainty.
2.1 QUANTIFYING COMPOSITIONAL UNCERTAINTY VIA GRAPH AUTOREGRESSIVE PROCESS (GAP)
To properly model the uncertainty p[G|z) from seq2seq model, we need intermediate prob- abilistic representation to translate the raw token-level probability to the distribution over graph elements (i.e., nodes and edges). To this end, we introduce simple probabilistic formalism termed Graph Autoregressive Process (GAP), which is a probability distribution assigning seq2seq learned probability the graph elements G.
Specifically, as the sereseq-predieted graph adopts both a sequence-based representation , (N, E), the GAP model adopts both an autoregressive
$1.... $L and a graph representation representation p(g[z) = II p(s; $2i, .) analogous to that of the seq2seq model (Section 2.1.1). and also a probabilistic graphical model representation p(G ()) IleG p(v) pa) for proper quan- tification of model uncertainty on the graph (Section 2.2 Both representations share the same set of underlying probability measures (i.e., the graphical- model likelihood p( (G( can be derived from the autoregressive probabilities p(s:|s<c,, x)). As will show, GAP serves as powerful medium for quantifying compositional uncertainty for seq2seq graph parsing.
2.1.1 AUTOREGRESSIN REPRESENTATION FOR LINEARIZED SEQUENCE g
Given an input sequence x and output sequence y 919/2 .......-00 yN. the token-level autoregres- sive distribution from a seq2seq model p(ylx) = II p(ulvee, In the context graph parsing, the output sequence describes a linearized graph g 3132 3r. where each symbol 8; = (8r Vi2 ... ".,., represents either node n E N or an edge e E E the graph and cor- responds to a collection beam-decoded tokens {y,, Via ... yin, }. This process is illustrated as follows:
3

---

Published as a conference paper at ICLR 2023
y: Vr VaYs V,V,Va ... YuaYN
..
To this end, GAP assigns probability to each linearized graph g = $182 1.. autoregressively as
p(g[z) = II p(s $ s:c, x), and the conditional probability p(s,|s<1, 2) e is computed by aggregat- ing the token probability:
Ni
p(8 = =p((ss ... "VMx,, Hsss, = plu,, Wice, 826,
II
(1)
Marginal and Conditional Probability. Importantly GAP allows us to compute the marginal and (non-local) conditional probabilities for graph elements 8t. Given the input z, the marginal probability of s; is computed as
p(8/(1)) = p(sillce
by integrating over the space of all possible subsequences ses before the symbol s, Then, the (non-local) conditional probability between two graph elements (s) with j is computed
p(s)(s,,2)
p(a,, Si- 8i, sci; s))((s:sssss.))))))) be (r))s
by integrating over the space of subsequences 8!اi between 83) and the subsequence sev be- fore 5;. Higher order conditional (e.g.. ((s)((s,, gives the ability to reason about rong-range dependencies between non-adjacent symbols the sequence. Furthermore, the conditional probability on the reverse direction can also be computed using the Bayes' rule: p(s (5, p(e, p(),(s.))p(ss/1))
81), 81),
can be computed analogously. Notice this
p(ayla)
Efficient Estimation Using Beam Outputs. In practice, we can estimate p(s[(z) and p(s, [s,]s;;))) efficiently via importance sampling using the output from the beam decoding 1K where K is the beam size (Malinin & Gales 2020). The marginal probability can be computed as
exp(: log logr(as(<))
((s:(1)) Σ p(s: (a (i, Tky TT
K Amm exp( log p(g]lz))
here и is the importance weight proportional the beam candidate 9 log likelihoods, and t is the temperature parameter fixed to small constant (e.g., t 0.1) (Malinin & Gales (020). If the symbol 8; does not appear in the hthh beam, we set p(8)|8M.<s, = 0. As shown, the marginalized probability p(s.(z) provides way to reason about the global importance of s; by integrating the
probabilistic evidence s(s x) over the whole beam-sampled posterior space. It is able to capture the cases of spurious graph elements 8; with high local probability p(s,) Sk,ci, x) but low global likelihood (i.e., only appear a few low-probability beam candidates). Therefore, it is a useful quantity for structure induction (e.g., edge and node pruning) in graphical model inference (Diantti 2016).
Then, for symbols (si, with i can estimate the conditional probability
K
exp(+ log I(s, E gx)
p(s)(s,,2) =
Σ p(sy|ss (5,5ssss,,1+55 Sk, Sk,ci, Th Ak
Ek= exp(: (gg(())))) I(s; E gk)
(5)
here गे. is the importance weight among beam candidates that contains s;, Notice this is different from Equation 4 where TT is computed over all beam candidates regardless of whether it contains St-
2.1.2 PROBABILISTIC GRAPHICAL MODEL REPRESENTATION FOR G
So far, we have focused on probability computation based the graph's 's linearized representation p[g[z) = [[ (ig x). In this section, we further consider GAP's graphical model representation p(G|z) TIvee (

---

Published as a conference paper at ICLR 2023
Autoregressive Sequential Representation (Le., Beam Candidates)
9
F1
+
fg
ng
2
ng
9
F1
f
Graphical Model Representation (ie., Meta Graph)
F4
F
+
n2
Figure 2: Visual illustration of constructing graphical model representation for meta graph & from autoregressive representation { 1==1-
k-1 well-established algorithms exist synthesize different graph predictions into meta graph Briefty, these methods first convert each string Io into their original graph representation G (N Ex), then merge multiple graphs
Specifically, given a beam sample of linearized graphs {ou 1K
{G+) using a graph matching algorithm (Cai Knight 2013 Hoang al. 2021).
A visual illustration of the resulting graph G is shown in Figure where and 6j are the candidates for the node and edge predictions collected from beam sequences. As shown, compared to the sequence-based representation, the meta graph G (1) explicitly enumerates different candidates for each node and edge prediction (e.g., T4 V.s. Tig for predicting the first element), and (2) provides an explicit account of the parent-child relationships between variables on the graph (e.g., 67 is child node of ny in the predicted graph, which not reflected the autoregressive representation).
From the probabilistic learning perspective, the meta graph & describes the space of possible graphs (i.e., the support) for graph distribution p(G[z) G > [0, 1]. describes the possible node and edge variables and their dependencies the graph G (i.e., the shaded squares in the Figure 2 and also different possible values for each node and edge variable (i.e., the solid squares within each shaded square in Figure
To this end, GAP assigns proper graph-level probability p(G(ar) to graphs G sampled from the meta graph via the graphical model likelihood:
p(G = II p(v) pa()), vEG
II p(n) pa(n), * II p(el pa(e), cEE
(6)
WEN
where p(u] pa(v), .) the conditional probability for e with respect to their parents pa(v) G. Given the candidates graphs (G+) k== we can express the likelihood for p(u) pa(v).ar .r) by writing down a multinomial likelihood enumerating over different values of pa(c) (Murphy 2012).
This in fact leads to simple expression for the model likelihood simple averaging of the beam- sequence log likelihoods:
1 Σ log ( pa(n) c*) log p(n) pa(n), x) x K
where eg is the value of pa(n) in 1eth beam sequence, and the conditional probabilities are computed using Equation (5). See Appendix [ for detailed derivation.
In summary, for each graph element variable v E G. GAP allows to compute the graphical mooell conditional likelihood p(elpo(e)) ar) via its graphical model representation, and also compute the marginal probability p( (())a)))))))))))))) via autoregressive presentation. Algorithm summarizes the full GAP computation.
2.2 EVALUATING COMPOSITIONAL UNCERTAINTY
In this section, we present how to evaluate compositional uncertainty. A common approach to evaluate model's uncertainty quality is to measure its calibration performance, i.e., whether the
5

---

Published as a conference paper at ICLR 2023
Algorithm Graph Autoregressive Process (GAP)
Inputs:
Beam candidates with probabilities {p(gk[=) Meta graph g
Output:
Marginal probabilities (p(s|z)}, Graph model likelihood log p(G]x)
for E G do
Compute marginal likelihood:
p(u = =|x) (Equation
Compute graphical model likelihood:
log = pa(r)..)) .r) (Fquation
Return
Marginal Probabilities: {p(e|x)}
Graphical Model Likelihood: logp(G(x)) Evec log p(e) pa(v),
model's predictive uncertainty is indicative of the predictive error, e.g., expected calibration error (ECE; Nacini et al., 2015). In this work, we propose a compositional calibration metric based on ECE, which measures the difference in expectation between the model's predictive confidence (c.g., the maximum probability score) on graph elements (nodes or edges) and their actual match to the gold graph.
Formally, during inference time, given input and a target graph G, we first partition the confi- dence interval into B equal bins JI...., JB. Then in each measure the absolute difference between the node/edge accuracy and confidence of predictions that bin. This gives the compositional expected calibration error (CECEe) for graph G as:
1 G
Σ
C(e, G)
E. 2)E4
where |G] is the number of graph elements in the target graph G, 6g is the tth element (node/edge) in the predicted graph G. C(ăa, G:) denotes if 0e matches in the graph G, using graph matching algorithm, and p(0g|ar can be obtained by GAP in Section 2.1 Specifically, we use the matching algorithm adopted in SMATCH (Cai & Knight 2013). which is the same graph matching algorithm for constructing meta graph G (see Appendix for details). Alternatively, we can compute CECE only for node/edge predictions, namely CECEN and CECEg.
EXPERIMENTAL EVALUATION
Datasets. In this paper, we take semantic parsing canonical application, and build a large benchmark consisting of three semantic parsing tasks and covering ten different domains, ranging from graph-based grammar parsing to dialogue-oriented semantic parsing:
Redwoods: The LinGO Redwoods Treebank is a collection of hand-annotated corpora for an En- glish grammar consisting of more than 20 datasets. The underlying grammar is called English Resource Grammar (ERG; Flickinger et al. 20144) Bender et al. 2015). which is an open-source, domain-independeenr linguistically precise, and broad-coverage grammar. ERG can be presented into different types of annotation formalism. This work focuses on the Elementary Dependency Structure (EDS: Oepen & Lønning 2006), which is compact representation that be pressed as a DAG. Following previous works, for in-domain test, we train and evaluate models on the subset treebank corresponding to the 25 Wall Street Journal (WSJ) sections with standard data splits (Flickinger et al. 2012). For out-of-domain (OOD) evaluations, we select 7 diverse datasets from Redwoods: Wikipedia (Wiki), the Brown Corpus (Brown), the Eric Raymond Essay (Es- say), customer emails (E-commerce), meeting/hotel scheduling (Verbmobil), Norwegian tourism (LOGON) and the Tanaka Corpus (Tanaka) (See Appendix [ for more details).
SMCalFlow: SMCalFlow (Andreas et al.] 2020) is a large corpus of semantically detailed an- notations of task-oriented natural dialogues. The annotation uses dataflow computational graphs, composed of rich set of both general and application specific functions, to represent user re- quests as rich compositional expressions. We use the standard data split in the original paper and evaluate inference results on development set.
SNIPS: SNIPS (Coucke et al.) 2018) is a slot filling dataset containing 39 slot names from different domains collecting from the SNIPS voice assistant. is usually formulated sequence

---

Published as a conference paper at ICLR 2023
Performance Metries SMATCH(1)
Calibration Metrics
Dataset
ACC
Flx
Flg(()
(CF,,())
CBCC&(L)
(ECEx(()
CFCFg(()
WSJ (In domain)
$1.01
95.92
97.38
94.33
0.3632
0.0345
0,0221
0.0465
Min
Doesain distanee
Tanaka
68.10
95.27
95.65
94.95
0.2562
0,0452
0,0405
0,0498
E.commence
94.18
0.0652
Brown
40.93
92.32
93.81
90.89
0.3969
0.0673
0,0530
0.0824
Essay
30,80
94.18
0.4589
0.0691
0.0565
0.0808
1.OGON
31.45
91 91.10
92.58
90.20
0.5148
0.0334
0.0726
0.0944
Verbmobil
51.45
90.38
91.45
90.02
0.3298
0.0960
0.0861
0.1063
Wilki
28.16
64
90.65
89.37
0.4105
0.1038
0.0939
0.1135
SMCallow
82.83
93.87
94.21
93.48
0.1427
0.0651
0.0605
0.0702
SNIPS
98.49
0.0756
Max
Table Evalution results on three tasks. Aceseg means sequence accuracy (exact match); F/ means Fl scores for nodes/edges; CECE for graph/nodes/edges. Since we use pseudo edges to transfer examples to graphs for SNIPS, we skip edge-related evaluations for SNIPS. The background color in calibration metrics indicates the number order in column (Green: Min; Red: Max).
means compositional ECE
labeling problem. Following previous work (Yu et al. 2021b. we train models on five source domains, use sixth for development, and test the remaining domian.
We transfer all the data into linearized graphs (Appendix B To reduce the sequence length, since the number of node/edge names are limited, we set them untokenizable to the tokenizer.
Evaluation Metrics, Consistent with previous work, the performance metric used for Redwoods is SMATCH score (Cai & Knight 2013), which computes the degree of overlap between two semantic graphs (see Appendix D for details). For SMCalFlow, we use sequence accuracy (exact match). For SNIPS, we slot Fl score, which is equal to node F1 score when transfer the SNIPS data into PENMAN notation. For model calibration, we report naive ECE based on sequence accuracy and compositional uncertainty CECE introduced Section 2.2
Seq2seq Model. We adopt T5 (Raffel et al. 2020) as the baseline model, which is pre-trained seq2seq Transformer model that has been widely used in many NLP applications. We use the open-sourced T5X] which is new and improved implementation of T5 codebase in JAX and Flax. Specifically, we use the official pretrained Ta-large (770 million parameters) and finetuned it on three datasets respectively. By evaluating the performance metrics for each task, we find that the T5 model is capable of achieving the state-of-th the-trrrrt results on all the tasks compared to previous work (see Table 3 in Appendix ( for full comparison).
3.1 EVALUATING COMPOSITIONAL UNCERTAINTY UNDER DISTRIBUTIONAL SHIFT
Comparing Compositional ECE to vanilla ECE. Table reports the evaluation results on the benchmark. First, we find that sequence accuracy (ACCseq) does not necessarily correlate to the SMATCH score, which makes the vanilla ECE based on sequence accuracy, i.e., ECEwey, less infor- mative in reflecting model's ' calibration on predicting graph structures. Second, comparing to Red- woods (in-domain) which requires parsing a natural language sentence into a pre-defined grammar representation, and SNIPS which requires labeling intent slots for natural language sentence, SM- CalFlow is more ambiguous and difficult as it involves complex dialogue histories and fine-grained intent slots (Andreas al. 2020 We notice that the CECE is larger for SMCalFlow on in-domain test, indicating that CECE is better metrics to reflect this task ambiguity/dffficule the model generalization degrades across different domains for Redwoods, CECE also increases accordingly, indicating that CECE can reflect model's generalization under domain shift.
Finally, as
Comparing Advanced Uncertainty Methods. In recent year, variety of methods have been devel- oped to improve the DNNs uncertainty quality for classification problems. Here, we are interested to understand the benefit brought by those advanced methods to classification setting translates also to the graph parsing setting. In this section, we evaluate the performance of 6 uncertainty baselines on Redwoods across 8 different domains. We consider T5-Large (Raffel et al.) (2220) as the base model, and select six methods based on their practical applicability for the base model.
Specifically, we consider (1) Deterministic model which is the base T5 model: (2) Monte Carlo Dropout (MC Dropout) which estimates uncertainty using the Monte Carlo average of 5 dropout samples Gal & Ghahramani 2016):: (3) Deep Ensemble (DE) which trains 4 deterministic models individually and averages all predictions (Lakshminarayanan et al. 2017); (4) Batch Ensemble (BF),

---

Published as a conference paper at ICLR 2023
Deterministi
DE
SNGP
SNGP-DE
SNGP18E
01
0.00
0.2
Tanala
Fromr
Pray
LocoR
Part:
2912
195)
Tonsta
Emey
LOCDN
wil
Tassin
From
Blay
Loccte
Wert.
0.12
2.30
0.08
3.06
3.6
0.07
5.02
1951
Tanala
From
Exsy
Looo
Port:
Tonsta
Brown
Exey
LOGON
Figure 3: Evaluation results for different uncertainty baselines in terms of SMATCH score, ECEsey
CÉCE3 CECEN, and CECEg under distributional shift.
an ensemble method which has much lower computational and memory costs comparing to MC Dropout and Deep Ensemble (Wen et al. 2019); (5) Spectral-normalized Neural Gaussian Process (SNGP), recent state-of-the neural network into an approximate Gaussian process model (Liu al. 2020); (6) SNGP+DE which
approach which improves uncertainty quality by transforming
is the deep ensemble for 4 individual SNGP models; (7) SNGP+BE which
combination of The full evaluation results
Batch Ensemble and SNGP layers. The results are shown in Figure
be found in Appendix G (Table 4h.
Results. As shown the figure, these uncertainty baselines generally follows the same pattern on domain shift, i.c., decrease SMATCH corresponds increase in CECEg, while we cannot in- fer distributional shift via ECE.q Some uncertainty baselines (c.g.. MC Dropout and SNGP+DE) can achieve better in both ECE, and CECEg compared to deterministic model across different domains, where MC Dropout achieves the best results in ECEwey and SNGP+DE achieves the best results in CECE.- By further evaluating CECEN and CECEE, we notice that the improvement in CECE; mainly comes from node predictions (the difference in CECEN is more obvious than CECEg), while for edge predictions, only little improvement is observed. This suggests that uncer- tainty estimation is structurally different for seq2seq graph parsing tasks compared to classification tasks, and further research is needed for designing better calibrated model with more focus on com- positional uncertainty calibration.
3.2 PRACTICAL EPFECTIVENESS: UNCERTAINTY-GUIDEI COLLABORATIVE SEMANTIC PARSING
Motivation. To further explore the correlation between model uncertainty and performance, we plot the histogram for the T5 model's probabilities verses the node/edge accuracies Appendix H (Fig- ure (). where we find that low model probability generally corresponds to low model performance. This serves as motivation for collaborative semantic parsing using composotional uncertainty, where the model is allowed to send a limited number of uncertain subgraphs for human review. This a practical setting in lots of realistic scenarios, for example, in Figure [ the model can ask for clarification regarding the uncertain subgraph (dotted squared) via modeling the uncertainty score for each element in the parsed semantic graph. This process allows the system to collaborate with the users to avoid triggering unwanted actions, which cannot be achieved without properly quantifying compositional uncertainty over graph elements.
pucrtainty-based Subgraph Selection. uncertain subgraphs by (1) finding e uncertain nodes as root nodes based on ranked compositional uncertainty scores the predicted graph; (2) tracing descendants from root nodes up depth
For well-trained seq2seq parser in Section 3.1 find
? Here the number of subgraphs and the maximum depth d are our review capacity for uncertain subgraphs (in experiment, try E [1,3, and d [1, (1).
8

---

Published as a conference paper at ICLR 2023
(13 WSgg (ch-21
(5) SMC low (ch-2)
(4) SNIPP (ch-11
100
1400
10.0
Craci Dra-ten
Crucks
Creck
47.25
Drocee
0 $7.00
66.75
Seqparoe
30
$5.0
50.0
16.2
11.00
Numberat Subgrephe
Number Subgraote (e]
Number Subgraphe
Figure 4: Collaborative performance for different semantic parsing tasks. The performance metrics are SMATCH score for Redwoods, sequence accuracy for SMCalflow and slot (node) FI for SNIPS
Baselines for Comparision. We take another three subgraph selections as comparision: (1) Random subgraph selection by randomly finding e nodes root nodes and tracing descendants from roots up to depth d: (2) Oracle subgraph selection by finding e incorrectly predicted nodes as root nodes and tracing descendants from roots up depth d: (3) Oracle* subgraph selection by finding incorrectly predicted nodes (prioritizing the most uncertain nodes) and tracing descendants from roots up to depth d.
Training and Inference. The training examples for the collaborative model are generated by at- taching human edit results of random subgraphs imput sentences During the inference, the test examples are generated by attaching corresponding human edit results for each subgraph selection strategy to input sentences.
Results.
The results are shown in Figure Due to space limitation, we only report results on for SNIPS. Full results for different combinations
for Redwoods and SMCalflow, and of example numbers and depths are reported in Table 5 and Table [6] (Appendix []. We see that for all three tasks, uncertainty-base selection with average error reduction rates 13.64%, 24.45% and 52. 12.11% respectively, and performs fairly close to Oracle with an average difference in prediction error as small as 0.33. This shows that compositional uncertainty is effective in detecting potential incorrect subgraph predicted by the model. Meanwhile, we notice that Oracle* performs better than Oracle, indicating that incorrect predicted subgraphs with high uncertainty
subgraph selection consistently outperforms random subgraph
informative the collaborative model.
Theoretically, the performance of collaborative parsing is determined by how many in- correctly predicted subgraphs can be selected for human edits, where Oracle is the headroom given limited budgets. In Table / (Appendix [] We further conduct an analysis to subgraphs selected by different strategies by calculating the coverage rate of incorrect nodes in subgraphs to incorrect nodes in the entire graph (i.e., eтror node coverage rate). The results indicates that compositional uncertainty is effective in detecting incorrectly predicted nodes.
Analysis.
4 CONCLUSION AND FUTURE WORK
Over the past few years, lots of efforts have been made to apply seq2seq models to graph parsing, which an important area NLP. Despite achieving the state-of-the-art in various graph parsing tasks, these seq2seq approaches pose challenge on how to interpret model's predictive uncertainty on predicting graph structures. This work is the first to provide general method to properly quan- tify and evaluate compositional uncertainty for seq2seq graph parsing, which is achieved by simple probabilistic framework (GAP) and rigorous metric (CHCE). The experimental evaluation demon- strates that CECE is an effective metric to reflect distributional shift and compositional uncertainty is a useful tool for downstream tasks such as collaborative semantic parsing. For future work, several directions are worth investigations, including: (1) evaluating the practical effectiveness of advanced uncertainty methods in collaborative semantic parsing; (2) learning theoretic experiments to inter- rogate the seq2seq model's ability in capturing the true distribution of the probabilistic graphical model; (3) extending the benefit of compositional uncertainty to more real-world NLP tasks, e.g., vetrieval-augmest augmented semantic parsing (Hashimoto al.. 2018) and active learning.
'The model is of the same setting in Section 3.1
Here we take gold subgraphs human edit results.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We appreciate the insightful comments from the anonymous reviewers. We would like to thank Jie Ren for discussion and proofreading.
REFERENCES
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dornrr, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk. Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, llya Lintsbakh, Andy McGovern, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin. Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thom- son, Andrei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexan- der Zotov. Task-oriented dialogue as dataflow synthesis. Transactions of the Association doi: 10.1162ttcl URL https:
for Computational Linguistics, 8:556-571, 2020.
//aclanthology Swwpatthoooy....g///0o. ttt.:/........111111...
Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. Abstract Meaning Representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperabil- ity with Discourse, pp. 178-186, Sofia, Bulgaria, August 2013. Association for Computational org/ 3 2322
Linguisties. URL
Emily M. Bender, Dan Flickinger, Stephan Oepen, Woodley Packard, and Ann Copestake. Layers of interpretation: On grammar and compositionality. In Proceedings of the 11th International Conference on Computational Semantics, pp. 239-249, London, UK, April 2015. Association for /1 5 0128
Computational Linguistics.
Michele Bevilacqua, Rexhina Blloshmi, and Roberto Navigli. One spring to rule them both: Sym- metric amr semantic parsing and generation without a complex pipeline. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12564-12573, 2021.
Shu Cai and Kevin Knight. Smatch: an evaluation metric for semantic feature structures. In Pro- ceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 748-752, Sofia, Bulgaria, August 2013. Association for Computational Linguisties.
Junjie Cao, Zi Lin, Weiwei Sun, and Xiaojun Wan. Comparing knowledge-intensive and data- intensive models for English resource semantic parsing. Computational Linguistics, 4731):43 68, March 2021. doi: 10.1 162/coli a a_00395. URL
Yufei Chen, Weiwei Sun, and Xiaojun Wan. Accurate SHRG-based semantic parsing. In Pro- ceedings of the 56th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers). pp. 408 418, Melbourne, Australia, July 2018. Association for Computational Lin- guistics. doi: 18.18653/v I/P18- 1038. UtL http://://///aaahhhcacsee www.thhoo.ooggo..o...ooo 1038
Yufei Chen, Yajie Ye, and Weiwei Sun. Peking at MRP 2019: Factorization- and composition- based parsing for elementary dependency structures. In Proceedings of the Shared Task Cross- Framework Meaning Representation Parsing at the 2019 Conference on Natural Language Learn- ing, pp. 166-176, Hong Kong, November 2019. Association for Computational Linguistics. doi: 11/8863/1//K112220
URL
Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, al. Snips voice plat- form: an embedded spoken language understanding system for private-hy-design voice interfaces. arXiv preprint 1rxvv:1805.1111 2018
Ruixiang Cui, Rahul Aralikatte, Heather Lent, and Daniel Hershcovich. Compositional generaliza- tion in multilingual semantic parsing over wikidata. Transactions of the Association for Compu- fational Linguistics, 10:937-955. 2022.
10

---

Published as a conference paper at ICLR 2023
Navid Dianati. Unwinding the hairball graph: Pruning algorithms for weighted complex networks.
Physical Review E, 93(1)x0123 2016.
Li Dong, Chris Quirk, and Mirella Lapata. Confidence modeling for neural semantic parsing. Pro- ceedings of the 56th Annual Meeting of the Association for Computational Linguistics ( (Volume /: Long Papers), pp. 743-753, Mclbourne, Australia, July 2018. Association for Computational Lin- guistics. doi: 10.18653/v 1/P18- 1069. URL http:t:sss//aaaaatohooggeeo
azg/P18-1069
Andrew Drozdov, Jiawei Zhou, Radu Florian, Andrew McCallum, Tahira Naseem, Yoon Kim, and Ramón Astudillo. Inducing and using alignments for transition-based AMR parsing. In Pro- ceedings of the 2022 Conference of the North American Chapter of the Association for Compu- tutional Linguistics: Human Language Technologies, pp. 1086-1098, Seattle, United States, July 2022. Association for Computational Linguistics. doi: wwtpo////2222 wtw.:/222n.aaaaca..m..a naacl maaeee-mmin.. 80.
1/2022.nac222 main.80. URL
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah Smith. Recurrent neural network
grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Language Technologies, pp. 199-209, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10.18653/11/16-10000 1024.
URL https: http::://aaaathoologgooo htw.laanthooooyoor//iie org/N16 1024
Ramón Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, and Radu Flo-
rian. Transition-based parsing with stack-transformers. In Findings of the Association for
Computational Linguistics: EMNLP 2020, pp. 1001-1007, Online, November 2020. Associa-
tion for Computational Linguistics. doi: 10.18653/v1/2020) //aclanthology..ek wtw.://www..r./2.............. windiiggn...nnnnnsnneee http://000...inngeeeeiiie
URL https:
Dan Flickinger, Yi Zhang, and Valia Kordoni. Deepbank. dynamically annotated treehank of the wall street journal. In Proceedings of the 11th International Workshop on Treebanks and Linguistic Theories, pp. 85-96, 2012.
Dan Flickinger, Emily M. Bender, and Stephan Oepen. Towards an encyclopedia of compositional semantics: Documenting the interface of the English Resource Grammar. In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'I4) 14), pp. 875- 881, Reykjavik, Iceland, May 2014. European Language Resources Association (ELRA). URL http: / www. rec- conf. o
.ddf
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learming, pp. 1050-1059. PMLR, 2016.
Tatsunori B Hashimoto, Kelvin Guu, Yonatan Oren, and Percy S Liang. A retrieve-and-edit frame- work for predicting structured outputs. Advances in Neural Information Processing Systems, 31, 2018.
Thanh Lam Hoang, Gabriele Pieco, Yufang Hou, Young- Lee, Lam Nguyen, Dzung Phan, Vanessa Lopez, and Ramon Fernandez Astudillo. Ensembling graph predictions for amr pars- ing. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 8495-8505. Curran Asso- ciates, Inc., 2021. URL https:::pproceedigg.... neurips.....pp........... sc/pppee/222///ile// 479bb6deSaaTD0DD1eeebebbblee
Papere pdf
Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How can we know when language models know? on the calibration of language models for question answering. Transactions the Association for Computational Linguistics, 9:962-977, 2021. doi: a URL
htttp:://aclamtholoog
Robert T Kasper. A flexible interface for linking applications penman's 's sentence generator. In Speech and Natural Language: Proceedings of a Workshop Held at Philadelphia, Pennsylvania, February 21-23, 1989, 1989.
11

---

Published as a conference paper at ICLR 2023
Ioannis Konstas, Srinivasan Iyer, Mark Yatskar, Yejin Choi, and Luke Zettlemoyer. Neural AMR: Sequence-to-see -o-euueecee models for parsing and generation. In Proceedings of the 55th Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 146-157, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653/v1/ P17-1014. htt.h//pe///ccclaccoooooo.ooorg.
Aviral Kumar and Sunita Sarawagi. Calibration of encoder decoder models for neural machine translation. arXiv preprint
2019.
Balaji Lakshminarayanan. Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances neural information processing systems, 30, 2017.
Zi Lin, Jeremiah Liu, and Jingho Shang. Neural-symbolic inference for robust autoregressive graph parsing via compositional uncertainty quantification. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4759-4776, Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics.
Zi Lin, Jeremiah Zhe Liu, and Jingbo Shang. Towards collaborative neural-symbolic graph se- mantic parsing via uncertainty. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 4160-410 4170, Dublin, Ireland, May 2022b. Association for Computational Linguis- tics. doi: 10. 10.118653/11/022.. htt.://////.222....nnnn---a-- indings-acl.328. URL https::// http:p/////claatthooooo..o..o/// Findings-aci- 328
Jeremiah Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax Weiss, and Balaji Lakshmi- narayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances in Neural Information Processing Systems, 33:7498-7512, 2020.
David M. Magerman and Mitchell Mareus. Pearl: A probabilistic chart parser. In Fifth Confer- ence of the European Chapter of the Association for Computational Linguistics, Berlin, Germany, April 1991. Association for Computational Linguistics. URL
org erg/E91- 1004
Andrey Malinin and Mark Gales. Uncertainty estimation in autoregressive structured prediction. In International Conference on Learning Representations, 2020.
Ryan McDonald. Discriminative learning and spanning tree algorithms for dependency parsing.
University of Pennsylvania Philadelphia, 2006.
Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated prob- abilities using bayesian binning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Roberto Navigli, Rexhina Blloshmi, and Abelardo Carlos Martinez Lorenzo. Babelnet meaning representation: A fully semantic formalism to overcome language barriers. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 12274-12279, 2022.
Joakim Nivre. Algorithms for deterministic incremental dependency parsing. Computational doi: 10.1162/cu0.077055-----777000000
Linguistics, 34(4)5513-553, 2008
URL https://
aclanthology. wwtp://ooooyyoo/0-----o---0
Stephan Oepen and Jan Tore Lønning, Discriminant-base based MRS banking. In Proceedings the Fifth International Conference on Language Resources and Evaluation (LREC'06), Genoa, Italy, May 2006. European Language Resources Association (ELRA). URL wwtp:tttp////.. wwwp coff bote///ooeedinng///eee00//////// httpe///444p_ffff_aee pdf
A Emin Orhan. Compositional generalization in semantic parsing with pretrained transformers.
arXiv preprint 109 2021.
Jiahuan Pei, Cheng Wang. and György Szarvas. Transformer uncertainty estimation with hierar- chical stochastic attention. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11 11147-1115. 2022.
12

---

Published as a conference paper at ICLR 2023
Xiaochang Peng, Chuan Wang, Daniel Gildea, and Nianwen Xue. Addressing the data spar- sity issue in neural AMR parsing. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguisties: Volume 1, Long Papers, pp. 366- 375, Valencia, Spain, April 2017. Association for Computational Linguistics. URL https:
T/aclanthollogy.ooo 7
Libo Qin, Wanxiang Che, Yangming Li, Haoyang Wen, and Ting Liu. A pack-propagation frame- work with token-level intent detection for spoken language understanding. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Inter- national Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2078-2087, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. Mach. Learn. Rex., 21 (1140)) 2020.
Artem Shelmanov, Evgenii Tsymbalov, Dmitri Puzyrev, Kirill Fedyanin, Alexander Panchenko, and Maxim Panov. How certain is your Transformer? In Proceedings of the 16th Conference of the European Chupter of the Association for Computational Linguisties: Main Volume, pp. 1833- 1840, Online, April 2021. Association for Computational Linguistics. doi: 10. (0.18653/1/20211 cacl-main. 157. URL https: http://aaaaantooo...oooooo /tt.ppppp///ccaaaooooooooooooo
Jens EL Van Gysel, Meagan Vigus, Jayeol Chun, Kenneth Lai, Sarah Moeller, Jiarui Yao, Tim O' D'Gorman, Andrew Cowell, William Croft, Chu-Ren Huang, et al. Designing a uniform meaning representation for natural language processing. KI- KI-Kinstliche Intelligenz, 35(3):343-33) 2021.
Vishal Thanvantri Vasudevan, Abhinav Sethy, and Alireza Roshan Ghias. Towards better confidence estimation for neural models. In ICASSP 2019- JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 7335-7339 IEEE, 2019.
Oriol Vinyals, E ukasz Kaiser, Terry Koo, Slav Petrov, llya Sutskever, and Geoffrey Hinton. Gram- mar foreign language. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Asso- ciates, Inc., 2015. URL
Paper. pdf
Yu Wang, Yilin Shen, and Hongxia Jin. A bi-model based RNN semantic frame parsing model for intent detection and slot filling. In Proceedings of the 2018 Conference of the North Ameri- can Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Short Papers). pp. 309-314, New Orleans, Louisiana, June 2018. Association for Com- putational Linguistics. doi: 00.18653/v1/N188 11/3/11/N11-205/ 2050. URL ht.p:://aclaatthooooyy
N18 2000
Yuxia Wang, Daniel Beck, Timothy Baldwin, and Karin Verspoor. Uncertainty estimation and reduc- tion of pre-trained models for text regression. Transactions of the Association for Computational Linguisticc, 10:680-696, 2022. doi: 10. 1,2/1662/cccaa000 a 00483. URL org/ /ogg/202.cco Eacc-1...
Yeming Wen, Dustin Tran, and Jimmy Ba. Batchensemble: an alternative approach to efficient ensemble and lifelong learning. In International Conference on Learning Representations, 2019.
Dongqin Xu, Junhui Li, Muhua Zhu, Min Zhang, and Guodong Zhou. Improving amr parsing with sequence-to-seqqeecc pre-training. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 2501-2511, 2020.
Hiroyasu Yamada and Yuji Matsumoto. Statistical dependency analysis with support vector ma- chines. In Proceedings of the Eighth International Conference on Parsing Technologies, pp- 195-206, Nancy, France, April 2003. URL htttts:://aaaaaahllllataa
org. wwg/wo3- 3023
Dian Yu, Luheng He, Yuan Zhang, Xinya Du, Panupong Pasupat, and Qi Li. Few-shot intent clas- sification and slot filling with retrieved examples. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 734-749, 2021.
13

---

Published as a conference paper at ICLR 2023
Chenwei Zhang, Yaliang Li, Nan Du, Wei Fan, and Philip Yu. Joint slot filling and intent detec- tion via capsule neural networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. pp. 9259-52667, Florence, Italy, July 2019. Association for Com- URL https: ac www.clnnhhollc..oo loy.. ogy.org/
putational Linguistics. doi: 10. 10.18633/v1/11-11
P19-1519
Jiawei Zhou, Tahira Naseem, Ramón Fernandez Astudillo, and Radu Florian. AMR parsing with action-pointer transformer. In Proceedings of the 2021 Conference the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5585- 5598, Online, June 2021. Association for Computational Linguistics. doi: 10.1 (0.18653/v1/2022 naacl-main.443, URL https:
woa.hhlloy...r.gg...... nnac -ma n. 443
A RELATED WORK
A.1 SEQ2SEQ GRAPH PARSING
Seq2seq graph parsing is inspired by the success of recent seq2seq models (particularly pretrained models), which are the heart of modern neural machine translation. This type of parser encodes and views target graph string from another language (Vinyals et al. 2015).
However, simply applying seq2seq models to graph parsing is not always successful when the target graph is complecated, e.g., for Abstract Meaning Representation (AMR: [Banarescu al. 2013) or English Resource Grammar (ERG; Flickinger et al.] 2014). This is because effective linearization (encoding graphs as linear sequences) and data sparsity were thought pose significant challenges KKnntaa et al. 2017). Alternatively, some specifically designed preprocessing procedures for vo- cabulary and entities can help address these issues (Konstas et al. 2017 Peng el al.) 2017). These preprocessing procedures are very specific to certain type of meaning representation and are dif- ficult to transfer others. To address this, (Bevilacqua et al., (021) propose use special tokens to represent variables in the linearized graph and to handle co-referring nodes. [in et al. (2022b) propose a variable-free top-down linearization and a compositionallty-awaar graph preprocessing, and successfully transfer the ERG parsing into translation problem that can be solved by a state-of-the-an seq2seq model T5 (Raffel et al. 2020). Their parser achieves the best known results on the in in-oomain test set for ERG parsing.
tokenization for ERG
A.2 UNCERTAINTY QUANTIFICATION FOR GRAPH PARSING
Compared to seq2seq graph parsing, uncertainty quantification is straightforward if the parser explicitly models the target graph structures, e.g., chart parsers (Magerman & Marcus 1991), factorization-bart parsers (McDonald) 2006 Cao et al., 2021) or composition-based parsers (Chen et 2018 2019), given that the model's score function naturally aligned with the graph structure. As for transition-based parser (Fernandez Astudillo et al.) 2020 Zhou et al., (202I). where the target graph is generated via series of actions, in a process that is very similar to dependency tree pars- ing Yamadaa & Matsumoto| 20033; Nivre 2008), some previous work has used important sampling estimate probabilities (Dyer al.) 2016). and model uncertainty for alignments between graph nodes and imput text tokens (Drozdov et al. 2022). These works are very specific to the formalism of the target graph, and it is difficult to transter to other graph parsing problems.
Some previous uncertainty quantification methods have focused on sequential or token-level uncer- tainty for seq2seq model. For example, Dong et al. (2018) model uncertainty for neural semantic parsers by outlining three major causes of uncertainty including model uncertainty, data uncertainty and input uncertainty, and design various metrics to quantify these factors. [in et al. (2022b) uses predictive probability generated by the T5 model signal for neural-symbolic parsing. However, these uncertainty quantification methods cannot model compositional uncertainty over the graph structures.
B PENMAN NOTATION
PENMAN notation, originally called Sentence Plan Notation in the PENMAN project (Kasper) 1989). is a serialization format for the directed, rooted graphs used encode semantic dependencies,
14

---

Published as a conference paper at ICLR 2023
N
N1
E
E1 ( N3
E4 ( NS )
ES ( N6*
E
E
:2 ( N4
:E3-of N2
2
N
EE N6*
Graph
PENMAN Graph
most notably in the Abstract Meaning Representation (AMR) framework (Banarescu et al. 2013). It looks similar Lisp's S-Expression in using parentheses to indicate nested structures. To make PENMAN notation compatible with the seq2seq learning, we adopted variable-free version of PENMAN which was first proposed in Lin et al. (2022b). The general template illustrated as follows:
The linearized form can only describe projective structures such as trees, so in order to capture non- projective graphs, this notation (1) reverse some of the edges to make it can be written in top-down tree order, e.g., of here (2) use star markers indicate a node referred later to establish reentrancy, e.g., E here. Table 2 shows some variable-free PENMAN linearized examples for different semantic parsing tasks.
Datasets
Inputs
Outputs
tARG1 named ceery "Bentagon"
Redwoods
The Pontagon foiled the plan.
:BV-oE -theeg 1
:ARG2
.plan.n..
:BV-0E .the_q
start findsvent
SMCalfow
User: What time on Thesday my planning meeting?
FARG]
:ARG1 Ryent-ppe sname "planning"
tstact Timespec tweekday "tuesday"
S.SSEAKKLLGRAATVE....O icarg "movie"
SNIPS
Find movic called Living in America.
:ARSI SULOOBJECTTTTTE
:ARG?
SlIOORTRCT NAME. searg "Living, Incamerr rea
Table Examples for variable-fre free PENMAN lincarized graph (template can be found in Appendix in three different semantic parsing tasks (task details can be found in Section 3). Here carrg means corresponding spans in the sentence.
C SIMPLIFIED EXPRESSION FOR GRAPHICAL MODEL LIKELIHOOD
Given the candidates graphs (K down a multinomial likelihood enumerating over different values of pa(e) (Murphy 2012). For example, say pa(n)- (e1, e2) which represents subgraph of two edges (e1, e2) pointing into node n. Then the conditional probability p(n) pa(n), æ) can be computed by enumerating over the observed values of (e1, 62) pair:
can express the likelihood for p(vl pa(u),a x:) by writing
p(n] pa(m), x) p(n[(e1, 22),
II
e2) e2) = =c
oE CECandiinl((rr.ea))
where Candidate(e) is the collection of possible symbols s the variable e can take, and K₃ is the number of times (2) takes particular value Candidate(e e2) Candidate(ei) x Candidate(e2).
Then, the log likelihood becomes:
log logp(n)pa(n).a)) Σ logp(n((er,,e) c)
(10)
To simplify this above expression, we notice that log p(n) pa(n), x) can be divided by the constant beam size K without impacting the inference. As result, the log probability be computed by
15

---

Ke Published as a conference paper at ICLR 2023
simplify averaging the values of log p(u) pa(t) ck) across the beam candidates:
K
log pa(n), x)) Σ
log logp(n((e1,,)) [2) = 1
logp(n|(e1, 02)== =cx)
(11)
K
where cp is the value of (e1, 62) hthh beam candidate.
D OOD DATASETS FOR ERG PARSING
Wikipedia (Wiki) The DeepBank team constructed treebank for 100 Wikipedia articles on Com- putational Linguistics and closely related topics. The treebank of 11,558 sentences comprises 16 sets articles. The corpus contains mostly declarative, relatively long sentences, along with some fragments.
The Brown Corpus (Brown) The Brown Corpus was carefully compiled selection of current American English, totalling about million words drawn from wide variety of sources.
The Eric Raymond Essay (Essay) The treebank is based on translations of the essay "The Cathe- dral and the Bazaar" by Eric Raymond. The average length and the linguistic complexity these sentences is markedly higher than the other treebanked corpora.
E-commerce While the ERG was being used in commercial software product developed by the YY Software Corporation for automated response to customer emails, a corpus training and test data was constructed and made freely available, consisting of email messages composed by people pretending to be customers of fictional consumer products online store. The messages in the corpus fall into four roughly equal-sized categories: Product Availability, Order Status, Order Cancellation, and Product Return.
Meeting/hotel scheduling (Verbmobil) This dataset is collection of transcriptions of spoken dialogues, each of which reflected negotiation either to schedule meeting, to plan a hotel stay. One dialogue usually consists of 20-30 turns, with most the utterances relatively short, including greetings and closings, and not surprisingly with high frequency of time and date expressions as well as questions and sentence fragments.
Norwegian tourism (LOGONN The Norwegian/English machine translation research project LO- GON acquired for its development and evaluation corpus set of tourism brochures originally writ- in Norwegian and then professionally translated into English. The corpus consists almost entirely of declarative sentences and many sentence fragments, where the average number of tokens per item higher than in the Verbmobil and E-commerce data.
The Tanaka Corpus (Tanaka) This treebank is based parallel Japanese- Eopanese-English sentences, which was adopted to be used with in the WWWJDIC dictionary server as a set of example sentences associated within words in the dictionary.
GRAPH MATCHING ALGORITHM IN SMATCH
In general, finding the largest common subgraph is well-known computationally intractable prob- lem graph theory. However, for graph parsing problems where graphs have labels and a simple tree-like structure, some efficient heuristics are proposed to approximate the best match by hill- climbing algorithm (Cai & Knight 2013). The initial match modified iteratively to optimize the total number of matches with predefined number of iterations (default value set to 5). This algo- rithm is very efficient and effective, was also used to calculate the SMATCH score in Cai Knight 2013).
16

---

Published as a conference paper at ICLR 2023
F COMPARING T5 TO PREVIOUS WORK
Table shows the in in-domain performance of the T3 model compare to previous work on Redwoods, SMCalflow and SNIPS. The results indicate that the model is capable achieving the state-of- the-art results all the tasks compared to previous work. Interestingly, notice that by rewriting SMC into PENMAN notation, the sequence accuracy increase from 72.9 to 82.8 on devel- opment set, indicating that proper linearization and tokenization important for graph parsing tasks.
Redwoods Inn-ommai)) Node
SMCalflow
SNIPS
Model
Edge
SMATCH
Model
AC0se
Model
Slot
Chen et ul.
2018
94.5
87.3
90.9
Andreas et al. 2020
72.9
Wang et al
2018
93.5
Chen al 2019
97.3
94.0
95.7
Zhang et a.
2019
91.8
96.4
93.7
95.1
Qin
2019
94.2
15
z022h
97.3
95.8
96.6
T5 (Our implementation)
97.4
94.4
95.9
82.8
98.5
Table 3: In-domain performance evaluation for three semantic parsing tasks. The T5 model is built based on Lin et al. (2022b) on Redwoods and it surprisingly achieves the state-of-the-art results on the other datasets (SMCalflow and SNIPS).
G FULL RESULTS FOR COMPARING UNCERTAINTY BASELINES
In Table 4 we reported the full results for comparing different uncertainty baselines on the bench- mark introduced in Section 3
H HISTOGRAM OF CALIBRATIONS
The correlations between the subgraph's probability and performance ERG parsing shown in Figure 5) where we can see that low model probability generally corresponds to low model perfor- mance, Le., the model is relatively calibrated in predicting graph structures.
I FULL RESULTS FOR COLLABORATIVE SEMANTIC PARSING
In Table 5 and Table 6 we report the full results for collaborative performance under different set- tings of budgets of subgraphs by different combinations of number of subgraphs (e) and max depth of each subgraphs (d). Note that for SNIPS, since the performance is almost close to 100% when selecting number of subgraphs greater than 3, i.c., the total graph has been covered, we will evaluate cases where 3. We can see from the table that uncertainty based subgraph selection consistently outperforms random subgraph selection, and performs close to oracle subgraph selec- tion.
In Table We further conduct an analysis to subgraphs selected by different strategies by calculating the coverage rate of incorrect nodes in subgraphs to incorrect nodes in the entire graph (i.e., error node coverage rate). The results indicates that compositional uncertainty is effective in detecting incorrectly predicted nodes.
LIMITATIONS
Here we discuss some potential limitations of the current study:
Linguistic Breadth The GAP model this work is a general uncertainty quantification frame- work for graph parsing problems using seq2seq model, which theoretically has restriction to formalism and languages adopted for the output graph. this work, we have tested GAP on Red- woods, SMCalflow and SNIPS, which are all English based, but is worth how the approach
17

---

Published as a conference paper at ICLR 2023
ACC
SMATCH(")
Fly(t)
Flg(t)
ECB
CECCEG()
(ECT)N()
(ECTgg()
Deterministic
51.01
95.92
97.38
94.35
0.3632
0.0345
0.0221
0.0465
MC Deopout
50.17
95.83
97.32
94,
0.1034
0.0312
0.0171
0,0460
DE
51.70
96.07
97.46
94.54
0.2545
0.0326
0.0202
0,0448
WSI (In-domain)
BE
49.13
95.91
97.33
94.37
0,3209
0.034]
0.0217
0,0452
SNGP
48.50
95.85
97.39
94.35
0.2213
0.0326
0.0199
0.4533
S
49.55
95.98
97.45
94,53
0.1067
0.0299
0.0166
0.0431
SNGP+BE
47.46
95.74
97.27
94.30
0.1652
0.0338
0.0202
0.0472
Deterministic
68.10
95.27
95.65
94,95
0.2562
0.0452
0.0405
0.0498
MC Dropout
67.53
95.20
95.55
94.90
0.1
0.0405
0.0326
0.0492
DE
69.42
95.45
95.79
95. 17
0,1987
0.0411
0.0357
0.0467
Tanaka
BE
67.67
95.24
95.66
94.88
0.2367
0.0450
0.0395
0.0512
SNGP
67.10
95.25
95.57
95.57
0.1998
0.0429
0.0367
0.0501
68.03
95.51
95.83
95.30
0.1287
0.0394
0.0320
0.0477
SNGP+BE
63.88
95.24
95.53
95.09
0.1913
0.0427
0.0363
0.0494
Deterministic
51.53
93.48
94,18
92.88
0.3840
0.0721
0.0652
0,0793
MC Deopout
49.46
93.04
93.72
92.50
0.1661
0.0725
0.0618
0.0835
DE
53.14
93.72
94.38
93.15
0.3083
0.0676
0.0603
0,0754
Foommerce
BE
50.63
93.66
94.29
93.
0,3558
0.0677
0.0608
0.0740
SNGP
50.43
93.09
93.79
93.79
0.2748
0.0743
0.0650
0.0849
SN
50.99
93.22
93.89
92.73
0.1848
0.0706
0.0599
0
SNGP+BE
49.28
93.17
93,91
92.65
0.2678
0.0739
0.0652
0.0832
Deterministic
40.93
92,32
93.81
90.89
0.3969
0.0673
0.0530
0.0824
MC Dropout
40.10
92.17
93.64
90.76
0.0982
0.0600
0.0409
0.0779
DE
41.75
92,54
94,00
91.
0.2589
0.0622
0.0473
0.0768
Brown
BE
40.19
92.07
93.69
90.54
0.3179
0.0690
0.0524
0.0854
SNGP
36.98
91.93
93.44
90.76
0,2409
0.0666
0.0492
0.0832
SNG
38.63
92.26
93.71
93
011
0.0597
0.0417
0.0770
SNGP+BE
36.94
91.83
93.39
90.63
0.1905
0.0655
0.0481
0.0823
Deterministic
30,80
92.07
94,18
90.96
0,4589
0.0691
0.0565
0,0808
MC Dropout
29.10
91.82
93.22
90.78
0.0993
0.0615
0.0464
0.0783
DE
31.81
92.35
93,70
91.34
0,2859
0.0630
0.0505
0,0750
Essay
BE
27.75
91.71
93.22
90.54
0,381
0.0725
0.0587
0.0855
SNGP
25.04
91.61
93.16
90.96
0,2188
0.0675
0.0551
0.0822
DE
25.89
92.02
93.53
91.35
0.1 124
0.0627
0.0474
0.0774
SNGP+BE
24.03
91.62
93.15
91.01
0.2207
0.0693
0.0544
0.0840
Deterministic
31.45
91.10
92.58
90.70
0.5148
0.0834
0.0726
0.0944
Dropout
30.71
90,99
90.64
0.1457
0.0760
0.0628
0.0893
DE
31.82
91.28
92,76
90.89
0.3393
0.0789
0.0672
0.0903
LOGON
BE
30.82
90.85
92.40
90.32
0,4288
0.0852
0.0738
0.0956
SNGP
26.65
89.81
91.21
91:21
0.1553
0.0802
0 066667
0.0933
SNGP+DE
26.60
90.75
92.24
90.86
0.0979
0.0752
0.0610
0.0890
SNGP+BE
24.49
90.01
91.36
90.31
0.1555
0.0810
0.0695
0.0926
Deterministic
51.45
90.38
91.45
90.02
0.3298
0.0960
0. 0.0861
1063
MC Dropout
$2.74
90.42
91.54
89.92
0.1003
0.0873
0.0731
0,1033
DE
54.56
90.67
91.69
90.35
0.2283
0.0909
0.0834
0.0996
Verhmobil
BE
$1.56
90.00
91.12
89.58
0.2933
0.1010
0.0900
0.1126
SNGP
52.63
90.21
91,30
91.30
0.2233
0.0981
0.0850
0,12
SN
56.07
90.81
91.90
90.47
0.1
0.0861
0.0737
0.0999
SNGP+BE
$3.92
90.42
91.48
89.99
0.2091
0.0943
0.0840
0,1060
Deterministic
28.16
89.64
90.65
89.37
0.4105
0.1038
0.0939
0.1135
Dropout
26.63
90.10
89.89
0.0492
0.0891
0.0731
0,1039
DE
31.22
90.71
91.65
90.44 40.46
0.1974
0.0910
0.0798
0.1019
Wiki
BE
29.15
89.86
90.97
89.49
0.2658
0.0993
0.0881
0.1107
SNGP
24.87
89.57
90.59
89.72
0.1631
0.0927
0. 0.0804
0.10
SNGP+DE
27.31
90.63
91.58
90.69
0.0666
0.0803
0.0663
0.0942
SNGP+BE
26.78
89.74
90.89
89.82
0.1281
0.0907
0.0777
0.1025
Table Evaluations for different uncertainty baselines on different domains in Redwoods treebanks. BE refers to Batch Ensemble, and DE refers to Deep Ensemble.
can scale up (with the number of languages covered) and down (with diminished resource avail- ability in low-resource languages). For example, many efforts have been made to build practical and lrguusiinguistically valid graph formalism to overcome language barriers, e-g., Uniform Mean- ing Representation (UMR; Van Gysel et al. 202I) ) and BabelNet Meaning Representation (BMR; Navigli et al. 2022), and it is interesting to explore the model behavior on these graph formalism in terms of compositional uncertainty.
Graphical Model Specification The GAP model presented in this work considers classical graphical model likelihood p(G],z) II p(u) 2)) which leads to clean factorization be- tween graph elements e and fast probability computation. However, it also assumes a local Markov property that is conditional independent to its ancestors given the parent pa(r). In theory, the
18

---

Published as a conference paper at ICLR 2023
39993 193 pa01
13h 11M
PARIS
1966
a 0778 8421 6.M
1/200
(a) WSJ (In-domain)
(b) Tanaka
0.7
7.4
32955 3.165 65512
53752 3.595 E5806 09164 0.993
2,0000
12000
0.305 6.231 08912 6.906
09990 19993 1.000
6,996
89999 1.0000
Sadatape Probobiit
(c) Ecommerce
(d) Brown
1.0
3.7
0.7
3.4
3800:
3.107
64666
BAGLS
36682 66863
6967
66866
1206
0.264
0242 66666
6,912
69921 E80O 5.068
99990
Sedutep: Prbtililee
(c) Essay
(f) LOGON
5.0
1.0
0.7
3.4
Vodetape Frob-bRites
lodwldpe hobbbbera
(g) Verbmobil
(h) Wiki
Figure 5: Diagrams for the T5 model's probabilities verses the T5 model's accuracies at subgraph level (nodes and edges). Each bin contains the number of examples. Since at of the subgraphs. the model is pretty certain (log P > -le- 5), we exclude these pretty certain predictions the figures.
probability learned by seq2seq model is capable of modeling higher order conditionals between arbitrary elements on the graph. Therefore it is interesting to ask if a more sophisticated graphi- cal model with higher-order dependency structure lead to better performance in practice while maintaining reasonable computational complexity.
19

---

Published as a conference paper at ICLR 2023
Datasel
Retrival Type
Random
Det
MCD
GP
BE
BEGP
DE
DEGP
Oracle
c=1,d=1
96.05
96.26
96.24
96.16
96.24
96.
96.21
96.15
cw c=1,d
96.02
96.42
96.47
96.27
96.49
96.21
96.47
96.37
96.67
c=1,d=3
96.27
96.60
96.59
96.45
96.52
96.33
96.52
96.68
c=3dm=1
96.07
96.41
96.43
96.34
96.45
96.29
96.42
96.47
96.56
WSI (In domain)
c=3d==2
96.42
97.08
97.17
96.89
97.15
96.75
97.12
96.99
97.47
cw3ddm3
96.53
97.28
97.24
96.88
97.27
96.67
97.27
96.91
97. 52
c=
96.17
96.60
96.56
96.54
96.67
96.44
96.53
96.57
96.85
96.70
97.33
97.46
97.06
97.42
97.00
97.42
97.30
97, .8
97.03
97.67
97.80
97.28
97.76
97.25
97.76
97.44
97.91
[1
95.35
96.23
96.18
96.02
96.24
96.01
96.21
96.14
96.22
(=1,4=2
95.88
96.
96,75
96.45
96.63
96.31
96.69
96.54
96.92
96.03
96.96
97.00
96.60
96.91
96.52
96.94
96.70
97.
(=3,==1
96.15
96.79
96,94
96.77
96.84
96.85
96.88
96.91
97.11
Tanaka
96.96
97.
97.66
97.73
97.91
97. 97.85
(=3,==3
97.15
98.18
98.43
98.31
98.43
98.
98.32
98.36
43
0=5,dm1
96.57
97,
97.
97.27
97.37
c=5,==2
97.40
98.38
9R,
98, 34
98.41
98.47
98.43
98.55
98.44
0=5,dm3
97.99
99
98,
99.05
99.1
c [=
93,56
94.54
94.47
94,,14
94.95
94,21
94.76
94.29
94.98
cm c=1
94.75
95.49
95.58
94,95
95.56
94,83
95.61
95.14
96.
95.75
Ecommerce
-=3
95.02
96.31
96.68
96.44
96.54
96.31
96.66
96.35
97. 18
96.59
96.76
(=
95.21
95.83
95.5 S1
95.80
95.99
95.88
95.98
95.98
96. 28
0=5,d=2
96.30
97.20
97.61
97.24
97.55
97.09
97.47
97.31
(=5,d=3
96.83
97.85
91. 12
97.97
98_30
98.03
988.13
98.15
918 45
[=1,0=1
92.54
92.89
92.98
92:77
92.97
92.09
92.95
92.91
88
c=1.d=2
92.76
93.47
93.46
93.18
93.48
93.09
93.42
93.34
93.80
c=1.d=3
92.78
93.60
93.41
93.08
93.53
93.88
c=3
92.66
93.44
93.50
93.49
93.56
93.33
93.66
93.59
93.76
Brown
-=3
93,53
94.79
95.04
94.49
94.89
94
94.98
94.68
95,24
c=3
93.88
95.27
95.53
94.79
95.39
94.48
95.34
95.17
95.87
93.13
93.92
94.04
94.07
93.98
93.89
94.06
94.17
94.32
-=
94,06
95.33
95.59
95.16
95.51
94.80
95.62
95.39
95.76
94.61
96.22
96.41
95.96
96.27
95.75
96.32
95.99
96.6
=1
92.38
92.62
92.73
92.82
92.70
92.56
92.77
92.63
92.37
c=1,4=2
92.15
92.83
92.70
92.32
92.61
92.35
92.66 66
92.64
92.99
(=1,-=3
92.36
92.92
92.92
92.63
92.99
92.56
93.02
92.90
93.10
c=3d==1
92,30
93.29
93.15
93.15
93.30
92.97
93.11
93.28
93,40
Essay
92.82
94.03
93.76
95.48
93.75
c=3d==3
93.13
94 64
94.76
94,06
94.14
93.96
94.44
94.39
95.5 38
92.26
93.25
93.52
93.27
93:55
93.65
c=
93.66
94.84
94.88
94.36
94.91
94.16
94.79
94.48
95.
68
95.38
95.77
94.96
95.75
96.55
c [=
91.42
91.93
91.75
91.60
91.78
91.61
91.86
91.70
91.72
c=l d=1
91.87
92.52
92.45
91.93
92.54
91.88
92.53
92.03
92.83
LOGON
c= -=3
92.65
93.68
93.74
933.09
93.74
92.85
93.74
93.33
94.38
93.19
91.92
92.77
92.97
92.92
92.78
92.81
92.81
92.77
93.3 28
0=5
93.42
94.75
94,00
94.58
93.85
94.45
94. 24.22
93.76
93.24
95.40
94.551
95.32
94.31
95.29
94.93
15.77
90.16
90.09
90.77
90.59
90.76
90.43
90.74
90.68
90.
c=
90.63
91.92
91.51
91.44
91.65
91.08
91.84
.959
91.76
90.78
91.92
91.76
91.83
92.10
91.66
91.85
91.
66
89.98
91.42
91.67
91.68
91.72
91.35
91.59
91.65 .6.
91.14
Verbmobil
92.15
93.75
94,13
94.04
94.03
93.54
94.00
93.93
94.18
c=3
93.36
95.32
95.44
95.07
95.11
94.68
95.24
95.20
95, 95.40
90.98
92.74
92.78
92.70
92.89
92.80
92.49
92.86
92.37
94,00
95.35
95.47
95.38
95.33
94.85
95.29
95.39
95.43
3
94.56
96.45
96.59
96.53
96.53
96.04
96.50
96.88
96.26
91.34
91.82
91.78
91.73
91.82
91.70
91.75
91.72
91.84
c=1,d=2
91.88
92.14
92.34
91.98
92.30
92.09
92.25
91.98
92,70
(=1,1=3
91.74
92.22
92.32
92.00
92.53
91.77
92.35
91.96
92.53
c=3d==1
91.48
92.15
92.18
92.37
92.20
92.34
92.23
92:40
92.38
Wiki
92.07
93.12
92.63
93.23
92.92
c=3d==3
92.17
93.20
NaN
93,14
93.33
93.02
93.58
93.17
93. 84
c=5,dm1
92.64
92.66
92.
92.56
92.87
92.
92.92
93.97
94.00
93.80
94.14
93.59
94.24
93.80
94.67
93.07
93.89
93.68
94.07
Table 5: Full collaborative performance Redwoods (ERG parsing) including different uncer- tainty baselines (Det: Deterministic; MCD: MC Dropout; GP: SNGP; BE: Batch Ensemble; BEGP: SNGP+Batch Ensemble; DE: Deep Ensemble; DEGP: SNGP+Deep Ensemble), the performance metrics are SMATCH score for Redwoods (Red: Best; Green: Second Best; Orange: Third).
20

---

Published as a conference paper at ICLR 2023
e=1 d=l
c=1 d-2
e=l d=3
t=3 d=l
c=3 d=2
c=3 d=3
c=5 d=1
c=5 d=2
c=5 d=3
Oracle
90.57
92.44
93.33
93.21
95.84
96.10
94.27
96.38
97.16
SMCalflow
Oracle*
91.01
93.38
94.55
93.41
96.56
97.36
94.19
97.39
97.87
Random
88.10
88.99
89.71
90.10
92.21
93.47
91.30
93.80
95.19
Uncertain
90.12
91.15
92.13
92.18
94.50
95.50
93.27
96.00
96.88
Oracle
99.48
99.54
99.56
99.74
99.78
Oracle*
99.64
99.72
99.80
99.78
99.90
99.98
SNIPS
Random
99.36
99.36
99.50
99 44
99.74
99.76
Uncertain
99.62
Table Full collaborative parsing performance on SMCalflow and SNIPS, the performance metrics are sequence accuracy for SMCalflow and slot (node) F1 for SNIPS.
Dataset
Selection
c=1,del
e=1,de2
c=1,de3
cm3,dml
em3,de2
em3,dm3
c=5,dm1
e=5,de2
em5,dm3
Random
3.65
7.21
8.79
9.19
19.33
23.78
14.29
28.69
33.14
WSJ (In-domain)
Uncertain
12.16
18.46
20.43
24.09
40.75
29.85
Oracle
24,54
35.82
36,20
49.08
68.52
70.44
62.31
80, 10
81.32
Random
11.78
20.19
22.05
29.33
46.81
48.00
39.13
58.20
64.05
Tanaka
Uncertain
30.88
42.22
45.24
47.30
66.09
71.37
56.56
76.91
81,16
Oracle
47.61
63.33
65.96
79.87
90.38
92.07
87.54
93.80
94.68
Random
9.69
16.75
21.39
23.73
36.53
44.91
32.67
49,80
54.25
Ecommerce
Uncertain
23.75
33.17
34.52
42.65
55.84
59.35
51.10
69.12
72.65
Oracle
41,80
$4.27
58.72
73.70
87.34
88.17
85.19
93.52
94.78
Random
5.38
11.06
12.47
14.90
27.47
31.13
21.70
37.98
42.26
Brown
Uncertain
14.09
22.34
25.54
28.52
44.08
49,21
35.73
55.01
60.62
Oracle
24.88
36.01
38.90
52.53
67.79
72.42
64.86
79.60
82.79
Random
4.88
12.92
11.51
25.74
26.16
18.96
41,22
Essay
Uncertain
12.60
19.50
22.15
25.59
41.85
45.32
32.89
52.59
$9.30
Oracle
20.62
29.87
33.65
45.80
64.54
70.77
62.43
80,33
84.33
Random
12.42
14.97
23.51
LOGON
Uncertain
14,68
23.15
25.49
29.95
46.00
50.49
38.34
58.14
64.29
Oracle
25,50
37.31
42.11
56.44
74.25
74.57
85.82
87.71
27.55
62.55
Verbmobil
Uncertain
23.54
35.75
39.59
45.21
63.38
69.61
55.11
75.06
80.65
Oracle
34.05
52.33
56.65
70.01
82.70
86.63
81.45
92.10
92.45
Random
13.63
30.83
20.67
Wiki
Uncertain
14.18
21.61
23.13
28.64
42.78
47.16
36.62
53.76
57.82
Oracle
22.13
32.57
33.78
47.54
62.21
66.99
59.19
76.53
79.26
Random
10.90
16.24
21.28
21.27
33.55
44.07
29.30
45.24
$6,20
SMCalflow
Uncertain
14.45
21.46
27.32
24.45
37.36
47.85
31.77
48.11
59.67
Oracle
21.75
30.02
37.65
42.97
59.87
65.89
55.28
70.99
77.35
Random
39.02
67.07
56.10
65.85
86.59
90.24
SNIPS
Uncertain
70.73
76.83
76.83
98.78
100.00
100.00
Oracle
75.61
Table Error node coverage rate for different subgraph selection strategies and budget refers number of examples (subgraphs), d refers to the depth of the subgraphs).
21


Reviews:
[{"review_id": "sRvg_rSV9X", "reviewer": "Reviewer_jzBV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors do seq2seq parsing with various semantic parsing datasets, and employ a specialized method called GAP that is meant to incorporate \"compositional uncertainty\" (UC). My interpretation is that UC incorporates probabilities over graph construction (i.e. edge and node creation) rather than token predictions when training seq2seq models with max-likelihood objectives (although there is a fine line between these two, and perhaps the former is achieved simply by using the right action space). Also, their training involves approximate normalization over subgraphs via importance sampling. Because of uncertainty measures that GAP implements, it is suitable for human-in-the-loop graph editing (sec 3.2). This last idea is quite interesting --- maybe your initial graph is fine and a human can slightly fix it up to drastically improve performance. That being said, the eval is somewhat limited and the main text is lacking details.", "summary_of_the_review": "The core idea of the paper, that uncertainty can be used to inform graph editing, seems very interesting but I am not sure it is well executed. Parts of the presentation are confusing, and there could be more analysis on the graph editing portion. By fixing up writing, adding appropriate baselines, and providing more emphasis on graph editing part, then I think this could be a stronger paper. Right now I do not think it meets standards of the conference.", "strength_and_weaknesses": "# Strengths\n\n1. The paper is focused on seq2seq parsing with T5. This is a challenging task and active research area. They evaluate on many semantic parsing tasks.\n\n2. The authors explicitly model the graph rather than solely treat it as a string-to-string task.\n\n3. The authors evaluate in a creative scenario where humans can edit noisy graphs to drastically improve performance, although this section is limited.\n\n# Weaknesses\n\n1. There are many missing related work, and it is not right to say they are first to explore local probabilities for seq2seq parsing.\n\n2. The evaluation is very hard to interpret. In the main table 1, there are no baselines and only T5 w/ GAP is evaluated as far as I can tell. In figure 3 there are many methods but I am not sure how it ties into the main storyline regarding T5 w/ GAP. In addition the evaluation is not very standard, which alone is not a major problem, but warrants further explanation in the text.\n\n3. To me the most exciting part of the work is that noisy graphs can potentially be edited to improve performance. This section leads to some concerns... I am surprised RANDOM can be so effective. There are not really any details on how human edits are done. There is not much analysis on the subgraph editing, and it seems like most of editing can be done by editing one or two labels.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rqb1VozEDV", "reviewer": "Reviewer_3RNa", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is a novel and profound contribution to sequence-to-sequence graph parsing of natural language, quantifying and evaluating compositional uncertainty in seq2seq graph parsing through a newly-proposed probabilistically interpretable framework and a new metric which measures a model's calibration in predicting graph structures. A large battery of tests together with human evaluations shows strong empirical support for the framework.", "summary_of_the_review": "Contained above.", "strength_and_weaknesses": "Strengths:\n- A novel and creative contribution to modelling and evaluation for uncertainty in seq2seq parsing.\n- Thorough experiments, high-quality writeup, convincing results.\n\nWeaknesses:\n- The selection of datasets is not thoroughly elaborated from the viewpoint of availability vs. linguistic breadth. English is dominant in graph parsing, but care should be taken to qualify how the approach would scale up (with the number of languages covered) and down (with diminished resource availability in low-resource languages). A Limitations section addressing this linguistic breadth angle, and an honest account of this contribution being by and large for English only, would suffice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-t1r-Y7mkw", "reviewer": "Reviewer_oThz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper propose a method to calculate the compositional uncertainty of sequence to sequence model for semantic parsing tasks, that is in tasks where the input is an utterance and the output is a graph.\nFor doing so the authors propose to marginalize the probability of output sequences so to calculate the expected probability of a node, give its parent node in a generated graph. Since marginalizing over all possible subsequences between two symbols is intractable in general, the authors propose to approximate this process using beam decoding.\nThe authors use the compositional uncertainty to calculate the expected calibration error, that is how well the uncertainty matches the performances of the model. The authors compare standard ECE and compositional ECE, showing that the second one is a better choice.\n\nFinally the model is used in a collaborative semantic parsing where parts of the predictions (for example where the models is more uncertain on) can be send to human validation. Results show that the proposed measure of uncertainty finds more errors than random, and it is close to an oracle selection.", "summary_of_the_review": "This work introduce a technique that allows practitioner to calculate compositional uncertainty in seq 2 seq model for graph parsing.\nI am not an expert in graph parsing but it seems that this paper fills a void in that space.\nI am not able to judge if more experiments on different datasets are required to prove if the approach is general enough to be used in any kind of text 2 graph task.", "strength_and_weaknesses": "The paper is well written and seems to be a missing piece in the semantic parsing literature. Calibration error is a standard metric to understand how trustworthy the predictions of a model are, and apparently this is the first attempt at calculating it in the setting of compositional sequence to sequence models.\n\nThe paper is pretty clear and goes step by step explaining the various concepts used in the paper. it is equation-heavy but easy to understand.\n\nThe premises for section 3.2 are a bit vague, to me modelling compositional uncertainty would be very helpful in an active learning framework, where subgraph on which the model is uncertain are asked to be reannotated. The collaborative semantic parsing scenario is not very realistic to me.\nIt is not clear to me also how the oracle is defined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster