Browse Prior Art Database

Language Model Thresholding Scheme for Fast Match

IP.com Disclosure Number: IPCOM000103740D
Original Publication Date: 1993-Jan-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 98K

Publishing Venue

IBM

Related People

Bahl, L: AUTHOR [+5]

Abstract

Given a dictionary tree to be searched, the invention determines the parts of the tree that are not likely to lead to the required words by estimating language model probabilities for all words corresponding to the leaves in these parts of the tree.

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

Language Model Thresholding Scheme for Fast Match

       Given a dictionary tree to be searched, the invention
determines the parts of the tree that are not likely to lead to the
required words by estimating language model probabilities for all
words corresponding to the leaves in these parts of the tree.

      The current fast match part of the speech decoder works roughly
as follows.  For any utterance, the fast match in a first step finds
a list of words A = {w e Voc A (w) > eAC} that best
fits this utterance acoustically (here Voc is the vocabulary, A(w) is
the acoustic score for word w corresponding to the given utterance
and eA is some fixed or dynamic threshold.  The acoustic score A(w)
is computed by searching a dictionary tree made up from phonetic
transcriptions of all the words in the vocabulary.

      In a second step, the fast match finds a shorter list B of
words in the vocabulary.  The words are selected for the shorter list
based on the criterion B = {w e A S(w) = A(w) + LM(w) >
eAC + eLM = e}, where LM(W) estimates the probability to have the
word w in a certain part of the sentence and eLM is some threshold.

      The disadvantages of this method are the following. First, it
can happen that w does not belong to A if A(w) < eAC, but S(w)
> e. Secondly, it can happen that for a large part of the tree all
words corresponding to the leaves of this part have so low LM(w) that
they are dropped from B.  But some of these words could have high
enough acoustic scores to be placed in A.  Thus, useless work was
done in searching this part of the dictionary tree.  The invention
described here uses the language model already in the first step to
determine scores in order to avoid the above shortcomings.

      The proposed scheme is the following.  Assume that we must
decode the ith word in the sentence.  First we attach to each node a
of the tree the score S(a) by the following inductive rule: 1) For
each leaf node a we put S(a) = LM(wa) where wa is the word
corresponding to the leaf a and LM(wa) is the probability of having
wa in the given part of the sentence, and 2) For each internal node a
we set S(a) = maximum of S(a') for all descendants a' of a.  After we
attach score S(a) to each node in the tree we proceed as follows.
Assume that we want to evaluate a node a of the tree, i.e., we must
decide whether to visit nodes below a in the case...