AMR-to-text generation as a Traveling Salesman Problem

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2084–2089, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics AMR-to-text generation as a Traveling Salesman Problem Linfeng Song1, Yue Zhang3, Xiaochang Peng1, Zhiguo Wang2 and Daniel Gildea1 1Department of Computer Science, University of Rochester, Rochester, NY 14627 2IBM T.J. Watson Research Center, Yorktown Heights, NY 10598 3Singapore University of Technology and Design Abstract The task of AMR-to-text generation is to gen- erate grammatical text that sustains the seman- tic meaning for a given AMR graph. We at- tack the task by first partitioning the AMR graph into smaller fragments, and then gener- ating the translation for each fragment, before finally deciding the order by solving an asym- metric generalized traveling salesman prob- lem (AGTSP). A Maximum Entropy classifier is trained to estimate the traveling costs, and a TSP solver is used to find the optimized solu- tion. The final model reports a BLEU score of 22.44 on the SemEval-2016 Task8 dataset. 1 Introduction Abstract Meaning Representation (AMR) (Ba- narescu et al., 2013) is a semantic formalism en- coding the meaning of a sentence as a rooted, di- rected graph. Shown in Figure 1, the nodes of an AMR graph (e.g. “boy”, “go-01” and “want- 01”) represent concepts, and the edges (e.g. “ARG0” and “ARG1”) represent relations between concepts. AMR jointly encodes a set of different semantic phe- nomena, which makes it useful in applications like question answering and semantics-based machine translation. AMR has served as an intermediate representation for various text-to-text NLP applica- tions, such as statistical machine translation (SMT) (Jones et al., 2012). The task of AMR-to-text generation is to gener- ate grammatical text containing the same semantic meaning as a given AMR graph. This task is im- portant yet also challenging since each AMR graph want-01 boy go-01 ARG1 ARG0 ARG0 Figure 1: AMR graph for “The boy wants to go”. usually has multiple corresponding sentences, and syntactic structure and function words are abstracted away when transforming a sentence into AMR (Ba- narescu et al., 2013). There has been work deal- ing with text-to-AMR parsing (Flanigan et al., 2014; Wang et al., 2015; Peng et al., 2015; Vanderwende et al., 2015; Pust et al., 2015; Artzi et al., 2015). On the other hand, relatively little work has been done on AMR-to-text generation. One recent exception is Flanigan et al. (2016), who first generate a span- ning tree for the input AMR graph, and then apply a tree transducer to generate the sentence. Here, we directly generate the sentence from an input AMR by treating AMR-to-text generation as a variant of the traveling salesman problem (TSP). Given an AMR as input, our method first cuts the graph into several rooted and connected frag- ments (sub-graphs), and then finds the translation for each fragment, before finally generating the sen- tence for the whole AMR by ordering the transla- tions. To cut the AMR and translate each fragment, we match the input AMR with rules, each …

Content truncated to 500 words