CRF

条件随机场（CRF）

0. 预备知识

0.1 概率图模型（Probabilistic Graphical Model，PGM）

概念：图结构，结点（node）表示随机变量，边（edge）表示结点间关系。简而言之，不相连的结点直接毫无关系。

分类：

有向图：贝叶斯网络，变量之间的因果关系
无向图：马尔科夫随机场，变量之间的相关关系，常用于图像去噪等

0.2 团与极大团

定义：团就是一个两两之间有边的顶点集合

绿色圆圈是一个团，蓝色圆圈是一个极大团

极大团算法

0.3 势函数

概念：应用等势线、等高线的概念，存在一条等高线，使得高于等高线的属于(ψ_1)，低于等高线的属于(ψ_2)

应用：node之间的相关关系通过势函数进行度量*（恒>=0，局部）

为了满足非负性，常用指数函数进行定义:

[ψ(x)=e^{-H(x)}\ 其中H（x）是一个定义在变量x上的实值函数 ]

对于一个x_{i}确定的区域，其势函数的表达式为 $K(X,X_{i})$ 一个势函数有以下特点：

当X越接近 $X_{i}$ 时， $K(X,X_{i})$ 的函数值越大，当 $X=X_{i}$ 时， $K(X,X_{i})$ 取得最大值
当X越远离 $X_{i}$ 时， $K(X,X_{i})$ 的函数值越小，特别的 $X=X_{j}$ （其中j不等于i）时， $K(X,X_{i})$ 值通常非常小

分类：

第一类势函数：采用对称的多项式展开，通常需要为正交函数集

第二类势函数：选择双变量的对称函数

$K(x,x_{i})=e^{-alpha left | x-x_{i} ight |^{2}}$ 当 $x=x_{i}$ 时有最大值1 当x远离 $x_{i}$ 时，趋近于0

$K(x,x_{i})=frac{1}{1+alphaleft | x-x_{i} ight |^{2} }$

0.4 马尔科夫性

马尔可夫随机场是生成式模型，生成式模型最关心的是变量的联合概率分布。

时间复杂度限制：

非相对独立时：n个取值的随机变量((x_1,x_2,...,x_n))，其取值分布包括(2^n)种可能，因此联合概率分布(p(x_1,x_2,...,x_n))需要(2_n-1)个参数
相对独立时：(p(x_1,x_2,...,x_n)) = (p(x_1)p(x_2)...p(x_n))，需要n个参数

能不能将联合概率分布分解为一组子集概率分布的乘积呢？那么应该怎么划分子图呢？应该遵循怎样的原则？

为确保条件独立

全局马尔科夫性：设节点集合A，B是在无向图G中被节点集C分开的任意节点集合，如下图所示。全局马尔可夫性是指在给定(x_C)的条件下，和(x_A)和(x_B)条件独立，记为((x_A⊥x_B)|x_C)

[p(x_A,x_B|x_C) = p(x_A|x_C)p(x_B|x_C) ]
局部马尔科夫性

[P(x_v,x_o|x_w) = p(x_v|x_w)p(x_o|x_w) ]

成对马尔科夫性
[p(x_i,x_j,x_{(i,j)}) = p(x_i|x_{(i,j)})p(x_j|x_{(i,j)})\ 其中x_{(i,j)}表示所有变量x去除x_i和x_j的集合 ]

0.5 马尔可夫随机场

我不清楚具体的定义，但我觉得满足马尔可夫性+随机场 = 马尔科夫随机场

在马尔可夫随机场中，多个变量的联合概率分布能基于团分解为多个势函数的乘积，每一个团对应一个势函数。马尔可夫随机场有一组势函数，亦称因子，这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。

C是一个团，(ψ_C)为团C对应的势函数

[p(x) = frac{1}{Z}prod_C ψ_C(x_C)\ Z=sum_xprod_C ψ_C(x_C) ]

1. CRF介绍

1.1 CRF简介：

1.1.1 命名缘由：Conditional random field

Random指的是随机变量X和Y
Conditional指的是条件概率

1.1.2 CRF是在给定一组输入随机变量序列 $X=(x_1,x_2,...,x_n)$ 的条件下，输出目标序列 $Y=(y_1,y_2,...,y_n)$ ，且Y要是马尔科夫随机场

时序模型、判别模型
应用：词性标注

例子：词性标注

“Bob drank coffee at Starbucks”，注明每个单词的词性后是这样的：“Bob (名词) drank(动词) coffee(名词) at(介词) Starbucks(名词)”。

(名词，动词，名词，介词，名词)

(名词，动词，动词，介词，名词)

挑选出一个最靠谱的作为我们对这句话的标注

凡是标注中出现了动词后面还是动词的标注序列，要给它负分！！

上面所说的动词后面还是动词就是一个特征函数，我们可以定义一个特征函数集合，用这个特征函数集合来为一个标注序列打分，并据此选出最靠谱的标注序列。也就是说，每一个特征函数都可以用来为一个标注序列评分，把集合中所有特征函数对同一个标注序列的评分综合起来，就是这个标注序列最终的评分值。

输出值是0或者1,0表示要评分的标注序列不符合这个特征，1表示要评分的标注序列符合这个特征。

特征函数(f_j)：

句子s（就是我们要标注词性的句子）
i，用来表示句子s中第i个单词
$ l_i$，表示要评分的标注序列第i个单词标注的词性
(l_{i-1})，表示要评分的标注序列给第i-1个单词标注的词性

(f_1(s,i,l_i,l_{i-1})=1) ,当(l_{i-1})是介词，(l_i)是名词时，(f_1 = 1)，其他情况(f_1=0)。(λ_1)也应当是正的，并且(λ_1)越大，说明我们越认为介词后面应当跟一个名词。

将特征函数(f_j)赋予一个权重(λ_j)，只有一个句子s，有一个标注序列 (l) ，对前面定义的特征函数集来对$ l $ 评分：

[score(l|s) = sum_{j=1}^msum_{i=1}^nlambda_jf_j(s,i,l_i,l_{i-1}) ]

1.2 CRF参数化定义（书中是直接给定的，不懂）

CRF在统计语料库总相邻词是否满足特征函数的频次，给出(P_w(y|x))。在给定的((x,y))，满足的特征函数越多，模型认为(P_w(y|x))越大。

[p(x) = frac{1}{Z}prod_C ψ_C(x_C)\ Z=sum_xprod_C ψ_C(x_C) ]

softmax 随机神经网络玻尔兹曼机

[P(y|x) = frac{1}{Z(x)}exp(sum_{i,k}lambda_kt_k(y_{i-1},y_i,x,i))+sum_{i,l}mu_ls_l(y_i,x,i))\ Z(x) = sum_yexp(sum_{i,k}lambda_kt_k(y_{i-1},y_i,x,i))+sum_{i,l}mu_ls_l(y_i,x,i)) ]

每个(f_i)都有一个权重(omega)，(t(y_{i-1},y_i,x,i)) 和 (s(y_i,x,i)) 用 (F(y,x)) 表示，将上式简化为：

[p_w(y|x) = frac{1}{Z_W(x)}exp(w*F(y,x))\ Z_w(x) = sum_yexp(w*F(y,x)) ]