概率无向图模型

Posted on

概率无向图模型

概率无向图模型（probabilistic undirected graphical model），又称为马尔可夫随机场（Markov random field），是一个可以由无向图表示的联合概率分布。

1. 模型定义

图是由结点及连接结点的边组成的集合，记作\(G = (V,E)\)，无向图是指没有方向的边。

概率图模型是由图表示的概率分布。设有联合概率分布\(P(Y)\)，\(Y \in \mathscr{Y}\)是一组随机变量。由无向图\(G=(V,E)\)表示概率分布\(P(Y)\)，即在图\(G\)中，结点\(v \in V\)表示一个随机变量\(Y_v\)，\(Y = (Y_v)_{v \in V}\)；边\(e \in E\)表示随机变量之间的概率依赖关系。

给定一个联合概率分布\(P(Y)\)和表示它的无向图\(G\)。首先定义无向图表示的随机变量之间存在的成对马尔可夫性、局部马尔可夫性和全局马尔可夫性：

  1. 成对马尔可夫性：设\(u\)和\(v\)是无向图\(G\)中任意两个没有边连接的结点，结点\(u\)和\(v\)分别对应随机变量\(Y_u\)和\(Y_v\)。其他所有节点为\(O\)，对应随机变量组是\(Y_O\)。成对马尔可夫性是指给定随机变量组\(Y_O\)的条件下随机变量\(Y_u\)和\(Y_v\)是条件独立的，即 \[P(Y_u,Y_v|Y_O) = P(Y_u|Y_O) P(Y_v|Y_O)\]
  2. 局部马尔可夫性：设\(v \in V\)是无向图\(G\)中任意一个结点，\(W\)是与\(v\)有边连接的所有结点，\(O\)是\(v,W\)以外的其他所有结点。\(v\)表示的随机变量是\(Y_v\)，\(W\)表示的随机变量组是\(Y_W\)，\(O\)表示的随机变量组是\(Y_O\)。局部马尔可夫性是指在给定随机变量组\(Y_W\)的条件下随机变量\(Y_v\)与随机变量组\(Y_O\)是独立的，即 \[P(Y_v, Y_O|Y_W) = P(Y_v|Y_W) P(Y_O|Y_W)\] 在\(P(Y_O|Y_W) > 0\)时，等价地， \[P(Y_v|Y_W) = P(Y_v | Y_W, Y_O)\]
  3. 全局马尔可夫性：设结点集合\(A,B\)是在无向图\(G\)中被结点集合\(C\)分开的任意结点集合，如下图所示。结点集合\(A,B\)和\(C\)所对应的随机变量组分别是\(Y_A,Y_B\)和\(Y_C\)。全局马尔可夫性是指在给定随机变量组\(Y_C\)的条件下随机变量组\(Y_A\)和\(Y_B\)是条件独立的，即 \[P(Y_A,Y_B|Y_C) = P(Y_A|Y_C) P(Y_B|Y_C)\]

上述成对的、局部的、全局的马尔可夫性定义是等价的。

概率无向图模型：设有联合概率分布\(P(Y)\)，由无向图\(G=(V,E)\)表示，在图\(G\)中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布\(P(Y)\)满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型，或马尔可夫随机场。

对于给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解。

2. 概率无向图模型的因子分解

团与最大团：无向图\(G\)中任何两个结点均有边连接的结点子集称为团（clique）。若\(C\)是无向图\(G\)的一个团，并且不能再加进任何一个\(G\)的结点使其成为一个更大的团，则称此\(C\)为最大团（maximal clique）。

下图表示由4个结点组成的无向图。图中2个结点组成的团有5个：\(\{Y_1,Y_2\},\{Y_2,Y_3\},\{Y_3,Y_4\},\{Y_4,Y_2\}\)和\(\{Y_1,Y_3\}\)。有2个最大团\(\{Y_1,Y_2,Y_3\}\)和\(\{Y_2,Y_3,Y_4\}\)。而\(\{Y_1,Y_2,Y_3,Y_4\}\)不是一个团，因为\(Y_1\)和\(Y_4\)没有边相连。

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解。

给定概率无向图模型，设其无向图为\(G\)，\(C\)为\(G\)上的最大团，\(Y_C\)表示\(C\)对应的随机变量。那么概率无向图模型的联合概率分布\(P(Y)\)可写作图中所有最大团\(C\)上的函数\(\Psi_C(Y_C)\)的乘积形式，即 \[P(Y) = \frac{1}{Z} \prod_C \Psi_C(Y_C)\] 其中\(Z\)为规范化因子， \[Z = \sum_Y \prod_C \Psi_C (Y_C)\] 规范化因子保证\(P(Y)\)构成一个概率分布。函数\(\Psi_C(Y_C)\)称为势函数（potential function）。这里要求势函数\(\Psi_C(Y_C)\)是严格正的，通常定义为指数函数： \[\Psi_C(Y_C) = \exp \{ - E(Y_C) \}\] 概率无向图模型的因子分解由下述定理来保证：
Hammersley-Clifford定理：概率无向图模型的联合概率分布\(P(Y)\)可以表示为如下形式：
\[\begin{equation} P(Y) = \frac{1}{Z} \prod_C \Psi_C(Y_C) \nonumber \\ Z = \sum_Y \prod_C \Psi_C (Y_C) \nonumber \end{equation}\] 其中，\(C\)是无向图的最大团，\(Y_C\)是\(C\)的结点对应的随机变量，\[\Psi_C(Y_C)\]是\(C\)上定义的严格正函数，乘积是在无向图所有的最大团上进行的。