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

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

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

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

目次

A. マルコフモデルの概要???? 訳注:前編

1. 最初の文
2. 重み分布
3. 特別な付加要素
4. マルコフモデルは どのように 動くか
5. 完全な例のまとめ

B. もう一歩進んだマルコフモデル???? 訳注:後編

1. スケールアップした例
2. 分布
3. さらに大きなウィンドウ

C. Pythonでの実装???? 訳注:後編

1. Dictogramデータ構造
2. ハッシュテーブルのデータ構造
3. マルコフモデル構造
4. マルコフモデルの解析

D. 参考資料、提案と考察???? 訳注:後編

1. 応用
2. 参考資料
3. まとめ

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

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????でよくできたマルコフモデルを実装しましょう。そして気を引き締めて楽しみながら先に進みましょう。????????