Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and Math Word Problem

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2841–2852 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 2841 Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and Math Word Problem Shucheng Li∗†, Lingfei Wu∗‡, Shiwei Feng†, Fengyuan Xu†, Fangli Xu§, Sheng Zhong† †National Key Lab for Novel Software Technology, Nanjing University, China ‡IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USA §Squirrel AI Learning, New Jersey, USA †{shuchengli,fengyuan.xu,swfeng98,sheng.zhong}@smail.nju.edu.cn ‡lwu@email.wm.edu, §lili@yixue.us Abstract The celebrated Seq2Seq technique and its numerous variants achieve excellent perfor- mance on many tasks such as neural machine translation, semantic parsing, and math word problem solving. However, these models ei- ther only consider input objects as sequences while ignoring the important structural infor- mation for encoding, or they simply treat out- put objects as sequence outputs instead of structural objects for decoding. In this pa- per, we present a novel Graph-to-Tree Neural Networks, namely Graph2Tree consisting of a graph encoder and a hierarchical tree decoder, that encodes an augmented graph-structured input and decodes a tree-structured output. In particular, we investigated our model for solv- ing two problems, neural semantic parsing and math word problem. Our extensive experi- ments demonstrate that our Graph2Tree model outperforms or matches the performance of other state-of-the-art models on these tasks. 1 Introduction Learning general functional dependency between arbitrary input and output spaces is one of the key challenges in machine learning. While many efforts in machine learning have mainly focused on design- ing flexible and powerful input representations for solving classification or regression problems, many applications require researchers to design novel models that can deal with complex structured in- puts and outputs, such as graphs, trees, sequences, or sets. In this paper, we consider the general prob- lem of learning a mapping between a graph in- put G ∈ G and a tree output T ∈ T , based on a training sample of structured input-output pairs (G1, T1), ..., (Gn, Tn) ∈ G × T drawn from some fixed but unknown probability distribution. Such learning problems often arise in a variety of applications, ranging from semantic parsing, to ∗ authors contributed equally to this research. SP Text Input: what jobs are there for web developer who know ’c++’ ? Structured output: answer( A , ( job ( A ) , title ( A , W ) , const ( W , ’Web Developer’ ) , language ( A , C ) , const ( C , ’c++’ ) ) ) MWP Text input: 0.5 of the cows are grazing grass . 0.25 of the cows are sleep- ing and 9 cows are drinking water from the pond . find the total number of cows . Structured output: ( ( 0.5 * x ) + ( 0.25 * x ) ) + 9.0 = x Table 1: Examples of structured input and output of se- mantic parsing (SP) and math word problem (MWP). For inputs, we consider parsing tree augmented se- quences to …

Content truncated to 500 words