条件付き確率場のマルコフ性とか準マルコフ連鎖とか

　実装する上ではどうでもいい、言葉の定義の問題のところに足を突っ込みつつあるような気もするけれど、CRFについて調べていたらどんどん混乱してきたので、現在のところの理解をまとめてみる。たぶん、突っ込みどころはいっぱいありますので、突っ込んで頂けると幸いです。
　CRFは入力Xと出力Yの組をたくさん与えることで、未知のXに対してもP(Y|X)を計算できるようにするモデルである。ただし、Yは構造を持つ（この構造を持つというのがどう言うことかもややこしくて今調べているのだが、こちらはとりあえず棚上げする）ものとする。
　CRFはP(Y|X) = \frac{\exp(W \cdot (X, Y))}{Z(X)}であるということしか規定せず、自然言語処理ではlinear chain CRFとsemi markov CRFの2つ、特にlinear chain CRFがよく使われている。
　linear chain CRFは出力Yが一本鎖の構造になっているところが特徴である。linear chain CRFはマルコフ連鎖であると言っていいのだろうか？
　マルコフ連鎖は、マルコフ過程（マルコフ性を持つ確率過程）のうち、状態が離散的なもののことである。
　マルコフ性とは、現在の状態が決まれば、未来の状態の確率分布は過去の状態に依存せずに決まる、という性質である。CRFにおいてはP(Y_{i+1}|X,Y_i)の分布が、P(Y_{i+1}|X,Y_0, Y_i, ...Y_i)の分布と同じになる、と言えれば、マルコフ性が成り立っていると言える。これはlinear chain CRFであれば明らかに成り立つので、linear chain CRFはマルコフ連鎖であると言える。なお、linear chain CRFの場合は時間に対しても離散的である。
　P(Y|X) \propto \exp(W \cdot (X, Y))は正規化項Zなしでは確率としては正しくないので、 P(Y_i|X)の計算がなんだかうまくいかないような気が一瞬したが、普通にP(Y|X) = \frac{\exp(W \cdot(X, Y))}{Z(X)}からY_i以外のYを積分消去してやればP(Y_i|X)は計算できるので、CRFはマルコフ連鎖であるはずだ。
　次に、semi markov CRFについて考える。semi markov CRFは準マルコフ連鎖であるような構造を持つCRFである。準マルコフ連鎖に関しては、ちゃんとした教科書を調べてみるとなんか難しすぎて歯が立たないし、Sarawagiらの論文(pdf)ではP(Y|X)の代わりにP(S|X)を最大化するよ、Sはセグメントで<開始位置, 終了位置, ラベル>の3つ組で構成されるよ、というsemi markov CRFの定義しかなく、準マルコフ連鎖自体の定義は書いてない。
　wikipediaの準マルコフ過程のページを見たところによると、準マルコフ過程では、状態に対して滞留時間を考える。つまり、ある状態に一定期間留まったままいられるというモデルである。準マルコフ過程では、

  • 状態をジャンプする確率過程はマルコフ連鎖
  • 滞留時間をサンプリングする分布はなんでもいい

　という条件がつく。（2つ目は条件とは言えないか…。）この1つ目のマルコフ連鎖と2つ目の滞留時間を決定する確率分布の2つを合わせて準マルコフ過程という。
　このwikipediaの定義と、Sarawagiらの定義には、私の目からは食い違っているようには見えないので、以下はこの定義を採用して話をすすめる。
　semi markov CRFでは、状態をジャンプする確率過程はマルコフ連鎖であると言えるのだろうか？linear chain CRFの場合と同じく、積分消去してやればマルコフ性が言えて、マルコフ連鎖である、と言えると思うのだが、なんだか自信が持てない。ここがマルコフ連鎖であると言えてしまうと、ラベルバイアスの話的になんかうまくない気がする。ここがクリアになれば、CRFが理解できたと言ってもいいような気がするんだけど…。
　追記：@nokunoさんから CRFみたいな識別モデルもマルコフ連鎖って呼ぶんでしたっけ？ マルコフ連鎖は生成モデルの印象が… という意見をいただきました。HMMとMEMMとCRFのグラフィカルモデルを並べて眺めていると、正直どんどんとよくわからなくなってくるのですが、定義を見た限りではマルコフ連鎖は状態空間が離散的なマルコフ過程である、という事しか書いてないので、マルコフ性を満たす確率過程であればなんでもマルコフ連鎖って呼べるんじゃないかと思います。ただ、CRFが確率過程になっているのかどうかは、私にとっては自明でないので、そこら辺は考える必要もありますね。