@article{bjorklund-etal-2022-improved,
title = "Improved N-Best Extraction with an Evaluation on Language Data",
author = {Bj{\"o}rklund, Johanna and
Drewes, Frank and
Jonsson, Anna},
journal = "Computational Linguistics",
volume = "48",
number = "1",
month = mar,
year = "2022",
address = "Cambridge, MA",
publisher = "MIT Press",
url = "https://aclanthology.org/2022.cl-1.4",
doi = "10.1162/coli_a_00427",
pages = "119--153",
abstract = "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.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="bjorklund-etal-2022-improved">
<titleInfo>
<title>Improved N-Best Extraction with an Evaluation on Language Data</title>
</titleInfo>
<name type="personal">
<namePart type="given">Johanna</namePart>
<namePart type="family">Björklund</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Frank</namePart>
<namePart type="family">Drewes</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anna</namePart>
<namePart type="family">Jonsson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2022-03</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<genre authority="bibutilsgt">journal article</genre>
<relatedItem type="host">
<titleInfo>
<title>Computational Linguistics</title>
</titleInfo>
<originInfo>
<issuance>continuing</issuance>
<publisher>MIT Press</publisher>
<place>
<placeTerm type="text">Cambridge, MA</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">periodical</genre>
<genre authority="bibutilsgt">academic journal</genre>
</relatedItem>
<abstract>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.</abstract>
<identifier type="citekey">bjorklund-etal-2022-improved</identifier>
<identifier type="doi">10.1162/coli_a_00427</identifier>
<location>
<url>https://aclanthology.org/2022.cl-1.4</url>
</location>
<part>
<date>2022-03</date>
<detail type="volume"><number>48</number></detail>
<detail type="issue"><number>1</number></detail>
<extent unit="page">
<start>119</start>
<end>153</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Journal Article
%T Improved N-Best Extraction with an Evaluation on Language Data
%A Björklund, Johanna
%A Drewes, Frank
%A Jonsson, Anna
%J Computational Linguistics
%D 2022
%8 March
%V 48
%N 1
%I MIT Press
%C Cambridge, MA
%F bjorklund-etal-2022-improved
%X 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.
%R 10.1162/coli_a_00427
%U https://aclanthology.org/2022.cl-1.4
%U https://doi.org/10.1162/coli_a_00427
%P 119-153
Markdown (Informal)
[Improved N-Best Extraction with an Evaluation on Language Data](https://aclanthology.org/2022.cl-1.4) (Björklund et al., CL 2022)
ACL