マルコフ連鎖」という言葉を聞いたことがあるかもしれませんが、確率論やコンピュータサイエンスのアルゴリズムの授業を何度か受けたことがない限り、それが何であり、どのように機能し、なぜそれほど重要なのか、おそらくご存じないことでしょう。

マルコフ連鎖の概念は「隠れた」ものであり、その恩恵を受けるためには、それが何であるかを知る必要はない、ということです。しかし、その仕組みを知っておくと、必ず役に立ちます。シンプルですが、いろいろと便利なんです。

そこで、マルコフ連鎖について知っておくべきことを、わかりやすく1つの記事に凝縮してご紹介します。もっと深く知りたい方は、カーンアカデミーの無料の「情報理論」コースを試してみてください（他のオンラインコースサイトも検討してみてください）。

マルコフ連鎖 101

例えば、明日の天気を予想したいとします。本当の予報、つまり専門の気象予報士が出すような予報は、何百、何千という様々な変数が常に変化しているものである。気象システムは非常に複雑で、少なくとも私やあなたのような素人にはモデル化することはできません。しかし、確率的な推定で問題を単純化することができます。

30年分の気象データがあるとします。最初から始めて、1日目が晴れていることに気づきます。続けて、2日目も晴れ、3日目は曇り、そして4日目は雨、5日目は雷雨、6日目は晴れ間が広がっていることに気がつきます。

理想はもっと洗練されて、1日ごとではなく1時間ごとの分析を選ぶことですが、これはコンセプトを説明するための単なる例ですので、ご容赦ください。

これを30年間のデータセット全体（ちょうど11,000日になる）で行い、今日の天気から明日の天気の確率を計算するのです。例えば、今日が晴れなら、です。

• 明日も50パーセントの確率で晴れるそうです。
• 明日は30％の確率で曇り。
• 明日は20％の確率で雨が降るそうです。

今度はこのステップを、起こりうるすべての天候について繰り返す。今日が曇りの場合、明日、晴れ、雨、霧、雷、あられ、竜巻などが発生する確率はどのくらいでしょうか？やがて、明日の天気だけでなく、翌日や翌々日の天気も予測できる完全な確率体系ができあがります。

過渡期の国々

これがマルコフ連鎖の本質である。状態（この場合は天候）が分かれていて、それぞれの状態は他の状態に変換でき（例えば、晴れの日は曇りに変換できる）、これらの変換は確率に基づいて行われます。1週間後の天気を予測したい場合、7日後のさまざまな可能性を見て、どれが一番可能性が高いかを判断することができるのです。したがって、マルコフ「連鎖」である。

マルコフとは何者か？彼はロシアの数学者で、ある国が他の国に直接つながるということを、他の要素が影響しない一定の確率に基づいて考え出した人です。基本的にはマルコフ連鎖を発明したのが名前の由来です。

マルコフ連鎖の実世界への応用

これらの説明を踏まえた上で、実際の応用例を探ってみましょう。知らず知らずのうちにマルコフ連鎖を活用していたことに驚くかもしれませんよ。

名前世代

テーブルトップゲームやMMORPG、あるいは小説の執筆に携わったことはありますか？あなたはおそらく、キャラクターの名前付けに苦労していることでしょう（少なくともある程度は）。そして、気に入った名前がなかなか思いつかないとき、オンラインの名前ジェネレーターに頼るかもしれません。

名前ジェネレーターがどのように機能するか、不思議に思ったことはありませんか？その多くがマルコフ連鎖を利用していることがわかり、最もよく使われるソリューションの一つとなっています。(もちろん、同じように機能する他のアルゴリズムもあります!)

必要なのは、それぞれにフォローアップの候補となるレターのリストがあるコレクションだけです。例えば、"M "が "a "を指す確率は60％、"I "を指す確率は40％であるとする。これを他の文字についても行い、アルゴリズムを実行します。バン、君の名は、意味があるんだ!(たいていの場合、とにかく)

Googleページランク

マルコフ連鎖理論の興味深い点は、連鎖の長さが長くなる（状態遷移の数が増える）と、ある状態に到達する確率が固定値に収束し、その値はシステム内での開始位置に依存しないことである。

これは、WWW全体をマルコフシステムと考え、各ページを状態、ページ間のリンクを確率のある遷移とすると、非常に興味深いことです。この定理は基本的に、「長い」閲覧を想定した場合、どのページから始めても、あるページに到達する確率Xは一定である、というものです。

PageRankアルゴリズムは、実はマルコフ連鎖アルゴリズムの改良型である。

あるページに到達する「固定確率」が高いほど、そのページの順位は高くなります。これは、固定確率が高いということは、他のページからのリンクが多いということであり、Googleは、リンクが多いページは価値があるに違いないと判断しているからです。インカミングリンクは多ければ多いほど価値があります。

もちろん、もっと複雑なのですが、理にかなっています。なぜabout.comのようなサイトが検索結果ページで優先されるのですか？なぜなら、ユーザーはネットサーフィンをするときにそこにたどり着く傾向があることがわかったからです。面白いでしょう？

入力された単語の予測

携帯電話には何十年も前から予測入力方式がありますが、この予測はどのように生成されているか分かりますか？Android（キーボードオプションあり）でもiOS（キーボードオプションあり）でも、選択したアプリがマルコフ連鎖を使っている可能性は高いです。

そのため、キーボードアプリケーションは、あなたのタイピングの習慣に関するデータを収集できるかどうかを尋ねます。例えばGoogle Keyboardでは、Share snippetsという設定があり、「Google Appsで入力した内容や方法のスニペットを共有し、Google Keyboardを改善する」ことを求めています。基本的に、あなたの言葉は分析され、アプリケーションのマルコフ連鎖の確率に組み込まれます。

そのため、キーボードアプリケーションでは、通常、3つ以上の選択肢を、可能性の高いものから低いものの順で提供します。次に入力するものが決まるわけではありませんが、大抵は正しいものです。

サブレディットシミュレーション

Redditを使ったことがない人は、少なくともこの「/r/subredditimulator」という魅力的な実験をチェックすることをお勧めします。

簡単に言うと、subredditsimulatorはRedditの多くのコミュニティから大量のコメントや見出しを取り込み、それぞれの文章の構成を単語単位で分析するものである。このデータをもとに単語間の確率を算出し、その確率をもとに見出しやコメントを一から生成しています。

この実験の興味深い点は、コメントや見出しがデータの発信元であるコミュニティによって分類されていることで、/r/foodのデータセットが生成するコメントや見出しの種類は、/r/soccerのデータセットが生成するものと非常に異なっているのです。

最も興味深い（あるいは気になる）点は、生成されたコメントや見出しが実際のユーザーのものと見分けがつかないことが多いことです。本当に魅力的です。

マルコフ連鎖の他のクールな使い方や、答えてほしい質問があれば、下のコメント欄で教えてください。