Improved Confusion Network Algorithm and Shortest Path Search from Word Lattice
Jian Xue, Yunxin Zhao · 2006
We propose a novel confusion network (CN) generation algorithm with linear time complexity, O(T), which is capable of transforming a very large lattice into a confusion network with insignificant time. We further extend the confusion network concept to incorporate the case that a long word is split into short words. Finally, we develop a shortest path search algorithm that finds a sentence hypothesis from a word lattice to minimize the expected word error rate directly. The proposed algorithms are evaluated on the Switchboard task, where significant reduction of computation time was observed for the proposed confusion network algorithm as compared with a previously proposed confusion network algorithm, and improved word accuracy performance was observed for both the proposed CN algorithm and the shortest path algorithm as compared with one-best beam search decoding.