Beam Search（ビーム・サーチ）とは
言語モデルと言えば、「与えられた文章に対して次にくる言葉を確率的に予測する」というのが基本的な考え方です。この単純なアプローチは、次にくる言葉を予測するためのグリーディな手法として広く用いられています。しかし、さまざまな応用において、他の選択肢も存在します。今回の記事では、このグリーディな手法の一つの代替として、ビーム・サーチに焦点を当てます。
ビーム・サーチは機械翻訳や音声認識など、特定の問題において選択されることがある技術です。まずは、グリーディな手法を解説し、それと比較する形でビーム・サーチを紹介します。
では、さっそく始めましょう。
グリーディな手法とは？
「グリーディ」（Greedy）は英語で「貪欲」を意味し、ここでの「グリーディな手法」は、常にその時点で最も良いと思われる選択肢を選ぶアルゴリズムを指します。この手法は素早く、単純な解を見つけるのに効果的ですが、必ずしも全体として最適な解が得られるわけではありません。
例を挙げます。ある小学生が作文を書くのに「冬の休日に」から始めることにしました。そして次の文として、以下の三つの選択肢を考えます。
「雪だるまを作った」
「家で本を読んだ」
「南国へ旅行に行った」
この時点で最も一般的な選択肢は1の「雪だるまを作った」かもしれません。グリーディな手法だと、この選択肢を選ぶ可能性が高いでしょう。それは、「冬の休日に」という直近の文脈に続く確率が高い文章だからです。
この手法は素早く、単純な解を見つけるのに効果的ですが、必ずしも全体として最適な解が得られるわけではありません。時には一見良さそうな解が、全体のストーリーや文脈と合わないこともあるのです。
例えば、この小学生は作文の最後に家族との素晴らしい南国での冒険を書く予定だとしたらどうでしょうか。この場合は、雪だるまを作る話よりも、南国での冒険に続けるほうが話がスムーズで、全体の流れとして最適でしょう。よって、あとに続く文脈を考慮して初めて全体としての最適な言葉選びが可能となるケースがあることがわかります。そのようなケースはグリーディな手法では扱うことができません。
では、グリーディな手法の一つの代替として、ビーム・サーチを紹介します。ビーム・サーチは機械翻訳や文章生成など、特定の言語モデルの問題において選択されることがある技術です。
ビーム・サーチとは？
ビーム・サーチは、文章を作成する際に言語モデルが使う手法の一つで、複数の候補の文を同時に考えながら最適な文章の探索を行うものです。
ビーム・サーチのイメージを掴む具体例として、ある作家が物語の冒頭を書こうとしている様子を想像してみましょう。次のような出だし文から文章を展開しようとしているとします。
出だし文: 「ある晴れた朝、男は目を覚ました。」
グリーディな手法では、この文章に続く一つの最適解を選択し、物語を進めていきます。しかし、この時点で後続する最適な文章を決められないとしたらどうでしょうか。
というのも、この出だし文に続けて書く文として複数の候補があり、ある程度の続きを書き出してみないと文章として一番良いものを見極めることができないからです。よって、続ける文章として良さそうなものを次の三つの選択肢に絞ったとします。
「窓からは美しい海が広がっていた。」
「床には謎の手紙が落ちていた。」
「今日は大切な試験の日だった。」
そして、この三つの選択肢からさらに次の選択肢へと探求を深め、物語がどう展開するのか複数の方向で考えるわけです。
たとえば、選択肢2「床には謎の手紙が落ちていた。」の続きとして、新たな三つの選択肢を展開します。
「手紙を開いてみると、予期せぬ人物からの招待状だった。」
「手紙の筆跡を見て、彼は昔の友人からだと気づいた。」
「手紙は未開封で、宛名もなく、どこから来たのかが謎だった。」
このように、ビーム・サーチは一つの選択肢からさらに複数の可能性を探索し、それぞれの選択肢がどう展開するのか同時に考えます。この方法によって、最も引き込まれる物語の経路を見つけることができるかもしれません。
つまり、文章を書き続けることで文脈が生成され、全体的に最適な文章を選ぶことができるようになります。このように、ビーム・サーチは物語作りのプロセスに例えることができます。これはグリーディな手法では不可能な探索です。
しかし、こんな疑問も湧きます。複数の選択肢を同時にどんどん展開したら、考慮すべき文章が増えすぎで計算量が大きくなりすぎないでしょうか。
そのような状況の対策としてビーム幅があります。これについて知るには、ビーム・サーチの仕組みを確率の問題として理解した方が良いでしょう。
ビーム・サーチの仕組み
ここからはビーム・サーチを確率の問題として捉えて解説します。
ビーム・サーチの話を進める前に、言語モデルの解説などよくで使われる「トークン」という言葉について簡単に説明します。言語モデルでは、文章を作る際に使う最小の単位を「トークン」と呼びます。たとえば、「猫」という言葉は1つのトークンになりますし、「走る」という言葉も1つのトークンです。これらのトークンを組み合わせて、文章が作られます。トークンは単語と似た概念ですが、厳密には異なります。しかし、この説明の文脈では、トークンを単語のようなものとして考えても問題ありません。
これまで、文章を一つの単位として扱って説明してきましたが、ここからはトークンの組み合わせで文章を作るという前提で解説します。グリーディな手法では、ある文脈（書き出し分など）を与えられた状況で、次のトークンとしてもっとも確率の高いトークンを選びます。これがビーム・サーチではどうなるのかをみていきましょう。
この例では、わかりやすくするためにディクショナリに4つのトークンしかないと仮定しています。しかし、実際の言語モデルでは、ディクショナリには数千から数万のトークンが存在し、ビーム・サーチはそれらの中から最適なシーケンスを探します。
まず、$${\boldsymbol{x}}$$を書き出し文章とします。つまり、文脈として$${\boldsymbol{x}}$$をが与えられた上で、その次に続く言葉（トークン）の確率を、それぞれのトークンに対して計算します。この際、選べるトークンが４つしかないと仮定しているので、計算する確率は、$${P(y_1|\boldsymbol{x}),P(y_2|\boldsymbol{x}),P(y_3|\boldsymbol{x}),P(y_4|\boldsymbol{x})}$$の４つになります。
ここでビーム幅（ビームサイズ）を２としています。ビーム幅とは、継続して探索する文章の流れの数です。よって、文脈$${\boldsymbol{x}}$$に続くものとして４つの選択肢から２つのトークンを選びます。上図では、黄色にハイライトされた$${y_1}$$と$${y_3}$$
さらに、その２つのトークンから続けて４つのトークンに対する確率を計算します。そうすると全部で８つのトークンが候補になるのですが、この８つの候補から、ビーム幅に従って２つの選択肢に絞ります。
この際に考慮する確率は、個々のトークンに対する確率ではなく、文章の流れ全体に対する確率です。
具体的には、ビームサーチにおける確率の計算では、現時点までのトークンシーケンス（トークンの並び）全体に対する確率を考慮します。言い換えると、選択されたトークンを追加するたびに、そのトークンが追加される前の文章の流れ全体に対する確率に、新しいトークンの条件付き確率を乗算していきます。
例えば、トークンを２つ続けた場合の確率は次のように表現できます。
$$
P(y^{(1)}, y^{(2)} | \boldsymbol{x}) = P(y^{(1)} | \boldsymbol{x}) \cdot P(y^{(2)} | y^{(1)}, \boldsymbol{x})
$$
$${y^{(1)}}$$は、一番目に選ばれたトークンという意味です。上述の例では$${y_1, y_2, y_3, y_4}$$の内の一つになります。
このように継続して$${n}$$個のトークンを選択したとすると確率は次のように計算できます。
$$
P(\boldsymbol{y} | \boldsymbol{x}) = P(y^{(1)} | \boldsymbol{x}) \cdot P(y^{(2)} | y^{(1)}, \boldsymbol{x}) \cdot \dots \cdot P(y^{(n)} | y^{(n-1)}, \dots, y^{(1)}, \boldsymbol{x})
$$
ここで、$${\boldsymbol{y}}$$は、選択されたトークンのシーケンス（$${y^{(1)}, y^{(2)}, \dots, y^{(n)}}$$）をベクトルとして表現しています。
ビームサーチにおけるこの確率の計算は、文章の流れを考慮して探索を行うための重要な部分であり、単に各トークンの確率を独立に考慮するのではなく、文章全体としての一貫性と流れを評価する役割を果たします。この計算を各文章の流れ（ビーム）に対して行い、最適なビームをビーム幅の数だけ選びます。
このようにビーム幅を使うことで探索する候補がどんどん増加していく問題を回避しています。また、ある段階では最適解でなかった文章が後で最適になるような場合にも対処できます。
なお、ビーム幅が１の場合は、グリーディな手法と同等です。グリーディな手法では、常に一つのビームしかないのでより最適な解を見逃す可能性があります。
また、ビーム幅がトークンの数と同じ場合を全探索、しらみつぶし検索（Exhaustive Search）、力まかせ探索（Brute-force Search）などと呼びます。全探索は最も単純で、最良の解を見つけるための確実な方法ですが、文章が長くなるほど解の空間はどんどん大きくなるので非効率で時間がかかります。よって、あまり実用的ではないでしょう。
その点、ビームサーチは、より効率的です。一度に考慮する候補の数をビーム幅として制限し、最良でない候補を途中で捨てるため、全ての可能な組み合わせを探索する必要がなく、計算が高速化されます。
まとめ
今回は、文章生成などで利用されるビーム・サーチについて解説しました。ビーム・サーチは、一度に複数の候補解を保持して探索を行う手法で、以下のようなメリットとデメリットがあります。
メリット
より広い探索空間が可能: 単なるグリーディな手法と比べ、多岐にわたる候補を考慮することができます。これにより、特定のタスクでの改善が期待される場合があります。
効率的な探索: 全探索に比べ、計算量を削減しながらも、より賢明な探索が可能です。
デメリット
計算量の増加: より広い探索空間を考慮するため、計算量は必然的に増加します。これにより、計算コストが上昇する場合があります。
最適なビーム幅の選定の難しさ: ビーム幅の選定はタスク、データセット、モデルの特性などが影響するため、最適な値を見つけることは容易ではありません。
ビーム・サーチを使用する際の挑戦の一つとして、ビーム幅の最適な値の選定が挙げられます。実際の応用でハイパーパラメータとして調整が必要で、様々なシチュエーションやアプリケーションにおいて、最適なパフォーマンスを引き出すための重要な部分となります。
いずれにせよ、ビーム・サーチは機械翻訳、音声認識、文章生成など、多岐にわたる応用分野で用いられる貴重な手法です。
（以上）
