The forward-backward search algorithm

The authors introduce a technique that greatly speeds up expensive time-synchronous beam searches in speech recognition. The algorithm is called the forward-backward search and is mathematically related to the Baum-Welch forward-backward training algorithm. It uses a simplified forward pass followed by a detailed backward search. The information stored in the forward pass is used to decrease the computation in the backward pass by a large factor. An increase in speed of a factor of 40 with no increase in search errors was observed. The authors also describe how they have incorporated this algorithm into a real-time speaker-independent spoken language understanding system. One version of this is based on the 1000 word Resource Management vocabulary and is directed by a statistical class grammar. Another version has been incorporated into a military transportation planning application called DART (Dynamic Analysis Re-planning Tool)