条件随机场CRF

作者: mmmwhy | 来源:发表于2018-07-28 20:48 被阅读210次

CRF
NLP入门（八）使用CRF++实现命名实体识别(NER)
条件随机场CRF
CRF（条件随机场）
CRF条件随机场
CRF条件随机场
条件随机场（CRF）
条件随机场(CRF)
条件随机场（CRF）
CRF 条件随机场

条件随机场（conditional random field，简称 CRF），是一种鉴别式机率模型，是随机场的一种，常用于标注或分析序列资料，如自然语言文字或是生物序列。更多见 iii.run

介绍

先上张著名的图 HMM vs CRF

89289-8p01mnj7au.png

从随机场到马尔科夫随机场

首先，我们来看看什么是随机场。

“随机场”的名字取的很玄乎，其实理解起来不难。

随机场是由若干个位置组成的整体，当给每一个位置中按照某种分布随机赋予一个值之后，其全体就叫做随机场。

还是举词性标注的例子：假如我们有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在我们已知的词性集合（名词，动词...)中去选择。当我们为每个词选择完词性后，这就形成了一个随机场。

马尔科夫随机场是随机场的特例，它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。

从随机场到马尔科夫随机场

对于CRF，我们给出准确的数学语言描述：

设X与Y是随机变量， $P(Y|X)$ 是给定 $X$ 时 $Y$ 的条件概率分布，若随机变量 $Y$ 构成的是一个马尔科夫随机场，则称条件概率分布 $P(Y|X)$ 是条件随机场

理解了马尔科夫随机场，再理解CRF就容易了。CRF是马尔科夫随机场的特例，它假设马尔科夫随机场中只有 $X$ 和 $Y$ 两种变量， $X$ 一般是给定的，而 $Y$ 一般是在给定 $X$ 的条件下我们的输出。

这样马尔科夫随机场就特化成了条件随机场。在我们十个词的句子词性标注的例子中， $X$ 是词， $Y$ 是词性。因此，如果我们假设它是一个马尔科夫随机场，那么它也就是一个CRF。

从马尔科夫随机场到条件随机场

注意在CRF的定义中，我们并没有要求X和Y有相同的结构。而实现中，我们一般都假设X和Y有相同的结构，即:
$X =(X_1,X_2,...X_n),\;\;Y=(Y_1,Y_2,...Y_n)$

$X$ 和 $Y$ 有相同的结构的CRF就构成了线性链条件随机场(Linear chain Conditional Random Fields,以下简称 linear-CRF)。

linear-CRF的数学定义：

设 $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_2,...Y_n) = P(Y_i|X,Y_{i-1},Y_{i+1})$

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

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

对于上一节讲到的linear-CRF，我们如何将其转化为可以学习的机器学习模型呢？这是通过特征函数和其权重系数来定义的。什么是特征函数呢？

节点特征函数

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

$s_l(y_i, x,i),\;\; l =1,2,...L$

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

局部特征函数

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

$t_k(y_{i-1},y_i, x,i),\;\; k =1,2,...K$

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

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

解释一下

举个例子，比如有这么一个句子

68518-7ntofv56k9.png

特征样例：

30157-zm62ptxjkqo.png

所以 $t_k$ 和 $s_k$ 是这么来的

linear-CRF的参数化形式

$P(y|x) = \frac{1}{Z(x)}exp\Big(\sum\limits_{i,k} \lambda_kt_k(y_{i-1},y_i, x,i) +\sum\limits_{i,l}\mu_ls_l(y_i, x,i)\Big)$

其中， $Z(x)$ 为规范化因子：
$Z(x) =\sum\limits_{y} exp\Big(\sum\limits_{i,k} \lambda_kt_k(y_{i-1},y_i, x,i) +\sum\limits_{i,l}\mu_ls_l(y_i, x,i)\Big)$

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

举例

假设输入的都是三个词的句子，即 $X=(X_1,X_2,X_3)$
输出的词性标记为 $Y=(Y_1,Y_2,Y_3)$ , 其中 Y∈{1(名词)，2(动词)}
$t_1 =t_1(y_{i-1} = 1, y_i =2,x,i), i =2,3,\;\;\lambda_1=1$
$t_2 =t_2(y_1=1,y_2=1,x,2)\;\;\lambda_2=0.6$
$t_3 =t_3(y_2=2,y_3=1,x,3)\;\;\lambda_3=1$
$t_4 =t_4(y_1=2,y_2=1,x,2)\;\;\lambda_4=1$
$t_5 =t_5(y_2=2,y_3=2,x,3)\;\;\lambda_5=0.2$
$s_1 =s_1(y_1=1,x,1)\;\;\mu_1 =1$
$s_2 =s_2( y_i =2,x,i), i =1,2,\;\;\mu_2=0.5$
$s_3 =s_3( y_i =1,x,i), i =2,3,\;\;\mu_3=0.8$
$s_4 =s_4(y_3=2,x,3)\;\;\mu_4 =0.5$

解释一下

t
$t_1 =t_1(y_{i-1} = 1, y_i =2,x,i), i =2,3,\;\;\lambda_1=1$
表示第2个或第3个观测值 $X_i$ 为x时，对应的标注y1和y2分别为名词和动词。
s
$s_2 =s_2( y_i =2,x,i), i =1,2,\;\;\mu_2=0.5$
表示第1个或第2个观测值 $X_i$ 为x时，它对应的标注很可能为动词，可能性为 0.5。
求标记(1,2,2)的最可能的标记序列。

位置1初始化

如果位置1是名词
$\delta_1(1) = \mu_1s_1 = 1$
如果位置1是动词
$\delta_1(2) = \mu_2s_2 = 0.5$
表示第一个位置，名词的概率为1，动词的概率为0.5。

注意，这里没有做 规范化处理，因为没啥必要，反正最后选最大的就行了。

这也符合我们的预期，一般动词做句首比较少。

$\Psi_{1}(1) =\Psi_{1}(2) = start$
因为这个问题是一个bp动态规划问题，所以我们需要一个参数来记住走过的路。

位置2

如果位置2是名词
$\delta_2(1) = max\{\delta_1(1) + t_2\lambda_2+\mu_3s_3, \delta_1(2) + t_4\lambda_4+\mu_3s_3 \} = max\{1+0.6+0.8,0.5+1+0.8\} =2.4\;\;\;\Psi_{2}(1) =1$
如果位置2是动词
$\delta_2(2) = max\{\delta_1(1) + t_1\lambda_1+\mu_2s_2, \delta_1(2) + \mu_2s_2\} = max\{1+1+0.5,0.5+0.5\} =2.5\;\;\;\Psi_{2}(2) =1$

位置2 的两种情况都是从位置1位名词的情况下转移过来的，

位置3

如果位置3是动词
$\delta_3(1) = max\{\delta_2(1) +\mu_3s_3, \delta_2(2) + t_3\lambda_3+\mu_3s_3\} = max\{2.4+0.8,2.5+1+0.8\} =4.3$

$\Psi_{3}(1) =2$

如果位置3是名词

$\delta_3(2) = max\{\delta_2(1) +t_1\lambda_1 + \mu_4s_4, \delta_2(2) + t_5\lambda_5+\mu_4s_4\} = max\{2.4+1+0.5,2.5+0.2+0.5\} =3.9$

$\Psi_{3}(2) =1$

结果

最终得 $y_3^* =\arg\;max\{\delta_3(1), \delta_3(2)\}$ , 然后倒退回去。
或者(1,2,1)，即标注为(名词，动词，名词)

要注意的是，每个位置的概率竟然是加起来的，不是乘起来的，怪不得Tensorflow做了那么妖娆的优化，将时间复杂度降到了 $O(n)$

CRF
条件随机场（CRF）的理解如何轻松愉快地理解条件随机场（CRF）？条件随机场(CRF)如何直观地理解条件随机场，并...
NLP入门（八）使用CRF++实现命名实体识别(NER)
CRF与NER简介 CRF，英文全称为conditional random field, 中文名为条件随机场，...
条件随机场CRF
条件随机场（conditional random field，简称 CRF），是一种鉴别式机率模型，是随机场的一种...
CRF（条件随机场）
CRF（条件随机场）构建步骤为了建一个条件随机场，我们首先要定义一个特征函数集，每个特征函数都以整个句子s，当...
CRF条件随机场
CRF和HMM，朴素贝叶斯一样都是概率图模型，概率图模型构建了这样的图，用观测结点表示观测到的数据，隐含结点表示潜...
CRF条件随机场
线性链条件随机场 DEFINITION ESTIMATION 损失函数为即对求导结果为关注一下是怎么得来的：解释：...
条件随机场（CRF）
Naive Byaes、HMM、CRF都是概率图模型，可以看做是一种递进的关系。 HMM中的两个假设：齐次Mar...
条件随机场(CRF)
《统计学习方法》Page196 例11.1 设有一标注问题：输入观测序列为，输出标记序列为，取值于，求标记序列为...
条件随机场（CRF）
参考： https://blog.csdn.net/qq_39526294/article/details/104...
CRF 条件随机场
在为一张照片分类时，必须将与它相邻的照片的标签信息考虑进来。 eg: 词性标注问题动词后面还是动词就是一个特征函...