The method determining the beam width

There are two methods to determine the beam width.

1. Select the beam width based on some criterion.

2. Select a fixed 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 $G_t(w_1,w_0,i)$ to be sorted for each frame. This requires a lot of computation. But, $G_t(w_1,w_0,i)$ need not be fully sorted, i.e., only the value of the best $B$ likelihoods are needed. Concretely, if the maximum beam width is $N$, this calculation is only of order $O( log N )$ , 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.