バウム＝ウェルチアルゴリズムは、期待値最大化（EM）アルゴリズムの特殊ケースであり、隠れマルコフモデル（HMM）の未知パラメータを求めるために使用される。これはHMMにおける推論の主要な手法であり、期待値ステップの統計量を計算するために前向き後向きアルゴリズムを利用する。このアルゴリズムは、レオナルド・E・バウムとロイド・R・ウェルチにちなんで名付けられており、彼らは1960年代後半から1970年代初頭にかけて、プリンストンのIDAコミュニケーションズリサーチセンターで同僚とともに開発した。
隠れマルコフモデルは、隠れた離散確率変数と観測された離散確率変数の集合の同時確率を記述する。これは、i番目の隠れ変数が(i-1)番目の隠れ変数が与えられたとき、それ以前の隠れ変数から独立であり、現在の観測変数は現在の隠れ状態にのみ依存するという仮定に基づいている。バウム＝ウェルチアルゴリズムは、観測された特徴ベクトルの集合が与えられたとき、EMアルゴリズムを用いてHMMのパラメータの最尤推定を見つける。
正式な記述
\(X_t\)を\(N\)個の可能な値を持つ離散的な隠れ確率変数とし、合計\(N\)個の状態を表すものとする。遷移確率は時間に依存しないと仮定され、確率的遷移行列\(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\)の定義につながる。初期状態分布は\(\pi_i = P(X_1 = i)\)で与えられる。
観測変数\(Y_t\)は\(K\)個の可能な値のうちの1つを取ることができる。時刻\(t\)における状態\(X_t = j\)での特定の観測\(y_i\)の確率は、\(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\)で与えられる。これにより、\(N \times K\)行列\(B = \{b_j(y_i)\}\)が得られる。観測系列は\(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\)で与えられる。したがって、隠れマルコフ連鎖は\(\theta = (A, B, \pi)\)で記述できる。バウム＝ウェルチアルゴリズムは、\(\theta^* = \arg\max_\theta P(Y \mid \theta)\)の局所最大値を見つける。
アルゴリズムの手順
このアルゴリズムは、パラメータ推定を反復的に洗練させる。期待値ステップでは、前向き確率\(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\)と後向き確率\(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\)を前向き後向きアルゴリズムを用いて計算する。これらは、時刻\(t\)で状態\(i\)にいる確率や、時刻\(t\)と\(t+1\)の間で状態\(i\)から状態\(j\)へ遷移する確率などの期待十分統計量を計算するために使用される。
最大化ステップでは、アルゴリズムは期待対数尤度を最大化するためにパラメータ\(A\)、\(B\)、および\(\pi\)を更新する。更新された遷移確率は、状態\(i\)から状態\(j\)への遷移の期待回数と、状態\(i\)にいる期待回数の比として計算される。同様に、出力確率は各状態における観測の期待回数に基づいて更新される。初期状態分布は、時刻1で各状態にいる期待確率に基づいて更新される。
アルゴリズムは収束するまで反復を続け、通常は対数尤度の変化が閾値を下回ったときに終了する。これは尤度関数の局所最大値に収束することが保証されているが、必ずしも大域的最大値ではない。
数値的安定性
バウム＝ウェルチアルゴリズムは、同時確率の再帰的計算により数値的に不安定である。変数の数が増えるにつれて、これらの同時確率はますます小さくなり、前向き再帰が機械精度以下の値に急速に近づくことがある。これは、特に長い観測系列の場合、実際の実装でアンダーフローを引き起こす可能性がある。これを軽減するために、実装では各時間ステップで前向き変数と後向き変数を正規化するスケーリング手法や、対数領域で計算する手法がしばしば用いられる。
応用
HMMの最初の主要な応用の1つは、音声処理の分野であった。1980年代には、HMMは生物学的システム、特に遺伝情報の分析において有用なツールとして登場した。それ以来、ゲノム配列の確率的モデリングにおける重要なツールとなっている。バウム＝ウェルチアルゴリズムは、自然言語処理、例えば品詞タグ付けや固有表現認識、また計算生物学における遺伝子発見やタンパク質構造予測にも使用されている。
関連概念
バウム＝ウェルチアルゴリズムは、機械学習における他のパラメータ推定手法と密接に関連している。これは、潜在変数モデルに広く使用される期待値最大化アルゴリズムの特定のインスタンスである。主要な構成要素である前向き後向きアルゴリズムは、デコーディングのためのビタビアルゴリズムなど、他のHMM推論タスクでも使用される。現代の深層学習では、潜在変数を持つモデルの訓練において同様の原理が現れるが、ニューラルネットワークはEMの代わりにAdamオプティマイザやSGDの変種のような勾配ベースの手法をしばしば使用する。このアルゴリズムの機械学習と人工知能への関連は基礎的であり、系列データから学習するための初期の枠組みを提供した。