CRF

李宏毅课程-CRF

• 处理的问题：输入是序列(sequence)（），输出是序列（）

• Example Task: POS tagging （对句子中的每个词用相应的词性表明）

  • 输入是句子的各单词组成的序列，然后输出是各单词词性组成的序列

  • 困难：单词的词性必须知道整个句子的information，然后才能确定其词性，仅仅根据查表是不能实现的。

• OUTLINE
  

HMM

• HMM第一步：
  先生成一个基于语法标准的POS sequence（词性构成的语句）

  从start开始，然后之后每次选择都是概率性选择词性。

例如：%3D0.40.80.250.950.1#card=math&code=P%28%27%27PN%5C%3A%5C%3A%20V%20%5C%3A%5C%3AD%5C%3A%5C%3A%20N%27%27%29%3D0.4%2A0.8%2A0.25%2A0.95%2A0.1)

• HMM第二步：
  根据词典，对不同词性进行填写对应单词（也是概率性选择单词）
  

条件概率：%3D%5Cfrac%7BP(AB)%7D%7BP(B)%7D#card=math&code=P%28A%7CB%29%3D%5Cfrac%7BP%28AB%29%7D%7BP%28B%29%7D)

• 如何计算：
  

这里和一般的HMM不一样，因为一般HMM模型中，训练样本对应着一个可见的观测样本，一个是隐的马尔可夫链，这个隐马尔可夫链的状态是并不能像这个例子一样写出来，所以需要EM联合确定

• 如果给定一个句子X，求Y （从上面已知P(x, y)的求法）
  

• HMM存在的问题：概率之间存在相互关联，条件不独立
  

产生这种问题的原因是：HMM假定了transition probability和emission probability之间相互独立。实际上是不独立的。

• CRF在保证model和HMM一样，同时假设transition probability和emission probability之间相互独立。但是解决了以上的问题。

CRF

• 描述P(x,y)的方法：
  

• CRF与HMM本质是一样的，证明如下：
  

中的每一项都对应了一个概率值，但是实际中由训练获得，所以可能导致的值大于1（即概率大于1），显然这是不合理的，因此不能说%3Dexp(w%C2%B7%5Cphi(x%2Cy))#card=math&code=P%28x%2Cy%29%3Dexp%28w%C2%B7%5Cphi%28x%2Cy%29%29)而应该是#card=math&code=P%28x%2Cy%29)正比于)#card=math&code=exp%28w%C2%B7%5Cphi%28x%2Cy%29%29)

• Feature Vector
  
  

If there are |S| possible tags, |S| X|S|+ 2|S| dimensions

因此#card=math&code=%5Cphi%28x%2Cy%29)可以自己定义，限制性更小。

• Training Criterion
  

某一项的grad计算结果：

%3D%5Carg%20%5Cmax%7By%5Cin%20Y%7DP(x%2Cy)%3D%5Carg%5Cmax%7By%5Cin%20Y%7Dw%C2%B7%5Cphi(x%2Cy)#card=math&code=y%3D%5Carg%20%5Cmax%7By%5Cin%20Y%7DP%28y%7Cx%29%3D%5Carg%20%5Cmax%7By%5Cin%20Y%7DP%28x%2Cy%29%3D%5Carg%5Cmax_%7By%5Cin%20Y%7Dw%C2%B7%5Cphi%28x%2Cy%29)

可以由Viterbi algorithm实现

则对于整个w：
![](GMNN_CRF_Note/image-20211010085421300.png#alt=Training_all)

• summary
  

《统计学习方法》李航-CRF

马尔可夫随机场

• 概率图模型是由图表示的概率分布。设由联合分布#card=math&code=P%28Y%29)，Y是一组随机变量。由无向图#card=math&code=G%3D%28V%2CE%29)表示概率分布#card=math&code=P%28Y%29)，即图G中，结点表示一个随机变量，%7Bv%5Cin%20V%7D#card=math&code=Y%3D%28Y_v%29%7Bv%5Cin%20V%7D)；边表示随机变量之间的概率依赖关系。

• 如果想求联合分布#card=math&code=P%28Y%29)，需要给图添加约束，更容易求得。

• 成对马尔可夫性/局部马尔可夫性/全局马尔可夫性 本质是等价的，从不同视角看待

• 局部马尔可夫性 %3DP(Y_v%7CY_W)P(Y_O%7CY_W)%5Ctag%7B1-1%7D%0A#card=math&code=P%28Y_v%2CY_O%7CY_W%29%3DP%28Y_v%7CY_W%29P%28Y_O%7CY_W%29%5Ctag%7B1-1%7D%0A)

其中，设是无向图中任意一个结点，对应的随机变量是。是与有边连接的所有的结点，对应的随机变量组是。是以外的其他所有结点，对应的随机变量组是。
即给定随机变量组的条件下，随机变量和是条件独立的。

• 由概率乘积规则： %3DP(Y_v%7CY_O%2CY_W)P(Y_O%7CY_W)%5Ctag%7B1-2%7D%0A#card=math&code=P%28Y_v%2CY_O%7CY_W%29%3DP%28Y_v%7CY_O%2CY_W%29P%28Y_O%7CY_W%29%5Ctag%7B1-2%7D%0A)

由(1-1)与(1-2)得： %3DP(Y_v%7CY_W)%5Ctag%7B1-3%7D%0A#card=math&code=P%28Y_v%7CY_O%2CY_W%29%3DP%28Y_v%7CY_W%29%5Ctag%7B1-3%7D%0A)

即不影响，只有影响

• 满足马尔可夫性（三个之一）的随机场就是马尔可夫随机场

马尔可夫随机场的因子分解

• 团：无向图中任意两个结点均有边连接的结点子集。
  最大团：无向图中的一个团，并且不能再添加进任何一个结点使其成为一个更大的团。

• （Hammersley-Clifford定理）概率无向图模型的联合概率分布： %3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod_C%5CPsi_C(Y_C)%0A#card=math&code=P%28Y%29%3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod_C%5CPsi_C%28Y_C%29%0A)

其中是无向图的最大团，是的结点对应的随机变量；势函数#card=math&code=%5CPsi_C%28Y_C%29)是严格正的 %3D%5Cexp(-E(Y_C))%3D%5Cexp(%5Csum_k%5Clambda_kf_k%7B(C%2Cy%7CC%2Cx)%7D)%0A#card=math&code=%5CPsi_C%28Y_C%29%3D%5Cexp%28-E%28Y_C%29%29%3D%5Cexp%28%5Csum_k%5Clambda_kf_k%7B%28C%2Cy%7CC%2Cx%29%7D%29%0A)

Z是规范化因子，保证#card=math&code=P%28Y%29)构成一个概率分布 %0A#card=math&code=Z%3D%5Csum_Y%5Cprod_C%5CPsi_C%28Y_C%29%0A)

乘积是在无向图所有的最大团上进行的。

含义：对一个无向图进行因子分解（即分解成多个最大团，最大团就是因子），然后无向图的联合概率分布就等于最大团的势函数的累乘除以规范因子。

条件随机场及线性链条件随机场

满足马尔可夫性的是马尔可夫随机场，可以表征联合分布#card=math&code=P%28Y%29) 而#card=math&code=P%28Y%7CX%29)就是条件随机场

• 设与是随机变量，#card=math&code=P%28Y%7CX%29)是给定条件下的条件概率分布，若随机变量构成一个由无向图#card=math&code=G%3D%28V%2CE%29)表示的马尔可夫随机场，即 %3DP(Y_v%7CX%2CY_w%2Cw%5Csim%20v)%0A#card=math&code=P%28Y_v%7CX%2CY_w%2Cw%5Cneq%20v%29%3DP%28Y_v%7CX%2CY_w%2Cw%5Csim%20v%29%0A)

对任意结点成立，则称条件概率分布#card=math&code=P%28Y%7CX%29)为条件随机场。其中，表示在图#card=math&code=G%3D%28V%2CE%29)中与结点有边连接的所有结点，表示结点以外的所有结点，与为结点与对应的随机变量。

与之前推导的：%3DP(Y_v%7CY_W)#card=math&code=P%28Y_v%7CY_O%2CY_W%29%3DP%28Y_v%7CY_W%29)本质一样

• 线性链条件随机场 %5C%7D)%2Ci%3D1%2C2%2C…%2Cn-1%0A#card=math&code=G%3D%28V%3D%5C%7B1%2C2%2C…%2Cn%5C%7D%2CE%3D%5C%7B%28i%2Ci%2B1%29%5C%7D%29%2Ci%3D1%2C2%2C…%2Cn-1%0A)

• 中的之间呈线性关系

#card=math&code=X%3D%28X1%2CX_2…X_n%29)#card=math&code=Y%3D%28Y_1%2CY_2…Y_n%29)#card=math&code=P%28Y%7CX%29)%3DP(Y_i%7CX%2CY%7Bi-1%7D%2CY%7Bi%2B1%7D)%5C%5C%0Ai%3D1%2C2%2C…%2Cn%EF%BC%88%E5%9C%A8i%3D1%E5%92%8Cn%E6%97%B6%E5%8F%AA%E8%80%83%E8%99%91%E5%8D%95%E8%BE%B9%EF%BC%89%0A#card=math&code=P%28Y_i%7CX%2CY_1%2C…%2CY%7Bi-1%7D%2C…%2CYn%29%3DP%28Y_i%7CX%2CY%7Bi-1%7D%2CY_%7Bi%2B1%7D%29%5C%5C%0Ai%3D1%2C2%2C…%2Cn%EF%BC%88%E5%9C%A8i%3D1%E5%92%8Cn%E6%97%B6%E5%8F%AA%E8%80%83%E8%99%91%E5%8D%95%E8%BE%B9%EF%BC%89%0A)

#card=math&code=P%28Y%7CX%29)> 在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。

• 如果再假设与具有相同的图结构，同时分别是已知条件下得到

条件随机场的参数化形式

• 设#card=math&code=P%28Y%7CX%29)为线性链条件随机场，则在随机变量取值为的条件下，随机变量取值为的条件概率具有如下形式： %3D%5Cfrac%7B1%7D%7BZ(x)%7D%5Cexp%7B(%5Csum%7Bi%2Ck%7D%5Clambda_kt_k(y%7Bi-1%7D%2Cyi%2Cx%2Ci)%2B%5Csum%7Bi%2Cl%7D%5Cmuls_l(y_i%2Cx%2Ci))%7D%0A#card=math&code=P%28y%7Cx%29%3D%5Cfrac%7B1%7D%7BZ%28x%29%7D%5Cexp%7B%28%5Csum%7Bi%2Ck%7D%5Clambdakt_k%28y%7Bi-1%7D%2Cyi%2Cx%2Ci%29%2B%5Csum%7Bi%2Cl%7D%5Cmu_ls_l%28y_i%2Cx%2Ci%29%29%7D%0A)

其中， %3D%5Csumy%5Cexp%7B(%5Csum%7Bi%2Ck%7D%5Clambdakt_k(y%7Bi-1%7D%2Cyi%2Cx%2Ci)%2B%5Csum%7Bi%2Cl%7D%5Cmuls_l(y_i%2Cx%2Ci))%7D%0A#card=math&code=Z%28x%29%3D%5Csum_y%5Cexp%7B%28%5Csum%7Bi%2Ck%7D%5Clambdakt_k%28y%7Bi-1%7D%2Cyi%2Cx%2Ci%29%2B%5Csum%7Bi%2Cl%7D%5Cmu_ls_l%28y_i%2Cx%2Ci%29%29%7D%0A)

和是特征函数，和是对应的权值，#card=math&code=Z%28x%29)是规范化因子，求和是在所有可能的输出序列上进行的。
这是线性链条件随机场模型的基本形式，表示给定输入序列x，对输出序列y预测的条件概率。
是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置。是定义在结点上的特征函数，称为状态特征，依赖于当前位置。和都依赖于位置，是局部特征函数。通常，特征函数和取值为1或0；当满足特征条件时取值为1，否则为0。条件随机场完全由特征函数，和对应的权值和确定。

由因子分解得到的%3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod_C%5CPsi_C(Y_C)#card=math&code=P%28Y%29%3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod_C%5CPsi_C%28Y_C%29)推导得到参数化形式

条件随机场的简化形式

• 简化过程：

  1. 将转移特征和状态特征及其权值用统一符号表示：设有个转移特征，个状态特征，，记 %3D%0A%5Cbegin%7Bcases%7D%0Atk(y%7Bi-1%7D%2Cyi%2Cx%2Ci)%2C%5Cquad%20k%3D1%2C2%2C…%2CK_1%5C%5C%0As_l(y_i%2Cx%2Ci)%2C%5Cquad%20k%3DK_1%2Bl%3Bl%3D1%2C2%2C…%2CK_2%0A%5Cend%7Bcases%7D%0A#card=math&code=f_k%28y%7Bi-1%7D%2Cy%2Cx%2Ci%29%3D%0A%5Cbegin%7Bcases%7D%0Atk%28y%7Bi-1%7D%2Cy_i%2Cx%2Ci%29%2C%5Cquad%20k%3D1%2C2%2C…%2CK_1%5C%5C%0As_l%28y_i%2Cx%2Ci%29%2C%5Cquad%20k%3DK_1%2Bl%3Bl%3D1%2C2%2C…%2CK_2%0A%5Cend%7Bcases%7D%0A)

1. 对转移与状态特征在各个位置求和，记 %3D%5Csum%7Bi%3D1%7D%5E%7Bn%7Df_k(y%7Bi-1%7D%2Cy%2Cx%2Ci)%2C%5Cquad%20k%3D1%2C2%2C…%2CK%0A#card=math&code=fk%28y%2Cx%29%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7Dfk%28y%7Bi-1%7D%2Cy%2Cx%2Ci%29%2C%5Cquad%20k%3D1%2C2%2C…%2CK%0A)

1. 用表示特征#card=math&code=f_k%28y%2Cx%29)的权值，即

1. 此时条件随机场可以表示为： %3D%5Cfrac%7B1%7D%7BZ(x)%7D%5Cexp%5Csum%7Bk%3D1%7D%7BK%7Dw_kf_k(y%2Cx)%5C%5C%0AZ(x)%3D%5Csum_y%5Cexp%5Csum%7Bk%3D1%7D%5E%7BK%7Dwkf_k(y%2Cx)%0A#card=math&code=P%28y%7Cx%29%3D%5Cfrac%7B1%7D%7BZ%28x%29%7D%5Cexp%5Csum%7Bk%3D1%7D%7BK%7Dwkf_k%28y%2Cx%29%5C%5C%0AZ%28x%29%3D%5Csum_y%5Cexp%5Csum%7Bk%3D1%7D%5E%7BK%7Dw_kf_k%28y%2Cx%29%0A)

1. 将其中的乘积的累加转换为内积操作
   即以权重向量%5ET#card=math&code=w%3D%28w_1%2Cw_2%2C…%2Cw_k%29%5ET)和全局特征向量%3D(f_1(y%2Cx)%2Cf_2(y%2Cx)%2C…%2Cf_k(y%2Cx))%5ET#card=math&code=F%28y%2Cx%29%3D%28f_1%28y%2Cx%29%2Cf_2%28y%2Cx%29%2C…%2Cf_k%28y%2Cx%29%29%5ET)来简化函数

2. 最终得到条件随机场简化形式： %3D%5Cfrac%7Bexp(w%C2%B7F(y%2Cx))%7D%7BZ_w(x)%7D%5C%5C%0AZ_w(x)%3D%5Csum_y%5Cexp(w%C2%B7F(y%2Cx))%0A#card=math&code=P_w%28y%7Cx%29%3D%5Cfrac%7Bexp%28w%C2%B7F%28y%2Cx%29%29%7D%7BZ_w%28x%29%7D%5C%5C%0AZ_w%28x%29%3D%5Csum_y%5Cexp%28w%C2%B7F%28y%2Cx%29%29%0A)

条件随机场的矩阵形式

• 为了转换为矩阵形式，我们引入特殊的状态标记

• 对观测序列x的每一个位置，定义一个m阶矩阵（m是标记可以取值的个数） %3D%5BMi(y%7Bi-1%7D%2Cyi%7Cx)%5D%5C%5C%0AM_i(y%7Bi-1%7D%2Cyi%7Cx)%3D%20%5Cexp(W_i(y%7Bi-1%7D%2Cyi%7Cx))%5C%5C%0AW_i(y%7Bi-1%7D%2Cyi%7Cx)%3D%5Csum%7Bi%3D1%7D%5E%7BK%7Dwkf_k(y%7Bi-1%7D%2Cyi%2Cx%2C%20i)%0A#card=math&code=M_i%28x%29%3D%5BM_i%28y%7Bi-1%7D%2Cyi%7Cx%29%5D%5C%5C%0AM_i%28y%7Bi-1%7D%2Cyi%7Cx%29%3D%20%5Cexp%28W_i%28y%7Bi-1%7D%2Cyi%7Cx%29%29%5C%5C%0AW_i%28y%7Bi-1%7D%2Cyi%7Cx%29%3D%5Csum%7Bi%3D1%7D%5E%7BK%7Dwkf_k%28y%7Bi-1%7D%2Cy_i%2Cx%2C%20i%29%0A)

这样，给定观测序列x，标记序列y的非规范化概率可以通过n+1个矩阵的乘积#card=math&code=%5Cprod%7Bi%3D1%7D%5E%7Bn%2B1%7DM_i%28y%7Bi-1%7D%2Cyi%7Cx%29)表示，于是，条件概率#card=math&code=P_w%28y%7Cx%29)是 %3D%5Cfrac%7B1%7D%7BZ_w(x)%7D%5Cprod%7Bi%3D1%7D%5E%7Bn%2B1%7DMi(y%7Bi-1%7D%2Cyi%7Cx)%0A#card=math&code=P_w%28y%7Cx%29%3D%5Cfrac%7B1%7D%7BZ_w%28x%29%7D%5Cprod%7Bi%3D1%7D%5E%7Bn%2B1%7DMi%28y%7Bi-1%7D%2Cy_i%7Cx%29%0A)

其中，#card=math&code=Zw%28x%29)为规范化因子，是n+1个矩阵的乘积的(start,stop)元素: %3D(M_1(x)M_2(x)%E2%80%A6M%7Bn%2B1%7D(x))%7Bstart%2Cstop%7D%0A#card=math&code=Z_w%28x%29%3D%28M_1%28x%29M_2%28x%29%E2%80%A6M%7Bn%2B1%7D%28x%29%29_%7Bstart%2Cstop%7D%0A)

注意，与表示开始状态与终止状态，规范化因子#card=math&code=Zw%28x%29)是以start为起点stop为终点通过状态的所有路径的非规范化概率#card=math&code=%5Cprod%7Bi%3D1%7D%5E%7Bn%2B1%7DMi%28y%7Bi-1%7D%2Cy_i%7Cx%29)之和。