条件随机场（Conditional Random Field，CRF）

​

1. 概率无向图模型

概率无向图模型（probabilistic undirected graphical model），又称为马尔可夫随机场（Markov random field），是一个可以由无向图表示的联合概率分布。

1.1 模型定义

图Graph包含顶点node、边edge，无向图指的是边没有方向的图。

概率图模型指的是，图中的边表示随机变量之间的概率依赖关系。

无向图表示的随机变量之间存在 成对马尔科夫性、局部马尔科夫性、全局马尔科夫性 。

• 成对马尔可夫性 任意不相连的两个结点

分别对应随机变量

。其他所有结点为

, 对应随机变量组为

。

成对马尔可夫性指：

• 局部马尔可夫性 设

是无向图中任意一个结点，

是与

有连接的所有结点，

是

和

以外的其他所有结点。

局部马尔可夫性指：

在

时，上式等价于

• 全局马尔可夫性 设结点集合

是图中被结点集合

分开的任意结点集合

全局马尔可夫性指：

上述成对的、局部的、全局的马尔可夫性定义是等价的

1.2 概率无向图模型的因子分解

团与最大团 的定义：

任何两个结点均有连接的结点子集称为团，若

是无向图的一个团，且不能再加进任何一个结点使其成为一个更大的团，则称

为最大团（maximal clique）

例如，上图中2个结点组成的团有5个

，有2个最大团

。

而

不是一个团，因为

和

没有边连接。

将概率无向图模型的联合概率分布表示为其 最大团 上的随机变量的函数的乘积形式的操作，称为 概率无向图模型的因子分解（factorization） 。

给定概率无向图模型，

是图

上的最大团，

表示

对应的随机变量。那么，概率无向图模型的联合概率分布

可写作所有最大团

上的函数

的乘积形式：

`$

\color{red}P(Y) = \frac{1}{Z} \prod\limits_C \Psi_C(Y_C),\quad 其中Z=\sum\limits_Y \prod\limits_C \Psi_C(Y_C)是规范化因子

$`

函数

称为势函数（potential function），通常定义为指数函数

2. 条件随机场的定义与形成

2.1 条件随机场的定义

条件随机场：

设

与

是随机变量，

是在给定

的条件下

的条件概率分布。若随机变量

构成一个无向图的马尔科夫随机场，即：

`$

\color{red}P(Yv|X,Y\omega, \omega \neq v) = P(Yv|X,Y\omega,\omega \sim v)

$`

左边表示，条件里是多个

, 且

；右边是多个

, 且

都与

相连。则称条件概率分布

为条件随机场。

线性链条件随机场：

`$

\color{red}P(Yi|X,Y_1,...,Y{i-1},Y{i+1},...,Y_n) = P(Y_i|X,Y{i-1},Y_{i+1})\

i=1,2,...,n(在i=1,n时只考虑单边)

$`

则称条件概率分布

为线性链条件随机场。在标注问题中，

表示输入观测序列，

表示对应的输出标记序列或状态序列。

2.2 条件随机场的参数化形式

根据上面，可以给出线性链条件随机场

的因子分解式，各因子是定义在相邻两个结点（最大团）上的势函数。在随机变量

取值为

的条件下，随机变量

取值为

的条件概率具有如下形式：

`$

\begin{aligned}

\color{red}P(y|x) &\color{red}= \frac{1}{Z(x)} \exp \Bigg( \sum\limits{i,k} \lambda_k t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)\

其中，Z(x) &= \sum\limitsy \exp \Bigg( \sum\limits{i,k} \lambdak t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)

\end{aligned}

$`

式中，

是特征函数，

是对应权值。

是规范化因子。

• ​

是边上的特征函数，称为转移特征，依赖于当前和前一个位置

• ​

是结点特征函数，称为状态特征，依赖于当前位置

• ​

都依赖于位置，是局部特征函数。函数取值 1 或者 0

• 条件随机场完全由

特征函数，

对应权值 确定

• 线性链条件随机场是对数线性模型（log linear model）

例题

设有一标注问题：输入观测序列

，输出标记序列

，

取值于

.

假设特征

和对应权值

如下：

`$

\begin{aligned}

t1&=t_1(y{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\

t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\

t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\

t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\

t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\

s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\

s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\

s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\

s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5

\end{aligned}

$`

对给定的观测序列

，求标记序列为

的非规范化条件概率(未除以规范化因子的条件概率)。

解：

由线性链条件随机场模型有：

`$

\begin{aligned}

P(y|x) &\propto \exp \Bigg( \sum\limits{i,k} \lambda_k t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)\

&= \exp \Bigg\sum\limits{k=1}^5 \lambda_k \sum\limits{i=2}^3tk (y{i-1},yi,x,i) + \sum\limits{k=1}^4 \muk \sum\limits{i=1}^3 s_k(y_i,x,i) \Bigg\

&= \exp (1+0.2+1+0.5+0.5) = \exp (3.2)

\end{aligned}

$`

2.3 条件随机场的简化形式

• 统一

个转移特征和

个状态特征，

，记特征函数：

`$ fk(y{i-1},y_i,x,i)=\left{

\begin{aligned}

tk(y{i-1},y_i,x,i), \quad\quad\quad\quad k=1,2,...,K_1 \

s_l(y_i,x,i), \quad k=K_1+l; l=1,2,...,K_2

\end{aligned}

\right.

$`

• 对转移和状态特征在各个位置

求和，记作：

`$

fk(y,x) = \sum\limits{i=1}^n fk(y{i-1},y_i,x,i)，k=1,2,...,K

$`

• 用

表示特征

的权值，即

`$ \omega_k=\left{

\begin{aligned}

\lambda_k, \quad\quad\quad\quad\quad\quad k=1,2,...,K_1 \

\mu_l, \quad k=K_1+l; l=1,2,...,K_2

\end{aligned}

\right.

$`

• 条件随机场可表示为

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

Z(x) = \sum\limitsy \exp \sum\limits{k=1}^K \omega_kf_k(y,x)$`

• 用

表示权值向量，

• 用

表示全局特征向量，即

• 条件随机场写成向量内积形式：

2.4 条件随机场的矩阵形式

• 在标记序列的两端添加首尾状态标记

• 引进

，对比2.2节的表达式，可见该式少了对位置

求和

• 对每个位置创建一个

的方阵（m为状态的个数，行为

位置的状态，列为

位置的状态，值为

, 用矩阵

来表示所有的情况）

• 又因为

• 于是条件概率

是规范化因子，是

个矩阵乘积的

位置的元素，是路径

所有可能的状态组合的非规范化概率之和。

例题

假设有如下线性链条件随机场，观测序列

, 状态序列

, 标记

, 假设

，各个位置的随机矩阵

是

求状态序列

以

为起点，

为终点所有路径的非规范化概率及规范化因子。

解：

所有可能的路径有 8 条：

各路径的非规范化概率是：

`$a{01}b{11}c{11},\quad a{01}b{11}c{12},\quad a{01}b{12}c{21},\quad a{01}b{12}c{22}\

a{02}b{21}c{11},\quad a{02}b{21}c{12},\quad a{02}b{22}c{21},\quad a{02}b{22}c{22}$`

规范化因子

`$Z\omega(x) = [M_1(x)M_2(x) M_3(x)M{4}(x)]_{1,1}\

a{01}b{11}c{11}+ a{01}b{11}c{12}+ a{01}b{12}c{21}+a{01}b{12}c{22}+\

a{02}b{21}c{11}+ a{02}b{21}c{12}+ a{02}b{22}c{21}+a{02}b{22}c{22}$`

矩阵其他3个位置为 0 。可见规范化因子恰好等于所有路径的非规范化概率之和。

3. 条件随机场的概率计算问题

• 给定条件随机场

，输入序列

，输出序列

• 计算条件概率

以及相应数学期望

类似HMM，引进前向-后向向量进行计算。

3.1 前向-后向算法

对每个位置

，定义前向向量

：

`$\alpha_0(y|x)=\left{

\begin{aligned}

1, \quad y=start\

0, \quad\quad\quad 否则

\end{aligned}

\right.

$`

递归公式：

又可以表示为：

表示在位置

的标记是

并且从 1 到

的前部分标记序列的非规范化概率，

可取的值有

个，所以

是

维列向量，

表示转置。

同样，对每个位置

，定义后向向量

：

`$\beta{n+1}(y{n+1}|x)=\left{

\begin{aligned}

1, \quad y_{n+1}=stop\

0, \quad\quad\quad\quad 否则

\end{aligned}

\right.

$`

又可以表示为：

表示在位置

的标记是

并且从

到

的后部分标记序列的非规范化概率。

3.2 概率计算

根据前后向向量的定义，可知：

`$

P(Y_i = y_i|x) = \frac{\alpha_i^T(y_i|x) \beta_i(y_i|x)}{Z(x)}\

P(Y{i-1}=y{i-1},Yi = 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)}\

其中，Z(x) = \alpha_n^T(x)\mathbf{1} = \mathbf{1}\beta_1(x),\mathbf{1}是元素均为1的m维列向量。

$`

3.3 期望值的计算

• 特征函数

关于条件分布

的数学期望

`$\begin{aligned}

E{P(Y|X)}f_k &= \sum{y}P(y|x)f_k(y,x)\

&= \sum{y}P(y|x)\sum{i=1}^{n+1} fk(y{i-1},y_i,x,i)\

&= \sum{i=1}^{n+1}\sum{y{i-1}y_i}f_k(y{i-1},yi,x,i)P(Y{i-1}=y_{i-1},Y_i=y_i|x)\

&= \sum{i=1}^{n+1}\sum{y{i-1}y_i}f_k(y{i-1},yi,x,i)\frac{\alpha{i-1}^T(y{i-1}|x)M_i(y{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\

\end{aligned}$`

其中，

，

• 假设边缘分布

的经验分布为

，特征函数

关于联合分布

的数学期望：

`$\begin{aligned}

E{P(X,Y)}f_k &= \sum{x,y}P(x,y)f_k(y,x)\

&= \sumx\tilde P(x) \sum{y}P(y|x)\sum{i=1}^{n+1} f_k(y{i-1},y_i,x,i)\

&= \sumx\tilde P(x)\sum{i=1}^{n+1}\sum{y{i-1}yi}f_k(y{i-1},yi,x,i)\frac{\alpha{i-1}^T(y{i-1}|x)M_i(y{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}

\end{aligned}$`

其中，

，

通过一次前向扫描计算

，一次后向扫描计算

，可以计算所有的概率、特征的期望

4. 条件随机场的学习算法

学习方法包括极大似然估计和正则化的极大似然估计。

具体的优化实现算法有改进的迭代尺度法IIS、梯度下降法、拟牛顿法。

看不懂（跳过）

5. 条件随机场的预测算法

给定条件随机场

和观测序列

，求条件概率最大的状态序列

。与 HMM 类似，使用维特比算法。

由式

可得：

`$

\begin{aligned}

y^* &= \argmaxy P\omega(y|x)\

&= \argmaxy \frac{\exp (\omega \cdot F(y,x))}{Z\omega(x)}\

&= \argmax_y \exp(\omega \cdot F(y,x))\

&= \argmax_y (\omega \cdot F(y,x))

\end{aligned}

$`

• 预测问题变成求非规范化概率最大的最优路径问题：

其中：

`$

\begin{aligned}

\omega &= (\omega_1,\omega_2,...,\omega_K)^T\

F(y,x) &= (f_1(y,x),f_2(y,x),...,f_K(y,x))^T\

fk(y,x) &= \sum\limits{i=1}^nfk(y{i-1},y_i,x,i),\quad k=1,2,...,K

\end{aligned}

$`

最优路径问题：

其中，

是局部特征向量

维特比算法：

• 先求出位置 1 的各个状态

的非规范化概率：

• 求出到位置

的各个状态

的非规范化概率的最大值，同时记录最大路径

• 到

时终止，求得非规范化概率最大值

，最优路径终点

• 由最优路径终点返回，

• 求得最优路径

例题

设有一标注问题：输入观测序列

，输出标记序列

，

取值于

.

假设特征

和对应权值

如下：

`$

\begin{aligned}

t1&=t_1(y{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\

t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\

t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\

t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\

t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\

s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\

s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\

s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\

s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5

\end{aligned}

$`

求给定的观测序列

对应的最优标记序列

。

解：

• 初始化

`$\delta_1(j) = \omega \cdot F_1(y_0 = start, y_1 = j, x), \quad j=1,2 \quad \quad \quad \quad \quad \quad \quad \quad \

i=1, \quad \delta_1(1) = \mu_1s_1=1,\quad \delta_1(2) = \mu_2s_2 = 0.5 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $`

• 递推

`$

\begin{aligned}

i=2\quad \delta_2(l) &=\max\limits_j {\delta_1(j) + \omega \cdot F_2(j,l,x)}\

\delta_2(1) &= \max{1+\lambda_2t_2 + \mu_3s_3,\quad 0.5+\lambda_4t_4 + \mu_3s_3} = \max{2.4,2.3} = 2.4\

&\quad\Psi_2(1) = 1\

\delta_2(2) &= \max{1+\lambda_1t_1 + \mu_2s_2,\quad 0.5+ \mu_2s_2} = \max{2.5,1} = 2.5\

&\quad\Psi_2(2) = 1\

i=3 \quad \delta_3(l) &=\max\limits_j {\delta_2(j) + \omega \cdot F_3(j,l,x)}\

\delta_3(1) &= \max{2.4+ \mu_3s_3,\quad 2.5+\lambda_3t_3 + \mu_3s_3} = \max{3.2,4.3} = 4.3\

&\quad\Psi_3(1) = 2\

\delta_3(2) &= \max{2.4+\lambda_1t_1 + \mu_4s_4,\quad 2.5+\lambda_5t_5 + \mu_4s_4} = \max{3.9,3.2} = 3.9\

&\quad\Psi_3(2) = 1\

\end{aligned}

$`

• 终止

`$

\max\limits_y(\omega \cdot F(y,x)) = \max \delta_3(l) = \delta_3(1) = 4.3\

y_3^* = \argmax\limits_l \delta_3(l) = 1$`

• 返回

`$y_2^ = \Psi_3(y_3^) = \Psi_3(1) = 2\

y_1^ = \Psi_2(y_2^) = \Psi_2(2) = 1

$`

所以最优状态序列为

例题python代码

# -*- coding:utf-8 -*-
# Python 3.7
# @Time: 2020/2/6 20:42
# @Author: Michael Ming
# @Website: https://michael.blog.csdn.net/
# @File: ConditionalRandomField_viterbi.py
import numpy as np


def viterbi(s, t):
    time = len(s)
    y_state = [0, 1]  # 表示状态 1，2
    m = len(y_state)  # 状态数量
    y_star = np.zeros((time), dtype=np.int32)  # 最优路径
    delta = np.zeros((time, m))  # 最大概率矩阵(可以DP状态压缩)
    psi = np.zeros((time, m), dtype=np.int32)  # 记录最优路径

    # 初始化delta
    delta[0][0] = s[0][0]
    delta[0][1] = s[0][1]

    # 递推
    for i in range(1, time):
        for j in range(m):
            temp = [delta[i - 1][k] + s[i][j] + t[i][k][j] for k in range(m)]
            # i表示时间，从k状态转移到j状态
            psi[i][j] = np.argmax(temp)  # 返回最大值的下标
            delta[i][j] = temp[psi[i][j]]  # 最大的概率填入

    # 终止
    y_star[time - 1] = np.argmax(delta[time - 1])

    # 返回
    for i in range(time - 2, -1, -1):
        y_star[i] = psi[i + 1][y_star[i + 1]]
    return y_star, delta, psi


def crf_viterbi():
    # 状态特征
    s = np.array([[1, 0.5],
                  [0.8, 0.5],
                  [0.8, 0.5]])
    # 转移特征
    t = np.array([[[0, 0],
                   [0, 0]],  # 辅助，使得后面序号方便
                  [[0.6, 1],
                   [1, 0]],
                  [[0, 1],
                   [1, 0.2]]])
    y_star, delta, psi = viterbi(s, t)

    print("最优路径:", y_star + 1)  # +1表示所有的都+1，序号从1开始
    print("概率矩阵：\n", delta)
    psi[1:] += 1  # 序号从1开始，第0行没用
    print("Psi路径：\n", psi)


if __name__ == '__main__':
    crf_viterbi()

运行结果，与上面一致。

最优路径: [1. 2. 1.]
概率矩阵：
 [[1.  0.5]
 [2.4 2.5]
 [4.3 3.9]]
Psi路径：
 [[0 0]
 [1 1]
 [2 1]]

Process finished with exit code 0