SmBoP: Semi-autoregressive Bottom-up Semantic Parsing

• URL: http://arxiv.org/abs/2010.12412v2
• Date: Sun, 11 Apr 2021 11:37:59 GMT
• Title: SmBoP: Semi-autoregressive Bottom-up Semantic Parsing
• Authors: Ohad Rubin and Jonathan Berant
• Abstract summary: We propose a Semi-autoregressive Bottom-up (SmBoP) that constructs at decoding step $t$ the top-$K$ sub-trees of height $leq t$. From an efficiency perspective, bottom-up parsing allows to decode all sub-trees of certain height in parallel, leading to logarithmic complexity runtime rather than linear. We apply SmBoP on Spider, a challenging zero-shot semantic parsing benchmark, and show that SmBoP leads to a 2.2x speed-up in decoding time and a $$5x speed-up in training time
• Score: 44.802643057976354
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The de-facto standard decoding method for semantic parsing in recent years has been to autoregressively decode the abstract syntax tree of the target program using a top-down depth-first traversal. In this work, we propose an alternative approach: a Semi-autoregressive Bottom-up Parser (SmBoP) that constructs at decoding step $t$ the top-$K$ sub-trees of height $\leq t$. Our parser enjoys several benefits compared to top-down autoregressive parsing. From an efficiency perspective, bottom-up parsing allows to decode all sub-trees of a certain height in parallel, leading to logarithmic runtime complexity rather than linear. From a modeling perspective, a bottom-up parser learns representations for meaningful semantic sub-programs at each step, rather than for semantically-vacuous partial trees. We apply SmBoP on Spider, a challenging zero-shot semantic parsing benchmark, and show that SmBoP leads to a 2.2x speed-up in decoding time and a $\sim$5x speed-up in training time, compared to a semantic parser that uses autoregressive decoding. SmBoP obtains 71.1 denotation accuracy on Spider, establishing a new state-of-the-art, and 69.5 exact match, comparable to the 69.6 exact match of the autoregressive RAT-SQL+GraPPa.

Related papers

• Structured Dialogue Discourse Parsing [79.37200787463917]
  discourse parsing aims to uncover the internal structure of a multi-participant conversation. We propose a principled method that improves upon previous work from two perspectives: encoding and decoding. Experiments show that our method achieves new state-of-the-art, surpassing the previous model by 2.3 on STAC and 1.5 on Molweni.
  arXiv  Detail & Related papers  (2023-06-26T22:51:01Z)
• Hexatagging: Projective Dependency Parsing as Tagging [63.5392760743851]
  We introduce a novel dependency, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. Our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. We achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set.
  arXiv  Detail & Related papers  (2023-06-08T18:02:07Z)
• TreePiece: Faster Semantic Parsing via Tree Tokenization [2.1685554819849613]
  TreePiece tokenizes a parse tree into subtrees and generates one subtree per decoding step. On TopV2 benchmark, TreePiece shows 4.6 times faster decoding speed than standard AR.
  arXiv  Detail & Related papers  (2023-03-30T05:44:44Z)
• Interactive Code Generation via Test-Driven User-Intent Formalization [60.90035204567797]
  Large language models (LLMs) produce code from informal natural language (NL) intent. It is hard to define a notion of correctness since natural language can be ambiguous and lacks a formal semantics. We describe a language-agnostic abstract algorithm and a concrete implementation TiCoder.
  arXiv  Detail & Related papers  (2022-08-11T17:41:08Z)
• Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation [41.51966652141165]
  We propose a model-based pruning method, which also enables parallel encoding during inference. Our experiments show that our Fast-R2D2 improves performance significantly in grammar induction and competitive results in downstream classification tasks.
  arXiv  Detail & Related papers  (2022-03-01T07:54:44Z)
• Span Pointer Networks for Non-Autoregressive Task-Oriented Semantic Parsing [55.97957664897004]
  An effective recipe for building seq2seq, non-autoregressive, task-orienteds to map utterances to semantic frames proceeds in three steps. These models are typically bottlenecked by length prediction. In our work, we propose non-autoregressives which shift the decoding task from text generation to span prediction.
  arXiv  Detail & Related papers  (2021-04-15T07:02:35Z)
• Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
  Parsing sentences into syntax trees can benefit downstream applications in NLP. Transition-baseds build trees by executing actions in a state transition system. Existing transition-baseds are predominantly based on the shift-reduce transition system.
  arXiv  Detail & Related papers  (2020-10-27T19:19:38Z)
• Efficient Second-Order TreeCRF for Neural Dependency Parsing [23.426500262860777]
  In the deep learning (DL) era, parsing models are extremely simplified with little hurt on performance. This paper presents a second-order TreeCRF extension to the biaffine. We propose an effective way to batchify the inside and Viterbi algorithms for direct large matrix operation.
  arXiv  Detail & Related papers  (2020-05-03T03:18:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.