条件随机场是一个马尔科夫网.首先来看一下形如下图所示的马尔科夫网:

回顾马尔科夫网的联合概率计算公式,设 $X$ 与 $Y$ 分别为两个集合:

$P(X,Y) = \frac{1}{Z}\prod_{k=1}^K \phi_k(D_k)$

其中 $Z$ 将结果转化为概率:

$Z = \sum_{X,Y}\prod_{k=1}^K \phi_k(D_k)$

因为上图马尔科夫网的特殊形式,极大团只有 $\{Y _ { i } , Y _ { i + 1 }\}$ 和 $\{Y _ { i } , X _ { i }\}$ ,所以还可以进一步简化上述公式:

$P( Y , X ) = \frac{1}{Z}\prod _ { i = 1 } ^ { k - 1 } \phi \left( Y _ { i } , Y _ { i + 1 } \right) \prod _ { i = 1 } ^ { k } \phi \left( Y _ { i } , X _ { i } \right)$

马尔科夫网是生成式模型,对联合概率 $P(X,Y)$ 进行建模,而条件随机场是辨别式模型,试图对 $P(Y | X)$ 进行建模.

根据条件概率公式:

$P(Y | X) = \frac{P(X,Y)}{P(X)}$

我们可以很容易将 $P(X,Y)$ 转化为 $P(Y | X)$ :

$P(Y | X) = \frac{1}{Z(X)}\prod _ { i = 1 } ^ { k - 1 } \phi \left( Y _ { i } , Y _ { i + 1 } \right) \prod _ { i = 1 } ^ { k } \phi \left( Y _ { i } , X _ { i } \right)$

在马尔科夫网中为了归一化 $P(X,Y)$ ,所以 $Z$ 是所有与 $X,Y$ 相关的因子总和,而在归一化 $P(Y | X)$ 时X为已知常量,所以只需累加 $Y$ :

$Z(X) = \sum_Y \prod _ { i = 1 } ^ { k - 1 } \phi \left( Y _ { i } , Y _ { i + 1 } \right) \prod _ { i = 1 } ^ { k } \phi \left( Y _ { i } , X _ { i } \right)$

由于条件随机场定义了Y关于X的一个条件分布,因此可以将其视为一个部分有向图:

对数线性模型

既然条件随机场是一个特殊的马尔科夫网,那么也可以用对数线性模型表示:

$P ( y | x ) = \frac { 1 } { Z ( x ) } \exp \left( \sum _ { i , k } \lambda _ { k } t _ { k } \left( y _ { i - 1 } , y _ { i } , x , i \right) + \sum _ { i , l } \mu _ { l } s _ { l } \left( y _ { i } , x , i \right) \right)$

$Z ( x ) = \sum _ { y } \exp \left( \sum _ { i , k } \lambda _ { k } t _ { k } \left( y _ { i - 1 } , y _ { i } , x , i \right) + \sum _ { i , l } \mu _ { l } s _ { l } \left( y _ { i } , x , i \right) \right)$

式中 $t_k$ 和 $s_l$ 是特征函数, $\lambda _ { k }$ 和 $\mu _ { l }$ 是对应的权值, $k$ 和 $l$ 分别为转移特征与状态特征个数.

假设我们在某一节点我们有 $K_1$ 个局部特征函数和 $K_2$ 个节点特征函数，总共有 $K=K_1+K_2$ 个特征函数。我们用一个特征函数 $f_k(y_{i-1},y_i, x,i)$ 来统一表示如下:

$f_k(y_{i-1},y_i, x,i)= \begin{cases} t_k(y_{i-1},y_i, x,i) & {k=1,2,...K_1}\\ s_l(y_i, x,i)& {k=K_1+l,\; l=1,2...,K_2} \end{cases}$

对 $f_k(y_{i-1},y_i, x,i)$ 在各个序列位置求和得到：

$f_k(y,x) = \sum\limits_{i=1}^nf_k(y_{i-1},y_i, x,i)$

同时我们也统一 $f_k(y_{i-1},y_i, x,i)$ 对应的权重系数 $w_k$ 如下：

$w_k= \begin{cases} \lambda_k & {k=1,2,...K_1}\\ \mu_l & {k=K_1+l,\; l=1,2...,K_2} \end{cases}$

这样，我们的linear-CRF的参数化形式简化为：

$P(y|x) = \frac{1}{Z(x)}exp\sum\limits_{k=1}^Kw_kf_k(y,x)$

其中， $Z(x)$ 为规范化因子：

$Z(x) =\sum\limits_{y}exp\sum\limits_{k=1}^Kw_kf_k(y,x)$

如果将上两式中的 $w_k$ 与 $f_k$ 的用向量表示，即:

$w=(w_1,w_2,...w_K)^T\;\;\; F(y,x) =(f_1(y,x),f_2(y,x),...f_K(y,x))^T$

则linear-CRF的参数化形式简化为内积形式如下：

$P_w(y|x) = \frac{exp(w\cdot F(y,x))}{Z_w(x)} = \frac{exp(w\cdot F(y,x))}{\sum\limits_{y}exp(w \cdot F(y,x))}$

条件随机场的矩阵形式

我们定义一个 $m \times m$ 的矩阵 $M$ ， $m$ 为 $y$ 所有可能的状态的取值个数。 $M$ 定义如下：

$M_i(x) = \Big[ M_i(y_{i-1},y_i |x)\Big] = \Big[ exp(W_i(y_{i-1},y_i |x))\Big] = \Big[ exp(\sum\limits_{k=1}^Kw_kf_k(y_{i-1},y_i, x,i))\Big]$

我们引入起点和终点标记 $y_0 =start, y_{n+1} = stop$ , 这样，标记序列 $y$ 的非规范化概率可以通过 $n+1$ 个矩阵元素的乘积得到，即：

$P_w(y|x) = \frac{1}{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i |x)$

其中 $Z_w(x)$ 为规范化因子。

前向后向算法

当我第一次看到条件随机场使用前向后向算法的时候,我感到非常的亲切,因为在学习隐马尔可夫模型的时候,花了很多时间理解前向后向算法.隐马尔可夫模型是因为有隐变量,所以使用前向后向算法推导概率,而条件随机场虽然没有隐变量,但是 $Z(x)$ 却难以直接求解,所以这里也使用前向后向算法.

计算条件概率 $P(y_i|x)$ 可以使用如下递推公式：

$\alpha_{i+1}(y_{i+1}|x) = \alpha_i(y_i|x)M_{i+1}(y_{i+1},y_i|x) \;\; i=1,2,...,n+1$

在起点处，我们定义：

$\alpha_0(y_0|x)= \begin{cases} 1 & {y_0 =start}\\ 0 & {else} \end{cases}$

假设我们可能的标记总数是 $m$ , 则 $y_i$ 的取值就有 $m$ 个，我们用 $\alpha_i(x)$ 表示这 $m$ 个值组成的前向向量如下：

$\alpha_i(x) = (\alpha_i(y_i=1|x), \alpha_i(y_i=2|x), ... \alpha_i(y_i=m|x))^T$

同时用矩阵 $M_i(x)$ 表示由 $M_i(y_{i-1},y_i |x)$ 形成的 $m \times m$ 阶矩阵：

$M_i(x) = \Big[ M_i(y_{i-1},y_i |x)\Big]$

这样递推公式可以用矩阵乘积表示：

$\alpha_{i+1}^T(x) = \alpha_i^T(x)M_{i+1}(x)$

同样的。我们定义 $\beta_i(y_i|x)$ 表示序列位置 $i$ 的标记是 $y_i$ 时，在位置 $i$ 之后的从 $i+1$ 到 $n$ 的部分标记序列的非规范化概率。

这样，我们很容易得到序列位置 $i+1$ 的标记是 $y_{i+1}$ 时，在位置 $i$ 之后的部分标记序列的非规范化概率 $\beta_{i}(y_{i}|x)$ 的递推公式：

$\beta_{i}(y_{i}|x) = M_{i+1}(y_i,y_{i+1}|x)\beta_{i+1}(y_{i+1}|x)$

在终点处，我们定义：

$\beta_{n+1}(y_{n+1}|x)= \begin{cases} 1 & {y_{n+1} =stop}\\ 0 & {else} \end{cases}$

如果用向量表示，则有：

$\beta_i(x) = M_{i+1}(x)\beta_{i+1}(x)$

由于规范化因子 $Z(x)$ 的表达式是：

$Z(x) = \sum\limits_{c=1}^m\alpha_{n}(y_c|x) = \sum\limits_{c=1}^m\beta_{1}(y_c|x)$

也可以用向量来表示 $Z(x)$ :

$Z(x) = \alpha_{n}^T(x) \cdot \mathbf{1} = \mathbf{1}^T \cdot \beta_{1}(x)$

其中， $\mathbf{1}$ 是 $m$ 维全1向量。

有了前向后向概率的定义和计算方法，我们就很容易计算序列位置 $i$ 的标记是 $y_i$ 时的条件概率 $P(y_i|x)$ :

$P(y_i|x) = \frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)} = \frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{ \alpha_{n}^T(x) \cdot \mathbf{1}}$

也容易计算序列位置 $i$ 的标记是 $y_i$ ，位置 $i-1$ 的标记是 $y_{i-1}$ 时的条件概率 $P(y_{i-1},y_i|x)$ :

$P(y_{i-1},y_i|x) = \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} = \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{ \alpha_{n}^T(x) \cdot \mathbf{1}}$

梯度下降法求解

在使用梯度下降法求解模型参数之前，我们需要定义我们的优化函数，一般极大化条件分布 $P_w(y|x)$ 的对数似然函数如下：

$L(w)= log\prod_{x,y}P_w(y|x)^{\overline{P}(x,y)} = \sum\limits_{x,y}\overline{P}(x,y)logP_w(y|x)$

其中 $\overline{P}(x,y)$ 为经验分布，可以从先验知识和训练集样本中得到,这点和最大熵模型类似。为了使用梯度下降法，我们现在极小化 $f(w) = -L(P_w)$ 如下：

$\begin{align}f(w) & = -\sum\limits_{x,y}\overline{P}(x,y)logP_w(y|x) \\ &= \sum\limits_{x,y}\overline{P}(x,y)logZ_w(x) - \sum\limits_{x,y}\overline{P}(x,y)\sum\limits_{k=1}^Kw_kf_k(x,y) \\& = \sum\limits_{x}\overline{P}(x)logZ_w(x) - \sum\limits_{x,y}\overline{P}(x,y)\sum\limits_{k=1}^Kw_kf_k(x,y) \\& = \sum\limits_{x}\overline{P}(x)log\sum\limits_{y}exp\sum\limits_{k=1}^Kw_kf_k(x,y) - \sum\limits_{x,y}\overline{P}(x,y)\sum\limits_{k=1}^Kw_kf_k(x,y) \end{align}$

对 $w$ 求导可以得到：

$\frac{\partial f(w)}{\partial w} = \sum\limits_{x,y}\overline{P}(x)P_w(y|x)f(x,y) - \sum\limits_{x,y}\overline{P}(x,y)f(x,y)$

有了 $w$ 的导数表达书，就可以用梯度下降法来迭代求解最优的 $w$ 了。注意在迭代过程中，每次更新 $w$ 后，需要同步更新 $P_w(x,y)$ ,以用于下一次迭代的梯度计算。

维特比算法解码

条件随机场与隐马尔可夫模型一样使用维特比算法解码.

维特比算法就是将动态规划的一个特例,用来解决上述篱笆网络最优路径问题.现在每个时刻有3种状态,我们每个时刻要取1种状态,有很多种取法:

篱笆网络中每个节点的概率可以根据模型计算出来,现在的问题是如何找出概率最大的那条路径,显然不能用贪心算法,而枚举所有路径复杂度太高,这个问题可以用动态规划算法来解决.

假设我们知道了最优路径,那么最优路径一定会经过第i层的节点,如果求出到第i层所有节点的最优路径,那么全局最优路径一定在这些局部最优路径中.

所以动态规划的求解过程:

计算到第2层的所有最优路径
在前面的基础上,计算到第3层的所有最优路径
在前面的基础上,计算到第4层的所有最优路径
…
在前面的基础上,计算出到第n层的所有最优路径

我们的第一个局部状态定义为 $\delta_i(l)$ ,表示在位置 $i$ 标记 $l$ 各个可能取值(1,2…m)对应的非规范化概率的最大值。之所以用非规范化概率是，规范化因子 $Z(x)$ 不影响最大值的比较。根据 $\delta_i(l)$ 的定义，我们递推在位置 $i+1$ 标记 $l$ 的表达式为：