A comparison of several approximate algorithms for finding multiple (N-best) sentence hypotheses

The authors introduce a new, more efficient algorithm, the word-dependent N-best algorithm, for finding multiple sentence hypotheses. The proposed algorithm is based on the assumption that the beginning time of a word depends only on the preceding word. The authors compare this algorithm with two other algorithms for finding the N-best hypotheses: the exact sentence-dependent method and a computationally efficient lattice N-best method. Although the word-dependent algorithm is computationally much less expensive than the exact algorithm, it appears to result in the same accuracy. The lattice method, which is still more efficient, has a significantly higher error rate. It is demonstrated that algorithms that use Viterbi scoring have significantly higher error rates than those that use total likelihood scoring.>