概率图模型之CRF

$\newcommand{\x}{\mathbf{x}}$

第一次接触CRF的确很难理解,因为《统计自然语言处理》这本书上讲CRF一共就两页多一点,还有些概念没有铺垫就扔出来,所以读完依旧懵逼……

后来反复结合上下篇章,以及CRF论文,才明白CRF有很多的背景知识需要了解,如:马尔可夫网络马尔可夫性(Markov property)、团(clique)、PGM中无向图建模方法、团的势能函数(clique potential function)、判别模型等知识,以及CRF和HMM、MEMM的关系等,所以这里写一篇blog给自己整理一下思路。

马尔可夫网络

马尔可夫网络
也称作马尔可夫随机场(Markov random field, MRF),是一组有 马尔可夫性质 的随机变量的联合概率分布模型,它由一个 无向图 $G$和定义于$G$上的 势函数 组成。

无向图$G=(V, E)$,每个顶点$x_i\in V$ 表示集合$X$上的一个随机变量,每条边$\brace{ x_i,x_j} \in E \, (i\neq j)$ 表示直接相连的两个随机变量$x_i$和$x_j$之间的依赖关系。

无向图

无向图中的完全连通子图。比如,$\x_C=\brace{ x_1,x_2}$ 表示团$C$中的所有结点。
极大团
如果团中加入任意一个结点均不再是团。比如,$\brace{ x_1,x_2,x_3}$ 和 $\brace{ x_1,x_3,x_4}$ 都是极大团。

回忆一下贝叶斯网络和HMM的建模方法,采用条件概率来计算整个图的联合概率。但在无向图中,不用条件概率密度建模,而采用团势能(clique potentials)。

团势能
也称作团势能函数势函数,是定义在团上的非负实函数。一般定义为 $\phi(\x_C)=\exp(-E(\x_C))$,其中,$E(\x_C)$称作$\x_C$的能量函数(energy function)。
Hammersley-Clifford 定理
对$n$个随机变量$\brace{ x_1,x_2,\cdots,x_n}$组成的马尔可夫网络$G$,如果$C=\brace{ C_1,C_2,\cdots,C_K}$是$G$上极大团的集合,则$G$的联合分布可以用$C$的势函数$\phi(\x_c)$进行建模(因子化):

其中,$Z$是一个归一化常量,称为划分函数(partition function):

条件随机场

类似于HMM,CRF同样有两个序列(解决序列标注问题,比如分词、NER问题):

  • 观测序列 $X$,如已经分好的词序列
  • 标注序列 $Y$,如需要标注的实体序列

CRF通过直接定义条件概率$P(Y\vert X)$,而不是联合概率建模。

CRF定义:在MRF基础上,需要观察序列$X$为条件时,每一个随机变量$Y$都满足以下马尔可夫特性:

其中,$w\sim v$表示两个结点在图$G$里是邻接结点。意思就是某点的条件概率可以只用它的邻接结点来表示。

【注】马尔可夫性质包括pairwise/local/global三种逐渐增强的性质,简单来说,在无向图中,给定所有其他结点/邻接结点/分离集合结点的条件下,两部分不相邻的结点(随机变量)条件独立

一般都使用线性链式CRF,结构如图:

Linear-chain CRF

马尔可夫性质举例来说 $P(Y_2\vert X,Y_1,Y_3,\cdots,Y_n)=P(Y_2\vert X,Y_1,Y_3)$

参考MRF中团势能的定义,这里单个标注值$y_i$和观察序列$X$就构成一个极大团,团势能可以(人为)定义为:

符号说明:

  • $t_j(y_{i-1},y_i,X,i)$ 是转移函数(transition),表示对观测序列$X$的标注序列$Y$在$i$和$i-1$位置上标记的转移概率;
  • $s_k(y_i,X,i)$ 是状态函数(status),表示对观测序列$X$的标注序列$Y$在$i$位置的标记概率;
  • $\lambda_j$ 和 $\mu_k$ 分别是函数 $t_j$ 和 $s_k$ 的权重,需要从训练样本中估计。

对整个CRF建模:

其中,$Z$ 还是规范化因子,保证整个函数作为概率归一化到$(0,1)$之间。

参考最大熵模型,转移函数$t$和状态函数$s$都是(人为)定义出来的特征函数。

总之,CRF建模过程大概就是这样,这样捋一下可能看书更容易理解了。如果要实际使用可以参考CRF++

参考

  • 《统计自然语言处理》宗成庆
  • Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, J Lafferty, 2001
  • An Introduction to Conditional Random Fields, Charles Sutton, 2010 (照理说CRF只看这篇论文就够了,不过很长,90页……)