Mike Schuster
Memory-efficient LVCSR search
using a one-pass stack decoder
Abstract:This report describes the details of a fast, memory-efficient one-pass stack decoder for efficient evaluation of the search space for large vocabulary continuous speech recognition. A modern, efficient search
engine is not based on a single idea, but is a rather complex collection of separate algorithms and practical implementation details, which only in combination make the search efficient in time and memory
requirements. Being the core of a speech recognition system, the software design phase for a new decoder is often crucial for its later performance and flexibility. This paper tries to emphasize this point – after defining the requirements for a modern decoder, it describes the details of an implementation that is
based on a stack decoder framework. It is shown how it is possible to handle arbitrary order N-grams,
how to generate N-best lists or lattices next to the first-best hypothesis at little computational overhead,
how to handle efficiently cross-word acoustic models of any context order, how to efficiently constrain
the search with word-graphs or word-pair grammars, and how to use a fast-match with delay to speed
up the search, all in a single left-to-right search pass. The details of a disk-based representation of an N-gram language model are given, which make it possible to use LMs of arbitrary (file) size in only a few
hundred kB of memory. On-demand N-gram smearing, an efficient improvement over the regular unigram
smearing used as an approximation to the LM scores in a tree lexicon, is introduced. It is also shown how
lattice rescoring, the generation of forced alignments and detailed phone-/state-alignments can efficiently
be integrated into a single stack decoder. The decoder named "Nozomi" awas tested on a Japanese newspaper dictation task using a 5000 word vocabulary. Using computationally cheap models it is possible to achieve realtime performance with 89% word recognition accuracy at about 1% search error using only 4 MB of total memory on a 300 MHz Pentium II. With computationally more expensive acoustic models, which also cover the for the Japanese language essential cross-word effects, more than 95% recognition accuracy bis reached.
(a:"Nozomi" is the name of the fastest, most comfortable and most expensive bullet train in Japan,
and also means "hope" in Japanese. b:which are currently the best reported results on this task)