Weighted DAG Automata for Semantic Graphs

Weighted DAG Automata for Semantic Graphs David Chiang∗ University of Notre Dame Frank Drewes∗∗ University of Ume˚a Daniel Gildea† University of Rochester Adam Lopez‡ University of Edinburgh Giorgio Satta§ University of Padua Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the frameworks of finite automata for strings and finite tree automata for trees. A possible starting point for such a framework is the formalism of directed acyclic graph (DAG) automata, defined by Kamimura and Slutzki and extended by Quernheim and Knight. In this article, we study the latter in depth, demonstrating several new results, including a practical recognition algorithm that can be used for inference and learning with models defined on DAG automata. We also propose an extension to graphs with unbounded node degree and show that our results carry over to the extended formalism. ∗ Department of Computer Science and Engineering, University of Notre Dame, IN 46656, United States. E-mail: dchiang@nd.edu. Some of the work described in this paper was done while Chiang was at the University of Southern California, Information Sciences Institute. ∗∗ Department of Computing Science, Ume˚a University, 90187 Ume˚a, Sweden. E-mail: drewes@cs.umu.se. † Department of Computer Science, University of Rochester, Rochester, NY 14627, United States. E-mail: gildea@cs.rochester.edu. ‡ School of Informatics, University of Edinburgh, Edinburgh, EH8 9AB, United Kingdom. E-mail: alopez@inf.ed.ac.uk. Some of the work described in this paper was done while Lopez was at Johns Hopkins University. § Department of Information Engineering, University of Padua, I-35131 Padova, Italy. E-mail: satta@dei.unipd.it. Submission received: 1 August 2016; revised version received: 9 May 2017; accepted for publication: 11 October 2017. doi:10.1162/COLI a 00309 © 2017 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 44, Number 1 1. Introduction Statistical models of natural language semantics are making rapid progress. At the risk of oversimplifying, work in this area can be divided into two streams. One stream, semantic parsing (Mooney 2007), aims to map from sentences to logical forms that can be executed (for example, to query a knowledge base); work in this stream tends to be on small, narrow-domain data sets like GeoQuery. The other stream aims for broader coverage, and historically tackled shallower, piecemeal tasks, like semantic role labeling (Gildea and Jurafsky 2000), word sense disambiguation (Brown et al. 1991), coreference resolution (Soon, Ng, and Lim 2001), and so on. Correspondingly, resources like OntoNotes (Hovy et al. 2006) provided separate resources for each of these tasks. This piecemeal situation parallels that of early work on syntactic parsing, which fo- cused on subtasks like part-of-speech tagging (Ratnaparkhi 1996), noun-phrase chunk- ing (Ramshaw and Marcus 1995), prepositional phrase attachment (Collins and Brooks 1995), and so on. As the field matured, these tasks were increasingly synthesized into a single process. This was made possible because of a single representation (phrase structure …

Content truncated to 500 words