条件随机场（Conditionalrandomfield，CRF）本⽂简单整理了以下内容：
（⼀）马尔可夫随机场（Markov random field，⽆向图模型）简单回顾
工程拆除
（⼆）条件随机场（Conditional random field，CRF）
这篇写的⾮常浅，基于 [1] 和 [5] 梳理。感觉 [1] 的讲解很适合完全不知道什么是CRF的⼈来⼊门。如果有需要深⼊理解CRF的需求的话，还是应该仔细读⼀下⼏个英⽂的tutorial，⽐如 [4] 。
（⼀）马尔可夫随机场简单回顾
概率图模型（Probabilistic graphical model，PGM）是由图表⽰的概率分布。概率⽆向图模型（Probabilistic undirected graphical model）⼜称马尔可夫随机场（Markov random field），表⽰⼀个联合概率分布，其标准定义为：ur
设有联合概率分布 P(V) 由⽆向图 G=(V, E) 表⽰，图 G 中的节点表⽰随机变量，边表⽰随机变量间的依赖关系。如果联合概率分布 P(V) 满⾜成对、局部或全局马尔可夫性，就称此联合概率分布为概率⽆向图模型或马尔可夫随机场。
设有⼀组随机变量 Y ，其联合分布为 P(Y) 由⽆向图 G=(V, E) 表⽰。图 G 的⼀个节点v\in V表⽰⼀个随机变量Y_v，⼀条边e\in E就表⽰两个随机变量间的依赖关系。
1. 成对马尔可夫性（pairwi Markov property）
设⽆向图 G 中的任意两个没有边连接的节点 u 、v ，其他所有节点为 O ，成对马尔可夫性指：给定Y_O的条件下，Y_u和Y_v条件独⽴
P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)
2. 局部马尔可夫性（local）
设⽆向图 G 的任⼀节点 v ，W 是与 v 有边相连的所有节点，O 是 v 、W 外的其他所有节点，局部马尔可夫性指：给定Y_W的条件下，Y_v和Y_O条件独⽴男性英文名
P(Y_v,Y_O|Y_W)=P(Y_v|Y_W)P(Y_O|Y_W)
当P(Y_O|Y_W)>0时，等价于
P(Y_v|Y_W)=P(Y_v|Y_W,Y_O)
如果把等式两边的条件⾥的Y_W遮住，P(Y_v)=P(Y_v|Y_O)这个式⼦表⽰Y_v和Y_O独⽴，进⽽可以理解这个等式为给定条件Y_W下的独⽴。
3. 全局马尔可夫性（global）
设节点集合 A 、B 是在⽆向图 G 中被节点集合 C 分开的任意节点集合，全局马尔可夫性指：给定Y_C的条件下，Y_A和Y_B条件独⽴
P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)
这⼏个定义是等价的。
4. 概率⽆向图模型
⽆向图模型的优点在于其没有隐马尔可夫模型那样严格的独⽴性假设，同时克服了最⼤熵马尔可夫模型等判别式模型的标记偏置问题。
（1）有向图的联合概率分布
考虑⼀个有向图G^d=(V^d,E^d)，随机变量间的联合概率分布可以利⽤条件概率来表⽰为
P(v_1^d,...,v_n^d)=\prod_{i=1}^nP(v_i^d|v_{\pi i}^d)
其中v_{\pi i}^d表⽰节点v_i^d的⽗节点的集合。
（2）⽆向图的因⼦分解（Factorization）
不同于有向图模型，⽆向图模型的⽆向性很难确保每个节点在给定它的邻节点的条件下的条件概率和以图中其他节点为条件的条件概率⼀致。由于这个原因，⽆向图模型的联合概率并不是⽤条件概率参数化表⽰的，⽽是定义为由⼀组条件独⽴的局部函数的乘积形式。因⼦分解就是说将⽆向图所描述的联合概率分布表达为若⼲个⼦联合概率的乘积，从⽽便于模型的学习和计算。
实现这个分解要求的⽅法就是使得每个局部函数所作⽤的那部分节点可以在 G 中形成⼀个最⼤团（maximal clique）。这就确保了没有⼀个局部函数是作⽤在任何⼀对没有边直接连接的节点上的；反过来说，如果两个节点同时出现在⼀个团中，则在这两个节点所在的团上定义⼀个局部函数来建⽴这样的依赖。
⽆向图模型最⼤的特点就是易于因⼦分解，标准定义为：
将⽆向图模型的联合概率分布表⽰为其最⼤团（maximal clique，可能不唯⼀）上的随机变量的函数的乘积形式。
给定⽆向图 G ，其最⼤团为 C ，那么联合概率分布 P(Y) 可以写作图中所有最⼤团 C 上的势函数（potential function）\psi_C(Y_C)的乘积形式：P(Y)=\frac1Z\prod_C\psi_C(Y_C)
Z=\sum_Y\prod_C\psi_C(Y_C)
其中 Z 称为规范化因⼦，对 Y 的所有可能取值求和，从⽽保证了 P(Y) 是⼀个概率分布。要求势函数严格正，通常定义为指数函数
\psi_C(Y_C)=\exp(-\mathbb E[Y_C])
上⾯的因⼦分解过程就是 Hammersley-Clifford 定理。
（⼆）条件随机场
条件随机场（Conditional random field，CRF）是条件概率分布模型 P(Y|X) ，表⽰的是给定⼀组输⼊随机变量 X 的条件下另⼀组输出随机变量 Y 的马尔可夫随机场，也就是说 CRF 的特点是假设输出随机变量构成马尔可夫随机场。
条件随机场可被看作是最⼤熵马尔可夫模型在标注问题上的推⼴。
这⾥介绍的是⽤于序列标注问题的线性链条件随机场（linear chain conditional CRF），是由输⼊序列来预测输出序列的判别式模型。
图⽚来源：[3]
图⽚来源：[2]
图⽚来源：[4]
从问题描述上看，对于序列标注问题，X 是需要标注的观测序列，Y 是标记序列（状态序列）。在学习过程时，通过 MLE 或带正则的 MLE 来训练出模型参数；在测试过程，对于给定的观测序列，模型需要求出条件概率最⼤的输出序列。
如果随机变量 Y 构成⼀个由⽆向图 G=(V, E) 表⽰的马尔可夫随机场，对任意节点v\in V都成⽴，即
P(Y_v|X,Y_w,w\not=v)=P(Y_v|X,Y_w,w\sim v)
对任意节点v都成⽴，则称 P(Y|X) 是条件随机场。式中w\not=v表⽰ w 是除 v 以外的所有节点，w\sim v表⽰ w 是与 v 相连接的所有节点。不妨把等式两遍的相同的条件 X 都遮住，那么式⼦可以⽤下图⽰意：
很明显，这就是马尔可夫随机场的定义。
线性链条件随机场
在定义中并没有要求 X 和 Y 具有相同的结构，⽽在现实中，⼀般假设 X 和 Y 有相同的图结构。对于线性链条件随机场来说，图 G 的每条边都存在于状态序列 Y 的相邻两个节点，最⼤团 C 是相邻两个节点的集合，X 和 Y 有相同的图结构意味着每个X_i都与Y_i⼀⼀对应。
V=\{1,2,...,n\},\quad E=\{(i, i+1)\},\quad i=1,2,...,n-1
设两组随机变量X=(X_1,...,X_n),Y=(Y_1,...,Y_n)，那么线性链条件随机场的定义为
P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1}),\quad i=1,...,n
其中当 i 取 1 或 n 时只考虑单边。
⼀、线性链条件随机场的数学表达式
1. 线性链条件随机场的参数化形式：特征函数及例⼦
此前我们知道，马尔可夫随机场可以利⽤最⼤团的函数来做因⼦分解。给定⼀个线性链条件随机场 P(
Y|X) ，当观测序列为x=x_1x_2\cdots时，状态序列为y=y_1y_2\cdots的概率可写为（实际上应该写为P(Y=y|x;\theta)，参数被省略了）
P(Y=y|x)=\frac{1}{Z(x)}\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)
Z(x)=\sum_y\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)
Z(x)作为规范化因⼦，是对 y 的所有可能取值求和。
序列标注 vs 分类
是不是和Softmax回归挺像的？它们都属于对数线性模型（log linear model），线性链CRF⽤来解决序列标注问题，Softmax回归、最⼤熵模型都是⽤来解决分类问题。但需要注意，这两类问题存在⾮常⼤的区别：
（1）如果把序列标注问题看作分类问题，也就是为每⼀个待标注的位置都当作⼀个样本然后进⾏分类，那么将会有很⼤的信息损失，因为⼀个序列的不同位置之间存在联系：⽐如说有⼀系列连续拍摄的照⽚，现在想在照⽚上打上表⽰照⽚⾥的活动内容的标记，当然可以将每张照⽚单独做分类，但是
会损失信息，例如当有⼀张照⽚上是⼀张嘴，应该分类到“吃饭”还是分类到“唱K”呢？如果这张照⽚的上⼀张照⽚内容是吃饭或者做饭，那么这张照⽚表⽰“吃饭”的可能性就⼤⼀些，如果上⼀张照⽚的内容是跳舞，那这张照⽚就更有可能在讲唱K的事情。（这个例⼦来⾃ [5] 的开头。）
obvious的意思（2）不同的序列有不同的长度，不便于表⽰成同⼀维度的向量。
（3）状态序列的解集随着序列长度指数级增长，穷举法是不可⾏的。
特征函数
对于线性链CRF，特征函数是个⾮常重要的概念：
megapixel转移特征t_k(y_{i-1},y_i,x,i)是定义在边上的特征函数（transition），依赖于当前位置 i 和前⼀位置 i-1 ；对应的权值为\lambda_k。
状态特征s_l(y_i,x,i)是定义在节点上的特征函数（state），依赖于当前位置 i ；对应的权值为\mu_l。
⼀般来说，特征函数的取值为 1 或 0，当满⾜规定好的特征条件时取值为 1 ，否则为 0 。
英语被动语态以词性标注为例
下⾯给出⼀些特征函数的例⼦，参考⾃ [5] 。词性标注（Part-of-Speech Tagging，POS）任务是指 the goal is to label a ntence (a quence of words or tokens) with tags like ADJECTIVE, NOUN, PREPOSITION, VERB, ADVERB, ARTICLE. 在对英⽂序列进⾏词性标注时可以使⽤以下特征：（1）s_1(y_i,x,i)=1，如果y_i=ADVERB且x_i以“-ly”结尾；否则为 0 。如果该特征函数有⼀个较⼤的正权重，就表明倾向于将 “-ly” 结尾的单词标注为副词。
engine（2）s_2(y_i,x,i)=1，如果i=1、y_i＝VERB且 x 以“?”结尾；否则为 0 。如果该特征函数有⼀个较⼤的正权重，就表明倾向于将问句的⾸词标注为动词，例如“Is this a ntence beginning with a verb?”
rushhour（3）t_3(y_{i-1},y_i,x,i)=1，如果y_{i-1}=ADJECTIVE且y_{i}=NOUN；否则为 0 。如果该特征函数有⼀个较⼤的正权重，就表明倾向于认为形容词后⾯跟着名词。
（4）t_4(y_{i-1},y_i,x,i)=1，如果y_{i-1}=PREPOSITION且y_{i}=PREPOSITION；否则为 0 。如果该特征函数有⼀个较⼤的负权重，就表明倾向于认为介词不会连⽤。
CRF vs HMM
[5] 中还⽐较了 HMM 和 CRF在序列标注的异同，作者认为CRF更加强⼤，理由如下：
（1）可以为每个 HMM 都建⽴⼀个等价的 CRF（记号中的 s、l 就是本⽂的 x、y ）：
图⽚来源：[5]
（2）CRF 的特征可以囊括更加⼴泛的信息：HMM 基于“上⼀状态to当前状态”的转移概率以及“当前状态to当前观测”的释放概率，使得当前位置的词（观测）只可以利⽤当前的状态（词性）、当前位置的状态⼜只能利⽤上⼀位置的状态。但 CRF 的特征函数中，输⼊包含(y_{i-1},y_i,x,i)，对于当前位置 i 来说可以利⽤完整的 x 信息。
（3）CRF 的参数的取值没有限制，⽽ HMM 的参数（转移概率矩阵、释放概率矩阵、初始概率向量）
都需要满⾜⼀些限制。
2. 线性链条件随机场的简化形式
需要注意的是，以\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)这项为例，可以看出外⾯那个求和号是套着⾥⾯的求和号的，这种双重求和就表明了对于同⼀个特征（k），在各个位置（i）上都有定义。
基于此，很直觉的想法就是把同⼀个特征在各个位置 i 求和，形成⼀个全局的特征函数，也就是说让⾥⾯那⼀层求和号消失。在此之前，为了把加号的两项合并成⼀项，⾸先将各个特征函数 t（设其共有K_1个）、s（设共{K_2}个）都换成统⼀的记号 f ：
t_1=f_1,t_2=f_2,\cdots,t_{K_1}=f_{K_1},\quad s_1=f_{K_1+1},s_2=f_{K_1+2},\cdots,s_{K_2}=f_{K_1+K_2}
相应的权重同理：
\lambda_1=w_1,\lambda_2=w_2,\cdots,\lambda_{K_1}=w_{K_1},\quad \mu_1=w_{K_1+1},\mu_2=w_{K_1+2},\cdots,\mu_{K_2}=w_{K_1+K_2}
那么就可以记为
miyun
f_k(y_{i-1},y_i,x,i)=\begin{cas}t_k(y_{i-1},y_i,x,i), & k=1,2,...,K_1 \\s_l(y_i,x,i), & k=K_1+l;l=1,2,...,K_2\end{cas}
w_k=\begin{cas}\lambda_k, & k=1,2,...,K_1 \\\mu_l, & k=K_1+l;l=1,2,...,K_2\end{cas}
学习会计
然后就可以把特征在各个位置 i 求和，即
f_k(y,x)=\sum_{i=1}^n f_k(y_{i-1},y_i,x,i), \quad k=1,2,...,K
其中K=K_1+K_2。进⽽可以得到简化表⽰形式
P(Y=y|x)=\frac{1}{Z(x)}\exp\sum_{k=1}^Kw_kf_k(y,x)
Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)
如果进⼀步，记\textbf w=(w_1,w_2,...,w_K)^{\top}，F(y,x)=(f_1(y,x),...,f_K(y,x))^{\top}，那么可得内积形式：
P_{\textbf w}(Y=y|x)=\frac{1}{Z_{\textbf w}(x)}\exp(\textbf w^{\top}F(y,x))
Z_{\textbf w}(x)=\sum_y\exp(\textbf w^{\top}F(y,x))
3. 线性链条件随机场的矩阵形式
这种形式依托于线性链条件随机场对应的图模型仅在两个相邻节点之间存在边。在状态序列的两侧添加两个新的状态y_0 = start、y_{n+1}=stop 。
这⾥，引⼊⼀个新的量M_i(y_{i-1},y_i|x)：
M_i(y_{i-1},y_i|x)=\exp\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i),\quad i=1,2,...,n+1
⾸先，这个量融合了参数和特征，是⼀个描述模型的⽐较简洁的量；其次，不难发现，这个量相⽐于原来的⾮规范化概率
P(Y=y|x)\propto\exp\displaystyle\sum_{k=1}^Kw_kf_k(y,x)，少了对位置的内层求和，换句话说这个量是针对于某个位置 i （及其前⼀个位置 i-1 ）的。那么，假设状态序列的状态存在 m 个可能的取值，对于任⼀位置 i = 1,2,...,n+1 ，定义⼀个 m 阶⽅阵：
