1. 引言

前文提到，贝叶斯网络最大的特点就是能够人为指定各个因素的影响方向，但是实际生活中并非如此，生活中的变量更多是相互影响的，因此，便有了无向图上的图模型——无向图模型，又叫马尔可夫网。不过在认识马尔可夫网之前，需要了解一下下面几个概念。

---

2. 参数化

2.1 示例

目前有四个学生a、b、c、d。a只跟b、d玩，b跟a、c玩，c只跟b、d玩，d只跟a、c玩。此时大家同时对一个解法的正确性产生了不同的见解，都试图想要说服对方。0代表同意，1代表否定，degree代表同意或者否定的程度，越大表示程度越强。关系网如下如所示：

• 只看a、b，可以发现二人勉强能统一意见；
• 只看b、c，二者基本上能够统一意见；
• 只看c、d，二者存在很大的分歧；
• 只看a、d，二者基本上能够统一意见。

由于四个人的关系a不跟c玩，b不跟d玩，很难综合考虑四个人的意见，仿佛中了诅咒，那么，怎么才能打破这个诅咒呢？

于是上帝出手制定了如下规则：

• rule 1：
  把几个人之间的同意或者否定的程度定义为一个因子，用$\phi$ϕ表示，考虑了几个人的态度就把这几个人放到一起，用$Scope[\phi]$Scope[ϕ]表示。
  例如，$\phi_1[a,b]$ϕ1​[a,b]表示考虑了a、b的意见。

• rule 2：

  • 当考虑3个人时(以$a^i,b^i,c^i$ai,bi,ci)为例，必须按照一下的规则计算。$i=0、1$i=0、1，$a^i$ai代表$a$a的状态。
    $P(a,b,c)=\phi_1(a,b)*\phi_2(b,c)*\phi_3(c,a)$P(a,b,c)=ϕ1​(a,b)∗ϕ2​(b,c)∗ϕ3​(c,a)
  • 当考虑4个人时，必须按照一下的规则计算。
    $P(a,b,c,d)=\phi_1(a,b)*\phi_2(b,c)*\phi_3(c,d)*\phi_4(d,a)$P(a,b,c,d)=ϕ1​(a,b)∗ϕ2​(b,c)∗ϕ3​(c,d)∗ϕ4​(d,a)

• rule 3：
  考虑完所有人的意见之后，需要将其归一化。

根据上述三条规则:

• 若四个人都同意该解法$a^0,b^0,c^0,d^0$a0,b0,c0,d0，则有：
  $P(a^0,b^0,c^0,d^0)=\phi_1(a^0,b^0)*\phi_2(b^0,c^0)*\phi_3(c^0,d^0)*\phi_4(d^0,a^0)=30*100*1*100=300000$P(a0,b0,c0,d0)=ϕ1​(a0,b0)∗ϕ2​(b0,c0)∗ϕ3​(c0,d0)∗ϕ4​(d0,a0)=30∗100∗1∗100=300000;
• 若四个人状态为:$a^1,b^1,c^0,d^1$a1,b1,c0,d1，则有：
  $P(a^1,b^1,c^0,d^1)=\phi_1(a^1,b^1)*\phi_2(b^1,c^0)*\phi_3(c^0,d^1)*\phi_4(d^1,a^1)=10*1*100*1*100=100000$P(a1,b1,c0,d1)=ϕ1​(a1,b1)∗ϕ2​(b1,c0)∗ϕ3​(c0,d1)∗ϕ4​(d1,a1)=10∗1∗100∗1∗100=100000以此类推。

最后考虑完所有的人意见后，需要进行归一化处理
$Z= \sum_{a,b,c,d}\phi_1(a,b)·\phi_2(b,c)·\phi_3(c,d)·\phi_4(d,a)$Z=a,b,c,d∑​ϕ1​(a,b)⋅ϕ2​(b,c)⋅ϕ3​(c,d)⋅ϕ4​(d,a)
，即每个概率除以其加和，于是有：

此时再看AB的意见，已经变成了：

由此可见，在考虑了四个人的大背景下，其实a、b两个人的意见是相左的。

2.2 因子

在2.1节中，把几个重要的概念定义一下：

• a,b,c,d就是变量的集合$D$D；
• a,b,c,d每个人的态度叫做$Val(D)$Val(D)
• 能够将不同人的意见联系起来的东西，叫因子，它能够把程度变成一个量化的数字；
• 某个因子中考虑的人称为该因子的辖域。

概念：

1. 假定$D$D表示随机变量的集合，因子$\phi$ϕ定义为从$Val(D)$Val(D)映射到实数域$R$R的一个函数，假如因子中所有的值均为非负，则该因子为非负的。
2. 变量集$D$D称为因子的辖域，记为$Scope[\phi]$Scope[ϕ]。
3. 分配函数，用作归一化。
4. 因子的操作：令$X,Y,Z$X,Y,Z是三个不相交的变量集，且令$\phi_1(X,Y)$ϕ1​(X,Y)和$\phi_2(Y,Z)$ϕ2​(Y,Z)是两个因子，定义其乘积为新的因子$\Phi(X,Y,Z)$Φ(X,Y,Z)。
   $\Phi(X,Y,Z)=\phi_1(X,Y)·\phi_2(Y,Z)$Φ(X,Y,Z)=ϕ1​(X,Y)⋅ϕ2​(Y,Z)

2.2.1 因子的实际意义

利用该分布回答查询，例如在a,b,c上求和，可以得出$P(b^1)=0.7323, P(b^0)=0.268$P(b1)=0.7323,P(b0)=0.268，其意义为：B同学有26%的几率同意，如果我们知道c同学同意的情况下($c^0$c0)，那么$P(b^1|c^0)=0.06$P(b1∣c0)=0.06

注意：

2.2.2 打破诅咒的方法

从下图右侧可以看出，b与c，c与d，d与a的联系性最强，而ab之间稍弱，因此，若要打破这个无向图，需要从ab之间的关系下手。

---

3. 吉布斯分布

3.1 吉布斯分布定义

假如分布$P_{\Phi}$PΦ​定义如下：
$P_{\Phi}(X_1,...,X_n)=\frac{1}{Z}\widetilde{P}_{\Phi}(X_1,...,X_n) \tag{3.1}$PΦ​(X1​,...,Xn​)=Z1​PΦ​(X1​,...,Xn​)(3.1)
其中
$\widetilde{P}(X_1,...,X_n)=\phi_1(D_1)·...·\phi_m(D_m) \tag{3.2}$P(X1​,...,Xn​)=ϕ1​(D1​)⋅...⋅ϕm​(Dm​)(3.2)
且
$Z= \sum_{X_1,..,X_n}\widetilde{P}_{\Phi}(X_1,...,X_n) \tag{3.3}$Z=X1​,..,Xn​∑​PΦ​(X1​,...,Xn​)(3.3)
分布$P_{\Phi}$PΦ​就称为吉布斯分布。

---

4 无向图模型(马尔可夫网)

4.1 定义

马尔可夫网需要满足的条件：

1. 无向图
2. 无向图中每个节点表示一个或者一组势函数，也就是我们前文提到的“因子”。

4.2 团

马大爷说：这些因子各自抱团，于是就有了团的概念。当然是我瞎说的。

在无向图中任何两个结点均有边连接的结点子集称为团，例如，在下图中，假设有随机变量$X_1,X_2,X_3,X_4$X1​,X2​,X3​,X4​，则$\left \{X_1,X_2 \right \}${X1​,X2​}构成了一个团，$\left \{X_1,X_4 \right \}${X1​,X4​}未构成团。

此时，再往团中加入任意一个结点，若集合不满足成团的条件，则称加入结点之前的团为最大团。如，往集合$\left \{X_1,X_2 \right \}${X1​,X2​}中加入$X_3$X3​，$X_1,X_2,X_3$X1​,X2​,X3​三个点之间均有边连接，依然满足成团的条件，但是若继续加入结点$X_4$X4​，由于$X_1$X1​不与$X_4$X4​相连，故而$\left \{X_1,X_2,X_3 \right \}${X1​,X2​,X3​}为最大团。

4.3 马尔可夫随机场(Markov Random Field, MRF)

马尔可夫随机场作为一种典型的马尔可夫网，其多个变量之间的联合概率分布能够基于团分解为多个因子的乘积，每个因子仅与一个团有关。

4.3.1 MRF中的联合概率

假设有$N$N个变量，$\boldsymbol{X}=\{X_1,X_2,...,X_N\}$X={X1​,X2​,...,XN​}，所有团构成的集合为$C$C，与团$Q \in C$Q∈C对应的变量集合记为$X_Q$XQ​，则联合概率$P(x)$P(x)定义为（就是吉布斯分布）：
$P(x)=\frac{1}{Z}\prod_{Q\in C}\Phi_Q(X_Q) \tag{4.1}$P(x)=Z1​Q∈C∏​ΦQ​(XQ​)(4.1)

但是由于随机变量$X$X过多，所对应团的数量也过多，因此采用最大团来定义：所有最大团构成的集合为$C^*$C∗，与最大团$Q \in C^*$Q∈C∗对应的变量集合记为$X_{Q^*}$XQ∗​，则联合概率$P(X)$P(X)定义为：
$P(X)=\frac{1}{Z^*}\prod_{Q\in C^*}\Phi_Q(X_Q) \tag{4.2}$P(X)=Z∗1​Q∈C∗∏​ΦQ​(XQ​)(4.2)
所以4.2节中，无向图的团和最大团的联合概率分布可以定义为：
$P(X)=\frac{1}{Z}\phi_{123}(X_1,X_2,X_3)·\phi_{234}(X_2,X_3,X_4) \tag{4.3}$P(X)=Z1​ϕ123​(X1​,X2​,X3​)⋅ϕ234​(X2​,X3​,X4​)(4.3)

4.3.2 另一种表示方法——对数

在公式(4.2)中，联合概率$P(X)$P(X)各个团通过连乘的方式表达：
$P(X)=\frac{1}{Z^*}\prod_{Q\in C^*}\Phi_Q(X_Q) \tag{4.2}$P(X)=Z∗1​Q∈C∗∏​ΦQ​(XQ​)(4.2)

更一般的，把$\Phi_Q(X_Q)$ΦQ​(XQ​)换成了$\exp(-w_Qf_Q(X_Q))$exp(−wQ​fQ​(XQ​))

因此有如下表达形式：
$\begin{aligned} P(X)=&\frac{1}{Z^*}\prod_{Q\in C^*}\exp(-w_Qf_Q(X_Q))\\ =&\frac{1}{Z^*}\exp(\sum_{Q\in C^*}-w_Qf_Q(X_Q)) \tag{4.4} \end{aligned}$P(X)==​Z∗1​Q∈C∗∏​exp(−wQ​fQ​(XQ​))Z∗1​exp(Q∈C∗∑​−wQ​fQ​(XQ​))​(4.4)
其中，$w_Q$wQ​为某一个团的系数，$f_Q$fQ​则代表特征函数。

举个栗子：
在图中

考虑$A,B$A,B的关系，指示特征函数$f$f可以表示为：
$f_{a,b}(A,B)= \left\{\begin{matrix} 1, & A=a,B=b\\ 0, & Other \end{matrix}\right.$fa,b​(A,B)={1,0,​A=a,B=bOther​
为了表示$A,B$A,B的关系，引入四个对应表值的特征，所以有：

而此时，$A,B$A,B的关系只可能是4中情况中的一种，所以
$\phi(X_1,X_2)=\exp(-\sum_{kl}w_{kl}f^{kl}_{12}(X_1,X_2))$ϕ(X1​,X2​)=exp(−kl∑​wkl​f12kl​(X1​,X2​))
其中，$w_{kl}=-\log(a_{kl})$wkl​=−log(akl​)，$kl=\{00, 01, 10, 11\}$kl={00,01,10,11}

不管用哪种表示法，都不用再为$\{X_1,X_2\}${X1​,X2​}；$\{X_2,X_3\}${X2​,X3​}和$\{X_3,X_4\}${X3​,X4​}构建势函数了。

那么，怎么寻找这些特殊的点呢？

4.3.3 MRF中的独立性

这里有个问题啊，一开始以为分离集对应的就是连接最大团之间的点，结果发现不是，只是分离两个结点集的结点的集合？？？那这样的话分离集内结点的多少不是取决于连接结点集的结点数目？？？？

解答：
意思就是说：$\chi$χ是所有结点的集合，X,Y,Z是其中三个不互相包含的结点集，且有$X\bigcup Y\bigcup Z=\chi$X⋃Y⋃Z=χ，那么，在给定Z时，任意两个结点$x \in X$x∈X和$y \in Y$y∈Y之间没有路径，那么Z就是他们的分离集。

对于满足“条件独立”的点的确定可以参考《概率图模型基础(2)——贝叶斯网络中的因果关系》中结构1,2,3。

根据结构1,2,3可知：只要满足结构2即可。以下图为例

简化后为

所以：马尔可夫随机场有的三个性质：

• 成对马尔可夫性
  
  结点X、Y互不相连，其他所有节点记为Z。此时：在给定随机变量组Z的情况下，X, Y条件独立，即有
  $P(X, Y|Z)=P(Y|Z) P(X|Z)$P(X,Y∣Z)=P(Y∣Z)P(X∣Z)

• 局部马尔可夫性
  

在图中任意取一个结点X，将与之有边相连的结点均记为Z，Y是除Z、X之外的所有点，X表示随机变量X，Z表示随机变量组为Z，Y表示随机变量组Y，则：在给定随机变量组Z的情况下，X, Y条件独立，即有
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P(X, Y|Z)&=P(X…

• 全局马尔科夫性
  
  在图中设有集合X,Y是被集合Z分开的任意结点集合，其所对应的随机变量组分别为X,Y，则在此条件下，认定随机变量组Z条件下，随机变量组X,Y是条件独立的。
  $P(X, Y|Z)=P(X|Z) P(Y|Z)$P(X,Y∣Z)=P(X∣Z)P(Y∣Z)

如果联合概率分布$Y$Y满足成对、局部或全局马尔可夫性，则该联合概率分布为概率无向图模型（马尔科夫随机场）。

---

5 Markov的独立性

在概率图模型基础(3)——贝叶斯网络的独立性
的独立性中介绍了贝叶斯网络的I-Map和P-Map，那么，在Markov网中，二者有和不同？

对于规则：

1. D、I相互独立
2. 在给定G的条件下，D、I相互依赖。

贝叶斯网中P-Maps的表达结构为：

但是在马尔可夫网中，

该连接方式可能表现为在给定G的条件下，D、I相互独立。要是D、I相互依赖，只能表现为下图的形式，但又遗失了规则1.

小结：

---

6 参考文献

• Coursera——Probabilistic Graphical Models
• Probabilistic Graphical Models - Principles and Techniques