Finding the N Best Vertices in an Infinite Weighted Hypergraph
2017 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , 78 p.Article in journal (Refereed) Accepted
We propose an algorithm for computing the N best vertices in a weighted acyclic hypergraph over a nice semiring. A semiring is nice if it is finitely-generated, idempotent, and has 1 as its minimal element. We then apply the algorithm to the problem of computing the N best trees with respect to a weighted tree automaton, and complement theoretical correctness and complexity arguments with experimental data. The algorithm has several practical applications in natural language processing, for example, to derive the N most likely parse trees with respect to a probabilistic context-free grammar.
Place, publisher, year, edition, pages
Elsevier, 2017. , 78 p.
Hypergraph, N-best problem, Idempotent semiring
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-132501OAI: oai:DiVA.org:umu-132501DiVA: diva2:1081961