Article

Algorithms for an optimal A search and linearizing the search in the stack decoder

Author:

Douglas B. PaulAuthors Info & Claims

HLT '90: Proceedings of the workshop on Speech and Natural Language

Pages 200 - 203

https://doi.org/10.3115/116580.116646

Published: 24 June 1990 Publication History

Abstract

The stack decoder is an attractive algorithm for controlling the acoustic and language model matching in a continuous speech recognizer. It implements a best-first tree search of the language to find the best match to both the language model and the observed speech. This paper describes a method for performing the optimal A search which guarantees to find the most likely path (recognized sentence) while extending the minimum number of stack entries. A tree search, however, is exponential in the number of words. A second algorithm is presented which linearizes the search at the cost of approximating some of the path likelihoods.

References

[1]

L. R. Bahl, F. Jelinek, and R. L. Mercer, "A Maximum Likelihood Approach to Continuous Speech Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, PAMI-5, March 1983.

Google Scholar

[2]

L. Bahl, P. S. Gopalakrishnam, D. Kanevsky, D. Nahamoo, "Matrix Fast Match: A Fast Method for Identifying a Short List of Candidate Words for Decoding," ICASSP 89, Glasgow, May 1989.

Google Scholar

[3]

J. K. Baker, personal communication, 25 June 1990.

Google Scholar

[4]

F. Jelinek, "A Fast Sequential Decoding Algorithm Using a Stack," IBM J. Res. Develop., vol. 13, November 1969.

Digital Library

Google Scholar

[5]

D. E. Knuth, "The Art of Computer Programming: Sorting and Searching,", Vol. 3., Addison-Wesly, Menlo Park, California, 1973.

Digital Library

Google Scholar

[6]

B. T. Lowerre, "The HARPY Speech Recognition System," PhD thesis, Computer Science Department, Carnegie Mellon University, April 1976.

Digital Library

Google Scholar

[7]

N. J. Nilsson, "Problem-Solving Methods of Artificial Intelligence," McGraw-Hill, New York, 1971.

Digital Library

Google Scholar

[8]

D. B. Paul, "A CSR-NL Interface Specification," Proceedings October, 1989 DARPA Speech and Natural Language Workshop, Morgan Kaufmann Publishers, October, 1989.

Digital Library

Google Scholar

[9]

D. B. Paul, "Speech Recognition using Hidden Markov Models," Lincoln Laboratory Journal, Vol. 3, no. 1, Spring 1990.

Google Scholar

[10]

A. B. Poritz, "Hidden Markov Models: A Guided Tour," Proc. ICASSP 88, April 1988.

Google Scholar

Cited By

View all

Paul D(1992)An efficient A* stack decoder algorithm for continuous speech recognition with a stochastic language modelProceedings of the workshop on Speech and Natural Language10.3115/1075527.1075624(405-409)Online publication date: 23-Feb-1992
https://dl.acm.org/doi/10.3115/1075527.1075624
Paul D(1991)Experience with a stack decoder-based HMM CSR and back-OFF N-gram language modelsProceedings of the workshop on Speech and Natural Language10.3115/112405.112459(284-288)Online publication date: 19-Feb-1991
https://dl.acm.org/doi/10.3115/112405.112459

Index Terms

Algorithms for an optimal A search and linearizing the search in the stack decoder

Recommendations

Algorithms for an optimal A* search and linearizing the search in the stack decoder
ICASSP '91: Proceedings of the Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference

Two algorithms are presented for accelerating the operation of a stack decoder. The first is a method for computing the true least upper bound so that an optimal admissible A* search can be performed. The second is a set of methods for linearizing the ...
Beam-stack search: integrating backtracking with beam search
ICAPS'05: Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling

We describe a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. Called beam-stack search, the algorithm uses a new data structure, called a beam stack, that makes it possible to ...
The Lincoln large-vocabulary stack-decoder based HMM CSR
HLT '94: Proceedings of the workshop on Human Language Technology

The system described here is a large-vocabulary continuous-speech recognition (CSR) system with results obtained using the Wall Street Journal-based database [15]. The recognizer uses a stack decoder-based search strategy[1, 7, 14] with a left-to-right ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HLT '90: Proceedings of the workshop on Speech and Natural Language

June 1990

450 pages

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 24 June 1990

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 240 of 768 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Paul D(1992)An efficient A* stack decoder algorithm for continuous speech recognition with a stochastic language modelProceedings of the workshop on Speech and Natural Language10.3115/1075527.1075624(405-409)Online publication date: 23-Feb-1992
https://dl.acm.org/doi/10.3115/1075527.1075624
Paul D(1991)Experience with a stack decoder-based HMM CSR and back-OFF N-gram language modelsProceedings of the workshop on Speech and Natural Language10.3115/112405.112459(284-288)Online publication date: 19-Feb-1991
https://dl.acm.org/doi/10.3115/112405.112459

Abstract

References

Cited By

Index Terms

Recommendations