理解条件随机场

Submitted by huzhenda on Sat, 07/14/2018 - 11:47
linear-CRF

        条件随机场(conditional random fields,简称 CRF),是一种判别式概率模型,是给定一组输入序列条件下另一组输出序列的条件概率分布模型,常用于标注或分析序列资料。

1、哪些问题需要用到CRF模型

         我们以自然语言处理中的词性标注(POS Tagging)作为例子。词性标注的目标是给出一个句子中每个词的词性(名词,动词,形容词等)。而这些词的词性往往和上下文词的词性有关,因此,使用CRF来处理是很适合的。

2、从随机场到马尔可夫随机场

        首先,我们来介绍随机场。随机场是由若干个位置组成的整体,当给每一个位置中按照某种分布随机赋予一个值之后,其全体就叫做随机场。以词性标注为例:假如我们需要对一个包含十个词的句子做词性标注。这十个词每个词的词性可以在我们已知的词性集合(名词,动词...)中选择。当我们为每个词选择完词性后,这就形成了一个随机场。

        接下来我们再来看看马尔可夫随机场。马尔可夫随机场是随机场的特例,它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关,和与其不相邻的位置的赋值无关。在上个例子中,如果我们假设所有词的词性只和它相邻的词的词性有关时,这个随机场就特化成一个马尔可夫随机场。比如第四个词的词性除了与自己本身的位置有关外,只与第三个词和第五个词的词性有关。

3、从马尔可夫随机场到条件随机场

        理解了马尔可夫随机场,我们再来理解CRF。CRF是马尔可夫随机场的特例,它假设马尔可夫随机场中只有XY两种变量,X一般是给定的,Y是在给定X的条件下我们的输出。这样马尔可夫随机场就特化成了条件随机场。在本文的例子中,X是词,Y是词性。因此,如果我们假设它是一个马尔可夫随机场,那么它就是一个CRF。

        用数学语言描述,设XY是随机变量,P(Y|X)是给定XY的条件概率分布,若随机变量Y构成的是一个马尔可夫随机场,则称条件概率分布P(Y|X)是条件随机场。

4、从条件随机场到线性链条件随机场

        注意在CRF的定义中,我们并没有要求X和Y有相同的结构。而实现中,我们一般都假设XY有相同的结构,即:

                                                                         X=(X1,X2,...Xn), Y=(Y1,Y2,...Yn)

        我们一般考虑如下图所示的结构:XY有相同的结构的CRF就构成了线性链条件随机场(Linear chain Conditional Random Fields,简称 linear-CRF)。

1.1

        在我们词性标记的例子中,词有十个,词性也是十个。因此,如果我们假设它是一个马尔可夫随机场,那么它也就是一个linear-CRF。

        用数学语言描述,设X=(X1,X2,...Xn),Y=(Y1,Y2,...Yn)均为线性链表示的随机变量序列,在给定随机变量序列X的情况下,随机变量Y的条件概率分布P(Y|X)构成条件随机场,即满足马尔可夫性:

                                                                                   P(Yi|X,Y1,Y2,...Yn)=P(Yi|X,Yi−1,Yi+1)

  则称P(Y|X)为线性链条件随机场。

5、线性链条件随机场的参数化形式

  对于linear-CRF,我们将其转化为可以学习的机器学习模型,这是通过特征函数和其权重系数来定义的。

  在linear-CRF中,特征函数分为两类,第一类是定义在Y节点上的节点特征函数,这类特征函数只和当前节点有关,记为:

1.2

        其中L是定义在该节点的节点特征函数的总个数,i是当前节点在序列的位置。

  第二类是定义在Y上下文的局部特征函数,这类特征函数只和当前节点和上一个节点有关,记为:

1.3

        其中K是定义在该节点的局部特征函数的总个数,i是当前节点在序列的位置。之所以只有上下文相关的局部特征函数,没有不相邻节点之间的特征函数,是因为我们的linear-CRF满足马尔可夫性。

        无论是节点特征函数还是局部特征函数,它们的取值只能是0或者1,即满足特征条件或者不满足特征条件。同时,我们可以为每个特征函数赋予一个权值,用以表达我们对这个特征函数的信任度。假设t_k的权重系数是λ_k,s_l的权重系数是μ_l,则linear-CRF由我们所有的t_k,λ_k,s_l,μ_l共同决定。

  此时我们得到了linear-CRF的参数化形式如下:

1.4

       其中,Z(x)为规范化因子:

1.5

       回到特征函数本身,每个特征函数定义了一个linear-CRF的规则,则其系数定义了这个规则的可信度。所有的规则和其可信度一起构成了我们的linear-CRF的最终的条件概率分布。

6、线性链条件随机场的简化形式

        在上几节里面,我们用s_l表示节点特征函数,用t_k表示局部特征函数,同时也用了不同的符号表示权重系数,导致表示起来比较麻烦。其实我们可以对特征函数稍加整理,将其统一起来。

  假设我们在某一节点我们有K1个局部特征函数和K2个节点特征函数,总共有K=K1+K2个特征函数。我们用一个特征函数f_k(y_i−1,y_i,x,i)来统一表示如下:

1.6

        对f_k(y_i−1,y_i,x,i)在各个序列位置求和得到:

1.7

        同时我们也统一f_k(y_i−1,y_i,x,i)对应的权重系数w_k如下:

1.8

        这样,我们的linear-CRF的参数化形式简化为:

1.9

  其中,Z(x)为规范化因子:

1.10

         如果将上两式中的w_kf_k的用向量表示,即:

1.11

         则linear-CRF的参数化形式简化为内积形式如下:

1.12

7、线性链条件随机场实例

         这里我们给出一个linear-CRF用于词性标注的实例,为了方便,我们简化了词性的种类。假设输入的都是三个词的句子,即X=(X1,X2,X3),输出的词性标记为Y=(Y1,Y2,Y3),其中Y∈{1(名词),2(动词)}。

   这里只标记出取值为1的特征函数如下:

1.13

       求标记(1,2,2)的非规范化概率。

    利用linear-CRF的参数化公式,我们有:

1.14

       带入数值:

1.15

       (本文来自转载,更多内容见:https://www.cnblogs.com/pinard/p/7048333.html)