隠れマルコフモデルの紹介
1. 序章
このチュートリアルでは、隠れマルコフモデル、または略してHMMについて説明します。 これは、かなり前から存在している統計モデルの一種です。 1960年代に文献に登場して以来、さまざまな科学分野でのアプリケーションを通じてバトルテストが行われ、今日まで多くのデータモデリングタスクに取り組むための広く好まれている方法です。
HMMは最初に音声認識に使用されましたが、それ以来、科学者は品詞タグ付け、時系列分析、遺伝子予測、輸送の最適化、およびその他の多くのシーケンス関連タスクにこのアプローチを使用してきました。 なぜHMMはそれほど用途が広く、効果的であるのか疑問に思われるかもしれません。
2. モデル
その答えは、モデルが基づいている確かな数学的原理と、それに伴う単純さの両方にあります。 すべての隠れマルコフモデルは、私たちが観察するイベントが、直接観察できないいくつかの内部要因または状態に依存するという仮定に依存しています。 この特性は非常に一般的であるため、非常に適用可能であり、名前の隠された部分の由来でもあります。
ただし、マルコフの部分は、上記の隠れた状態の経時変化をモデル化する方法に由来します。 マルコフ性を使用します。これは、観測値を生成するプロセスがメモリレスであるという強い仮定です。つまり、次の非表示状態は現在の非表示状態のみに依存します。これにより、数学的に作業しやすくなります。後で見るように。
2.1. 推測ゲーム
隠れマルコフモデルの特性をよりよく理解するために、古典的な例のプロセスから始めましょう。 アリスとボブという2人の親しい友人がいて、お互いに遠く離れて住んでいますが、毎日電話で話し、彼らが何をしたかについて話し合っていると考えてください。 彼らは、ボブがその日にやっていたと彼女に言ったことだけに基づいて、アリスが天気を推測しようとする推測ゲームをプレイすることにしました。
簡単にするために、ボブの動作がかなり制限されていると想像してみましょう。 彼は日中、公園を散歩したり、買い物に行ったり、アパートを掃除したりする3つのことのいずれかを行うことができます。 さらに、彼の行動は特定の日の天気に完全に依存します。 また、天気には「雨」または「晴れ」の2つの状態しかありません。
2.2. マルコフ性
そのような状況でも、推測するのは難しいですが、アリスがこの問題にどのように取り組むかについて推論することができます。 今日の天気は、昨日の天気によってのみ影響を受けるとしましょう。 これは、すでに述べたマルコフ性であり、隠れマルコフモデルを使用するときに行う重要な仮定です。 数学的には、天気が特定の時間に特定の状態になる確率は、時間ステップにのみ依存すると言えます。
これは、時間に関する簡単な図で示すこともできます。
2.3. マルコフ連鎖
アリスはボブの地域の天気を知っているので、彼女の知識を確率に変換することもできます。
昨日が晴れの場合、今日も晴れの可能性があり、雨が降る可能性があります。 同様に、昨日雨が降っていた場合、再び雨が降る可能性と晴れの可能性があります。 そして、シーケンスはどこかから開始する必要があるため、彼女は、雨の日から始まり、晴れた日から始まる可能性があると言います。 アリスのモデルは次のようになります。
この種のモデルはマルコフ連鎖とも呼ばれ、ある状態から別の状態に移行する確率は遷移確率と呼ばれます。一般に、これらの確率は遷移行列を使用して定義されます。 この例では、遷移行列は次のようになります。
別の状態への遷移がある場合に注意すべき重要なプロパティの1つは、現在の状態が与えられた場合のすべての遷移確率の合計が1である必要があることです。つまり、行列の行の合計が1になる必要があります。
そして、どこかから始めたので、初期確率を含む別の1次元ベクトルを定義します。
2.3. モデルの概要
要約すると、いくつかの隠れた状態があります。それらを、遷移確率行列、および初期確率ベクトルと呼びましょう。 ただし、ボブの活動も何らかの形で組み込む必要があります。 すでに述べたように、それらは天候に完全に依存するため、各州に条件付き確率を割り当てることができます。これは、排出確率とも呼ばれます。
たとえば、今日は晴れていることを考えると、ボブが散歩に出かけたり、買い物に行ったり、家を掃除したりする可能性があると言っても過言ではありません。 しかし、アリスは毎日彼と話しているので、彼女は彼の行動の一連の観察を集め、よりよく知っています。 彼女の観察に応じて、確率の1つの可能な組み合わせは次のようになります。
ここで、マトリックスの各行は非表示の状態を表し、各列はアクティビティを表します。
を含めた後、アリスに正しく推測するための最良の機会を与える隠れマルコフモデルを組み立てるために必要なすべてのものができました。 視覚的には、次の図が表示されます。
もちろんですが、アリスはそれをどのように使用して天気を推測しますか？ さて、彼女は次の質問に答える必要があります：与えられた観測のシーケンスを最もよく説明するモデルが与えられた場合、隠された状態のシーケンスは何ですか？ ただし、これに答えるのはそれほど簡単ではありません。
3. 評価問題
上記の質問をよりよく理解するために、最初にその逆に答えてみましょう。この特定のモデルが特定の一連の観測値を生成した確率はどれくらいですか？
数学表記も追加しましょう。 この例では、時間ステップ、つまりボブと話している日数について一連の観察結果があります。 また、パラメータの形式でモデルがあり、これを略してとして表すことができます。 したがって、「この特定のモデルが特定の一連の観測値を生成する確率はどれくらいですか？」という質問です。 次のように表すことができます。
これに答えるために、最初に、一連の観測を生成した特定の一連の隠れた状態を想像してみましょう。 たとえば、数日間の観測がある場合、考えられる隠れたシーケンスの1つはです。 与えられたこの観測シーケンスを見る確率はどれくらいですか？
時間に隠された状態が与えられた場合に、特定の観測値を見る確率を乗算するだけで済みます。
これは、シーケンス内の各隠れた状態の特定の放出確率を調べることで簡単に計算できます。 例では、これは次のようになります。
3.1. 処方
しかし、私たちは私たちに観察を与えた正確な順序を知りません。 しかし、最初に、この例のように特定の隠れた状態のシーケンスが発生する確率を答えましょう。 マルコフ性の下で動作しているため、各状態遷移は独立しており、次のように単純に乗算できます。
したがって、特定の隠れシーケンスと特定の観測シーケンスを取得する同時確率は次のようになります。
ただし、観測シーケンスを生成した可能性のある状態シーケンスのすべての可能な組み合わせを考慮する必要があります。 これを行うために、すべての可能な隠れ状態シーケンスのすべての同時確率と、それらが合計によって発生する確率を無視することができます。
ここで、はすべての可能な非表示状態シーケンスの数です。
これを計算することは問題にはなりませんが、実際のシナリオでは計算の複雑さが非常に高くなります。 非表示の状態の数が存在する場合、可能な状態シーケンスがあります。 シーケンスごとに、時間を乗算する必要があります。 そして最後に、操作のためにそれらをすべて合計する必要があります。
つまり、操作の合計またはBigO表記です。
3.2. フォワードアルゴリズム
しかし、すべてが失われるわけではありません。 この膨大な計算には、私たちが求めている結果を定式化する別の方法の使用を意味する冗長な製品がたくさんあります。 最も一般的なアプローチは、分割統治の原則に強く依存するフォワードバックワードアルゴリズムです。 名前が示すように、このアルゴリズムは前方と後方の2つの部分で構成されていますが、通常、最初の質問に答えるには1つだけで十分なので、最初に前方の部分を見てみましょう。
このアプローチの前半部分を採用するには、特定の時間における特定の隠れた状態の確率を、その前のタイムステップで表す必要があります。 これを帰納的に行うには、新しい集計変数を導入します。これにより、特定のポイントまでの一連の観測値が表示され、モデルが指定された状態になる確率が取得されます。
変数の基本ケースは次のようになります。
為に 。
そして、帰納的ステップについて、より一般的に説明します。
と。
上記の式が言っていることは、状態までの一連の観測を見て、状態に到達する確率は、観測シーケンス（）に実際に遷移する確率を掛けた場合に状態に到達するすべての異なる方法の合計に等しいということです（）に移動し、現在（）の状態にあることを前提として、次の観測も観測します。
方程式を見る別の方法は、図を使用することです
さらに説明する必要があるのは、最後のタイムステップでは、遷移する必要がなくなったため、すべてのアルファを合計できることだけです。
全体として、アルゴリズムは、単純な計算と比較して、計算に対して大幅に高速に動作します。 すべてのタイムステップで、次のすべての状態の計算で以前のすべての状態を考慮しているため、計算の複雑さが大幅に改善されています。
3.3. 後方アルゴリズム
ただし、Forward-Backwardアルゴリズムのさらに興味深い点は、名前が示すように、逆に機能することです。すべての観測値があるので、同じロジックを逆方向に適用できます。 特定の時点までの観測を見て状態にある確率のパラメーターを定義する代わりに、どの観測が先にあるかを知っているときに状態にある確率を記述する新しい再帰パラメーターを定義できます。
基本ケースを定式化するために、観察の終わりから始めます。 以下に他の観測値がないため、次のように定義します。
そしてそれは私たちのすべての州のためです。
そして、帰納的に、他のすべてを次のように定義できます。
この方程式でも、状態間のすべての可能な状態遷移を考慮していますが、前方への遷移を考慮する代わりに、後方を振り返り、前の遷移ではなく後の遷移で説明しています。
違いを強調するための図を次に示します。
4. デコードの問題
これで、元の質問「与えられた観測のシーケンスを最もよく説明するモデルが与えられた場合の隠れた状態のシーケンスは何ですか？」に答える準備ができました。
これを行う1つの方法は、前のセクションの知識を使用して、モデルが隠れた状態のすべての可能なシーケンスに対して見た観測値を生成する確率を計算し、結果として最大の値を持つ1つのシーケンスを見つけることです。 ただし、前のセクションと同様に、ブルートフォースで計算することは不可能であることがわかります。
私たちにできることは、Forward-Backwardアルゴリズムからインスピレーションを得ようとすることです。 そのアルゴリズムの両方のバージョンで、スマートな再帰的な方法で状態の各非表示シーケンスを合計しています。 同様のことをしてみませんが、合計演算子を使用する代わりに、それを使用してください。 結果として得られるアプローチは、ビタビアルゴリズムと呼ばれます。
前と同じように、現在のタイムステップまでの最も可能性の高いパスを含み、状態で終わる再帰変数を定義できます。基本ケースは、最初のタイムステップから始まり、次のようになります。
ここで異なるのは、パスを再作成するために、各タイムステップでどこから来たかをメモする必要があることだけです。 この目的のために、現在の状態にある場合に、どの状態から来たかを示す変数を定義します。
基本ケースでは、状態を追跡する必要がないため、単純にゼロになります。
ご想像のとおり、新しいパラメータを拡張するための基本的な帰納的ステップは、フォワードバックワードアルゴリズムのステップと同様です。
これは本質的に、訪問した状態を追跡しながら、状態に移行して観測値を取得するためのタイムステップまでの最も可能性の高いパスを示すことを意味します。
視覚的に説明するために、推測ゲームの例を取り上げ、次のような観測の例をいくつか挙げて、隠れた状態の最も可能性の高いパスを示す図を描くことができます。
5. 結論
この記事では、マルコフプロパティとマルコフ連鎖の概念を紹介する架空の例から始めて、隠れマルコフモデルについて説明しました。 次に、これらは、観測されたアクションのみに基づいて天気をモデル化するように設計されたHMM内の場所を見つけました。 その結果、実際に正しい確率を割り当てることを追求して、Forward-Backwardアルゴリズムを検討し、最終的には、準備ができたHMMモデルを完全に利用するのに役立つ類似しているが重要なViterbiアルゴリズムになりました。
