Maximum entropy modelingから見たMEMMを書いて、「MEMM完全に理解した」と思った自分は、 イマドキはCRFだ、と煽られたので、この位軽いだろう、と理解しようとしたらめちゃくちゃ苦戦した。 こんな難しい事を皆理解しているのか？と思ったので解説を書こうとしたが、膨大になりそうなのでとりあえずメモを書くくらにしておく（気が向いたら行間を埋める予定）

後者はロジスティック回帰の方向から書いてあって、原典より現代の視点では分かりやすい。 ただMRF的な視点で何をやってるのか良く分からなくなった、というのがこのエントリを書くきっかけ。

使うのもそんな難しくなく、ご利益もわかりやすい

まず大前提として、HMMみたいな系列ラベルの改善版として考えると、 ラベルバイアスが無い、という事と、観測値xのモデリングが要らないので良さそう、というのは割とすぐに理解出来る。 さらに条件付き確率で遷移を予想するのは通常の分類器みたいに解釈出来るので、現代人的には別段難しい事は無いように思える。

さらにlatentなラベルの独立性を仮定して、積で（条件付き）同時確率が出せる、そしてそれらのラベルに、その周辺の観測をgivenの所に入れられるのでラベルバイアスは解決出来そう、みたいなふわっとしたくらいの理解はそう難しくない。

さらにforward backwardアルゴリズムでMRFのエッジや頂点に相当する周辺確率が出せれば、それらの言葉の意味を良く知らなくてもとりあえずは使えると思う（使った事無いのでイメージで語ってます）

という事で、ゆとりとしてはそうした系列ラベリングのモデルとしての特徴や具体的な計算方法だけ理解していれば良い、と言える。 なんかいい感じのラベルが得られて、それの変な所がどういう確率的な理由で来るのかがカウントから理解出来れば、Featureを作っていったりモデルを改善していったりは出来る。

そんな理解ではさっぱり何も分からない

問題は、この説明は一般的過ぎる、という事。 例えば条件付き確率を使う事でxの分布をモデリングしなくて良い、 というのは完全に正しいが、Markov Random Field（以下MRF）の立場からすれば、 条件付き確率でも同時確率でもファクターにはxが含まれる。 モデリングしなくて良い、というのは何を指しているのか？がわかりにくい。

本質的な事としては、Featureのempricalな期待値と推計している分布による期待値が一致するように分布を推計しているのだが、この分布が条件付き期待値だ、というのが一番の違いになっているのだけど、 これを理解する為には学習の詳細の所を追わないといけない。 だがこの学習が、元論文ではimproved iterative scalingとかいう物が使われていて、たぶん現代ではもうちょっと簡単で良い物があると思う（イメージで語ってます）。 だから元論文の難しい学習の所（4章のParameter estimationの所）を頑張って理解しないと分からないのに、それは今では使われてないので徒労感が強い。

現代的な学習を前提にこのあたりを解説してくれても良いと思うのだけど、どうしてもちゃんと解説しようとすると結構深いMRFの知識とMaximum Entropy Modelという情報理論のいにしえの話題にかなり突っ込まないと行けないので、イマドキの若者は読んでくれない。 という事であんまり見かけない気がする。

あらすじ的なメモ

ちゃんと解説するのは長くなるので、まずはメモくらいから始める。

CRFは、その名の通り条件付き確率の分布を推計する。 系列ラベルの場合は、ラベルの条件付きマルコフ性（と呼ぶのか？条件付きの確率にマルコフ性がある、という意味）は仮定される。 一般化すると「それはMRFと何が違うのか？」というのが凄くわかりにくくなるので、系列ラベルで理解するのが良い。

CRFは観測をFeatureにする。Featureは任意の可測関数で良いが、期待値が集計出来る事、というのがポイント。 可測関数と言っているので定義によりランダム変数。

まずランダム変数の期待値が分かっている時に、その分布を推計する、というサブ問題がある。

最大エントロピー原理とあるランダム変数の期待値だけが分かっている場合の分布

なんらかのランダム変数の期待値だけが分かっている時に、その元となる分布を推計する、と言っても、分布の形はいろいろ考えられる。 ここでは、この「期待値が所与の物で、entropyが最大の分布」というのが求める分布と仮定する。 するとこれは、以下の本の12.1で書かれているように、（英語のWikipediaのMaximum entropy probability distributionにも書いてあるが、下記教科書の方がだいぶ分かりやすい）

amazon: Elements of Information Theory (English Edition)

このランダム変数を\(f_i(x)\)とおいた場合、xの分布は

\[p(x) \propto exp(\sum{\lambda _i f_i(x)})\]

と書ける。これが以前maximum entropy modelingと言っていた物の、より一般化した定義。 ここで、\(\lambda _ i\)は、期待値が一致する、という制約条件に一致するように選ばれる（汎関数に対するラグランジュの未定定数法で証明出来る）。

期待値は\(f_i(x)\)の期待値だが出る分布はxの分布、という所に注目。

これはなかなか衝撃的な結論だ。期待値が一致する、というだけの制約で、その他ほとんど制約が無いような自由な分布の中で、entropyが最大になるもの、という普通の条件を入れるだけで、元の分布の方に期待値では無くで可測関数がそのまま入る。

なお、汎関数微分をちゃんと考えれば納得出来るけれど、証明だけなら心を無にして、まるで普通の変数による微分をするだけで答えは導出出来るので、関数解析分からないゆとりでも安心（でも全然結果の衝撃は理解出来ないが）。

CRFの文脈での応用

CRFでは、観測をgivenとした条件付き期待値としてラベルの系列の確率をモデル化する。 さらにラベル同士はconditionallyにはマルコフ性があると仮定する。

この条件付き確率で、Featureの期待値を教師データから集計する。 これをempricalな期待値と呼ぶ。

そしてこの期待値と一致するような、yの分布を考えるが、この時xはgivenなyの分布を考える。 この\(p(y|x)\)でのFeatureの期待値がemptricalに分かっているので、 この期待値と一致するような中でmaximum entropyなモデルを仮定すると、以下の形で書ける。

\[p(y|x) \propto exp(\sum{\lambda _i f_i(x, y)})\]

この辺まで来ると系列ラベリングな人たちには見慣れた式に近いだろう。

ただ、もちろんこんな一般的な形では何も言ってないに等しいので、そこはMRFの適当なトポロジーを仮定する。 典型的には、\(y_i, y_{i+1}\)と\(y_i\)でfactorizeされるとか。

だいたいは一般のclique tree algorithmで計算出来るので、yがチェインとかツリーとか、clique treeのトポロジーとして簡単そうな奴ならなんでも良い。

で、この制約条件を満たすようにラムダを決める、という話はiterative scalingアルゴリズムとかの話になるけれど、たぶんもっと現代的にちゃんと全部を分かっている人なら対数尤度をラムダで微分してSGDみたいな簡単な形になる気がする（けど自分は分かってない）。

CRFの確率場的な話

  1. 条件付き確率を推計する
  2. emptricalに(条件付き確率による)期待値が求められるようなフィーチャを定義し、期待値を集計する
  3. 条件付き確率を、その期待値に一致するentropy最大のモデルと仮定すると、expの形で書けるモデルになる
  4. さらに幾つかのMRFのトポロジーの仮定を入れる事で推計分布による期待値がclique tree algorithmで簡単に求まりやすい形にしておく

制約条件が（条件付き確率による）期待値なので、たぶんどんなアルゴリズムでもパラメータ更新式はこの期待値が出てくるはず。

本質的には期待値が求まるFeatureを元に分布を求める、という一般のMRFの問題のサブセットなのだが、そのうち観測データとかラベルとかの性質をうまい事考慮に入れたMRFを考える事でtractableな問題に落とし込んでいる、、、ってその言い方なら任意のMRFの応用がそう言えてしまうか。 実際CRFは抽象的に書くとXの分布をモデリングしない、以上には特に制約の無いMRFとほとんど変わらなくなってしまうので、何がCRFなのかは良く分からない。

これにラベル同士のマルコフ性だとか、期待値が集計で求まるようなFeature（ある程度同じFeatureのことなるラベルが無いと駄目だと思う）とか、系列ラベリングという問題設定で都合が良さそうでいい感じの結果になりそうな物をいろいろ入れた物がCRF、というのが自分の現時点での理解。