条件随机场

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

image

回顾马尔科夫网的联合概率计算公式,设 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的一个条件分布,因此可以将其视为一个部分有向图:

image

对数线性模型

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

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种状态,有很多种取法:

image

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

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

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

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

\delta_{i+1}(l) = \max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\;, l=1,2,...m

和HMM的维特比算法类似，我们需要用另一个局部状态 \Psi_{i+1}(l) 来记录使 \delta_{i+1}(l) 达到最大的位置 i 的标记取值,这个值用来最终回溯最优解， \Psi_{i+1}(l) 的递推表达式为：

\Psi_{i+1}(l) = arg\;\max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\; ,l=1,2,...m

参考:
Daphne Koller<概率图模型>

posted @ 2018/10/23 14:33:40