BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A Quantum Search Decoder for Natural Language Processing - Johanne
 s Bausch (University of Cambridge)
DTSTART:20200206T141500Z
DTEND:20200206T151500Z
UID:TALK139390@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:Probabilistic language models\, e.g. those based on an LSTM\, 
 often face the problem of finding a high probability prediction from a seq
 uence 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 num
 ber of highest-likelihood paths (the beam width) of the decoder are kept\,
  and at the end the maximum-likelihood path is chosen.\n  \nIn 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 th
 e input to the decoder is distributed as a power-law with exponent k>0\, o
 ur algorithm has runtime R^{n f(R\,k)}\, where f is upper-bounded by 1/2 a
 nd goes to 0 exponentially fast with increasing k\, hence making our algor
 ithm always more than quadratically faster than its classical counterpart.
 \n  \nWe further modify our procedure to recover a finite beam width varia
 nt\, which enables an even stronger empirical speedup while still retainin
 g higher accuracy than possible classically.  Finally\, we apply this quan
 tum 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
 .
LOCATION:MR21\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR