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

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

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_ks_l是特征函数,\lambda _ { k }\mu _ { l }是对应的权值,kl分别为转移特征与状态特征个数.

假设我们在某一节点我们有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_kf_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的矩阵Mmy所有可能的状态的取值个数。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+1n的部分标记序列的非规范化概率。

这样,我们很容易得到序列位置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.png
篱笆网络中每个节点的概率可以根据模型计算出来,现在的问题是如何找出概率最大的那条路径,显然不能用贪心算法,而枚举所有路径复杂度太高,这个问题可以用动态规划算法来解决.

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

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

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

我们的第一个局部状态定义为\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
评论加载中...

发表评论