Sökning: onr:"swepub:oai:DiVA.org:umu-132501" >
Finding the N Best ...
Finding the N Best Vertices in an Infinite Weighted Hypergraph
-
- Björklund, Johanna (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Drewes, Frank (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Jonsson, Anna, 1992- (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
(creator_code:org_t)
- Elsevier, 2017
- 2017
- Engelska.
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 682, s. 30-41
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Hypergraph
- N-best problem
- Idempotent semiring
- Computer Science
- datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas