Minimizing Computational Cost for Dynamic Programming Algorithms

Abstract

In this study we introduce and test several methods to reduce the computational cost in dynamic programming algorithms for isolated word recognition systems. Three methods will be discussed in detail: (1) Pruning by preset thresholds, (2) Search based on the Branch and Bound technique, (3) Branch and Bound based search with additional pruning. Compared to conventional algorithms, Method 3 could be seen to yield a speed up of approximately a factor of 5, at no loss of recognition accuracy. The branch and bound method with pruning is also ideally suited for research oriented systems, since pruning is independent of the parametrization used (eliminates the necessity for retuning thresholds). Additional features of this method, which are of importance to maintaining the flexibility and diagnosticity needed for such a system, will be discussed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 17, 1981
Accession Number
ADA104792

Entities

People

  • A. Waibel
  • N. Krishnan
  • Rekha Reddy

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Automated Speech Recognition
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Costs
  • Data Sets
  • Databases
  • Dynamic Programming
  • Efficiency
  • Errors
  • Recognition
  • Vocabulary
  • Word Recognition

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Regression Analysis.
  • Theoretical Analysis.