ビームサーチ法

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