Lopez, Adam

Fancellu, Federico

Gilroy, Sorcha

Engineering and Physical Sciences Research Council (EPSRC)

2019-03-26T11:50:07Z

2019-03-26T11:50:07Z

2019-07-01

In recent years, many datasets have become available that represent natural language semantics as graphs. To use these datasets in natural language processing (NLP), we require probabilistic models of graphs. Finite-state models have been very successful for NLP tasks on strings and trees because they are probabilistic and composable. Are there equivalent models for graphs? In this thesis, we survey several graph formalisms, focusing on whether they are probabilistic and composable, and we contribute several new results. In particular, we study the directed acyclic graph automata languages (DAGAL), the monadic second-order graph languages (MSOGL), and the hyperedge replacement languages (HRL). We prove that DAGAL cannot be made probabilistic, we explain why MSOGL also most likely cannot be made probabilistic, and we review the fact that HRL are not composable. We then review a subfamily of HRL and MSOGL: the regular graph languages (RGL; Courcelle 1991), which have not been widely studied, and particularly have not been studied in an NLP context. Although Courcelle (1991) only sketches a proof, we present a full, more NLP-accessible proof that RGL are a subfamily of MSOGL. We prove that RGL are probabilistic and composable, and we provide a novel Earley-style parsing algorithm for them that runs in time linear in the size of the input graph. We compare RGL to two other new formalisms: the restricted DAG languages (RDL; Bj¨orklund et al. 2016) and the tree-like languages (TLL; Matheja et al. 2015). We show that RGL and RDL are incomparable; TLL and RDL are incomparable; and either RGL are incomparable to TLL, or RGL are contained within TLL. This thesis provides a clearer picture of this field from an NLP perspective, and suggests new theoretical and empirical research directions.

http://hdl.handle.net/1842/35606

en

The University of Edinburgh

Gilroy, S., A. Lopez, and S. Maneth 2017a. Parsing graphs with regular graph grammars. In Proceedings of the Sixth Joint Conference on Lexical and Computational Semantics, *SEM@ACL 2017, Vancouver, Canada, 3-4 August 2017.

Gilroy, S., A. Lopez, S. Maneth, and P. Simonaitis 2017b. (Re)introducing regular graph languages. In Proceedings of the 15th Meeting on the Mathematics of Language (MoL 15), London, United Kingdom. Association for Computational Linguistics.

Vasiljeva, I., S. Gilroy, and A. Lopez 2018. The problem with probabilistic dag automata for semantic graphs.

graph formalisms

directed acyclic graph automata languages

DAGAL

monadic second-order graph languages

MSOGL

hyperedge replacement languages

HRL

Probabilistic graph formalisms for meaning representations

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy