条件随机场

CRF

Posted by Wwt on April 14, 2017

随机场

​ 随机场是一个随机推广过程的推广,使得底层的参数不再是一个简单的实数或整型“时间”,而是多维向量或点。在离散的情况下,随机场可以被认为是一组被确定在某个空间(如n维欧几里得空间)的离散点(随机数)列表。在统计学中,随机场可以看成一组随机变量的集合,而这组随机变量对应同一个样本空间。当然,这些随机变量之间常有某种依赖关系,一般来说,也只有当这些变量之间有依赖关系的时候,我们将其单独拿出来看成一个随机场才有实际意义。

​ 因此,确定一个随机场有如下重要的要素。第一,随机过程包含了哪些不同的样本空间;第二,样本空间中的随机变量相互之间形成何种依赖关系(换个角度讲,就是条件独立的关系)。这两个因素是构成“随机场”的基本要件。

​ 随机场包含如下两个要素:样本空间集合和单个样本空间中的随机变量集合。

​ 我么不妨拿种地来打个比方。“不同分布的样本空间”好比一亩亩农田;“相互依赖的随机变量”好比种的各种庄稼,这就好比给随机场的每个“样本空间”里赋予不同取值范围的随机变量。通俗一点地讲,随机场就是在哪块地里种什么庄稼的事情。

​ 求解一个随机场,就是要找到有多少种不同的样本空间,以及其中随机变量的概率分布。

马尔可夫随机场

​ 马尔科夫随机场是典型的马尔科夫网,这是一种著名的无向图模型。图中每个节点表示一个或一组变量,结点之间的边表示两个变量之间的依赖关系。马尔科夫随机场有一组势函数,亦称为“因子”,这是定义在变量子集上非负实函数,主要用于定义概率分布函数。

​ 图-1显示出一个简单的马尔科夫随机场。对于图中结点的一个子集,若其中任意两点间都有边连接线,则称该结点子集为一个“团”。若在一个团中加入另外任何一个节点都不再形成团,则称该团为“极大团”;换言之,极大团就是不再被其他团所包含的团。例如在图-1中,{x1,x2},{x1,x3},{x2,x4},{x2,x5},{x2,x6},{x3,x5},{x5,x6}和{x2,x5,x6}都是团,并且除了{x2,x5},{x2,x6}和{x5,x6}之外都是极大团;但是,因为x2和x3之间缺乏连接,{x1,x2,x3}并不构成团。显然,每个节点至少出现在一个极大团中。

3

​ 图-1 一个简单的马尔科夫随机场

​ 在马尔科夫随机场中,多个变量之间的联合概率分布能基于团分解为多个因子的乘积,每个因子仅于一个团相关。具体来说,对于n个变量$x={x_1,x_2···x_n}$,所有团构成的集合为C,与团$Q∈C$对应的变量集合记为$x_Q$,则联合概率p(x)定义为

式-1

​ 其中$ψ_Q$为与团Q对应的势函数,用于对团Q中的变量关系进行建模,$ Z= \sum_x ∏_{Q∈C}ψ_Q(x_Q)$为规范化因子,以确保P(x)是被正确定义的概率。在实际应用中,精确计算Z通常很困难,但许多任务往往并不需获得Z的精确值。

条件随机场

​ 条件随机场(Confitional Random Field,简称CRF)是一种判别式无向图模型,生成模型是直接对联合分布进行建模,而判别式模型则是对条件分布进行建模。隐马尔科夫和马尔科夫随机场都是生成式模型,而条件随机场则是判别式模型。

​ 条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说,若令$x={x_1,x_2···x_n}$为观察序列,$y={y_1,y_2···y_n}$为与之相应的标记序列。则条件随机场的目标是构建条件概率模型$P(y \mid x)$。需要注意的是,标记变量y可以是结构型变量,即分量之间具有某种相关性。例如在自然语言处理的词性标注任务中,观测数据为语句(即单词序列),标记为相应的词性序列,具有线性序列结构。如图-2所示。

2

​ 图-2

​ 令$G=<V,E>$表示结点与标记变量y中元素一一对应的无向图,$y_v$表示与结点v对应的标记变量,$n(v)$表示结点v的邻接结点,若图G的每个变量$y_v$都满足马尔科夫性,即

,

则$(y,x)$构成一个条件随机场

​ 理论上来说,图G可具有任意结构,只要能表示标记变量之间的条件独立性关系即可。但在现实应用中,尤其是对标记序列建模时,最常用的仍是图-3所示的链式结构,即“链式条件随机场”。下面我们主要讨论这种条件随机场。

1

​ 图-3链式条件随机场的图结构

链式条件随机场

​ 与马尔科夫随机场定义联合概率的方式类似,条件随机场使用势函数和图结构上的团来定义条件概率$P(y \mid x)$。给定观测序列x,图-3所示的链式条件随机场主要包含两种关于标记变量的团,即单个标记变量${y_i}$以及相邻的标记变量${y_{i-1},y_i}$。选择合适的势函数,即可得到形如式-1的条件概率定义。在条件随机场中,通过选用指数势函数并引入特征函数,条件概率被定义为

式-2

其中$t_j(y_{i+1},y_i,x,i)$是定义在观测序列的两个相邻标记位置上转移特征函数,用于刻画相邻标记变量之间的相关关系以及观测序列对它们的影响,$δ_k(y_i,x,i)$是定义在观测序列的标记位置i上的状态特征函数,用于刻画观测序列对标记变量的影响,$λ_j$和$υ_k$为参数,Z为规划化因子,用于确保式-2是正确定义的概率。

​ 显然要是用条件随机场,还需定义合适的特征函数。特征函数通常是实值函数,以刻画数据的一些很可能成立或期望成立的经验特性。以图-1所示的词性标注任务为例,若采用转移特征函数

则表示第i个观测值$x_i$为单词’knock’时,相应的标记$y_i$和$y_{i+1}$很可能分别为[v]和[P]。若采用状态特征函数

则表示观测值$x_i$为单词’knock’时,它所对应的标记很可能成为[v]。

Viterbi预测算法

​ 条件随机场的预测问题是给定义条件随机场$P(y \mid x)$和输入序列(观测序列)x,求条件概率最大的输出序列(标记序列)y*,即对观测序列进行标注。

于是,条件随机场的预测问题成为求非规范化概率最大的最优路径问题

根据维特比算法进行求解

条件随机场预测的维特比算法

输入:模型特征向量$F(x,y)$和权值向量w,观测序列$x=(x_1,x_2···,x_n)$

输出:最优路径

(1)初始化

(2)递推,对i=1,2,3,···n

(3)终止

λ

(4)返回路径

求最优路径

例子

设有一标注问题:输入观测序列为$x=(x_1,x_2,x_3)$,输出标记序列为$y=(y_1,y_2,y_3)$,$y_1,y_2,y_3$取值为1,2。

假设特征函数$t_j,s_k$和对应的权值$λ_j,μ_k$如下:

以$t_1$为例,其他特征函数类似:

现用维特比算法求解最可能的标记序列: 1.初始化

2.递推

3.终止

4.返回

所以最优标记序列为

参考

机器学习

条件随机场(CRF)-4-学习方法和预测算法(维特比算法)