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

Abstract: The celebrated Seq2Seq technique and its numerous variants achieve excellent performance on many tasks such as neural machine translation, semantic parsing, and math word problem solving. However, these models either only consider input objects as sequences while ignoring the important structural information for encoding, or they simply treat output objects as sequence outputs instead of structural objects for decoding. In this paper, 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 solving two problems, neural semantic parsing and math word problem. Our extensive experiments demonstrate that our Graph2Tree model outperforms or matches the performance of other state-of-the-art models on these tasks.

## 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 designing 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 inputs and outputs, such as graphs, trees, sequences, or sets. in this paper, we consider the general problem of learning a mapping between a graph input @xmath0, based on a training sample of structured input-output pairs (g 1 , t 1 ), ..., (g n , t n ) ∈ 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 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 sleeping and 9 cows are drinking water from the pond . find the total number of cows . ## graph2tree neural networks we aim to learn a mapping that translates a heterogeneous graph-structured input g and its corresponding tree-structured outputs t . we illustrate the workflow of our proposed graph2tree model for semantic parsing in figure 4 , and present each component of the model as follows. ## experiments in this section, we evaluate the effectiveness and generality of graph2tree model on two important tasks -semantic parsing and math word problem. the code and data for our graph2tree model are provided for research purpose foot_0 . ## conclusion and future work we presented a novel graph2tree model consisting of a graph encoder and a hierarchical tree decoder, for learning the translation between structured inputs and structured outputs. studies on two tasks -semantic parsing and math word problem demonstrated our model consistently outperformed or matched the performance of the state-of-the-art. our graph2tree model is generic and agnostic to the downstream tasks and thus one of the future works is to adapt it to the other nlp applications.