概率无向图模型

前面我们所讲的朴素贝叶斯，贝叶斯网络，马尔科夫模型，隐马尔科夫模型都属于概率有向图模型。概率无向图模型和概率有向图模型处理方法有少许不同，本文单独介绍。
马尔科夫随机场是一种著名的概率无向图模型，李航的书中直接将两者划为了等号。
本文首先介绍概率无向图模型的定义，然后介绍概率无向图模型的因子分解。

马尔科夫随机场的定义

马尔科夫随机场是一种著名的概率无向图模型。图中每个结点表示一个或者一组随机变量，结点之间的边表示两个随机变量之间的依赖关系。马尔科夫随机场有一组势函数，也可称之为因子。这些势函数是定义在变量子集上的非负实函数，可以用其定义联合概率分布。

团和极大团

假设C$C$是概率图中的一个子集。C$C$中任意两点间都有边链接，则可称C$C$为团。若在一个团中加入任何另外一个节点，都会破坏当前的团结构，则可称C$C$为级打团。换言之，极大团就是不能被其他团所包含的团。

从上图可以看出可包括如下团：(x1,x2),(x1,x3),(x2,x3),(x4,x3),(x4,x2),(x1,x2,x3),(x2,x3,x4)$(x_1,x_2),(x_1,x_3),(x_2,x_3),(x_4,x_3),(x_4,x_2),(x_1,x_2,x_3),(x_2,x_3,x_4)$，其中(x1,x2,x3)$(x_1,x_2,x_3)$和(x2,x3,x4)$(x_2,x_3,x_4)$为极大团。
在马尔科夫随机场中，多个变量之间的联合分布能基于团分解为多个因子的乘积，每一个因子仅仅与一个团相关，具体的说，假设有n$n$个随机变量，构成的集合为X={x1,x2,x3,...,xn}$X=\{x_1,x_2,x_3,...,x_n\}$。所有团构成的集合为C，与团QεC$Q\epsilon C$对应的变量集合为XQ$X_Q$，则联合概率分布P(X)$P(X)$可定义为：

P(X)=1Z∏QϵCφQ(XQ)$$P(X)=\frac{1}{Z}\prod _{QϵC}{\phi }_Q(X_Q)$$

。
其中φQ${\phi }_Q$为与团Q$Q$对应的势函数，他是对团Q$Q$中的变量关系进行建模，Z=∑x∏QϵCφQ(XQ)$Z=\sum _x\prod _{QϵC}{\phi }_Q(X_Q)$为规范化因子，为了确保P(X)$P(X)$是被正确定义的概率函数，实际计算中，想精确得到Z$Z$的值是非常困难的，但许多任务中，只是将Z$Z$当作一个规范化因子，对其要求并不高。
显然，若变量个数比较多的情况下，团的数目会非常的多，比如仅临的两个结点就可以组成一个团。这意味着上面的一个函数有着非常多的乘积，同时也需要大量的势函数，会给计算带来极大的负担。但是注意到若Q$Q$不是一个极大团，那么它必然被一个极大团所包含，那么极大团的势函数也会影响到团Q$Q$，所以单独计算非极大团的势函数有点计算多余。那么可以认为计算P(x)$P(x)$所对应的团的集合C$C$只需要包含极大团即可。

与贝叶斯网一样，马尔可夫随机场可以视为定义了一系列由图结构确定的独立性假设。
在马尔科夫随机场中如何获得条件性假设了？

条件性假设

在马尔科夫随机场中同样借助分离的概念，获得条件独立性。

若从结点集合A$A$中的点到达结点集合B$B$中，必须经过节点集合C$C$。则称节点集合C$C$为分离集，所以有性质：
全局马尔可夫性：给定两个子集的分离集，则这两个变量子集条件独立。
即：假设集合A$A$为XA$X_A$，集合B$B$为XB$X_B$，集合C$C$为XC$X_C$，则有：

p(XA,XB|XC)=p(XA|XC)p(XB|XC)$$p(X_A,X_B|X_C)=p(X_A|X_C)p(X_B|X_C)$$

由全局马尔科夫性可得到两个很有用的推论：
局部马尔可夫性：给定某变量的邻接变量，则该变量条件独立于其他变量。形式化的说，令V$V$为图中结点的集合，n(v)$n(v)$为节点v$v$的邻接结点，n∗(v)=n(v)⋃v$n^{\ast }(v)=n(v)\bigcup v$，则有

xv⊤xV∖n∗(v)|xn(v)$$x_v\mathrm{\top }{x}_{V\setminus n^{\ast }(v)}|x_{n(v)}$$

成对马尔科夫行：给定所有的其他变量，两个非邻接变量条件独立。形式化的说，令图的节点集合和边的节点集合分别为V$V$和E$E$，对图中的两个节点u$u$和v$v$，若u$u$和v$v$之间没有边连接，则有

xv⊤xv|xV∖<u,v>$$x_v\mathrm{\top }{x}_v|x_{V\setminus <u,v>}$$