概率无向图模型

又称马尔可夫随机场(Markov random field)或马尔可夫网络，是一个由无向图表示的联合概率分布。

图是由结点和边组成，无向图中的边没有方向。概率无向图中结点表示随机变量，边表示结点之间的概率依赖关系。

成对马尔可夫性：

设u和v是无向图G中任意两个没有连接边的结点，对应随机变量分别为Y_u和Y_v，图中其他所有结点为O，对应随机变量组Y_O，那么给定随机变量组Y_O的条件下，Y_u和Y_v是条件独立的，此为成对马尔可夫性，即

       (1)

局部马尔可夫性：

设v是无向图G中的任意一个节点，W是与v有边连接的所有结点，O是除v和W之外的其他所有结点（即，与v没有边连接的所有结点），给定随机变量组Y_W的条件下，Y_v与Y_O是条件独立的，此为局部马尔可夫性，即，

     (2)

如果P(Y_O|Y_W)>0，那么(2)式两边同时除以P(Y_O|Y_W)，

   (3)

下图表示局部马尔可夫性，

上图中，假设某个黑点表示v，那么与其有边连接的有一个或大于一个白点为W，剩余的其他点（包括白点和黑点）为O。

全局马尔可夫性：

设结点集合A和B是在无向图G中被结点集合C分开的任意结点集合，结点集合A,B,C所对应的随机变量组分别是Y_A,Y_B,Y_C，给定随机变量组Y_C的条件下，Y_A和Y_B是条件独立的，此为全局马尔可夫性，即，

      (4)

可用下图表示全局马尔可夫性，

从图中可见，A中任意结点到B中任意结点之间的所有路径，都经过C中结点，也就是说被C隔断，A和B关于C条件独立。

不难发现上述成对、局部和全局 马尔可夫性是等价的，从特殊到一般的过程。

 概率无向图

设联合概率分布P(Y)由无向图G=(V,E)表示，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型。

无向图G中如果存在一个结点子集，并且子集中任意两个结点均有边连接，则称这样的子集为团(clique)。

若C是G中的一个团，并且无法再加入一个G的其他结点，使C成为一个更大的团，那么C就是一个最大团。

如下图，由两个结点组成的团为：{Y₁,Y₂},{Y₂,Y₃},{Y₃,Y₄},{Y₄,Y₂},{Y₁,Y₃}，有两个最大团：{Y₁,Y₂,Y₃},{Y₂,Y₃,Y₄}。

将概率无向图的联合概率分布表示为其最大团上的随机变量的函数乘积形式的操作，称为因子分解。

给定概率无向图G，C为G上的最大团，Y_C表示C对应的随机变量组，那么G对应的联合概率分布P(Y)为G中所有最大团C上的函数的乘积，

             (5)

其中，Z是规范化因子，即

               (6)

规范化因子保证P(Y)构成一个概率分布，即对P(Y)求和为1。函数 称为势函数，是一个严格正的函数，通常定义为指数函数，

          (7)

条件随机场

 给定随机变量X的条件下，随机变量Y的马尔可夫随机场称为条件随机场。这里主要涉及线性马尔可夫链，所以就介绍线性链上的特殊的条件随机场，称为线性链条件随机场。在条件概率模型中P(Y|X)，Y是输出变量表示标记序列（或状态序列），X是输入变量表示需要标注的观测序列。利用训练数据集通过极大似然估计或正则化的极大似然估计学习条件概率模型。

 设随机变量X和Y，P(Y|X)表示给定X的条件下Y的条件概率分布。若Y构成一个由无向图G=(V,E)表示的马尔可夫随机场，即

   (8)

对任意结点v 成立，则称条件概率分布P(Y|X)为条件随机场。其中w~v表示图G中与v结点有边连接的所有结点w，w!=v表示结点v以外的所有结点。从上式可见，在给定X的大前提下，给定除v 之外所有结点条件下 v的条件概率，与 给定v结点有边连接的所有邻结点条件下v 的条件概率 相等，也就是说 v结点 与 除v和v的邻结点w之外的所有结点子集关于w条件独立，这正好就是指局部马尔可夫性。

实际中，一般假设X与Y有相同的图结构。

考虑如下图所示的线性链，此时图G可以表示为：G=(V={1,2,...,n}, E={(i,i+1)}), i=1,2,...,n-1，此时X=(X₁,X₂,...,X_n),Y=(Y₁,Y₂,...,Y_n)，最大团是相邻两个结点的集合。

　　　　　　线性链条件随机场　　　　　　　　　　　　　　　X和Y有相同图结构的线性链条件随机场

线性链条件随机场

设X=(X₁,X₂,...,X_n),Y=(Y₁,Y₂,...,Y_n)均为线性链表示的随机变量序列，给定X的条件下，Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔可夫性：

              (9)

其中，i=1,2,...,n，且在i=1和n的时候分别只考虑右边 和 左边，此时 P(Y|X)表示线性链条件随机场。

在标注问题中，X表示观测序列，Y表示对应的标注序列（或状态序列）

至此，以上内容都不难理解，然而下面给出线性链条件随机场的参数化形式则不是很显然的了，事实上，稍显突兀，不过没关系，本篇文章只要对上述内容能够理解即可，下面的参数化形式后面还要进行深入讨论的，这里只需有个印象便可。

 设P(Y|X)为线性链条件随机场，则随机变量X取值为x的条件下，随机变量Y取值为y的条件概率为，

      (10)

其中，

            (11)

式中，t_k和s_l是特征函数，λ_k和u_l是对应的权值，Z(x)是规范化因子，求和是在所有可能的输出序列{y}上进行的。

(10)和(11)是线性链条件随机场模型的参数化形式，表示给定输入序列x，对输出序列y的预测的条件概率。其实，t_k 是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置，s_l 是定义在结点上的特征函数，称为状态特征，依赖于当前位置。t_k 和 s_l 都依赖于位置，是局部特征函数，通常， t_k 和 s_l 取值为 1 或 0； 当满足特征条件时取值为1，否则为0。

ref

统计学习方法，李航

条件随机场（一）