1. 概要

このチュートリアルでは、ビームサーチアルゴリズムの定義を確認し、それがどのように機能するかを説明し、アルゴリズムにおけるビームサイズの役割を拡大します。

2. ビームサーチはどのように機能しますか？

ビームサーチは、幅優先探索（BFS）や最良優先探索（BeFS）に似た欲張り探索アルゴリズムです。 実際、2つのアルゴリズムはビームサーチの特殊なケースであることがわかります。

特定のノードに到達するためにトラバースしたいグラフ（）があると仮定しましょう。 ルートノードから始めます。 最初のステップは、このノードをすべての可能なノードで拡張することです。 次に、アルゴリズムの各ステップで、拡張可能なノードから特定の数のノードを選択します。 ビーム幅と呼びましょう。 これらのノードは、ヒューリスティックコストに基づく最適なノードです。 拡張は、ゴールノードに到達するまで続きます。

の場合、各ステップで拡張するのに最適なアルゴリズムを選択するため、BeFSアルゴリズムになります。これは、まさにBeFSの動作方法です。 ただし、その一方で、の場合、幅優先探索になります。 その理由は、展開するノードを選択するときに、現在のノードから1回の移動で、基準なしで到達可能なすべてのノードを考慮するためです。

3. ビームサーチ擬似コード

グラフでビームサーチを実行したい場合、その擬似コードは次のとおりです。

4. ビームサーチの例

ビームサーチの広く採用されているアプリケーションは、機械翻訳などのエンコーダ-デコーダモデルです。ある言語を別の言語に翻訳する場合、最初にソース言語から一連の単語をエンコードし、次に中間表現をデコードします。ターゲット言語の単語のシーケンス。 デコードプロセスでは、シーケンス内の単語ごとに、いくつかのオプションがあります。 ここでビームサーチが役立ちます。

簡略化されたサンプルデコードプロセスを段階的に見ていきましょう。 この例では、ヒューリスティック関数は、翻訳で可能な単語やフレーズの確率になります。 まず、シーケンスの開始を通知するトークンから始めます。 次に、語彙セット内のすべての単語の確率を計算することにより、最初の単語を取得できます。 最初の単語として、確率が最も高い（ビーム幅）単語を選択します（）：

その後、2つの単語を展開し、それらの後に続く可能性のある他の単語の確率を計算します。 確率が最も高い単語はになります。 これらの可能なパスから、最も可能性の高い2つのパスを選択します（）。 次に、これら2つを展開して、他の可能な組み合わせを取得します（）。 ここでも、現在のシーケンスの確率を最大化する2つの単語を選択します（）。 シーケンスの最後に到達するまでこれを続けます。 最終的に、最も可能性の高い翻訳シーケンスを取得する可能性があります。

途中で、小さなものを選択することにより、自然言語での長期的な依存関係が原因である可能性が高いいくつかのパスを無視していることを覚えておく必要があります。 この問題に対処する1つの方法は、より大きなビーム幅を選択することです。

5. ビームサーチ機能

5.1. ビームサーチの長所と短所

最良優先探索と比較して、ビームサーチの利点は、必要なメモリが少ないことです。これは、連続するすべてのノードをキューに格納する必要がないためです。 代わりに、最適な（ビーム幅）もののみを選択します。

一方で、BeFSの問題もいくつか残っています。 1つ目は、完全ではないということです。つまり、解決策がまったく見つからない可能性があります。 2番目の問題は、それも最適ではないということです。 したがって、それが解決策を返すとき、それは最良の解決策ではないかもしれません。

5.2. ビームサーチでビームサイズは何を表しますか？

ビーム幅は、ビームサーチのハイパーパラメータです。 このハイパーパラメータの選択は、作業中のアプリケーションとそれをどの程度正確にするかによって異なります。 たとえば、上記の例では、ビーム幅を大きくすると、より正確な長いフレーズを作成する単語を選択するのに役立ちます。 ただし、ビーム幅が大きくなることの欠点は、より多くのメモリが必要になることです。

全体として、ビーム幅が大きいほど、メモリが増えますが、ソリューションが向上します。 したがって、利用可能なリソースに基づいて、2つのバランスをとる必要があります。

6. 結論

この記事では、ビームサーチアルゴリズム、その長所と短所、およびハイパーパラメータとしてのビームサイズの役割について学習しました。