分类目录：《深入理解机器学习》总目录
马尔可夫随机场（Markov Random Field，MRF）是典型的马尔可夫网，这是一种著名的无向图模型，图中每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数（Potential Functions），亦称“因子”（Factor），这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。
上图显示出一个简单的马尔可夫随机场，对于图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个“团”（Clique），若在一个团中加入另外任何一个结点都不再形成团，则称该团为“极大团（Maximal Clique）；换言之，极大团就是不能被其他团所包含的团，例如，在上图中{x1,x2}\{x_1, x_2\}{x1,x2}、{x1,x3}\{x_1, x_3\}{x1,x3}、{x2,x4}\{x_2, x_4\}{x2,x4}、{x2,x5}\{x_2, x_5\}{x2,x5}、{x2,x6}\{x_2, x_6\}{x2,x6}、{x3,x5}\{x_3, x_5\}{x3,x5}、{x5,x6}\{x_5, x_6\}{x5,x6}和{x2,x5,x6}\{x_2, x_5, x_6\}{x2,x5,x6}都是团，并且除了{x2,x5}\{x_2, x_5\}{x2,x5}、{x2,x6}\{x_2, x_6\}{x2,x6}和{x5,x6}\{x_5, x_6\}{x5,x6}之外都是极大团；但是，因为x2x_2x2和x3x_3x3之间缺乏连接，{x1,x2,x3}\{x_1, x_2, x_3\}{x1,x2,x3}并不构成团，显然，每个结点至少出现在一个极大团中。
在马尔可夫随机场中，多个变量之间的联合概率分布能基于团分解为多个因子的乘积，每个因子仅与一个团相关，具体来说，对于nnn个变量x={x1,x2,⋯,xn}x=\{x_1, x_2, \cdots, x_n\}x={x1,x2,⋯,xn}，所有团构成的集合为C\mathcal{C}C，与团Q∈CQ\in\mathcal{C}Q∈C对应的变量集合记为xQx_QxQ，则联合概率P(x)P(x)P(x)定义为：
P(x)=1Z∏Q∈CψQ(xQ)P(x)=\frac{1}{Z}\prod_{Q\in\mathcal{C}}\psi_Q(x_Q)P(x)=Z1Q∈C∏ψQ(xQ)
其中ψQ\psi_QψQ为与团QQQ对应的势函数，用于对团QQQ中的变量关系进行建模，Z=∑x∏Q∈CψQ(xQ)Z=\sum_x\prod_{Q\in\mathcal{C}}\psi_Q(x_Q)Z=∑x∏Q∈CψQ(xQ)为规范化因子，以确保P(x)P(x)P(x)是被正确定义的概率，在实际应用中，精确计算ZZZ通常很困难，但许多任务往往并不需获得ZZZ的精确值显然，若变量个数较多，则团的数目将会很多（例如，所有相互连接的两个变量都会构成团），这就意味着上式会有很多乘积项，显然会给计算带来负担。注意到若团QQQ不是极大团，则它必被一个极大团Q∗Q^*Q∗所包含，即xQ⊆xQ∗x_Q\subseteq x_Q^*xQ⊆xQ∗。这意味着变量xQx_QxQ之间的关系不仅体现在势函数ψQ\psi_QψQ中，还体现在ψQ∗\psi_{Q^*}ψQ∗中。于是，联合概率P(x)P(x)P(x)可基于极大团来定义。假定所有极大团构成的集合为C∗\mathcal{C^*}C∗，则有：P(x)=1Z∗∏Q∈C∗ψQ(xQ)P(x)=\frac{1}{Z^*}\prod_{Q\in\mathcal{C^*}}\psi_Q(x_Q)P(x)=Z∗1Q∈C∗∏ψQ(xQ)
如上图中x={x1,x2,x3,⋯,x6}x=\{x_1, x_2, x_3, \cdots, x_6\}x={x1,x2,x3,⋯,x6}，联合概率分布P(x)P(x)P(x)定义为：
P(x)=1Zψ12(x1,x2)ψ13(x1,x3)ψ24(x2,x4)ψ35(x3,x5)ψ256(x2,x5,x6)P(x)=\frac{1}{Z}\psi_{12}(x_1, x_2)\psi_{13}(x_1, x_3)\psi_{24}(x_2, x_4)\psi_{35}(x_3, x_5)\psi_{256}(x_2, x_5, x_6)P(x)=Z1ψ12(x1,x2)ψ13(x1,x3)ψ24(x2,x4)ψ35(x3,x5)ψ256(x2,x5,x6)
其中，势函数ψ256(x2,x5,x6)\psi_{256}(x_2, x_5, x_6)ψ256(x2,x5,x6)定义在极大团{x2.x5,x6}\{x_2. x_5, x_6\}{x2.x5,x6}上，由于它的存在，使我们不再需为团{x2,x5}\{x_2, x_5\}{x2,x5}、{x2,x6}\{x_2, x_6\}{x2,x6}和{x5,x6}\{x_5, x_6\}{x5,x6}构建势函数。
在马尔可夫随机场中如何得到“条件独立性”呢？同样借助“分离”的概念，如下图所示，若从结点集AAA中的结点到BBB中的结点都必须经过结点集CCC 中的结点，则称结点集AAA和BBB被结点集CCC分离，CCC称为“分离集（Separating Set）。对马尔可夫随机场，有全局马尔可夫性（Global Markov Property），即给定两个变量子集的分离集，则这两个变量子集条件独立。如下图，若令AAA、BBB和CCC对应的变量集分别为xAx_AxA，xBx_BxB和xCx_CxC，则xAx_AxA和xBx_BxB在给定xCx_CxC的条件下独立，记为：xA⊥xB∣xCx_A\bot x_B | x_CxA⊥xB∣xC。
由全局马尔可夫性可得到两个很有用的推论：
局部马尔可夫性（Local Markov Property）：给定某变量的邻接变量，则该变量条件独立于其他变量。形式化地说，令VVV为图的结点集，n(v)n(v)n(v)为结点vvv在图上的邻接结点，n∗(v)=n(v)∪{v}n^*(v)=n(v)\cup \{v\}n∗(v)=n(v)∪{v}，则有xv⊥xV\n∗(v)∣n(v)x_v\bot x_{V\backslash n^*(v)} | n(v)xv⊥xV\n∗(v)∣n(v)成对马尔可夫性（Pairwise Markov Property）：给定所有其他变量，两个非邻接变量条件独立。形式化地说，令图的结点集和边集分别为VVV和EEE，对图中的两个结点uuu和vvv，若<u,v>∉E<u, v>\notin E<u,v>∈/E，则xu⊥xv∣xV\<u,v>xu_\bot x_v | x_{V\backslash <u, v>}xu⊥xv∣xV\<u,v>
现在我们来考察马尔可夫随机场中的势函数，显然，势函数ψQ(xQ)\psi_Q(x_Q)ψQ(xQ)的作用是定量刻画变量集xQx_QxQ中变量之间的相关关系，它应该是非负函数，且在所偏好的变量取值上有较大函数值，例如，假定上图的变量均为二值变量，若势函数为：
ψAC(xA,xC)={1.5,ifxA=xC0.1,otherwiseψBC(xB,xC)={0.2,ifxB=xC1.3,otherwise\psi_{AC}(x_A, x_C)=\left\{ \begin{aligned} 1.5, & \quad\text{if}\quad x_A = x_C \\ 0.1, & \quad\text{otherwise} \\ \end{aligned} \right.\\ \quad\\ \psi_{BC}(x_B, x_C)=\left\{ \begin{aligned} 0.2, & \quad\text{if}\quad x_B = x_C \\ 1.3, & \quad\text{otherwise} \\ \end{aligned} \right. ψAC(xA,xC)={1.5,0.1,ifxA=xCotherwiseψBC(xB,xC)={0.2,1.3,ifxB=xCotherwise
则说明该模型偏好变量xAx_AxA与xCx_CxC拥有相同的取值，xBx_BxB与xCx_CxC拥有不同的取值；换言之，在该模型中xAx_AxA与xCx_CxC正相关，xBx_BxB与xCx_CxC负相关。所以，令xAx_AxA与xCx_CxC相同且xBx_BxB与xCx_CxC不同的变量值指派将取得较高的联合概率，为了满足非负性，指数函数常被用于定义势函数，即：
ψQ(xQ)=e−HQ(xQ)\psi_Q(x_Q)=e^{-H_Q(x_Q)}ψQ(xQ)=e−HQ(xQ)
其中，HQ(xQ)H_Q(x_Q)HQ(xQ)是一个定义在变量xQx_QxQ上的实值函数，常见形式为：
HQ(xQ)=∑u,v∈Q,u≠vαuvxuxv+∑v∈QβvxvH_Q(x_Q)=\sum_{u,v\in Q,u\neq v}\alpha_{uv}x_ux_v+\sum_{v\in Q}\beta_vx_vHQ(xQ)=u,v∈Q,u=v∑αuvxuxv+v∈Q∑βvxv
其中αuv\alpha_{uv}αuv和βv\beta_vβv是参数。上式中的第二项仅考虑单结点，第一项则考虑每一对结点的关系。
参考文献：
[1] 周志华. 机器学习[M]. 清华大学出版社, .
深入理解机器学习——概率图模型（Probabilistic Graphical Model）：马尔可夫随机场（Markov Random Field MRF）
