Frank Drewes


2022

pdf bib
Improved N-Best Extraction with an Evaluation on Language Data
Johanna Björklund | Frank Drewes | Anna Jonsson
Computational Linguistics, Volume 48, Issue 1 - March 2022

We show that a previously proposed algorithm for the N-best trees problem can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared with the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor. The algorithm is implemented in the software Betty, and compared to the state-of-the-art algorithm for extracting the N best runs, implemented in the software toolkit Tiburon. The data sets used in the experiments are wtas resulting from real-world natural language processing tasks, as well as artificially created wtas with varying degrees of nondeterminism. We find that Betty outperforms Tiburon on all tested data sets with respect to running time, while Tiburon seems to be the more memory-efficient choice.

2021

pdf bib
Bridging Perception, Memory, and Inference through Semantic Relations
Johanna Björklund | Adam Dahlgren Lindström | Frank Drewes
Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing

There is a growing consensus that surface form alone does not enable models to learn meaning and gain language understanding. This warrants an interest in hybrid systems that combine the strengths of neural and symbolic methods. We favour triadic systems consisting of neural networks, knowledge bases, and inference engines. The network provides perception, that is, the interface between the system and its environment. The knowledge base provides explicit memory and thus immediate access to established facts. Finally, inference capabilities are provided by the inference engine which reflects on the perception, supported by memory, to reason and discover new facts. In this work, we probe six popular language models for semantic relations and outline a future line of research to study how the constituent subsystems can be jointly realised and integrated.

2020

pdf bib
Probing Multimodal Embeddings for Linguistic Properties: the Visual-Semantic Case
Adam Dahlgren Lindström | Johanna Björklund | Suna Bensch | Frank Drewes
Proceedings of the 28th International Conference on Computational Linguistics

Semantic embeddings have advanced the state of the art for countless natural language processing tasks, and various extensions to multimodal domains, such as visual-semantic embeddings, have been proposed. While the power of visual-semantic embeddings comes from the distillation and enrichment of information through machine learning, their inner workings are poorly understood and there is a shortage of analysis tools. To address this problem, we generalize the notion ofprobing tasks to the visual-semantic case. To this end, we (i) discuss the formalization of probing tasks for embeddings of image-caption pairs, (ii) define three concrete probing tasks within our general framework, (iii) train classifiers to probe for those properties, and (iv) compare various state-of-the-art embeddings under the lens of the proposed probing tasks. Our experiments reveal an up to 16% increase in accuracy on visual-semantic embeddings compared to the corresponding unimodal embeddings, which suggest that the text and image dimensions represented in the former do complement each other.

2019

pdf bib
A Survey of Recent Advances in Efficient Parsing for Graph Grammars
Frank Drewes
Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing

pdf bib
Bottom-Up Unranked Tree-to-Graph Transducers for Translation into Semantic Graphs
Johanna Björklund | Shay B. Cohen | Frank Drewes | Giorgio Satta
Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing

We propose a formal model for translating unranked syntactic trees, such as dependency trees, into semantic graphs. These tree-to-graph transducers can serve as a formal basis of transition systems for semantic parsing which recently have been shown to perform very well, yet hitherto lack formalization. Our model features “extended” rules and an arc-factored normal form, comes with an efficient translation algorithm, and can be equipped with weights in a straightforward manner.

pdf bib
Proceedings of the 16th Meeting on the Mathematics of Language
Philippe de Groote | Frank Drewes | Gerald Penn
Proceedings of the 16th Meeting on the Mathematics of Language

pdf bib
Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
Henrik Björklund | Frank Drewes | Petter Ericson
Proceedings of the 16th Meeting on the Mathematics of Language

2018

pdf bib
Weighted DAG Automata for Semantic Graphs
David Chiang | Frank Drewes | Daniel Gildea | Adam Lopez | Giorgio Satta
Computational Linguistics, Volume 44, Issue 1 - April 2018

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.

2017

pdf bib
DAG Automata for Meaning Representation
Frank Drewes
Proceedings of the 15th Meeting on the Mathematics of Language

pdf bib
Proceedings of the 13th International Conference on Finite State Methods and Natural Language Processing (FSMNLP 2017)
Frank Drewes
Proceedings of the 13th International Conference on Finite State Methods and Natural Language Processing (FSMNLP 2017)

pdf bib
Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages
Martin Berglund | Henrik Björklund | Frank Drewes
Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms

pdf bib
Contextual Hyperedge Replacement Grammars for Abstract Meaning Representations
Frank Drewes | Anna Jonsson
Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms

2016

pdf bib
EM-Training for Weighted Aligned Hypergraph Bimorphisms
Frank Drewes | Kilian Gebhardt | Heiko Vogler
Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata

2013

pdf bib
On the Parameterized Complexity of Linear Context-Free Rewriting Systems
Martin Berglund | Henrik Björklund | Frank Drewes
Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13)

2012

pdf bib
Proceedings of the Workshop on Applications of Tree Automata Techniques in Natural Language Processing
Frank Drewes | Marco Kuhlmann
Proceedings of the Workshop on Applications of Tree Automata Techniques in Natural Language Processing

2011

pdf bib
Incremental Construction of Millstream Configurations Using Graph Transformation
Suna Bensch | Frank Drewes | Helmut Jürgensen | Brink van der Merwe
Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing

2010

pdf bib
Proceedings of the 2010 Workshop on Applications of Tree Automata in Natural Language Processing
Frank Drewes | Marco Kuhlmann
Proceedings of the 2010 Workshop on Applications of Tree Automata in Natural Language Processing

pdf bib
Millstream Systems – a Formal Model for Linking Language Modules by Interfaces
Suna Bensch | Frank Drewes
Proceedings of the 2010 Workshop on Applications of Tree Automata in Natural Language Processing