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}))$ $P (y ∣ x) = \frac{1}{Z _{x, w}} exp (w \cdot ϕ (x, w))$
- 全体としての確からしさを考慮して ${\bold y}$ を決めている
$Z$ は確率の総和が $1$ となるようにするための，正規化項
${\bold x}$ $x$ を分類して ${\bold y}^{\*}$ $y\*$ を得るには， ${\bold y}^{\*} = {\textrm argmax}_{{\bold y}} \left( {\bold w} \cdot \phi ({\bold x,y}) \right)$ $y\*=argmaxy(w⋅ϕ(x,y))$ を解く必要がある
- しかし，この計算は大変
- そこで，素性関数に $\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}|$ $\sum_{i} lo g P (y^{(i)}, x^{(i)}) - c ∣ y ∣$
- これを最大化したい．第1項は尤度項，第2項は正則化項
尤度項 $\log P(\bold{y}|\bold{x})$ $lo g P (y ∣ x)$ の勾配 $\bold{g}$ $g$ を計算する
- $i$ 番目のデータを $(\bold{x}^{(i)}, \bold{y}^{(i)})$ で表す
- 一方， $\bold{x}$ や $\bold{y}$ は変数
- 対数尤度の $w_k$ $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}))$ $exp (w \cdot ϕ (x, w))$ について
- 最初からあるノード $N$ まで計算した値 $\alpha(N)$ と，あるノードから最後までを計算した値 $\beta(N)$ を用いる