Sixth International Conference on Spoken Language Processing
October 16-20, 2000
Exact Alpha-Beta Computation in Logarithmic Space with Application to MAP Word Graph Construction
Geoffrey Zweig, Mukund Padmanabhan
IBM T. J. Watson Research Center, Yorktown Heights, NY, USA
The classical dynamic programming recursions for the
forwards-backwards and Viterbi HMM algorithms are
linear in the number of time frames being processed.
Adapting the method of  to the context of speech
recognition, this paper uses a recursive divide-and-conquer
algorithm to reduce the space requirement to
logarithmic in the number of frames. With this procedure,
it is possible to do exact computations for observation
sequences of essentially arbitrary length. The
procedure works by manipulating a stack of alpha
vectors, and by using sparse vectors, the space savings can
be combined with those of traditional pruning
techniques. We apply this technique to MAP lattice
construction, and present the first results in the literature
for that technique. We find that it is an eective way of
creating word lattices, and that doing the exact
computations enabled by the log-space technique results in
lower word error rates than space saving via traditional
- J. Binder, K. Murphy and S. Russell. Space-Efficient
Inference in Dynamic Probabilistic Networks. Proc.
15th Int'l. Joint Conf. on AI, 1997.
Zweig, Geoffrey / Padmanabhan, Mukund (2000):
"Exact alpha-beta computation in logarithmic space with application to MAP word graph construction",
In ICSLP-2000, vol.2, 855-858.