Lattice-based Search Strategies for Large Vocabulary Speech Recognition

Fred Richardson

The design of search algorithms is an important issue in recognition, particularly for very large vocabulary, continuous speech. It is an especially crucial problem when computationally expensive knowledge sources are used in the system, as is necessary to achieve high accuracy. Recently, multi-pass search strategies have been used as a means of applying inexpensive knowledge sources early on to prune the search space for subsequent passes using more expensive knowledge sources. Three multi-pass search algorithms are investigated in this thesis work: the N-best search algorithm, a lattice dynamic programming search algorithm and a lattice local search algorithm. Both the lattice dynamic programming and lattice local search algorithms are shown to achieve comparable performance to the N-best search algorithm while running as much as 10 times faster on a 20,000 word vocabulary task. The lattice local search algorithm is also shown to have the additional advantage over the lattice dynamic programming search algorithm of allowing sentence-level knowledge sources to be incorporated into the search.

The full thesis in postscript format. (874 kB)

Return to the SSLI Lab Graduate Students Theses Page.
Return to the SSLI Lab Home Page.
For any inquiries about SSLI Lab's people, papers, or projects, send e-mail to
UDub Copyright ©1995-1999 University of Washington, College of Engineering - SSLI Lab
E-mail any questions/comments/corrections to:
(Most Recent Update: 18-Feb-2000)