A Quantum Search Decoder for Natural Language Processing
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
Probabilistic language models, e.g. those based on an LSTM, often face the
problem of finding a high probability prediction from a sequence of random
variables over a set of tokens. This is commonly addressed using a form of
greedy decoding such as beam search, where a limited number of
highest-likelihood paths (the beam width) of the decoder are kept, and at the
end the maximum-likelihood path is chosen. In this work, we construct a quantum
algorithm to find the globally optimal parse (i.e. for infinite beam width)
with high constant success probability. When the input to the decoder is
distributed as a power-law with exponent
Description
Funder: Science and Engineering Research Board; doi: https://doi.org/10.13039/501100001843
Funder: Cambridge Commonwealth Trust; doi: https://doi.org/10.13039/501100003342
Keywords
Journal Title
Conference Name
Journal ISSN
2524-4914