On Graph-based Reentrancy-free Semantic Parsing
Abstract
We propose a novel graph-based approach for semantic parsing that resolves two problems observed in the literature:
(1) seq2seq models fail on compositional generalization tasks;
(2) previous work using phrase structure parsers cannot cover all the semantic parses observed in treebanks.
We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems.
We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems.
Experimentally, our approach delivers state-of-the-art results on GeoQuery, Scan and Clevr, both for i.i.d. splits and for splits that test for compositional generalization.