There are two methods to determine the beam width.
Methods to select the beam width with some criterion are
usually used. These methods are computationally cheap.
However, the criterion must be determined before
recognition. Therefore, under some recognition conditions,
the output is faulty. The method to select a fixed beam
width requires
to be sorted for each frame.
This requires a lot of computation. But,
need not be fully sorted, i.e., only the value of the best
likelihoods are needed. Concretely, if the maximum beam
width is
, this calculation is only of order
, which is not too costly.
In this algorithm, the computational cost depends on the beam width and does not depend on the language model. Word trigram models have the same cost as word bigram models. This algorithm can used with all left-to-right parsing algorithms such as CYK. If we use a high order Markov model, the recognition rate can be raised for text-closed data.