ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


マルコフ連鎖


ヨミ: マルコフレンサ
掲示板をミル!
9カキコ!

マルコフ連鎖(英: 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モデルと呼ばれたりする。


関連商品


市場検索してみた結果より抜編集者は読んでないのでお薦めあれば教えてください。

■az4431708650
■az4434167391
■az4320122399


関連項目



最終更新日: 14/10/03 23:28
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ