2017年5月22日

マルコフモデル～概要から原理まで～（前編）

本記事は、元記事を翻訳した記事の前編となります。
B/C/D節については後編をご参照ください。

“マルコフモデルとは何か” という議論は昔からありますが、もし皆さんがその答えを知りたいのであれば、正直なところ、ウィキペディアを見る（または以下のTLDRだけを読む😉）ことをお勧めします。一方、マルコフモデルの概要やこのモデルが重要である理由、およびその実装方法に興味があり、サンプルを通じて理解を深めたいという方は、この記事を引き続きご覧ください(^ ^)。以下で、具体例を挙げて説明します。

TLDR：確率論において、マルコフモデルは不規則に変化するシステムをモデル化するための確率モデルである。なお、未来の状態は現在の状態のみに左右され、過去に起きた事象には影響されないと仮定する（つまり、マルコフ性を仮定する）。
引用元：https://en.wikipedia.org/wiki/Markov_model

ロードマップはとても重要です。この記事のロードマップにあたる目次は、以下の通りです。🚗

マルコフモデルの概要（☝️ 🐠 ✌️ 🐠 ⭕️ 🐠 🌀 🐠）

1.最初の文

マルコフモデルは、例を使って説明するのが一番分かりやすいでしょう。ここで取り上げる以下の例は、私自身がMake Schoolでマルコフモデルを学んだ際に使ったものです。

One fish two fish red fish blue fish.
ドクター・スース 🎩

2.重み分布

マルコフモデルを学ぶ前に、まずは指定の最初の文と重み分布、およびヒストグラムについて十分に理解しておく必要があります。

最初の文

この最初の文は有名なフレーズですが、一見したところ特に目を引く要素はありません。では、この文を分解して、構成要素について見ていきましょう。具体的には、この文は8単語（トークン）から成ります。ただし、一意の単語（キー）は5つだけです。

色付けした最初の文

ここでは一意の単語（キ―）に異なる色を割り当てました。一見すると、ただの色付けした文にしか見えませんが、実は各キーに別の色を付けたのには意味があります。一意のキーを色分けすることで、特定のキーが他のものより多く出現していることが分かるのです。

キーの分布

上のキーの分布を見ると、fishというキーが他のキーよりも4倍多く出現していると推測できます。このことから、最初の文において任意の位置で次の単語をランダムに抽出した場合、「fish」が得られる確率が高いと予測することもできます。他の単語に比べて、fishは非常に多く使用されているためです。💯

今回の重み分布の場合、任意のキーが出現する確率は、そのキーが出現する合計回数をトークンの総数で割ったものになります。例えば、fishは8単語中4回出てきているので、重み分布は50％です。また、One、two、red、blueの出現確率はそれぞれ12.5％(1/8)になります。

ヒストグラムは、重み分布を表現するための手法です。通常は、一連の計量値の度数分布を認識できるように描画したものです。この例では、多数の単語（計量値）から成る文が連続データということになります。

最初の文のヒストグラム

この最初の文のヒストグラムを見ると、これらの単語の基本的な分布を視覚的に👀かつ明確に把握できます。実際、データセットの中でfishが最も多く出現していることが一目で分かると思います🐠🐟 🐡🐠

3.特別な付加要素

やりましたね！　今では、文が多くのトークンとキーで出来ているという概念を受け入れたことと思います。さらに、ヒストグラムと重み分布の関係も理解しているでしょう。

✅💯✅ 補足の例 ✅💯✅

トークンというのは、文中の単語のことです。
キーというのは、個々の単語の出現を指します。
例： “Fish Fish Fish Fish Cat”には2個のキーと5個のトークンがあります。キーは “Fish” と “Cat” (🐠 と 😺)です。また単語1つ1つがトークンです。
ヒストグラムは重み分布に関連付けられます。なぜなら、ヒストグラムを見ると、連続データセットにおける頻度が視覚的に分かり、それは基本的にデータの重み分布を示しているからです。

✅💯✅ 補足終わり ✅💯✅

いいことです。これで文の外観と、ある単語が別の単語と比べてどのように多く出現するかを理解しました。しかし、先に進む前に、表面上で隠れているものの誰もが存在を認める特別な付加要素を文に追加しなければなりません。文のＳｔａｒｔとＥｎｄです…。

特別な付加事項が付いた最初の文

すてきです！　ちょっと時間を取って、元々の文に対する上の “付加要素” を調べましょう。今、これは不要な作業に見えます。しかし信じてほしいのですが、次のパート、つまりマルコフモデルに踏み込んだ際に、急に意味を持ち始めます。😌 要約すると、全ての文は隠れた “START” という目印で開始され、常に “END” という目印で締めくくられます。

変更した例におけるキーの分布

上記では、先へ進めて、前の例に2つの追加キー（STARTとEND）を加えて、前と同様にキーの分布を再構成しました。

4.マルコフモデルはどのように動くか

すごいですよ！　すでに何かしら学んでいるかもしれませんが、ついに本記事の核心に来ました。まず、マルコフモデルとは何かについて難しい定義から始めましょう（ウィキペディアによるものです。）

マルコフモデルとは不規則に変化するシステムに対して用いられる確率モデルで、未来の状態は現在の状態のみに左右され、過去に起きた事象には影響されないと仮定する（つまり、マルコフ性を仮定する）。一般的にこの仮定によって、他のアルゴリズムでは扱えないモデルに論拠と計算結果を与えることができる。
ウィキペディア

すごいですね！　面白そうです…　しかし、この大げさでつかみどころのないものは、一体何を意味しているのでしょうか？　マルコフモデルとは何かについて重要なところを太字にしておきました。要約すると、マルコフモデルとは、次の状態が現在の状態のみに基づくとするモデルです。

このことについて1つの考え方を挙げると、現在の状態（この文章の場合は1つのトークン）だけが見えるウィンドウがあり、この小さなウィンドウに基づいて次のトークンを決めなければならないというものです！

ウィンドウを使った次の単語の指示

上の図で、トークンからトークンへのつながりを示しました。さらに、元のキーごとに色分けし、次の単語へ向かう矢印に色を付けています。この図と下の図に少しばかり時間を費やすことをお勧めします。というのも、これによってマルコフモデルがどのように動くかの基礎が築かれるからです。

ペア登場。あるトークンから別のトークンへ！

どのトークンも別のトークンにつながることにお気づきでしょう（ENDでさえも、noneという別のトークンにつながります）。この場合、あるトークンと別のトークンのペアが出来上がるのです！

最初の単語に基づいた構成

上記では、最初のトークンによってペアをまとめました。もう、面白いことにお気づきかもしれません。先行するトークンは、自らがつなげられるキーだけからつながりを受けています。

各キーがつなげられるトークン

さて、ここまでの話は大丈夫でしょうか。 “ウィンドウ” によって形成されるペアを構成し、ペアになる次のトークンは何かを調べているということを理解していただけているでしょう。そのあと、ペアをさらに興味深いものへと軽量化しました。全てのキーはそのキーに続く可能性があるトークンの配列と照合されます。

✨💡✨ 小休止して考察 ✨💡✨

上に示した図について、ちょっと考察してみましょう。全てのキーは、それに続けることができるだろう単語を持っています。誰かが上記の構造を与えられた場合、もしかしたら元の文を再現できるかもしれません。

例：

最初に＊Start＊を与えます。それから、START → [One]に従うであろう単語の選択肢を見てみます。それは、次に選択しなければならない唯一のキーになります。今、この文では”One”ということになるようです。それでは”One” → [fish]に従うであろう単語を見て、先へ進んでみましょう。今度も同じ、これは簡単ですね。Oneに続けられるのは”fish”だけです。ということで、文は、”One fish”となります。それでは、”fish” → [two, red, blue, END]に従うであろうものを見ていきましょう。ここで、面白くなってきました。4つの選択肢の中から、どれでも次のものとして選ぶことができます。😳 つまり、”two”を選び先に進むことができたとすれば、もしかすると、元々の文が得られるかもしれません。しかし無作為に”END“を選ぶであろう確率は25%(1/4)です。この場合は、元の構造を使ったとしても、元の”One fish” 1️⃣ 🐠 とはかなり違った文を無作為に生成するでしょう。
✨💡✨ 考察終わり ✨💡✨

おめでとうございます🎉🎉。上で述べた小休止して考察の中でマルコフモデルをまさにひそかに実行していたのです。😏
素晴らしいです。しかし真面目な話、そのことについて考えてみてください。私たちは、次の状態を決定するために、現在の状態（現在のキー）を使いました。更に次の状態は、現在のキーに従うキーだけなのかもしれません。なかなかよさそうですが、さらに良くなっていきます。最初の文について、マルコフモデルを図に表してみましょう。

最初の文のマルコフモデル

さて、上の図は、私たちが実行したことをどのように表しているのでしょうか。詳しく見てください。単語が中に書かれた楕円はキーを表しており、その単語に続く可能性があるキーを示す矢印が描かれています。でもちょっと待ってください、もっとカッコよくなります。

確率を伴った最初の文のマルコフモデル

そうです。矢印はどれも、現在の状態から次の状態へと続くパスとして選ばれる確率を伴っています。

マルコフモデルを用いて作成された、最初の文の完全図

すごいですね。要するに、ドクター・スースの文を用いることにより、マルコフモデルを図解しました。面白い事実として、モデルを作るために使用したデータは、コーパスと呼ばれます。👻

5.まとめ

やりましたね。改めておめでとうございます。この時点で、あなたはマルコフモデルが何であるかを述べることができるでしょう。そして、この基本例と同じものを使って、恐らく他の誰かに教える事さえできるでしょう。順調に進んでいます。🚀 でも想像してみてください。これは、マルコフモデルへの理解をさらに深めようとする次のセクションに向けての単なる出発点に過ぎません。分布を覚えているでしょうか。そうですね、次の例で分布を使うつもりです。これは、潜在的にもっと実際的なモデルを作成するため、重み分布をどのように使うかを示すためです。更に、より大きなウィンドウについて話そうと思います😲（大きな方が良いですよね🙄）。そして、最後に、Python🐍でよくできたマルコフモデルを実装しましょう。そして気を引き締めて楽しみながら先に進みましょう。🔥🎢