A quantum search decoder for natural language processing

Journal article

AbstractProbabilistic language models, e.g. those based on recurrent neural networks such as long short-term memory models (LSTMs), 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 follows a power law with exponentk> 0, our algorithm has runtimeRnf(R,k), whereRis the alphabet size,nthe input length; heref< 1/2, and$f\rightarrow 0$f→0exponentially fast with increasingk, hence making our algorithm always more than quadratically faster than its classical counterpart. We further modify our procedure to recover a finite beam width variant, which enables an even stronger empirical speedup while still retaining higher accuracy than possible classically. Finally, we apply this quantum beam search decoder to Mozilla’s implementation of Baidu’sDeepSpeechneural net, which we show to exhibit such a power law word rank frequency.

Authors: Bausch, J; Subramanian, S; Piddock, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Quantum Machine Intelligence
• Volume: 3
• Issue: 1
• Article number: 16
• Publication date: 2021-04-30
• DOI: 10.1007/s42484-021-00041-1
• EISSN: 2524-4914
• ISSN: 2524-4906
• Language: English