Sixth International Conference on Spoken Language Processing
(ICSLP 2000)

Beijing, China
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 [1] 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 e ective 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 pruning.


  1. J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Proc. 15th Int'l. Joint Conf. on AI, 1997.

Full Paper

Bibliographic reference.  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.