CRF简介（一）
折闪电 2009年11月30日
CRF(Conditional random fields)，是一种判别式图模型，因为其强大的表达能力和出色的性能，得到了广泛的应用。从
最通用角度来看，CRF本质上是给定了观察值集合(observations)的马尔可夫随机场。在这里，我们直接从最通用的角度来
认识和理解CRF，最后可以看到，线性CRF和所谓的高阶CRF，都是某种特定结构的CRF。
1. 随机场
简单地讲，随机场可以看成是一组随机变量的集合（这组随机变量对应同一个样本空间）。当然，这些随机变量之间可能
有依赖关系，一般来说，也只有当这些变量之间有依赖关系的时候，我们将其单独拿出来看成一个随机场才有实际意义。
2. Markov随机场(MRF)
这是加了Markov性质限制的随机场。首先，一个Markov随机场对应一个无向图。这个无向图上的每一个节点对应一个随
机变量，节点之间的边表示节点对应的随机变量之间有概率依赖关系。因此，Markov随机场的结构本质上反应了我们的先验
知识——哪些变量之间有依赖关系需要考虑，而哪些可以忽略。Markov性质是指，对Markov随机场中的任何一个随机变量，
给定场中其他所有变量下该变量的分布，等同于给定场中该变量的邻居节点下该变量的分布。这让人立刻联想到马式链的定
义：它们都体现了一个思想：离当前因素比较遥远(这个遥远要根据具体情况自己定义）的因素对当前因素的性质影响不大。
Markov性质可以看作是Markov随机场的微观属性，那么其宏观属性就是其联合概率的形式。
假设MRF的变量集合为S=｛y1,...yn},
P(y1,...yn)= 1/Z * exp{-1/T * U(y1,..yn)},其中Z是归一化因子，即对分子的所有y1,..yn求和得到。U(y1,..yn)一般称为
energy function, 定义为在MRF上所有clique-potential之和。T称为温度，一般取1。什么是click-potential呢? 就是在MRF
对应的图中，每一个clique对应一个函数，称为clique-potential。这个联合概率形式又叫做Gibbs distribution。Hammersley
and Clifford定理表达了这两种属性的等价性。
如果click-potential的定义和clique在图中所处的位置无关，则称该MRF是homogeneous；如果click-potential的定义和
clique在图中的朝向(orientation)无关，则称该MRF是isotropic的。一般来说，为了简化计算，都是假定MRF即是homogeneous
也是iostropic的。
3.从Markov随机场到CRF
现在，如果给定的MRF中每个随机变量下面还有观察值，我们要确定的是给定观察集合下，这个MRF的分布，也就是条件
分布，那么这个MRF就称为CRF(Conditional Random Field)。它的条件分布形式完全类似于MRF的分布形式,只不过多了一
个观察集合x，即P(y1,..yn|x) = 1/Z(x) * exp{ -1/T * U(y1,...yn,x)。U(y1,..yn,X)仍旧是click-potential之和。
4.训练
通过一组样本，我们希望能够得到CRF对应的分布形式，并且用这种分布形式对测试样本进行分类。也就是测试样本中每个
随机变量的取值。
在实际应用中，clique-potential主要由用户自己定义的特征函数组成，即用户自己定义一组函数，这些函数被认为是可以
用来帮助描述随机变量分布的。而这些特征函数的强弱以及正向、负向是通过训练得到的一组权重来表达的，这样，实际应用
中我们需要给出特征函数以及权重的共享关系(不同的特征函数可能共享同一个权重),而clicque-potential本质上成了对应
特征函数的线性组合。这些权重就成了CRF的参数。因此，本质上，图的结构是用户通过给出特征函数的定义确定的（例如，
只有一维特征函数，对应的图上是没有边的)还有，CRF的分布成了对数线性形式。
看到这个分布形式，我们自然会想到用最大似然准则来进行训练。对其取log之后，会发现，表达式是convex的，也就是
具有全局最优解——这是很让人振奋的事情。而且，其梯度具有解析解，这样可以用LBFGS来求解极值。
此外，也可以使用最大熵准则进行训练，这样可以用比较成熟的GIS和IIS算法进行训练。由于对数线性的分布形式下，最
大熵准则和最大似然准则本质上是一样的，所以两者区别不是很大。
此外，由于前面两种训练方法在每一轮迭代时，都需要inference,这样会极大地降低训练速度。因此普遍采用另一种近
似的目标函数，称为伪似然。它用每个随机变量的条件分布(就是给定其他所有随件变量的分布)之积来替代原来的似然函数，
根据markov性质，这个条件分布只和其邻居有关(Markov Blanket),这样在迭代过程中不需要进行全局的inference,速度会得
到极大的提升。我自己的经验表明，当特征函数很多取实数值时，伪似然的效果跟最大似然的差不多，甚至略好于后者。但
对于大量二元特征(binary-valued)，伪似然的效果就很差了。
5.推断
如前所述，训练的过程中我们需要概率推断，分类的时候我们需要找出概率最大的一组解，这都涉及到推断。这个问
题本质上属于图模型上的概率推断问题。对于最简单的线性框架的结构，我们可以使用Viterbi算法。如果图结果是树形的，
可以采用信念传播(belief propogation),用sum-product得到概率，用max-product得到最优的configuration.但是对于任意图，
这些方法就无效了。一种近似的算法，称为loopy-belief propogation,就是在非树形结构上采用信念传播来进行推断，通过循
环传播来得到近似解。这么做据说在某些场合下效果不错。但是，在训练时如果采用近似推断的话，可能会导致长时间无
法收敛。
基于任意图上的概率推断算法称为junction tree。 这个算法能够保证对任意图进行精确推理。它首先把原来的图进行三角
化，在三角化的图上把clique按照某种方式枚举出来作为节点（实际上就是合并特征函数),clicque之间如果有交集，对应的节
点之间就有边，这样就得到一个新的图，通过对这个图求最大生成树，就得到了Junction tree. 最后在junction tree上进行信
念传播可以保证得到精确解。
本质上这3中算法都属于动态规划的思想。Viterbi的想法最直观，信念传播首先将特征函数都转换为factor，并将其与随机
变量组合在一起形成factor-graph, 这样在factor-graph上用动态规划的思想进行推断（即做了一些预处理)。junction tree的
做法是通过合并原有的特征函数, 形成一种新的图，在这个图上可以保证动态规划的无后效性，于是可以进行精确推理。(做
了更为复杂的预处理)
值得注意的是，junction tree虽然极大地避开了组合爆炸，但由于它要合并特征函数并寻找clique, 用户的特征函数
如果定义的维数过大，它得到新的clique也会很大，这样在计算的时候还是会很低效，因为在推断的过程中它需要遍历所有
clique中的配置，这和clique的大小是呈指数级的。所以，用户要避免使用维数过高的特征。