马尔可夫随机场

马尔可夫随机场（Markov Random Field,简称MRF）是典型的马尔可夫网，这是一种著名的无向图模型。图中每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数（potential functions）,亦称“因子”（factor），这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。

图 14.2 一个简单的马尔可夫随机场

图14.2显示出一个简单的马尔可夫随机场。对于图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个“团”（clique）。若在一个团中加入另外任何一个结点都不再形成团，则称该团为“极大团”（maximal clique）;换言之，极大团就是不能被其它团所包含的团。例如，在图14.2中， ${x_1,x_2},{x_1,x_3},{x_2,x_4},{x_2,x_5},{x_2,x_6},{x_3,x_5},{x_5,x_6}$ 和 ${x_2,x_5,x_6}$ 都是团,并且除了 ${x_2,x_5},{x_2,x_6}$ 和 ${x_5,x_6}$ 之外都是极大团;但是,因为 $x_2$ 和 $x_3$ 之间缺乏连接, ${x_1,x_2,x_3}$ 并不构成团.显然,每个结点至少出现在一个极大团中.

在马尔可夫随机场中,多个变量之间的联合概率分布能基于团分解为多个因子的乘积,每个因子仅与一个团相关.具体来说,对于 $n$ 个变量 $mathrm{x}={x_1,x_2,dots,x_n}$ ,所有团构成的集合为 $mathcal{C}$ ,与团 $Qinmathcal{C}$ 对应的变量集合记为 $mathrm{x_Q}$ ,则联合概率分布 $P(mathrm{x})$ 定义为

$P(mathrm{x})=frac{1}{Z}prod_{Qinmathcal{C}}psi_Q(mathrm{x_Q})$

其中 $psi_Q$ 为与团 $Q$ 对应的势函数，用于对团 $Q$ 中的变量关系进行建模， $Z=sum olimits_xprod olimits_{Qinmathcal{C}}psi_Q(mathrm{x_Q})$ 为规范化因子，以确保 $P(mathrm{x})$ 是被正确定义的概率.在实际应用中,精确计算 $Z$ 通常很困难,但许多任务往往并不需获得 $Z$ 的精确值.

显然,若变量个数较多,则团的数目将会很多(例如,所有相互连接的两个变量都会构成团), 这就意味着 $P(mathrm{x})$ 会有很多乘积项,显然会给计算带来负担.注意到若团 $Q$ 不是极大团，则它必被一个极大团 $Q^*$ 所包含，即 $mathrm{x}_Qsubseteqmathrm{x}_{Q^*}$ ；这意味着变量 $mathrm{x}_Q$ 之间的关系不仅体现在势函数 $psi_Q$ 中，还体现在 $psi_{Q^*}$ 中。于是，联合概率 $P(mathrm{x})$ 可基于极大团来定义.假定所有极大团构成的集合为 $mathcal{C}^*$ ,则有

$P(mathrm{x})=frac{1}{Z^*}prod_{Qinmathcal{C}^*}psi_Q(mathrm{x_Q})$

其中 $Z^*=sum olimits_xprod olimits_{Qinmathcal{C}^*}psi_Q(mathrm{x}_Q)$ 为规范化因子。例如图14.2中 $mathrm{x}={x_1,x_2,dots,x_6}$ ,联合概率分布 $P(mathrm{x})$ 定义为

$P(mathrm{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)$ ,

其中,势函数 $psi_{256}(x_2,x_5,x_6)$ 定义在极大团 ${x_2,x_5,x_6}$ 上,由于它的存在,使我们不再需为团 ${x_2,x_5},{x_2,x_6}$ 和 ${x_5,x_6}$ 构建势函数.

在马尔可夫随机场中如何得到”条件独立性”呢？同样借助“分离”的概念，如图 14.3所示，若从结点集A中的结点到B中的结点都必须经过结点集C中的结点，则称结点集A和B被结点集C分离，C称为“分离集”（separating set）.对马尔可夫随机场，有

“全局马尔可夫性”（global Markov property）: 给定两个变量子集的分离集，则这两个变量子集条件独立。

也就是说，图 14.3中若令A,B和C对应的变量集分别为 $mathrm{x}_A,mathrm{x}_B$ 和 $mathrm{x}_C$ ,则 $mathrm{x}_A$ 和 $mathrm{x}_B$ 在给定 $mathrm{x}_C$ 的条件下独立，记为 $mathrm{x}_Aperpmathrm{x}_B|mathrm{x}_C$ .

图 14.3 结点集A和B被结点集C分离

为便于讨论，我们令图 14.3中的A, B和C分别对应变量 $x_A,x_B$ 和 $x_C$ ，于是图 14.3简化为图 14.4.

图 14.4 图 14.3的简化版

对于图 14.4，可得联合概率

$P(x_A,x_B,x_C)=frac{1}{Z}psi_{AC}(x_A,x_C)psi_{BC}(x_B,x_C)$ .

基于条件概率的定义可得……

$P(x_A,x_B|x_C)=P(x_A|x_C)P(x_B|x_C)$

即 $x_A$ 和 $x_B$ 在给定 $x_C$ 时条件独立。

由全局马尔可夫性可得到两个很有用推论：

局部马尔可夫性（local Markov property）: 给定某变量的邻接变量，则该变量条件独立于其他变量。形式化地说，令 $V$ 为图的结点集， $n(v)$ 为结点 $v$ 在图上的邻接结点, $n^*(v)=n(v)cup{v}$ ,有 $mathrm{x}_vperpmathrm{x}_{Vsetminus{n^*(v)}}|mathrm{x}_{n(v)}$ .
成对马尔可夫性（pairwise Markov property）: 给定所有其他变量，两个非临接变量条件独立。形式化地说，令图的结点集和边集分别为 $V$ 和 $E$ ,对图中的两个结点 $u$ 和 $v$ ,若 $langle{u,v} angle otin{E}$ ,则 $mathrm{x}_uperpmathrm{x}_v|mathrm{x}_{vsetminuslangle{u,v} angle}$ .

现在我们来考察马尔可夫随机场中的势函数。显然，势函数 $psi_Q(mathrm{x}_Q)$ 的作用是定量刻画变量集 $mathrm{x}_Q$ 中变量之间的相关关系，它应该是非负函数，且在所偏好的变量取值上有较大函数值。例如，假定图 14.4中的变量均为二值变量，若势函数为

$\psi_{AC}(x_A,x_C)=\left\{ \begin{array}{rcl} 1.5,&&{\text{if}\;{x_A=x_C};}\\ 0.1,&&{\text{otherwise,}} \end{array}\right.$

$\psi_{BC}(x_B,x_C)=\left\{ \begin{array}{rcl} 0.2,&&{\text{if}\;{x_B=x_C};}\\ 1.3,&&{\text{otherwise,}} \end{array}\right.$

则说明该模型偏好变量 $x_A$ 与 $x_C$ 拥有相同的取值， $x_B$ 与 $x_C$ 拥有不同的取值；换言之，在该模型中 $x_A$ 与 $x_C$ 正相关， $x_B$ 与 $x_C$ 负相关。易知，令 $x_A$ 与 $x_C$ 相同且 $x_B$ 与 $x_C$ 不同的变量值指派将取得较高的联合概率。

为了满足非负性，指数函数常被用于定义势函数，即

$psi_Q(mathrm{x}_Q)=e^{-H_Q(mathrm{x}_Q)}$

$H_Q(mathrm{x}_Q)$ 是一个定义在变量 $mathrm{x}_Q$ 上的实值函数，常见形式为：

$H_Q(mathrm{x}_Q)=sum_{u,vin{Q},u ot=v}alpha_{uv}x_ux_v+sum_{vin{Q}}eta_vx_v$

其中 $alpha_{uv}$ 和 $eta_v$ 是参数.上式中的第二项仅考虑单结点,第一项则考虑每一对结点的关系.