概率图模型及求解方法
本文介绍概率图模型的定义和几个相关算法，概率图模型是贝叶斯统计和机器学习中的一个常用方法，在自然语言处理和生物信息中也有重要应用。关于概率图模型更详细全面的介绍参见[1],[6]。
1.1什么是概率图模型
概率图模型简单地说是用图作为数据结构来储存概率分布的模型。图中的节点表示概率分布中的随机变量，图中的边表示它连接的两个随机变量之间存在的某种关系（具体是什么关系将在后文提到）。概率图模型可以简洁的表示复杂的概率分布，并且可以利用图论中的算法来求解概率分布中的某些特性（条件独立性和边际概率），因此得到了广泛应用。
1.2有向图模型
1.2.1定义
概率图模型根据模型中的图是否为有向图分为有向图模型和无向图模型两种。有向图模型也叫贝叶斯网络。我们考虑的有向图模型中的图是有向无圈图，有向无圈图是指图中两点之间至多存在一条有向路径。我们可以对有向无圈图中的节点排序，使得图中的边都是从序号小的节点指向序号大的节点，这种排序称为拓扑排序。在有向图中，我们称存在有向边指向节点x的节点为x的父节点，节点x的边指向的节点为x的子节点。存在由节点x到节点y的一条有向路径，并且路径的方向指向节点y的所有y的集合称为x的后代节点。容易看出，在拓扑排序下父节点的序号总是小于子节点的序号。如果图G中存在有向圈，则节点x可能既是节点y的父节点又是节点的子节点，因此父节点、子节点只对有向无圈图有意义。
称概率分布P可以由有向无圈图G表出，如果概率分布可以分解为： P(x)?KP(x?k?1k|pak) (1.1)
其中，pak表示xk在图G中所有父节点组成的集合。
x1x2x3x5x4 图1. 简单的概率图模型
例1. 我们考虑图1对应的概率图模型，概率分布可以写成：
P(x1,x2,x3,x4,x5)?P(x1)P(x2)P(x3|x1,x2)P(x4|x3)P(x5|x2)
假设每个自变量可取3个值，那么用概率图模型表示这个概率分布，我们只需记录6+6+18+6+6=42个参数，而如果不用概率图模型，则需要记录3^5-1=242个参数。由此可以看出概率图模型可以节省储存空间。
1.2.2 条件独立
注意到公式（1.1）中P(xk|pak)取不同值时，模型表示的概率分布也不相同，但由于这些概率分布有相同的因式图，他们存在一些相同的性质。
考虑随机变量a、b、c；若它们满足P(a|b,c)?P(a|b)或P(b,c)?0，则称a与b在给定c的条件下条件独立，记为a?b|c。
由P(a|b,c)?P(a|b)可以推出P(a,b|c)?P(a|c)P(b|c)；反之当P(b|c)?0时，由
P(a,b|c)?P(a|c)P(b|c)可以推出P(a|b,c)?P(a|b)。因此我们有a?b|c当且仅
当P(a,b|c)?P(a|c)P(b|c)。
图2. 三个节点头尾相接
例2. a, b, c三个节点形状如图2所示，P(a,b,c)?P(a)P(c|a)P(b|c)，a, b的概率分布可以表示为：P(a,b)??cP(a)P(c|a)P(b|c)?P(a)P(b)，因a与b不独立。a, b
在给定c下的条件概率为：
P(a,b|c)?P(a)P(c|b)P(b|c)?P(a|c)P(b|c)P(c)
因此a?b|c。
图3. 三个节点尾尾相接
例3. a, b, c三个节点形状如图3所示，P(a,b,c)?P(c)P(a|c)P(b|c)，a, b的概率分布可以表示为： P(a,b) ? ? cP(c)P(a | c)P(b | c) ? P(a)P(b) ，因a与b不独立。a, b在给定c下的条件概率为：
P(a,b|c)?P(c)P(a|c)P(b|c)?P(a|c)P(b|c)，
P(c)因此a?b|c。
图4. 三个节点头头相接
例4. a, b, c三个节点形状如图4所示，P(a,b,c)?P(a)P(b)P(c|a,b)，a, b的概率分布可以表示为： P(a,b) ? ? c P(a)P(b)P(c | a,b) ? P(a)P(b) ，因a与b独立。a, b在给定c下的条件概率为：
P(a,b|c)?P(a)P(b)P(c|a,b)?P(a|c)P(b|c)，
P(c)因此a与b在条件c下不条件独立。
概率图模型中图G的结构与概率分布P中的条件独来性存在某种关系，为了揭示这种关系，我们首先给出有向分隔的定义：
A与B被C有向分隔如果A中任意节点到B中任意节点的路径满足下面两条中的任意一条：
1.路径经过C中某个节点，并且与C中节点“头尾相连”（形如图2）或“头头相连”（图3中的c）。
2.路径中“头头相连”的节点（形如图4中的c）和它的后代节点都不在C中。
我们有下面一个定理：
定理1. 概率分布P可以表示由有向图G表出当且仅当图G中有向分隔对应于概率分布P中的条件独立。 定理证明见参考文献[6]
有了定理1，我们可以通过找出图中所有的有向分隔来找出概率分布满足的条件独立性，但这并不能确保找出概率分布中的所有条件独立性。定理1同时建立了满足图结构的概率分布与满足一定条件独立性的概率分布之间的等价性。
1.3无向图模型
1.3.1定义
无向图模型也叫马尔科夫随机场，顾名思义，无向图模型对应的图是无向图。 首先给出最大团的定义：图的最大团是指图G的一个完全子图C，如果在C中加入G中的任何不在C中的节点后，C都不再是完全图。
我们称概率分布P可以由无向图G表出，如果概率分布可以分解为：
P(x)?1fC(xC) (1.2) ?ZC??其中xC是与图G中的最大团C对应的随机变量的集合（见1.0），?是图G中所有最大团组成的集合，fC(xC)是定义在C上的函数，称为特征函数。我们只考虑fC取值恒大于0的情形，因为只有在这个条件下，Hammersley-Clifford成立。
Z???fC(xc) (1.3)
XCZ称为划分函数，是为了使概率分布满足归一性而定义的量。我们可以灵活的定义fC，而不用考虑概率分布的归一性。
例5. 图5中的无向图模型的概率分布为：
P(x1,x2,x3,x4)?f1(x1,x2,x3)f2(x2,x5)f3(x3,x4)/Z
1.3.2条件独立性
与有向图模型类似，我们首先定义无向图模型中分隔的定义，然后给出分隔与条件独立的关系。
无向图模型的分隔定义与图论中的分隔定义完全一致：在图G中，称节点集A与节点集B被节点集C分隔开如果在G中删除C中的节点后，A与B之间不存在任何路径。
定理2（Hammersley-Clifford）如果无向图模型中的特征函数取值恒大于0，那么概率分布P可以表示由无向图G表出当且仅当图G中分隔对应于P中的条件独立。
有了定理2，我们可以通过找出图中所有的分隔来找出概率分布满足的条件独立性。
x1x2x3x5x4 图5. 一个简单的无向图模型（与图1相对应）
1.3.3有向图模型与无向图模型之间的关系
有向图模型总是可以转换为无向图模型。我们只需要连接每个节点的任意两个父节点，然后把有向边变为无向边，这样我们原来有向图中的每一个节点与其父节点形成的子图是完全图，令fk(xk,pak)?P(xk|pak)、Z?1，有向图模型就转化成了无向图模型。 例如：令f1(x1,x2,x3)?P(x3|x1,x2)，
f2(x2,x5)?P(x5|x3)，f3(x3,x4)?P(x4|x3)，Z?1，则例5表示的模型就是例1
表示的模型，如图5所示。
1.4概率图模型的两个基本问题
1.4.1两个基本问题 考虑两个基本问题：
概率图模型及求解方法
