The problem with probabilistic DAG automata for semantic graphs

Proceedings of NAACL-HLT 2019, pages 902–911 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 902 The Problem with Probabilistic DAG Automata for Semantic Graphs Ieva Vasiljeva∗and Sorcha Gilroy∗ and Adam Lopez Institute for Language, Cognition, and Computation School of Informatics University of Edinburgh {vasiljeva.ieva, gilroysorcha}@gmail.com, alopez@inf.ed.ac.uk Abstract Semantic representations in the form of di- rected acyclic graphs (DAGs) have been in- troduced in recent years, and to model them, we need probabilistic models of DAGs. One model that has attracted some attention is the DAG automaton, but it has not been stud- ied as a probabilistic model. We show that some DAG automata cannot be made into use- ful probabilistic models by the nearly uni- versal strategy of assigning weights to tran- sitions. The problem affects single-rooted, multi-rooted, and unbounded-degree variants of DAG automata, and appears to be pervasive. It does not affect planar variants, but these are problematic for other reasons. 1 Introduction Abstract Meaning Representation (AMR; Ba- narescu et al. 2013) has prompted a flurry of in- terest in probabilistic models for semantic pars- ing. AMR annotations are directed acyclic graphs (DAGs), but most probabilistic models view them as strings (e.g. van Noord and Bos, 2017) or trees (e.g. Flanigan et al., 2016), removing their ability to represent coreference—one of the very aspects of meaning that motivates AMR. Could we we in- stead use probabilistic models of DAGs? To answer this question, we must define prob- ability distributions over sets of DAGs. For in- spiration, consider probability distributions over sets of strings or trees, which can be defined by weighted finite automata (e.g. Mohri et al., 2008; May et al., 2010): a finite automaton generates a set of strings or trees—called a language—and if we assume that probabilities factor over its transi- tions, then any finite automaton can be weighted to define a probability distribution over this lan- guage. This assumption underlies powerful dy- ∗ Equal contribution. Work while Ieva Vasiljeva was at the University of Edinburgh namic programming algorithms like the Viterbi, forward-backward, and inside-outside algorithms. What is the equivalent of weighted finite au- tomata for DAGs? There are several candidates (Chiang et al., 2013; Bj¨orklund et al., 2016; Gilroy et al., 2017), but one appealing contender is the DAG automaton (Quernheim and Knight, 2012) which generalises finite tree automata to DAGs ex- plicitly for modeling semantic graphs. These DAG automata generalise an older formalism called pla- nar DAG automata (Kamimura and Slutzki, 1981) by adding weights and removing the planarity con- straint, and have attracted further study (Blum and Drewes, 2016; Drewes, 2017), in particular by Chiang et al. (2018), who generalised classic dy- namic programming algorithms to DAG automata. But while Quernheim and Knight (2012) clearly intend for their weights to define probabilities, they stop short of claiming that they do, instead ending their paper with an open problem: “Inves- tigate a reasonable probabilistic model.” We investigate probabilistic DAG automata and prove a surprising result: For some DAG au- tomata, …

Content truncated to 500 words