Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints (2023)

Abstract: Neural QCFG is a grammar-based sequence-to-sequence model with strong inductive biases on hierarchical structures. It excels in interpretability and generalization but suffers from expensive inference. In this paper, we study two low-rank variants of Neural QCFG for faster inference with different trade-offs between efficiency and expressiveness. Furthermore, utilizing the symbolic interface provided by the grammar, we introduce two soft constraints over tree hierarchy and source coverage. We experiment with various datasets and find that our models outperform vanilla Neural QCFG in most settings.

## introduction standard neural seq2seq models are versatile and broadly applicable due to its approach of factoring the output distribution into distributions over the next words based on previously generated words and the input @xcite @xcite . despite showing promise in approximating complex output distributions, these models often fail when it comes to diagnostic tasks involving compositional generalization @xcite @xcite , possibly attributed to a lack of inductive biases for the hierarchical structures of sequences (e.g., syntactic structures), leading to models overfitting to surface clues. in contrast to neural seq2seq models, traditional grammar-based models incorporate strong inductive biases to hierarchical structures but suffer from low coverage and the hardness of scaling up @xcite . to benefit from both of these approaches, blending traditional methods and neural networks has been studied @xcite @xcite . in particular, @xcite proposes * corresponding author neural qcfg for seq2seq learning with a quasisynchronous context-free grammar (qcfg) @xcite ) that is parameterized by neural networks. the symbolic nature of neural qcfg makes it interpretable and easy to impose constraints for stronger inductive bias, which leads to improvements in empirical experiments. however, all these advantages come at the cost of high time complexity and memory requirement, meaning that the model and data size is restricted, which leads to a decrease in text generation performance and limited application scenarios. in this work, we first study low-rank variants of neural qcfg for faster inference and lower memory footprint based on tensor rank decomposition @xcite , which is inspired by recent work on low-rank structured models @xcite @xcite . these variants allow us to use more symbols in neural qcfg, which has been shown to be beneficial for structured latent variable models @xcite @xcite . specifically, we study two low-rank variants with different trade-off between computation cost and ranges of allowed constraints: the efficient model (e model), following the decomposition method in tn-pcfg @xcite , and the expressive model (p model), newly introduced in this paper. furthermore, we propose two new constraints for neural qcfg, including a soft version of the tree hierarchy constraint used by vanilla neural qcfg, and a coverage constraint which biases models in favour of translating all source tree nodes foot_0 . we conduct experiments on three datasets and our models outperform vanilla neural qcfg in most settings. our code is available at https://github.com/louchao98/seq2seq_with_qcfg . ## preliminary: neural qcfg let s 1 , s 2 be the source and target sequences, and t 1 , t 2 be the corresponding constituency parse trees (i.e., sets of labeled spans). following previous work @xcite , we consider qcfg in chomsky normal form (cnf; @xcite with restricted alignments, which can be denoted as a tuple g[t 1 ] = (s, n , p, σ, r[t 1 ], θ), where s is the start symbol, n /p/σ are the sets of nonterminals/preterminals/terminals respectively, r[t 1 ] is the set of grammar rules in three forms: recently, @xcite proposes neural qcfg for seq2seq learning. he uses a source-side parser to model p(t 1 |s 1 ) and a qcfg to model p(t 2 |t 1 ). the log marginal likelihood of the target sequence s 2 is defined as follows: marginalizing t 2 in neural qcfg has a high time complexity of o(|n |(|n | + |p|) foot_2 s foot_3 t 3 ) where s/t are the source/target sequence lengths. in particular, the number of rules in qcfg contributes to a significant proportion, o(|n |(|n | + |p|) 2 s 3 ), of the complexity. below, we try to reduce this complexity by rule decompositions in two ways. figure 1 : extended factor graph notation of decomposed binary rules @xcite . each square represents a factor. arrows indicate conditional probabilities. ## experiments we conduct experiments on the three datasets used in @xcite . details can be found in appx. d.1. ## conclusion we have presented two low-rank variants of neural qcfg based on decomposition for efficiency and two new constraints over tree hierarchy and source coverage. experiments on three datasets validate the effectiveness and efficiency of our proposed models and constraints.