BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:A Quantum Search Decoder for Natural Language Proc
essing - Johannes Bausch (University of Cambridge)
DTSTART;TZID=Europe/London:20200206T141500
DTEND;TZID=Europe/London:20200206T151500
UID:TALK139390AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/139390
DESCRIPTION:Probabilistic language models\, e.g. those based o
n an LSTM\, often face the problem of finding a hi
gh probability prediction from a sequence of rando
m 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-l
ikelihood paths (the beam width) of the decoder ar
e kept\, and at the end the maximum-likelihood pat
h is chosen.\n \nIn this work\, we construct a qu
antum algorithm to find the globally optimal parse
(i.e. for infinite beam width) with high constant
success probability. When the input to the decod
er 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 exponenti
ally fast with increasing k\, hence making our alg
orithm 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 spee
dup while still retaining higher accuracy than pos
sible classically. Finally\, we apply this quantu
m beam search decoder to Mozilla's implementation
of Baidu's DeepSpeech neural net\, which we show t
o exhibit such a power law word rank frequency.
LOCATION:MR21\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR