Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved Thresholding Schemes to Reduce Search Effort in the Fast Match

IP.com Disclosure Number: IPCOM000114394D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Related People

Gopalakrishnan, PS: AUTHOR [+3]

Abstract

In the IBM isolated speech recognition system the computation of the maximum likelihood sentence is carried out using a stack search algorithm. Each iteration of this algorithm begins with the selection of the next path to be extended. For this path a fast match calculation is done to obtain a list of candidate words and then these candidate words are passed to the detailed match module to compute the detailed acoustic score. The fast match and detailed acoustic match scores are then combined with the language model score to obtain the final score which is used to rank the paths for further processing. For large vocabulary systems, a major part of the computation effort is in the fast match. The fast match is carried out as a tree search algorithm [*].

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Improved Thresholding Schemes to Reduce Search Effort in the Fast
Match

      In the IBM isolated speech recognition system the computation
of the maximum likelihood sentence is carried out using a stack
search algorithm.  Each iteration of this algorithm begins with the
selection of the next path to be extended.  For this path a fast
match calculation is done to obtain a list of candidate words and
then these candidate words are passed to the detailed match module to
compute the detailed acoustic score.  The fast match and detailed
acoustic match scores are then combined with the language model score
to obtain the final score which is used to rank the paths for further
processing.  For large vocabulary systems, a major part of the
computation effort is in the fast match.  The fast match is carried
out as a tree search algorithm [*].  If the score at a node of the
tree falls below a threshold then the subtree below that node is not
searched, thus reducing the search effort.  This invention describes
improved schemes for computing these search thresholds.

      Let n sub 0 n sub 1 ellipsis n sub k be the path from the root
node n sub 0 to a node n sub k in the fast match tree.  Let the score
at node n sub i be given by s sub i and the most likely boundary of
the node n sub i be given by b sub i.  The search threshold is
dependent on the time frame.  This array of thresholds is initialized
to a fixed value T sub C to begin with.  The application of the
threshold and the update of these thresholds is done as follows:
  1.  If the score s sub k of node n sub k is less than the threshold
       T(b sub k ) at the time frame b sub k then prune the subtree
       below the node n(k) (do not search any of the nodes in this
       subtree).  Also, decrea...