ビームの絞り方

ビームの絞り方には、次の２つの方法がある。

1. 尤度の閾値値で、計算を打ち切る方法
   
2. 一定の個数を残す方法
   

尤度の閾値で計算を打ち切る方法は、計算量が少なくてすむためよく利用さ れる。しかし、認識を行なう前に予め閾値を決めておく必要があるため、 認識の途中で 全ての経路が打ち切られたり、ビーム幅が急激に広がったりすることがあ る。一定の個数を残す方法は、フレーム ごとにソーティングが必要になるため、これが計算量の増大を招く と考えられてきた。しかし、フレームごとに上位からビー ム幅の個数を示す尤度だけを算出することによって、同様な結果を 得ることができる。この方法を採用することによって通常のソーティ ングに比較すると計算量が大幅に削減できる。具体的には$N$個の データがあったとき、フルソートでは$O (N\log_2 N)$の計算量が 必要であるが、上位からビーム幅の個数を示す尤度を算 出すれば計算量は $O ( log_2 N )$ですむ。このアルゴリズムで は、後者を選択した。