CRF 条件随机场概述

哈哈哈没错就是我,我我我又跑过来开新坑了,今天来和大家唠唠CRF的那点事儿.

条件随机场(conditional random field, CRF)

我们用CRF来做什么?

可以用于构造在给定一组输入随机变量的条件下,另一组输出随机变量的条件概率分布模型.

在开始之前

概率无向图

即马尔可夫随机场,是一个用无向图表示的联合概率分布.
- 定义: 图(graph) 是由 节点(node) 与 边(edge) 组成的集合,我们记节点为 $v$ ,记边为 $e$ ,将节点和边所处的集合分别置为
  $V$ 与 $E$ ,相应的,我们把该图记作 $G=(V,E)$ ,设由 $G$ 表示联合概率分布 $P(Y)$ ,在图 $G$ 中,每一个节点 $v∈V$ 都表示一个随机变量 $Y_v$ , $Y=(Y_v)_{v∈V}$ ,而与之对应的, $e∈E$ 则表示了随机变量之间的概率依赖关系.
- 三个性质:
  - 成对马尔可夫性:
    $P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)$
  - 局部马尔可夫性:
    $P(Y_u,Y_W|Y_O)=P(Y_u|Y_O)P(Y_W|Y_O)$
  - 全局马尔可夫性:
    $P(Y_M,Y_W|Y_O)=P(Y_M|Y_O)P(Y_W|Y_O)$
  显然成对,局部,全局马尔可夫性质都是等价的ww
- 我们可以说:
  - 如果联合概率分布图 $P(Y)$ 满足成对、局部或全局马尔可夫性,则我们可以称此联合概率分布为概率无向图模型或者马尔可夫随机场.
- 概率无向图因子分解:
  
  无向图模型实例.jpg
  - 最大团: 如上图 ${Y_1,Y_2,Y_3}$ 构成一个最大团,该最大团的特点是,从图上的各个其他节点当中,任选一个节点,都不可能同时存在与 $Y_1,Y_2,Y_3$ 的关系,这样的团(clique)我们称之为最大团(maximal clique).
  - 无向图会满足如下性质:
    $P(Y)=\frac {1} {Z}\prod_C \Psi_C(Y_C)$
    
    其中,C代表一个最大团, $Y_C$ 表示C对应的随机变量.
    
    $Z=\sum_Y \prod_C\Psi_C(Y_C)$
    
    我们通常称 $\Psi_C(Y_C)$ 为势函数,我们这里要求势函数 $\Psi_C(Y_C)$ 是严格正项.
    
    $\Psi_C(Y_C)=exp\{-E(Y_C)\}$
    
    这里我们用指数的形式来表达是因为指数函数良好的性质.
  - Hammersley-Clifford 定理
    - 概率无向图模型的联合概率分布 $P(Y)$ 可以表示为如下形式:
      $P(Y)=\frac{1}{Z} \prod_C \Psi_C(Y_C)$
      $Z=\sum_Y \prod_C \Psi_C (Y_C)$
    其中,C是无向图的最大团, $Y_C$ 是 $C$ 的节点对应的随机变量, $\Psi_C(Y_C)$ 是 $C$ 上定义的严格整函数,乘积在无向图所有的最大团上进行.

条件随机场的基础表达

条件随机场(conditional random field)是给定随机变量 $X$ 条件下,随机变量 $Y$ 的马尔可夫随机场.这里我们主要介绍定义在线性链上的特殊条件随机场,我们称之为线性链马尔可夫随机场(linear chain conditional random field).在该条件概率模型 $P(Y|X)$ 中, $Y$ 是输出变量,表示标记序列,即状态序列, $X$ 是输入变量,也就是我们得到的需要标注的观测序列.研究学习问题时,我们利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 $\hat P(Y|X)$ ,在研究预测问题时,我们根据给定的输入序列 $x$ ,求出条件概率 $\hat P(y|x)$ 最大的输出序列 $\hat y$ .
条件随机场的成立条件: 设 $X$ 与 $Y$ 是随机变量, $P(Y|X)$ 是在给定 $X$ 的条件下 $Y$ 的条件概率分布.若随机变量 $Y$ 构成一个由无向图 $G=(V,E)$ 表示的马尔可夫随机场,即
$P(Y_v|X,Y_w,w \ne v)=P(Y_v|X,Y_w,w~v)$
对任意结点 $v$ 成立,则称条件概率分布 $P(Y|X)$ 为条件随机场,式中 $w~v$ 表示在图 $G=(V,E)$ 中与结点 $v$ 有边链接的所有结点 $w$ , $w \ne v$ 表示结点 $v$ 以外的所有节点, $Y_v,Y_u,Y_w$ 为结点 $v,u,w$ 分别对应的随机变量.
线性链条件随机场: 设 $X=(X_1,X_2,...,X_n)$ , $Y=(Y_1,Y_2,...,Y_n)$ 均为线性链表示的随机变量序列,若在给定的随机变量序列 $X$ 的条件下,随机变量序列 $Y$ 的条件概率分布 $P(Y|X)$ 构成条件随机场,即满足马尔可夫性
$P(Y_i|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$ 时只考虑单边)
则称 $P(Y|X)$ 为线性链条件随机场,在标注问题中, $X$ 表示输入观测序列, $Y$ 表示对应的输出标记序列,或者我们可以称之为状态序列.

线性链条件随机场.png

X和Y具有相同图结构的线性链条件随机场.png

条件随机场的参数化形式:
$P(y|x)=\frac {1} {Z(x)} exp(\sum _{i,k} \lambda _k t_k(y_{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i))$

其中, $t_k,s_l$ 是特征函数, $\lambda_k,\mu_l$ 是对应的权值,而 $Z(x)$ 是规范化因子.

$Z(x)=\sum _y exp(\sum _{i,k} \lambda _k t_k(y_{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i)$
- 其中 $t_k$ 是定义在边上的特征函数,我们称之为转移特征,它同时依赖于当前位置和上一个位置.
- 而 $s_t$ 是定义在节点上的特征函数,我们称之为状态特征,它仅仅依赖于当前位置.
- 以上两个变量都依赖于位置属于局部特征,在满足条件时它们的取值为1,不满足条件时,它们的取值为0.
条件随机场的简化形式:为了方便记录起见,我们将转移特征和状态特征及其权值用统一的符号来表示.设有 $K_1$ 个转移特征, $K_2$ 个状态特征, $K=K_1+K_2$ ,记:

相应的我们把和写为如下格式:

权值对应的统一符号:

条件随机场对应的概率表达:

w表示权值向量:

$F(y,x)$ 表示全局特征向量:

我们可以对应地把条件随机场写成向量 $w$ 与 $F(y,x)$ 的内积的形式:

与之对应的归一化参数 $Z_w(x)$
条件随机场的矩阵形式:
对于观测序列 $x$ 的每一个位置我们都定义一个 $m$ 阶矩阵( $m$ 是标记 $y_i$ 的取值的个数):

矩阵化表示

这样一来,对于给定的观测序列 $x$ ,标记序列 $y$ 的非规范化概率可以通过 $n+1$ 个矩阵的乘积 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 来表示,于是,条件概率 $P_w(y|x)$ 就是:

其中 $Z_w(x)$ 为规范化因子,是 $n+1$ 个矩阵的乘积的 $( start,stop )$ 元素:

$y_0=start$ 与 $y_{n+1}=stop$ 表示开始状态与结束状态,规范化因子是这期间所有的概率矩阵的乘积.

CRF的概率计算问题

前向-后向算法:对于每个指标 $i=0,1,...,n+1$ ,定义前向向量 $\alpha_i(x)$ :

递推公式为:

终结项为:

同理可知我们的后向向量 $\beta_i(x)$ :

递推公式:

终结项:

由此我们可得出如下关系:

在已知前向后向序列时的条件概率运算:

其中:
期望值计算:

其中:

特征函数 $f_k$ 关于联合分布 $P(X,Y)$ 的数学期望是:

其中: