フォワード・バックワードアルゴリズムは、隠れマルコフモデル（HMM）および関連する確率的系列モデルの文脈で使用される、基本的な動的計画法の手法です。これは、観測系列が与えられたときの各隠れ状態の事後周辺分布を計算し、効率的な推論とパラメータ推定を可能にします。このアルゴリズムは古典的な機械学習の基盤であり、音声認識、バイオインフォマティクス、自然言語処理などの現代的な応用においても関連性を持ち続けています。
1960年代後半から1970年代初頭にかけて開発され、このアルゴリズムはレオナルド・バウムとその同僚たちによって、マルコフ連鎖の確率的関数に関する統計的推定の一連の論文で形式化されました。これは、最も可能性の高い隠れ状態の系列を見つけるビタビアルゴリズムと並べて提示されることが多く、一方でフォワード・バックワードアルゴリズムは各時間ステップにおける個々の状態の確率を計算します。このアルゴリズムは2つのパスで動作します。フォワードパスは、特定の時点までの観測系列を観測し、特定の状態で終了する確率を計算し、バックワードパスは、開始状態が与えられたときの系列の残りの部分を観測する確率を計算します。これら2つの確率の集合を組み合わせることで、所望の事後周辺分布が得られます。
数学的定式化
隠れ状態 \( S = \{s_1, s_2, \ldots, s_N\} \)、遷移確率 \( a_{ij} = P(s_j | s_i) \)、出力確率 \( b_j(o_t) = P(o_t | s_j) \)、初期状態分布 \( \pi_i = P(s_i) \) を持つHMMを考えます。観測系列 \( O = (o_1, o_2, \ldots, o_T) \) に対して、フォワード変数 \( \alpha_t(i) \) は、時間 \( t \) までの部分観測系列の確率と、時間 \( t \) における状態 \( s_i \) にある確率として定義されます。すなわち、\( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \) であり、ここで \( \lambda \) はモデルパラメータを表します。フォワードパスは \( \alpha_1(i) = \pi_i b_i(o_1) \) で初期化され、再帰的に \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \) を計算します。
バックワード変数 \( \beta_t(i) \) は、時間 \( t \) における状態が \( s_i \) であるという条件のもとで、時間 \( t+1 \) から \( T \) までの観測系列の確率として定義されます。すなわち、\( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \) です。バックワードパスはすべての \( i \) に対して \( \beta_T(i) = 1 \) で初期化され、再帰的に \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \) を計算します。時間 \( t \) における状態 \( s_i \) にある事後確率は、\( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \) で与えられます。
系列モデリングにおける応用
このアルゴリズムは、期待値最大化の一例であるバウム・ウェルチアルゴリズムによるHMMの訓練に広く使用されています。Eステップでは、フォワード・バックワードアルゴリズムが、状態間の遷移の期待数や各観測シンボルの出力の期待数などの期待十分統計量を計算します。これらの統計量はMステップでモデルパラメータを更新するために使用されます。この反復手順は、尤度関数の局所的最大値に収束します。
音声認識では、フォワード・バックワード訓練を用いたHMMが、1970年代から2000年代初頭まで音響モデリングの支配的なアプローチであり、その後、深層学習手法に大きく取って代わられました。バイオインフォマティクスでは、このアルゴリズムは遺伝子予測やタンパク質配列の解析に使用され、HMMが保存モチーフをモデル化します。自然言語処理では、品詞タグ付けや、構造化出力層を備えた系列から系列モデルの訓練に登場します。
現代の機械学習との関係
フォワード・バックワードアルゴリズムは古典的な手法ですが、その原理は現代の機械学習にも存続しています。フォワードパスはリカレントニューラルネットワークにおける情報の伝播に類似しており、バックワードパスは誤差信号の逆伝播に似ていますが、数学的な目的は異なります。系列ラベリングに使用されるニューラルネットワーク、例えば双方向LSTMでは、フォワードとバックワードの隠れ状態が組み合わされて両方向からの文脈を捉え、このアルゴリズムのフォワード変数とバックワード変数を反映しています。さらに、このアルゴリズムの動的計画法の効率的な使用は、トランスフォーマーベースのモデルにおける類似の手法に影響を与えており、例えば、ある種の構造化予測や、固有表現認識などのタスクにおける大規模言語モデルの訓練で使用されるフォワード・バックワードアルゴリズムがあります。
このアルゴリズムは、系列問題における計算複雑性を管理するという点でビームサーチの概念とも関連していますが、目的は異なります。ビームサーチは最も可能性の高い系列を近似するのに対し、フォワード・バックワードは正確な周辺確率を計算します。確率的グラフィカルモデルでは、フォワード・バックワードアルゴリズムはチェーングラフ上の和積アルゴリズムの特殊なケースであり、木構造モデルへの信念伝播によって一般化されます。
計算複雑性と変種
フォワード・バックワードアルゴリズムは、時間計算量 \( O(T N^2) \)、空間計算量 \( O(T N) \) で動作します。ここで、\( T \) は系列長、\( N \) は隠れ状態の数です。この効率性により、数百の状態を持つ数千の時間ステップの系列に対して実行可能です。大きな状態空間に対しては、フォワードフィルタリング・バックワードサンプリングアルゴリズムなどの近似が、粒子フィルタリングやモンテカルロ法で使用されます。オンライン設定では、フォワードアルゴリズム単独でフィルタリングに使用できますが、バックワードパスは系列全体を必要とするため、オフラインになります。変種には、長い系列と小さな確率を扱う際に一般的な数値アンダーフローを回避するためのスケーリングされたフォワード・バックワードアルゴリズムがあります。
関連項目
- hidden-markov-model
- ビタビアルゴリズム
- バウム・ウェルチアルゴリズム
- dynamic-programming
- sequence-modeling