条件随机场

条件随机场

条件随机场(Conditional Random Field, CRF)是一种判别式无向图模型。生成式模型是直接对联合分布进行建模,而判别式模型则是对条件分布进行建模。条件随机场是给定随机变量 XX 条件下,随机变量 YY 的马尔可夫随机场。

XXYY 是随机变量, P(YX)P(Y|X) 是在给 XX 的条件下 YY 的条件概率分布。若随机变量 YY 构成一个无向图 G=(V,E)G = (V,E) 表示的马尔可夫随机场,即

P(YvX,Yw,wv)=P(YvX,Yw,wv)P(Y_v|X,Y_w,w\neq v) = P(Y_v|X,Y_w,w\sim v)

对任意结点 vv 成立,则称条件概率分布 P(YX)P(Y|X) 为条件随机场。式中 wvw\sim v 表示在图 G=(V,E)G=(V,E) 中与结点 vv 有边连接的所有结点 wwwvw\neq v 表示结点 vv 以外所有结点, Yv,Yu,YwY_v,Y_u,Y_w 为结点 v,u,wv,u,w 对应的随机变量。

链式条件随机场

这里主要介绍定义在线性链上的特殊的条件随机场,称为线性链条件随机场(Linear Chain Conditional Random Field)。线性链条件随机场可以用于标注问题。这时,在条件随机概率模型 P(YX)P(Y|X) 中, YY 是输出变量,表示标记序列, XX 是输入变量,表示需要标注的观测序列。也把标记序列称为状态序列。学习时,利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 P^(YX)\hat{P}(Y|X);预测时,对于给定的输入序列 xx ,求出条件概率 P^(yx)\hat{P}(y|x) 最大的输出序列 y^\hat{y}

X=(X1,X2,,Xn)X=(X_1,X_2,\dots,X_n)Y=(Y1,Y2,,Yn)Y = (Y_1,Y_2,\dots,Y_n) 均为线性链表示的随机变量序列,若在给定随机变量序列 XX 的条件下,随机变量序列 YY 的条件概率分布 P(YX)P(Y|X) 构成条件随机场,即满足马尔可夫性

P(YiX,Y1,,Yi1,Yi+1,,Yn)=P(YiX,Yi1,Yi+1)P(Y_i|X,Y_1,\dots,Y_{i-1},Y_{i+1},\dots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})

i=1,2,,n(i=1n时只考虑单边) i=1,2,\dots,n(在i=1和n时只考虑单边)

则称 P(YX)P(Y|X) 为线性链条件随机场。在标注问题中, XX 表示输入观测序列, YY 表示对应的输出标记序列或状态序列。

请看第一张概率图模型构架图,CRF上面是马尔科夫随机场(马尔科夫网络),而条件随机场是在给定的随机变量 X (具体,对应观测序列 o_{1}, \cdots, o_{i} )条件下,随机变量 Y (具体,对应隐状态序列 i_{1}, \cdots, i_{i} 的马尔科夫随机场。 广义的CRF的定义是: 满足 P(Y_{v}|X,Y_{w},w \neq v) = P(Y_{v}|X,Y_{w},w \sim v) 的马尔科夫随机场叫做条件随机场

不过一般说CRF为序列建模,就专指CRF线性链(linear chain CRF):

概率无向图的联合概率分布可以在因子分解下表示为:

而在线性链CRF示意图中,每一个( I_{i} \sim O_{i} )对为一个最大团,即在上式中 c = i 。并且线性链CRF满足 P(I_{i}|O,I_{1},\cdots, I_{n}) = P(I_{i}|O,I_{i-1},I_{i+1})

所以CRF的建模公式如下:

我要敲黑板了,这个公式是非常非常关键的,注意递推过程啊,我是怎么从 ∏ 跳到 e^{\sum}

不过还是要多啰嗦一句,想要理解CRF,必须判别式模型的概念要深入你心。正因为是判别模型,所以不废话,我上来就直接为了确定边界而去建模,因为我创造出来就是为了这个分边界的目的的。比如说序列求概率(分类)问题,我直接考虑找出函数分类边界。所以才为什么会有这个公式。所以再看到这个公式也别懵逼了,he was born for discriminating the given data from different classes. 就这样。不过待会还会具体介绍特征函数部分的东西。除了建模总公式,关键的CRF重点概念在MEMM中已强调过:判别式模型特征函数

特征函数

上面给出了CRF的建模公式:

  • 下标i表示我当前所在的节点(token)位置。

  • 下标k表示我这是第几个特征函数,并且每个特征函数都附属一个权重 \lambda_{k} ,也就是这么回事,每个团里面,我将为 token_{i} 构造M个特征,每个特征执行一定的限定作用,然后建模时我再为每个特征函数加权求和。

  • Z(O) 是用来归一化的,为什么?想想LR以及softmax为何有归一化呢,一样的嘛,形成概率值。

  • 再来个重要的理解。 P(I|O) 这个表示什么?具体地,表示了在给定的一条观测序列 O=(o_{1},\cdots, o_{i}) 条件下,我用CRF所求出来的隐状态序列 I=(i_{1},\cdots, i_{i}) 的概率,注意,这里的I是一条序列,有多个元素(一组随机变量),而至于观测序列 O=(o_{1},\cdots, o_{i}) ,它可以是一整个训练语料的所有的观测序列;也可以是在inference阶段的一句sample,比如说对于序列标注问题,我对一条sample进行预测,可能能得到 P_{j}(I | O)(j=1,…,J)J条隐状态I,但我肯定最终选的是最优概率的那条(by viterbi)。这一点希望你能理解。

对于CRF,可以为他定义两款特征函数:转移特征&状态特征。 我们将建模总公式展开:

其中:t_{j} 为i处的转移特征,对应权重 \lambda_{j} ,每个 token_{i} 都有J个特征,转移特征针对的是前后token之间的限定。举个例子:

sl为i处的状态特征,对应权重μl,每个tokeni都有L个特征。举个例子:

不过一般情况下,我们不把两种特征区别的那么开,合在一起:

满足特征条件就取值为1,否则没贡献,甚至你还可以让他打负分,充分惩罚。

再进一步理解的话,我们需要把特征函数部分抠出来:

是的,我们为 token_{i} 打分,满足条件的就有所贡献。最后将所得的分数进行log线性表示,求和后归一化,即可得到概率值……完了又扯到了log线性模型。现在稍作解释:

log-linear models take the following form:

P(y|x;\omega) = \frac{ exp(\omega·\phi(x,y)) }{ \sum_{y^{'}\in Y }exp(\omega·\phi(x,y^{‘})) }

我觉得对LR或者sotfmax熟悉的对这个应该秒懂。然后CRF完美地满足这个形式,所以又可以归入到了log-linear models之中。

模型运行过程

模型的工作流程,跟MEMM是一样的:

  • step1. 先预定义特征函数  f_{a}(o,i)

  • step2. 在给定的数据上,训练模型,确定参数 \lambda_{k}

  • step3. 用确定的模型做序列标注问题或者序列求概率问题

1. 学习训练过程

一套CRF由一套参数λ唯一确定(先定义好各种特征函数)。

同样,CRF用极大似然估计方法、梯度下降、牛顿迭代、拟牛顿下降、IIS、BFGS、L-BFGS等等。各位应该对各种优化方法有所了解的。其实能用在log-linear models上的求参方法都可以用过来。

2. 序列标注过程

还是跟HMM一样的,用学习好的CRF模型,在新的sample(观测序列 o_{1}, \cdots, o_{i} )上找出一条概率最大最可能的隐状态序列 i_{1}, \cdots, i_{i}

只是现在的图中的每个隐状态节点的概率求法有一些差异而已,正确将每个节点的概率表示清楚,路径求解过程还是一样,采用viterbi算法。

啰嗦一下,我们就定义i处的局部状态为 \delta_{i}(I) ,表示在位置i处的隐状态的各种取值可能为I,然后递推位置i+1处的隐状态,写出来的DP转移公式为:

这里没写规范因子 Z(O) 是因为不规范化不会影响取最大值后的比较。

3. 序列求概率过程

跟HMM举的例子一样的,也是分别去为每一批数据训练构建特定的CRF,然后根据序列在每个MEMM模型的不同得分概率,选择最高分数的模型为wanted类别。

Source

Last updated