COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > A Quantum Search Decoder for Natural Language Processing

## A Quantum Search Decoder for Natural Language ProcessingAdd to your list(s) Download to your calendar using vCal - Johannes Bausch (University of Cambridge)
- Thursday 06 February 2020, 14:15-15:15
- MR21, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact Johannes Bausch. 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 k>0, our algorithm has runtime R^{n f(R,k)}, where f is upper-bounded by 1/2 and goes to 0 exponentially fast with increasing k, 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’s DeepSpeech neural net, which we show to exhibit such a power law word rank frequency. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- MR21, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- bld31
Note that ex-directory lists are not shown. |
## Other listsAAAS members and friends event Cambridge and Anglian Materials Society meetings Science and Technology Reading Group## Other talksBioinspired soft composites and functional materials using self-assembly Resonant Ultrasound Spectroscopy: characterisation of elastic and anelastic behaviour of metals, ceramics and functional oxides associated with ferroic, multiferroic and normal-superconductor phase transitions It's about time: The evolutionary ecology of circadian rhythms during infections Bigging up behaviour on coral reefs Towards the Modern Subject (Global Imaginaries through the Ages) Towards XNA molecularbiology: reinventing biology one protein at a time |