6 工程中算法需做变换，避免超出计算机浮点数范围

在实践中，因为规范因子$ Z_w(x) $在序列较长时值会非常大，因此所有和规范因子相关运算全部使用$ \log \sum \exp $替代。对应的概率操作也需要变换。

- 阅读剩余部分 -

5 对数似然

指数似然解释和过程参考

$ \tilde{p} $是经验分布概率，由样本简单统计得到。

$$ \begin{align} L_\tilde{P}(P_w) &= \log \prod_{x,y}p(y|x)^{\tilde{p}(x,y)} \\ &= \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{k=1} w_k f_k(x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x) \end{align} $$

- 阅读剩余部分 -

4 linear chain CRF Viterbi

超找给定$ x $序列最大概率输出序列$ y^\ast $。

与 HMM/MEMM viterbi 类似的搜索方法，但在CRF中并不用计算规范化概率。

$$ \begin{align} y^\ast &= \arg\max_y p(y|x) \\ &= \arg\max_y \frac{ \exp( w \cdot F(y,x) ) }{Z_w(x)} \\ &= \arg\max_y \exp( w \cdot F(y,x) ) \\ &= \arg\max_y w \cdot F(y,x) \\ &= \arg\max_y \sum_k w_k f_k(y, x) \\ &= \arg\max_y \sum_k w_k \sum_i f_k(y_{i-1}, y_i, x_i) \\ &= \arg\max_y \sum_i \sum_k w_k f_k(y_{i-1}, y_i, x_i) \\ &= \arg\max_y \sum_i f^\prime(y_{i-1}, y_i, x_i) \end{align} $$

$$ f^\prime(y_{i-1}, y_i, x_i)=\sum_k w_k f_k(y_{i-1}, y_i, x_i) $$

也就是说只需计算连续最大特征函数求和路径。

可看到线行链中只有前后两个$ y_{i-1}, y_i$是互相依赖的，因此这里和HMM类似，只是把求积换成求和。

- 阅读剩余部分 -

3 向前向后算法

和HMM第一大问题相似，计算给定x,y序列的条件概率。

定义 $ \alpha_i(x) $为在时刻$ i $止之前所有时刻的所有可能$ y $取值联合当前$y_i$取值的非规范化概率。$ m=|y| $。类似再定义和$ \alpha $相反，从 $n+1$时刻开始的反向计算的向量$ \beta_i(x) $。

- 阅读剩余部分 -

2. 条件随机场

给定变量$ X $时无向图$ Y $的随机场。

$$ P(Y_v|X, Y_w \neq Y_v) $$

$ Y_W $ 是所有与$ Y_v $有连接的节点(考虑局部独立性，这里使得条件随机场的$ P(Y|X) $可描述为$ Y_v $的联合概率)。

- 阅读剩余部分 -

1. 概率无向图模型

概率无向图是指随机变量节点连接边没有方向的概率图模型, 其节点$ v \in V$表示随机变量，节点之间的边$ e \in E $表示随机变量之间的依赖关系。

$$ G=(V, E) $$

- 阅读剩余部分 -