ビームサーチ法

ビームサーチ法は探索にかかる計算量を削減するために用いられる．翻訳候補の探索機において，翻訳確率の低い翻訳候補を枝刈りし，探索範囲を限定する．枝刈りは``histogram pruning''と``threshold pruning''によって行う．``histogram pruning''は確率の高い翻訳候補のみを一定数残す枝刈り法である．``threshold pruning''は一定の確率以上の翻訳候補のみを残す枝刈り法である．この2つの枝刈り法を用いて，探索範囲を限定する．しかし，図3.3を見てもわかるように，翻訳が進むほどに，翻訳候補の確率は低くなる．そのため，翻訳が進んだ翻訳候補と翻訳が進んでいない翻訳候補を比較したときに，翻訳が進んだ翻訳候補ほど枝刈りの対象となる可能性が高い．