2019
pdf
bib
abs
The problem with probabilistic DAG automata for semantic graphs
Ieva Vasiljeva

Sorcha Gilroy

Adam Lopez
Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)
Semantic representations in the form of directed acyclic graphs (DAGs) have been introduced 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 studied as a probabilistic model. We show that some DAG automata cannot be made into useful probabilistic models by the nearly universal strategy of assigning weights to transitions. The problem affects singlerooted, multirooted, and unboundeddegree variants of DAG automata, and appears to be pervasive. It does not affect planar variants, but these are problematic for other reasons.
pdf
bib
abs
Semantic graph parsing with recurrent neural network DAG grammars
Federico Fancellu

Sorcha Gilroy

Adam Lopez

Mirella Lapata
Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP)
Semantic parses are directed acyclic graphs (DAGs), so semantic parsing should be modeled as graph prediction. But predicting graphs presents difficult technical challenges, so it is simpler and more common to predict the *linearized* graphs found in semantic parsing datasets using wellunderstood sequence models. The cost of this simplicity is that the predicted strings may not be wellformed graphs. We present recurrent neural network DAG grammars, a graphaware sequence model that generates only wellformed graphs while sidestepping many difficulties in graph prediction. We test our model on the Parallel Meaning Bank—a multilingual semantic graphbank. Our approach yields competitive results in English and establishes the first results for German, Italian and Dutch.
2018
pdf
bib
abs
Recurrent Neural Networks as Weighted Language Recognizers
Yining Chen

Sorcha Gilroy

Andreas Maletti

Jonathan May

Kevin Knight
Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
We investigate the computational complexity of various problems for simple recurrent neural networks (RNNs) as formal models for recognizing weighted languages. We focus on the singlelayer, ReLUactivation, rationalweight RNNs with softmax, which are commonly used in natural language processing applications. We show that most problems for such RNNs are undecidable, including consistency, equivalence, minimization, and the determination of the highestweighted string. However, for consistent RNNs the last problem becomes decidable, although the solution length can surpass all computable bounds. If additionally the string is limited to polynomial length, the problem becomes NPcomplete. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.
bib
abs
Graph Formalisms for Meaning Representations
Adam Lopez

Sorcha Gilroy
Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: Tutorial Abstracts
In this tutorial we will focus on Hyperedge Replacement Languages (HRL; Drewes et al. 1997), a contextfree graph rewriting system. HRL are one of the most popular graph formalisms to be studied in NLP (Chiang et al., 2013; Peng et al., 2015; Bauer and Rambow, 2016). We will discuss HRL by formally defining them, studying several examples, discussing their properties, and providing exercises for the tutorial. While HRL have been used in NLP in the past, there is some speculation that they are more expressive than is necessary for graphs representing natural language (Drewes, 2017). Part of our own research has been exploring what restrictions of HRL could yield languages that are more useful for NLP and also those that have desirable properties for NLP models, such as being closed under intersection. With that in mind, we also plan to discuss Regular Graph Languages (RGL; Courcelle 1991), a subfamily of HRL which are closed under intersection. The definition of RGL is relatively simple after being introduced to HRL. We do not plan on discussing any proofs of why RGL are also a subfamily of MSOL, as described in Gilroy et al. (2017b). We will briefly mention the other formalisms shown in Figure 1 such as MSOL and DAGAL but this will focus on their properties rather than any formal definitions.
2017
pdf
bib
(Re)introducing Regular Graph Languages
Sorcha Gilroy

Adam Lopez

Sebastian Maneth

Pijus Simonaitis
Proceedings of the 15th Meeting on the Mathematics of Language
pdf
bib
abs
Parsing Graphs with Regular Graph Grammars
Sorcha Gilroy

Adam Lopez

Sebastian Maneth
Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017)
Recently, several datasets have become available which represent natural language phenomena as graphs. Hyperedge Replacement Languages (HRL) have been the focus of much attention as a formalism to represent the graphs in these datasets. Chiang et al. (2013) prove that HRL graphs can be parsed in polynomial time with respect to the size of the input graph. We believe that HRL are more expressive than is necessary to represent semantic graphs and we propose the use of Regular Graph Languages (RGL; Courcelle 1991), which is a subfamily of HRL, as a possible alternative. We provide a topdown parsing algorithm for RGL that runs in time linear in the size of the input graph.