Exact Alpha-Beta Computation in Logarithmic Space with Application to MAP Word Graph Construction

The classical dynamic programming recursions for the forward-backwards and Viterbi HMM algorithms are linear in the number of time frames being processed. Adapting the method of [8] 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 effective 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.