Linear-Chain CRF

通常の分類器の逐次適用

$y_i$のラベルを当てるのに，$y_1, \ldots y_{i-1}, x_1, \ldots, x_N$の情報を素性にとる分類器を構築するといった方法が考えられる
HMMよりは，使える情報は増えているが，最終結果が全体として最適であることは保証できない
CRFは「全体としての確からしさ」を考慮する

最大エントロピー法の系列に対する拡張
- CRFは一般的なグラフに適用可能だが，以下では系列に対するLinear-Chain CRF(Conditional Random Fields)について述べる
$P({\bold y} | {\bold x}) = \frac{1}{Z_{{\bold x,w}}} \exp ( {\bold w} \cdot \phi ({\bold x,w})) $
- 全体としての確からしさを考慮して${\bold y}$を決めている
$Z$は確率の総和が$1$となるようにするための，正規化項
${\bold x}$を分類して${\bold y}^{*}$を得るには，${\bold y}^{*} = {\textrm argmax}_{{\bold y}} \left( {\bold w} \cdot \phi ({\bold x,y}) \right)$を解く必要がある
- しかし，この計算は大変
- そこで，素性関数に$\phi_k ({\bold x, y}) = \sum_t \phi_k ({\bold x}, y_t, y_{t-1})$という制約をおくと，$ \sum_t {\bold w} \cdot \phi ({\bold x}, y_t, y_{t-1}) $を解けばよくなり，ビタビアルゴリズムが使える
- なお，$\phi_k ({\bold x, y}) = \sum_t \phi_k ({\bold x}, y_t, y_{t-1}, y_{t-2})$という制約をおくこともできる

目的関数は$\sum_i \log P(\bold{y}^{(i)}, \bold{x}^{(i)}) - c |\bold{y}|$
- これを最大化したい．第1項は尤度項，第2項は正則化項
尤度項$\log P(\bold{y}|\bold{x})$の勾配$\bold{g}$を計算する
- $i$番目のデータを$(\bold{x}^{(i)}, \bold{y}^{(i)})$で表す
- 一方，$\bold{x}$や$\bold{y}$は変数
- 対数尤度の$w_k$での偏微分は次式
  - $\frac{\partial \log P(\bold{y}^{(i)} | \bold{x}^{(i)})}{ \partial w_k} = \phi_k (\bold{x}^{(i)}, \bold{y}^{(i)}) - \sum_{\bold{y}} \phi_k (\bold{x}^{(i)}, \bold{y}) P(\bold{y} | \bold{x}^{(i)})$
- よって
  - $\bold{g} = \phi (\bold{x}^{(i)}, \bold{y}^{(i)}) - \sum_{\bold{y}} \phi (\bold{x}^{(i)}, \bold{y}) P(\bold{y} | \bold{x}^{(i)})$
あとは，（例えば）FOBOSが使える
- ただし，$\sum_{\bold{y}}$を「前向き後ろ向きアルゴリズム」で効率よく計算する必要がある

高村本p.155を参照
$\exp ( {\bold w} \cdot \phi ({\bold x,w}))$について
- 最初からあるノード$N$まで計算した値$\alpha(N)$と，あるノードから最後までを計算した値$\beta(N)$を用いる