Language Model Rest Costs and Space-Efficient Storage

======================================================================
                Joint Seminar
======================================================================
The Hong Kong University of Science & Technology
Human Language Technology Center
Department of Computer Science and Engineering
---------------------------------------------------------------------

Speaker:        Kenneth HEAFIELD
                Carnegie-Mellon University / University of Edinburgh

Title:          "Language Model Rest Costs and Space-Efficient Storage"

Date:           Monday, 23 July 2012

Time:           4:00pm - 5:00pm

Venue:          Room 3416 (via lifts 17/18), HKUST


Abstract:

Approximate search algorithms, such as cube pruning in syntactic machine
translation, rely on the language model to estimate probabilities of
sentence fragments.  We contribute two changes that trade between accuracy
of these estimates and memory, holding sentence-level scores constant.
Common practice uses lower-order entries in an N-gram model to score the
first few words of a fragment; this violates assumptions made by common
smoothing strategies, including Kneser-Ney.  Instead, we use a unigram
model to score the first word, a bigram for the second, etc.  This
improves search at the expense of memory. Conversely, we show how to save
memory by collapsing probability and backoff less accurate estimates for
sentence fragments.   These changes can be stacked, achieving better
estimates with unchanged memory usage.  In order to interpret changes in
search accuracy, we adjust the pop limit so that accuracy is unchanged and
report the change in CPU time.  In a German-English Moses system with
target-side syntax, improved estimates yielded a 63% reduction in CPU
time; for a Hiero-style version, the reduction is 21%.  The compressed
language model uses 26% less RAM while equivalent search quality takes 27%
more CPU.  Source code is released as part of KenLM.

(Joint work with Philipp Koehn and Alon Lavie.)


********************
Biogrpahy:

Kenneth HEAFIELD is a PhD student at Carnegie Mellon advised by Alon Lavie
and a research associate with Phillipp Koehn at the University of
Edinburgh.  Kenneth is interested in computationally efficient algorithms
for machine translation and language modeling as well as system
combination.  His language model, KenLM, has been adopted by several
translation systems, including Moses, cdec, and Joshua.