Improved N-Best Extraction with an Evaluation on Language Data

Improved N-Best Extraction with an Evaluation on Language Data Johanna Bj¨orklund Ume˚a University Department of Computing Science johanna@cs.umu.se Frank Drewes Ume˚a University Department of Computing Science drewes@cs.umu.se Anna Jonsson Ume˚a University Department of Computing Science aj@cs.umu.se 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. 1. Introduction Trees are standard in natural language processing (NLP) to represent linguistic analyses of sentences. Similarly, tree automata provide a compact representation for a set of such analyses. Bottom–up tree automata act as recognizing devices and process their input trees in a step-wise fashion, working upwards from the leaf nodes towards the root of the tree. For memory, they have a finite set of states, some of which are said to be accepting, and their internal logic is represented as a finite set of transition rules. A run of a tree automaton M on an input tree t is a mapping from the nodes of t to the states, which is Submission received: 18 March 2021; revised version received: 31 August 2021; accepted: 5 December 2021. https://doi.org/10.1162/COLI a 00427 © 2022 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 48, Number 1 compatible with the transition rules. In general, M can have several distinct runs on t, and accepts t if one of these runs maps the root of t to an accepting state. By equipping the transition rules with weights, M can be made to associate t with a likelihood or score: The weight of a run of M on t is the product of the weights of the transition rules used in the run, and the weight of t is the sum of the weights of all runs on t. This type of automaton is called a weighted-tree automaton (wta) and is popular in, for example, dependency parsing and machine translation. A central task is the extraction of the highest ranking trees with respect to a weighted tree automaton. For example, when the automaton represents a large set of intermediate solutions, it may be desirable to prune these down to a more …

Content truncated to 500 words