Efficient, High-Performance Algorithms for N-Best Search

Abstract

We present two efficient search algorithms for real-time spoken language systems. The first called the Word-Dependent N-Best algorithm is an improved algorithm for finding the top N sentence hypotheses. The new algorithm is shown to perform as well as the Exact Sentence-Dependent algorithm presented previously but with an order of magnitude less computation. The second algorithm is a fast match scheme for continuous speech recognition called the Forward-Backward Search. This algorithm, which is directly motivated by the Baum-Welch Forward-Backward training algorithm, has been shown to reduce the computation of a time-synchronous beam search by a factor of 40 with no additional search errors.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1990
Accession Number
ADA460351

Entities

People

  • Richard Schwartz
  • Steve Austin

Organizations

  • BBN Technologies

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automated Speech Recognition
  • Computations
  • Errors
  • Grammars
  • Hypotheses
  • Information Operations
  • Language
  • Mathematics
  • Natural Language Understanding
  • Natural Languages
  • Probability
  • Recognition
  • Sequences
  • Test Sets

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Speech Processing/Speech Recognition.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Machine Translation