CRFでない最大エントロピー法をgibbs sampling で解く

Finkel+2005, Incorporating non-local information into Information Extraction Systems by Gibbs sampling

最大エントロピーモデル
・素性値の経験分布での期待値とモデルによる期待値が一致するという制約
・制約から対数線形モデルを導出
・尤度関数の線形重みに対する勾配は閉じた式で書ける
正則化項を加える場合も、普通は微分可能なものを選ぶ（L1正則化なんか微分できない部分があるので一工夫が必要）
・勾配には、モデルによる素性値の期待値が含まれる
モデルが複雑な場合（例:CRF）、期待値の計算の効率化が必要（DPなど）←ポイント！

最大エントロピーモデルのパラメータ推定
・尤度（＋正則化項）の最大化
・勾配を使った近似解法
上記の勾配を使って、尤度を大きくするような方向に重みを調整していく
← 期待値計算が遅いと、線形で遅くなる
最大エントロピーモデルによる推論
・重みが分かっている状態で可能な候補を列挙、モデル確率が高い候補を選択
CRFではここでもDPで効率的な計算が可能
最大値をとる候補である必要はなくて、期待値でもいい ← ポイント！

Gibbs sampling
・複雑なグラフィカルモデル上の確率変数の期待値を出すための近似解法。

CRFなどのDPによる期待値計算が可能なグラフィカルモデル上での最大エントロピー法とは異なり、
非局所の依存関係を入れたグラフィカルモデルでは、期待値計算が難しい。
（単純にありえる依存関係組を列挙すると膨大になる）
そこで期待値計算を厳密にやるのを諦めて、gibbs sampling で近似する。

• -

CIKM-8 Charles Elkan's tutorial of "Log-linear models and conditional random fields"
スライドと予稿で解説。
gibbs sampling にも触れている。