CRF条件随机场

线性链条件随机场

DEFINITION

$p(\mathbf{y} | \mathbf{x})=\frac{1}{Z(\mathbf{x})} \prod_{t=1}^{T} \exp \left\{\sum_{k=1}^{K} \theta_{k} f_{k}\left(y_{t}, y_{t-1}, \mathbf{x}_{t}\right)\right\}$
$Z(\mathbf{x})=\sum_{\mathbf{y}} \prod_{t=1}^{T} \exp \left\{\sum_{k=1}^{K} \theta_{k} f_{k}\left(y_{t}, y_{t-1}, \mathbf{x}_{t}\right)\right\}$

ESTIMATION

损失函数为
$\ell(\theta)=\sum_{i=1}^{N} \log p\left(\mathbf{y}^{(i)} | \mathbf{x}^{(i)} ; \theta\right)$
即 $\ell(\theta)=\sum_{i=1}^{N} \sum_{t=1}^{T} \sum_{k=1}^{K} \theta_{k} f_{k}\left(y_{t}^{(i)}, y_{t-1}^{(i)}, \mathbf{x}_{t}^{(i)}\right)-\sum_{i=1}^{N} \log Z\left(\mathbf{x}^{(i)}\right)$
对 $\theta_k$ 求导结果为
$\begin{aligned} \frac{\partial \ell}{\partial \theta_{k}}=& \sum_{i=1}^{N} \sum_{t=1}^{T} f_{k}\left(y_{t}^{(i)}, y_{t-1}^{(i)}, \mathbf{x}_{t}^{(i)}\right) \\ &-\sum_{i=1}^{N} \sum_{t=1}^{T} \sum_{y, y^{\prime}} f_{k}\left(y, y^{\prime}, \mathbf{x}_{t}^{(i)}\right) p\left(y, y^{\prime} | \mathbf{x}^{(i)}\right)\end{aligned}$
关注一下 $p\left(y, y^{\prime} | \mathbf{x}^{(i)}\right)$ 是怎么得来的：
$\begin{aligned} \frac{\partial \log Z\left(\mathbf{x}^{(i)}\right)}{\partial \theta_{k}} &= \frac {1}{Z\left(\mathbf{x}^{(i)}\right)} \sum_{\mathbf{y}} \frac{\partial \left\{ \prod_{t=1}^{T} \exp \left\{\sum_{k=1}^{K} \theta_{k} f_{k}\left(y_{t}, y_{t-1}, \mathbf{x}_{t}\right)\right\} \right\} } {\partial \theta_k} \\ &=\frac {1}{Z\left(\mathbf{x}^{(i)}\right)} \sum_{\mathbf{y}} \left\{ \prod_{t=1}^{T} \exp \left\{\sum_{k=1}^{K} \theta_{k} f_{k}\left(y_{t}, y_{t-1}, \mathbf{x}_{t}\right)\right\} * \sum_{t=1}^{T} f_{k}\left(y_{t}, y_{t-1}, \mathbf{x}_{t}\right) \right\} \\ &= \sum_{\mathbf{y}} \left\{ p\left( \mathbf{y} | \mathbf{x}^{(i)}\right) * \sum_{t=1}^{T} f_{k}\left(y_t, y_{t-1}, \mathbf{x}_{t}^{(i)}\right) \right\} \\ &= \sum_{t=1}^{T} \sum_{y, y^{\prime}} f_{k}\left(y, y^{\prime}, \mathbf{x}_{t}^{(i)}\right) p\left(y, y^{\prime} | \mathbf{x}^{(i)}\right) \end{aligned}$
解释：
从第一行到第二行可以将累乘符号转换为exp中的累加即得。
从第三行到第四行是将中括号内部的求和符号放在外面去。然后进行边缘概率的计算。

理解清楚这里就可以利用prml里面的sum-product algorithm来进行优化求导。