Graph-Based Decoding for Task Oriented Semantic Parsing (2021)

Abstract: The dominant paradigm for semantic parsing in recent years is to formulate parsing as a sequence-to-sequence task, generating predictions with auto-regressive sequence decoders. In this work, we explore an alternative paradigm. We formulate semantic parsing as a dependency parsing task, applying graph-based decoding techniques developed for syntactic parsing. We compare various decoding techniques given the same pre-trained Transformer encoder on the TOP dataset, including settings where training data is limited or contains only partially-annotated examples. We find that our graph-based approach is competitive with sequence decoders on the standard setting, and offers significant improvements in data efficiency and settings where partially-annotated data is available.

## introduction semantic parsing, the task of mapping natural language queries to structured meaning representations, remains an important challenge for applications such as dialog systems. to support compositional utterances in a task oriented dialog setting, @xcite introduced the task oriented parse (top) representation and released a dataset consisting of pairs of natural language queries and associated top trees. as illustrated in figure 1 , top trees are hierarchically structured representations consisting of intents, slots, and query tokens. we propose a novel formulation of semantic parsing for top as a graph-based parsing task, presenting a graph-based parsing model (hereafter, gbp). our approach is motivated by the success of such approaches in dependency parsing @xcite @xcite and amr parsing @xcite . recently, sequence-to-sequence (seq2seq) models have become a dominant approach to semantic parsing (e.g., @xcite @xcite ), including on top (e.g., @xcite @xcite ). unlike such approaches that predict outputs auto-regressively, gbp decomposes parse tree scores over parent-child edge scores, predicting all edge scores in parallel. first, we compare gbp with seq2seq and other decoding techniques, within the context of a fixed encoder and pretraining scheme: in this case, bert-base @xcite . this allows us to isolate the role of the decoding method. we compare these models across the standard setting, as well as additional settings where training data is limited, or when fully annotated examples are limited but partially annotated examples are available. we find that gbp outperforms other methods, especially when learning from partial supervision. second, we compare gbp with seq2seq models that additionally leverage pretrained decoders. we find that gbp remains competitive, and continues to outperform in the partial supervision setting. ## task formulation we present a novel formulation of the top semantic parsing task as a graph-based parsing task. our goal is to predict a top tree y given a natural language query x as input. the nodes in y consist of intent and slot symbols from a vocabulary of output symbols v and the tokens in x. however, y cannot be predicted directly by a conventional graph-based approach @xcite for two reasons. first, given x, we do not know the subset of intent and slot 1 symbols that occur in y. second, intent and slot symbols can occur more than once in y. 2 to address this, let us consider a parse tree z in a space of valid trees defined as z(x). the parse tree z can be deterministically mapped to and from y. the parse tree z consists of: (1) the tokens in x, (2) every symbol in v replicated up to a maximum number of occurrences 3 and assigned a corresponding index, and (3) a special unused node in addition to the standard root node. let n (x) be this set of nodes which all trees in z(x) consist of. when mapping from y to z, output symbols occurring multiple times are indexed following a pre-order traversal, and any output symbol that does not occur in y is assigned to the unused node in z. for example, figure 1 illustrates an example top tree, y, and figure 2 illustrates a corresponding parse tree, z. ## scoring model given that the mapping between y and z is deterministic, our goal is to model p(z | x). we follow a conventional edge-factored graph-based approach @xcite , decomposing parse tree scores over directed edges between parent and child node pairs (p, c) in z: the scoring model is trained using a standard maximum likelihood objective. ## experiments the top dataset consists of trees where every token in the query is attached to either an intent (prefixed with in:) or slot label (prefixed with sl:). intents and slot labels can also attach to each other, forming compositional interpretations. we evaluate several models on the standard setup of the top dataset. we also devise new setups comparing the abilities of several models to learn from a smaller amount of fully annotated data, both with and without additional partially annotated data. models are compared on exact match accuracy. following rongali et al. (2020); einolghozati et al. (2018), and aghajanyan et al. (2020) , we filter out queries annotated as unsupported foot_1 , leaving 28414 train examples and 8241 test examples. ## related work the most recent state of the art on top has focused on applying new methods of pretraining; @xcite @xcite ) all use seq2seq methods, enhanced by better pretraining from bert @xcite , roberta @xcite , and bart @xcite while using similar model architectures. in this work, we instead investigate the choice of decoder. while the fsp model @xcite similarly uses a factored approach, its approach is more specific to top, as its trees must be projective and anchored to the input text. in dependency parsing, the performance of graph-based and transition-based parsing is compared in both @xcite and @xcite . graph-based parsing has also been used in amr parsing @xcite , which translates sentences into structured graph representations. similar methods have also been used in semantic role labeling @xcite , which requires labeling arcs between text spans. this work is the first to adapt graph-based parsing to tree-like task-oriented semantic parses. ## conclusions we propose a novel framing of semantic parsing for top as a graph-based parsing task. we find that our proposed method is a competitive alternative to the standard paradigm of seq2seq models, especially when fully annotated data is limited and/or partially-annotated data is available.