マルコフ連鎖(英: Markov chain)とは、確率過程(後述)の一種である。離散(状態)マルコフ過程とも呼ぶ。
概要
マルコフ性(後述)を持つ確率過程(stocastic process, 時間変化する確率変数)のうち取り得る事象を示す値が離散的なものを指す。
ロシア帝国の数学者アンドレイ・アンドレイェヴィチ・マルコフ(露: Андрей Андреевич Марков 1856-1922)によって研究され、物理学や統計学の基本的なモデルに応用されている他、情報学においても外すことのできない重要な概念となっている。
なお、厳密かつ専門的な話はWikipediaがかなり詳しい。
マルコフ性
マルコフ性(Markov property)とは、次の状態が過去の状態に依存せず現在の状態のみによって決まる性質のことである。
マルコフ性が存在する場合、状態が {q0, q1, q2, q3, ……, qn-1} のn通りを取るような状態遷移において、現在の状態が qi であった時に次の状態 qj に遷移する確率は純粋に次の状態と現在の状態のみで記述され、 P(qj | qi) で決定される。
同様に、状態遷移した順に並べた順序列 {a0, a1, a2, …, am-1} の生成確率は Πi=1m-1P(ai | ai-1) と表すことができる。
この様なマルコフ性を備えた確率過程を総称してマルコフ過程(Markov/Markovian process)と呼ぶ。その中でも状態空間が離散集合を採る(つまり取りうる状態を示す値が連続的でなく離散的である)ものを特にマルコフ連鎖と呼ぶ。
文生成の例
マルコフ連鎖を用いて文生成を行う例を示す。これは自然言語にマルコフ性を仮定していることに注意。
{今日は, いい天気, です, 。}という状態の集合があったとする。
「今日は」という状態の次に「です」という状態がくる確率はP(です | 今日は)で表される。
P(今日は | 今日は)、P(いい天気 | 今日は)、P(です | 今日は)、P(。 | 今日は)の4つのうち、最も高い確率をもつのはP(いい天気 | 今日は)であるはずである。
確率的に「いい天気」へと状態が遷移すると、「今日は いい天気」という文が生成される。
さらにその次の状態はP(今日は | いい天気)、P(いい天気 | いい天気)、P(です | いい天気)、P(。 | いい天気)の4つを比較して決定される。
確率が十分に正確であれば、「今日は いい天気 です 。」という文の生成確率が最も高くなり、結果的にこの並びが一番選ばれやすくなる。
この文の生成確率はP(今日は)×P(いい天気 | 今日は)×P(です | いい天気)×P(。 | です)で表される。
確率P(かんとか | なんとか)は大概(「なんとか かんとか」という遷移が発生した回数)/(「なんとか」という状態になった回数)で求められる。この確率の良し悪しで生成された文の良し悪しが決まる。
実際の文生成には状態として文節ではなく「形態素」と呼ばれる単語のようなものが用いられることが多いほか、直前の1個ではなく、4個までを考慮した高階マルコフ連鎖を使うことが多い。自然言語処理や音声認識の分野ではN-gramモデルと呼ばれたりする。
関連商品
市場で検索してみた結果より抜粋。編集者は読んでないのでお薦めあれば教えてください。
関連項目
- 8
- 0pt