隠れマルコフモデル

隠れマルコフモデル（かくれマルコフモデル、英語: Hidden Markov Model）は確率モデルのひとつであり、観測されない（隠れた）状態をもつマルコフ過程である。

概要

同じマルコフ過程でも、隠れマルコフモデルより単純なマルコフ連鎖では、状態は直接観測可能であり、そのため、状態の遷移確率のみがパラメータである。一方、隠れマルコフモデルにおいては、状態は直接観測されず、出力（事象）のみが観測される。ただしこの出力は、モデルの状態による確率分布である。従って、ある隠れマルコフモデルによって生成された出力の系列は、内部の状態の系列に関する何らかの情報を与えるものとなる。「隠れ」という語はモデルが遷移した状態系列が外部から直接観測されないことを指しており、モデルのパラメータについてのものではない。たとえパラメータが既知であっても隠れマルコフモデルと呼ばれる。隠れマルコフモデルはごく単純な動的ベイジアンネットワークとして表現することができる。

隠れマルコフモデルは、潜在変数（hidden variable, latent variable）が各々独立ではなく、マルコフ過程を通じて関連付けられている混合分布モデル(Mixture Model)を拡張したものとみなすことができる。この潜在変数は、それぞれの観測に対して選択されるように混合要素を制御するものである。近年、隠れマルコフモデルは、より複雑なデータ構造と非定常的なデータの取り扱いが可能なpairwise Markov modelsやtriplet Markov modelsに一般化されている。

隠れマルコフモデルに関する数学的概念はL. E. Baumと彼の同僚らによって開発された。これは、最初にフォワードバックワードアルゴリズムを発表したR. L. Stratonovichによる非線形フィルタリング問題の最適化についての初期の成果に関連している。

隠れマルコフモデルは、音声認識、バイオインフォマティクス、形態素解析（自然言語処理）、楽譜追跡、部分放電など、時系列パターンの認識に応用されている。連続的かつ伸縮しうる信号列のパターン抽出には適しているが、反面、長い距離をはさんで呼応しているような信号列からのパターン認識には、間の距離の長さに応じて状態数を増やす必要があり、計算量の観点から実用的ではない。また、局所最適に陥りやすいため、対象に応じて適切なパラメータの初期値を設定してやる（適切なモデルトポロジーを導入する）必要がある。

構成

ファイル:Hmm temporal bayesian net.svg

図1. 隠れマルコフモデルの一般的な構成

ファイル:HiddenMarkovModel.svg

図2. 隠れマルコフモデルのパラメータ（例）
[math]x[/math]: 潜在変数の状態
[math]y[/math]: 可能な観測値
[math]a[/math]: 状態遷移確率
[math]b[/math]: 出力確率

図1は、隠れマルコフモデルの一般的な構成を示している。確率変数 [math]x(t)[/math] は、時刻 [math]t[/math] における潜在変数である。確率変数 [math]y(t)[/math] は時刻 [math]t[/math] における観測値である。矢印は、条件付き確率間の依存関係を表している。

図2は潜在変数の状態数が3 ([math]x(t)\in\left\{x_1, x_2, x_3\right\}[/math]）、観測値の状態数が4（[math]y(t)\in\{y_1, y_2, y_3, y_4\}[/math]）の隠れマルコフモデルを示している。

時刻 [math]t[/math] における潜在変数 [math]x(t)[/math] の条件付き確率分布は、潜在変数 [math]x(t-1)[/math] にのみ依存する。[math]x(t-2)[/math] およびそれ以前の状態は影響しない。これを（単純）マルコフ性という。また、観測値 [math]y(t)[/math] は [math]x(t)[/math] にのみ依存する（時刻 [math]t[/math] が同じであることに注意）。ここで考えるような標準的な隠れマルコフモデルでは、潜在変数 [math]x(t)[/math] は離散的であり、観測値 [math]y(t)[/math] は連続的でも離散的でもよい。

隠れマルコフモデルのパラメータは、遷移確率と出力確率の2種類である。遷移確率は、時刻 [math]t-1[/math] での潜在変数から時刻 [math]t[/math] での潜在変数への状態遷移を表す。図2において、遷移確率は [math]a_{ij}[/math] で、出力確率は [math]b_{ij}[/math] で示されている。

潜在変数の状態空間は [math]N[/math] 個の値をとる離散分布である（図2では[math]N=3[/math]）。これは、時刻 [math]t[/math] において潜在変数がとりうる [math]N[/math] 個の値のそれぞれに対して、時刻 [math]x(t+1)[/math] での潜在変数がとりうる [math]N[/math] 個の値への遷移確率が存在することを意味する。結果的に、全体で [math]N^2[/math] の遷移確率がある（図2ではそのうち[math]a_{12}, a_{21}, a_{23}[/math]のみを示している）。この [math]N\times N[/math] 行列をマルコフ行列という。確率の公理より、ある特定の状態から他の状態への遷移確率の和は1である。そのため、特定の状態からのある遷移確率はそれ以外の確率がわかれば決まるので、[math]N\times (N-1)[/math] 個の遷移パラメータがあることになる。

これに加えて、[math]N[/math]個の状態のそれぞれに、潜在変数の特定の時刻において観測値の分布を支配する出力確率の組がある（図2では[math]M=4[/math]で、[math]3\times 4[/math]の出力確率[math] b_{ij}[/math]がある）。たとえば、観測値が離散分布で[math]M[/math]個の値をとるとき、個々の潜在変数に[math]M-1[/math]個のパラメータがあるから、全体で[math]N\times (M-1)[/math]個の出力パラメータがある。あるいは、観測値が任意の混合ガウス分布に従う[math]M[/math]次元ベクトルであれば、平均値のために[math]M[/math]個と、共分散行列に[math]M(M+1)/2[/math]個のパラメータがあるから、合わせて[math]N(M + M(M+1)/2) = NM(M+3)/2 = O(NM^2)[/math]の出力パラメータがある。

実際には、[math]M[/math]が小さくない限り、観測ベクトルの個々の要素間の共分散の特性に制約を設けることが現実的である。たとえば要素ごとに独立であるとか、もう少し制約を緩めて、隣接するいくつかの要素以外は独立であるなどとすることが考えられる。

推測

隠れマルコフモデルに関して、以下に示すようないくつかの統計的推測問題がある。

観測値系列の確率

ファイル:HMMsequence.svg

図3. 隠れマルコフモデルの状態遷移と出力確率
点線の下にある出力系列が観測されたとき、これがどのような状態系列によって得られたものかを考えると、図に示された状態遷移と出力確率の矢印から、次の状態系列が候補となる。
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
それぞれの候補について、状態系列と観測系列の同時確率を求めることによって、最もありそうな（つまり最尤の）状態系列を求めることができる。一般にこのような最尤観測系列の問題はビタビアルゴリズムで効率的に解くことができる。

モデルのパラメータが既知のとき、特定の出力系列が得られる確率を求める。これは、可能な状態系列についての確率の総和によって得られる。

長さ [math]L[/math] の観測値系列

[math]Y=y(0), y(1),\dots,y(L-1)[/math]

の確率は、潜在状態系列

[math]X=x(0), x(1), \dots, x(L-1)[/math]

の確率の総和を用いて次のように与えられる。

[math]P(Y)=\sum_{X}P(Y\mid X)P(X)[/math]

動的計画法の原理を適用すると、この問題は前向きアルゴリズムで効率的に扱うことができる。

潜在変数の確率

モデルパラメータと観測系列が与えられたとき、ひとつあるいはそれ以上の潜在変数の確率を求める以下のような問題がある。

フィルタリング

この問題は、モデルパラメータと観測系列が与えられたとき、系列の最後における潜在変数の状態の確率分布、つまり [math]P(x(t)\ |\ y(1),\dots,y(t))[/math] を求めるものである。この問題は、一般に、潜在変数の系列があるプロセスの背後の状態で、そのプロセスは各時刻の観測値に関してある過程が時刻の系列に従って遷移するものと考えられる場合に用いられる。従って、最後の時点でのプロセスの状態を知ることが自然である。この問題は、フォワードアルゴリズムで効率的に解くことができる。

平滑化

フィルタリングが系列の最後の状態を求めるのに対して、平滑化 (smoothing) は系列の途中のどこかの時点での潜在変数の確率分布、つまり ある時刻 [math]k \lt t[/math] における [math]P(x(k)\ |\ y(1), \dots, y(t))[/math]を求めるものである。これはフォワードバックワードアルゴリズムで効率的に解くことができる。

最尤系列推定

この問題は、前の2つの問題と異なり、特定の観測値系列を生成する潜在変数の系列全体の同時確率を求めるものである。これは一般に、隠れマルコフモデルをフィルタリングや平滑化とは異なる種類の問題に適用する場合に用いられる。

例えば自然言語処理の構文解析における品詞タグ付けは、単語の並びから品詞を推定するものである。品詞を隠れマルコフモデルの潜在変数とし、ある品詞から他の品詞につながる確率を品詞付与コーパスなどから遷移確率として求めておく。また、各状態（品詞）から具体的な単語が出力されると考え、その出現確率もコーパスから求めておく。分析したい単語の並びが観測系列となる。品詞タグ付けは、与えられた単語列から隠れた状態としての品詞列を最尤推定するが、このとき関心があるのは全体の品詞の系列であり、フィルタリングや平滑化が扱うような単一の語の品詞を求めることではない。

この問題は、可能な状態系列の確率の最大値を求めるものであり、ビタビアルゴリズムによって効率的に解くことができる。

統計的有意性

上記のいくつかの問題に対して、統計的有意性を知りたい場合がある。帰無仮説が真となる分布から得られた系列が、どのような状態系列の確率をもつか（フォワードアルゴリズムの場合）あるいは状態系列の確率の最大値（ビタビアルゴリズムの場合）で少なくとも特定の出力系列と同じくらい大きなものは何かというようなものである。 隠れマルコフモデルで、特定の出力系列に関する仮説の統計的適切性を評価する場合、その統計的有意性は、出力系列に対して間違って仮説を棄却してしまう擬陽性率 (false positive rate) を示す。

具体例

図3. Graphical representation of the given HMM

遠くに住んでいる友人のアリスとボブがいて、電話で毎日お互い自分のしたことを話している。ボブは「公園での散歩 (walk)」、「買い物 (shop)」、「部屋の掃除 (clean)」の3つのことにしか関心がない。何をするかは、その日の天気によってのみ決めている。アリスはボブが住んでいる地域の日々の天気については具体的に知らないが、一般的な天候の変化については知っている。ボブが毎日話すことにもとづいて、アリスは天気がどのようになっているかを推測しようとする。

アリスは、天気が離散マルコフ過程として変化すると考える。天気には「雨 (Rainy)」と「晴れ (Sunny)」の2つの状態があるが、アリスはそれを直接知ることができないから「隠れ」た状態である。毎日、ボブは天気に応じて「散歩」、「買い物」「掃除」のどれかひとつだけを必ずする。ボブがそれをアリスに話すことが、アリスにとっての観測（ボブからの出力）である。この状況全体が隠れマルコフモデルとなる。

アリスは、ボブのいる地域の一般的な天候の変化（遷移確率）については知っている。また、どの天気のときにボブがどの行動をするか（出力確率）を知っている。つまり隠れマルコフモデルのパラメータが既知である。これは、Pythonで次のように表される。

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
   'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
   'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
   }
 
emission_probability = {
   'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
   'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
   }

このコードでstart_probability は、ボブが最初に電話する前の時点で、隠れマルコフモデルがどちらの状態にあるかというアリスの考えである（彼女は平均的には雨の方がやや多いと知っている）。この確率分布は平衡なものではない（遷移確率によれば平衡は {'Rainy': 0.57, 'Sunny': 0.43}）。遷移確率 transition_probability はマルコフ連鎖での天気の変化を表す。この例では、今日が雨であれば、明日晴れる確率は30%である。出力確率 emission_probability は、その日にボブが行う行動の確率である。もし雨であれば掃除をする確率は50%で、晴れていれば散歩に行く確率は60%である。

ビタビアルゴリズム

"「ビタビアルゴリズム」"

ビタビアルゴリズム（Viterbi algorithm）は、モデルパラメータが既知のとき、与えられた配列を出力した可能性（尤度）が最も高い状態列（最尤状態列）を計算するアルゴリズムで、動的計画法の一種である。ある時点 t での最尤状態遷移列はtまでに観測された情報と、t-1 までで最も確からしい（＝尤もらしい）最尤状態遷移列だけに依存すると仮定する。

例えば、出力 'A' と 'B' を確率0.5ずつで出力し、他の状態にまれにしか遷移しない状態 A と、出力 'A' と 'C' を確率0.5ずつで出力し、他の状態にまれにしか遷移しない状態Bがあった場合、時点 t で 'A' が出力され、時点 t-1 で最尤だと推定された状態遷移列からの遷移確率が状態 A の方が高いならば、時点 t では状態 A にいたと推定される。しかし、t+1 以降で 'C' の出力が続いた場合、全体としての尤度は状態 B に遷移していたほうが高くなる。

ビタビアルゴリズムを使用するには、観測可能なイベントは観測不可能な状態遷移と1対1対応していることが求められる。

バウム・ウェルチアルゴリズム

"「バウム＝ウェルチアルゴリズム」"

バウム・ウェルチアルゴリズム（Baum-Welch algorithm）は、モデルが出力した系列からモデルパラメータを推定するアルゴリズムである。前向きアルゴリズム、後ろ向きアルゴリズム、EMアルゴリズムから構成される。前向きアルゴリズムおよび後ろ向きアルゴリズムは動的計画法の一種であり、ある時点で各状態にいる確率を求めるアルゴリズムである。