概率图基础

发表于   |   分类于   |   阅读次数

作者: 引线小白-本文永久链接：httpss://www.limoncc.com/post/b9646fbf6c8d542fdb68ac01ad3c1c5a/
知识共享许可协议: 本博客采用署名-非商业-禁止演绎4.0国际许可证

Knowledge is the antidote to fear.
摘要：本文意在理解与分析图模型。若有错误，请大家指正。
关键词: 图模型,图论,有向图,无向图

一、问题来源

有向图模型($\displaystyle \textit{Directed Graphical Models}$)又称贝叶斯网络($\displaystyle \textit{Bayes Nets}$)。

对于用简单方法来训练复杂系统，我基本知道两个原则：模块化和抽象化。在机器学习领域，我是计算概率的辩护者。因为我相信概率论用它深入和迷人的方式执行了两个原则——因子分解与平均。在我看来，充分利用这两种机制是机器学习的前进方向。—— $\displaystyle \textit{Michael Jordan 1997}$ $\displaystyle \textit{(quted in(Frey 1998)}$

假设我们观察多个相关变量，例如文档中的单词、图像中的像素或微阵列中的基因。

1、我们如何能简洁地表示联合分布 $\displaystyle p\big(\bm{x}\mid \bm{\theta}\big)$？
2、在合理的计算时间内，给定其他，我们如何利用这个分布来推断一组变量?
3、我们如何通过合理的数据量来学习这个分布的参数?

这些问题是概率建模、推断和学习的核心，也是概率图的主题。我们参照 $\displaystyle \textit{Matlab}$的向量形式定义如下符号：$\displaystyle \bm{x}_{1:t-1}=x_t,\cdots,x_{t-1}$。定义如下术语：条件概率表格 CPTs $\displaystyle \textit{(conditional probability tables)}$、条件概率密度 CPD$\displaystyle \textit{(conditional probability distribution)}$、条件独立 CI$\displaystyle \textit{(Conditional independence)}$

我们来考察一下马尔可夫模型：给定现在，未来独立于过去。 这叫做一阶马尔可夫假设(二元模型假设)
$$\begin{align}
p(\bm{x})=p(x_1)\prod_{t=2}^Tp\big(x_t\mid x_{t-1}\big)
\end{align}$$
尽管一阶马尔可夫假设对于定义一维序列的分布很有用，但是如何定义二维图像的分布，或者三维视频，或者更一般的：任意变量集合(例如属于某些生物通路的基因)？这正是我们引入图模型的切入点。

一个图模型是应用条件独立假设来表达联合概率分布的方法。是一套能简洁紧凑地表达变量关系的工具。下面我们将不厌其烦的对图论术语下定义(这些术语都是顾名思义的)和显然的。

二、基本概念

2.1、图模型的基本符号

图 $graph$： $\displaystyle \mathcal{G}=\{V,E\}$
节点集 $nodes$： $\displaystyle V(\mathcal{G})$
边集 $edges$： $\displaystyle E(\mathcal{G})=\{st\mid s,t\in V\}$
阶 $order$： $\displaystyle n=n(\mathcal{G})=\mid\mathcal{G}\mid$
边数 $edges numbers$： $\displaystyle e=e(\mathcal{G})=\parallel\mathcal{G}\parallel$

2.2、节点与边的符号

【节点】：引入一个符号 $\displaystyle v_s$，表示第 $\displaystyle s$个节点，这意味着我们也可以用 $\displaystyle s$表示第 $\displaystyle s$个节点。我们将会根据上下文，灵活使用这两种表示符号。

【边】：引入另外一个符号来表示边

有向边：$\displaystyle s\to t=v_s\to v_t\Rightarrow\mathcal{G}(s,t)=1\Rightarrow <st>\in E(\mathcal{G})$
无向边：$\displaystyle s-t=v_s-v_t\Rightarrow \mathcal{G}(s,t)=1\land\mathcal{G}(s,t)=1\Rightarrow(st)\in E(\mathcal{G})$
某种边：$\displaystyle s\rightleftarrows t=v_s\rightleftarrows v_t\Rightarrow \mathcal{G}(s,t)=1\lor\mathcal{G}(s,t)=1\Rightarrow st\in E(\mathcal{G})$
没有边：$\displaystyle \require{cancel} s\cancel{\rightleftarrows}t\Rightarrow\mathcal{G}(s,t)=0\Rightarrow st \notin E(\mathcal{G})$

【分类】如果一个图的所有边都是有向边，则称其为有向图 $\displaystyle \textit{(Directed Graph)}$；如果都是无向边，则称其为无向图 $\displaystyle \textit{(Undirected Graph)}$；如果皆有之，则称其为混合图$\displaystyle \textit{(Mixed Graph)}$

2.3、关于节点认识
2.3.1、有向图下的节点基本概念

一个节点的 $Parent$父节点集: $\displaystyle pa(s)=\{t\mid\mathcal{G}(t,s)=1,t\in V(\mathcal{G})\}$
一个节点的 $Child$子节点集: $\displaystyle ch(s)=\{t\mid\mathcal{G}(s,t)=1,t\in V(\mathcal{G}) \}$
一个节点的 $Family$族节点集: $\displaystyle fam(s)=\{s\}\cup Pa(s)$

一个节点是 $root$根: $\displaystyle \exists pa(s)=\emptyset\to \textit{s is a root}$
一个节点是 $leaf$叶: $\displaystyle \exists ch(s)=\emptyset\to \textit{s is a leaf}$

一个节点的 $Ancestors$祖节点集： $\displaystyle an(s)=\{t\mid t\leadsto s\}$
一个节点的 $Descendants$孙节点集： $\displaystyle de(s)=\{t\mid s\leadsto t\}$

拓扑序 $\displaystyle \textit{(Topological Ordering)}$
一个节点下标序列满足 $\displaystyle x_s\to x_t\Rightarrow s<t$，也就是说父节点下标比子节点的小。这种下标排序成为图 $\displaystyle \mathcal{G}$的一个拓扑序。

2.3.2、任意图下的节点基本概念

邻接点 $Neighbour$: $\displaystyle nb(s)=\{t\mid\mathcal{G}(s,t)=1\lor \mathcal{G}(t,s)=1,t\in V(\mathcal{G}) \}$

边界点 $Boundary$: $\displaystyle bd(s)= pa(s)\cap nb(s)$

节点度 $degree$： $\displaystyle d(v)=\mid E(v)\mid$ 含义是关联到节点 $\displaystyle v$的边的条数。特别的，对于有向图。有入度in-degree（父节点数量），出度out-degree（子节点数量）。

2.4、关于边的认识

路 $\displaystyle \textit{(Path)}$
有节点集合 $\displaystyle P=\{v_1,\cdots,v_k\},k\geqslant 3$， 若有 $\displaystyle \forall v_i\in P\subseteq V(\mathcal{G})\Rightarrow v_i\to v_{i+1}\lor v_i-v_{i+1}$存在，那么就说该节点集合 $\displaystyle P$在图 $\displaystyle \mathcal{G}$中形成了一条路径，记为 $\displaystyle \mathcal{G}_P$。

迹 $\displaystyle \textit{(Trail)}$
有节点集合 $\displaystyle T=\{v_1,\cdots,v_k\},k\geqslant 3$， 若有 $\displaystyle \forall v_i\in T\subseteq V(\mathcal{G})\Rightarrow v_i\rightleftarrows v_{i+1}$存在，那么就说该节点集合 $\displaystyle T$在图 $\displaystyle \mathcal{G}$中形成了一条迹，记为 $\displaystyle \mathcal{G}_T$。

环 $\displaystyle \textit{(Cycle)}$
节点集合 $\displaystyle C=\{v_1,\cdots,v_k\}$是图 $\displaystyle \mathcal{G}$的一条路，若还有 $\displaystyle v_k\to v_1\lor v_k-v_{1}$存在，这称节集合 $\displaystyle C$在图 $\displaystyle \mathcal{G}$中的形成了一个环，记为 $\displaystyle \mathcal{G}_C$。如果一个图不包含环，称该图为无环图 $\displaystyle \textit{(Acyclic Graph)}$。

圈 $\displaystyle \textit{(Loop)}$
节点集合 $\displaystyle L=\{v_1,\cdots,v_k\}$是图 $\displaystyle \mathcal{G}$的一条迹，若有 $\displaystyle v_k\rightleftarrows v_1$存在，这称节点集合 $\displaystyle L$在图 $\displaystyle \mathcal{G}$中形成了一个圈，记为 $\displaystyle \mathcal{G}_L$。

连通
非空图 $\displaystyle \mathcal{G}$的任意两个节点都有一条路存在，就成 $\displaystyle \mathcal{G}$是连通的。

无圈图是森林，特别的有向无圈图是多重树，如果每个节点至多只有一个父节点，则该有向图为森林，连通的森林是树。

弦
图 $\displaystyle \mathcal{G}$中的一个圈 $\displaystyle \mathcal{G}_L$，在 $\displaystyle L$中不连贯的节点的边成为弦。

2.5、导出子图与团

导出子图 $\displaystyle \textit{(Induced Subgraph)}$
在概率图中，我们关心的是导出子图：若 $\displaystyle A\subseteq V(\mathcal{G})$, 由 $\displaystyle A$生产一个图 $\displaystyle \mathcal{G}_A$，且 $\displaystyle E(\mathcal{G}_A)=\{st\mid \forall st\in E(\mathcal{G})\land s,t\in A\} $，我们称 $\displaystyle \mathcal{G}_A$是 $\displaystyle A$在图 $\displaystyle \mathcal{G}$中的导出子图。也就是说 $A= V(\mathcal{G}_{A})\subseteq V(\mathcal{G})$， $E(\mathcal{G}_A)\subseteq E(\mathcal{G})$

团 $\displaystyle \textit{(clique)}$
若导出子图 $\displaystyle \mathcal{G}_A$中，这个命题成立：$\displaystyle \forall s,t \in A\to \mathcal{G}_A(s,t)=1$；也就是说 $\displaystyle A$中的任意节点都有一条边，就称 $\displaystyle A$为团。特别的 $\displaystyle \forall B\supset A,B\subseteq V(\mathcal{G})$， $\displaystyle B$不是团，我们就称 $\displaystyle A$为极大团 $\displaystyle \textit{(Maximal Clique)}$。

2.6、有向图与联合分布

有向图中，联合概率分布根据链式法则可以表示为一系列条件概率的乘积。我们将条件概率分布的条件的随机变量，作为边的起点。这样有:


有向图与联合分布

三、有向无环图模型$\displaystyle \textit{ (DGM or DAG) }$

任意图模型的核心是一组条件独立假设。我们发现有不同方法来描述有向无环图模型 $\displaystyle \textit{(Directed Aclyclic Graphy)}$的这些条件独立假设，最后我们可以证明它们说的是一个意思。

3.1、有向马尔可夫性质

【有序马尔可夫性质 $\displaystyle O$】: 给定一个有向无环图的拓扑序 $\displaystyle \{1,\cdots,k,\cdots,K\}$，则有 $\displaystyle p(\bm{x})=\prod_{k=1}^Kp\big(x_k\mid Pa(x_k)\big)$。也就是说：给定父节点，当前节点与前置节点独立
$$\begin{align}
O=\left\{S\mid S:\forall x_k\in V(\mathcal{G})\to x_k\perp_\mathcal{G} \bm{x}_{pred(k)-pa(k)}\mid \bm{x}_{pa(k)}\right\}
\end{align}$$

【有向局部马尔可夫性质 $\displaystyle L$】: 给定父节点，当前节点与非后代节点独立
$$\begin{align}
L=\{S\mid S:\forall x_t\in V(\mathcal{G})\to x_t\perp_\mathcal{G} \bm{x}_{nd(t)-pa(t)}\mid \bm{x}_{pa(t)}\}
\end{align}$$
其中 $\displaystyle nd(t)=V(\mathcal{G})-\{t\}\cup de(t)$，且有$\displaystyle pred(t)\subseteq nd(t)$。

【全局马尔可夫性质 $\displaystyle G$】
$$\begin{align}
G=\{S \mid S:\bm{x}_A\perp_\mathcal{G}\bm{x}_B\mid \bm{x}_C\land A,B,C\subseteq V(\mathcal{G})\}
\end{align}$$
这些性质统称有向马尔可夫性质，它们之间是等价的。没错是等价的！！！

3.2、有向马尔可夫性质定理

$$\begin{align}
O\Longleftrightarrow L \Longleftrightarrow G
\end{align}$$

3.3、有向分离与贝叶斯球算法
3.3.1、迹的有向分离

如何找到全局马尔可夫性质，下面我们引入有向分离 $\displaystyle \textit{(D-Separation)}$的概念,
首先，我们说一条迹 $\displaystyle T$被节点集 $\displaystyle E\textit{ (containing the evidence)}$有向分离，那么该迹至少满足下面一条：
1、 $\displaystyle T$ 含有链迹 $\displaystyle x\to y\to z$ 或者 $\displaystyle x\leftarrow y\leftarrow z$，且 $\displaystyle y\in E$

2、 $\displaystyle T$ 含有叉迹 $\displaystyle x \swarrow ^y \searrow z$，且 $\displaystyle y\in E$

3、$\displaystyle T$ 含有撞迹 $\displaystyle x \searrow _y \swarrow z$,且 $\displaystyle y,\notin E \land de(y)\cap E=\emptyset$

3.3.2、节点集的有向分离

接下来，我们说给定已观测节点集 $\displaystyle E$，一节点集合 $\displaystyle A$与另一节点集
$\displaystyle B$有向分离，意思是说，对于每一条 $\displaystyle a\in A$到 $\displaystyle b\in B$的迹被节点集 $\displaystyle E\textit{ (containing the evidence)}$有向分离。

3.3.3、有向无环图的条件独立性质

最后，我们就能把图的分离性定义与分布的条件独立性质结合起来：
$$\begin{align}
\bm{x}_A\perp_\mathcal{G}\bm{x}_B\mid \bm{x}_E \iff \textit{ A is d-separation from B given E}
\end{align}$$

我们来详细考察一下：
【链迹】考察联合分布 $\displaystyle p(x,y,z)=p(x)p(y\mid x)p(z\mid y)$，然后我们考察基于 $\displaystyle y$的条件分布：
$$\begin{align}
p(x,z\mid y)=\frac{p(x)p(y\mid x)p(z\mid y)}{p(y)}=\frac{p(x,y)p(z\mid y)}{p(y)}=p(x\mid y)p(z\mid y)\iff x \perp z\mid y
\end{align}$$

【叉迹】考察联合分布 $\displaystyle p(x,y,z)=p(y)p(x\mid y)p(z\mid y)$，同样我们考察 $\displaystyle y$的分布：
$$\begin{align}
p(x,z\mid y)=\frac{p(y)p(x\mid y)p(z\mid y)}{p(y)}=p(x\mid y)p(z\mid y)\iff x \perp z\mid y
\end{align}$$

【撞迹】考察联合分布 $\displaystyle p(x,y,z)=p(x)p(z)p(y\mid x,z)$，同样我们考察 $\displaystyle y$的分布：
$$\begin{align}
p(x,z\mid y)=\frac{p(x)p(z)p(y\mid x,z)}{p(y)}\iff x \require{cancel} \cancel{\perp} z\mid y
\end{align}$$
但是，我们发现
$$\begin{align}
p(x,z)=\int p(x)p(z)p(y\mid x,z) dy=p(x)p(z)\iff x\perp z
\end{align}$$
我们把撞迹的这种现象叫解释消除 $\displaystyle \textit{(explaining away)}$

3.3.4、贝叶斯球算法

贝叶斯球算法 $\displaystyle \textit{(shachter 1998)}$是一种判断节点集是否有向分离的简单方法：


贝叶斯球算法
3.4、马尔可夫毯与全条件

下面我们将考察单个节点与其他节点的独立性质。我们定义图中所有与 $\displaystyle t$节点独立的其他节点集称为 $ t$的马尔可夫毯 Markov Blanket ，记为 $\displaystyle mb(t)$。 特别的在有向无环图中一个节点的马尔可夫毯是父节点、子节点、同父节点 (co-parents) (或者说它子节点的父节点)的集合。即：
$$\begin{align}
mb(t)=ch(t)\cup pa(t) \cup copa(t)
\end{align}$$

为何同父节点在马尔科夫毯中？注意到：

$$\begin{align}
p\big(x_t\mid \bm{x}_{-t}\big)= \frac{ p\big(x_t ,\bm{x}_{-t}\big)}{ p\big( \bm{x}_{-t}\big)}
\end{align}$$

其中所有不包含 $\displaystyle x_t$的项将在分子和分母之间被消掉，所以在这个视角下只剩下含有 $\displaystyle x_t$的概率密度的乘积。这个一点使用贝叶斯球算法的链迹、叉迹、撞迹、阻塞、反弹的概念判定独立不难理解。因此有：

$$\begin{align}
p\big(x_t\mid \bm{x}_{-t}\big)
\propto p \big(x_t\mid \bm{x}_{pa(t)}\big)\prod_{s\in ch(t)}p \big(x_s\mid \bm{x}_{pa(s)}\big)
\end{align}$$

得到的表达式被称为 $\displaystyle t$节点的全条件 (Full Conditional) ，当我们学习吉布斯抽样时这一结论是非常重要的。

四、图模型与联合概率分布

图模型是一种语言，联合概率分布也是一种语言。它们可以表达相同的事物。正如几何与代数的关系。下面我们将引入一系列定义，以方便寻找它们的联系。

4.1、图模型的条件独立性质与 $\displaystyle \text{I-Map}$

我们即将引入 $\displaystyle \text{I-Map}$的概念与定义，以方便简洁表达。这种手法是发展数学的动力之一。我们知道：任意图模型 $\displaystyle \mathcal{G}$的核心是一组条件独立假设集合，可以记为

$$\begin{align}
\bm{x}_A\perp_\mathcal{G}\bm{x}_B\mid \bm{x}_C
\end{align}$$

我们根据这一叙述可以定义一个“陈述” $\displaystyle \textit{(Senantics)}$。 $\displaystyle S:\bm{x}_A\perp_\mathcal{G}\bm{x}_B\mid \bm{x}_C$, $\displaystyle A,B,C\subseteq V(\mathcal{G})$。然后我们把“所有条件独立陈述的集合”定义为：$\displaystyle \mathcal{I}(\mathcal{G})=\{S\}$。也就是说：$\displaystyle\mathcal{I}(\mathcal{G})$是图模型 $\displaystyle \mathcal{G}$的所有条件独立陈述的集合。

同样样给出一个联合概率分布 $\displaystyle p$的所有条件独立陈述的集合，记为： $\displaystyle \mathcal{I}(p)$。

当然这些陈述是可以判断真假的，是真命题。至于为什么没有直接使用“命题的集合”这个的术语，考虑到我们是在给现实世界建模，而模型是否为真，还不一定，使用“陈述”这一术语是恰当的。

特别的：“一个联合分布 $\displaystyle p$满足一个图模型 $\displaystyle \mathcal{G}$的所有条件独立假设”。这句话可以写为：
$$\begin{align}
\mathcal{I}(\mathcal{G})\subseteq \mathcal{I}(p)
\end{align}$$
这种情况下，我们就说“图 $\displaystyle \mathcal{G}$是分布 $\displaystyle p$的一个 $\displaystyle\text{I-Map}$”。很快我们就会发现关于 $\displaystyle\mathcal{I}(\mathcal{G})$定义中的“所有”并不是必须的。也就说一个 $\displaystyle p$的 $\displaystyle\text{I-Map}$可以有很多个，例如完全图是任意分布的 $\displaystyle p$的 $\displaystyle\text{I-Map}$。

4.2、因子分解

同样，我们引入因子分解 $\displaystyle \textit{(factorization)}$的概念与定义。注意因子分解应该理解为一个动词。

若有向无环图模型 $\displaystyle \mathcal{G} $，有随机变量集(节点集) $\displaystyle \mathcal{X}=V(\mathcal{G})=\{x_i\}_{i=1}^n$，如果联合分布 $\displaystyle p$能表示为如下乘积形式：$$\begin{align}
\displaystyle p(\bm{x})=\prod_{i=1}^np\big(x_i\mid \bm{x}_{pa(i)}\big)
\end{align}$$那么我们称联合分布 $\displaystyle p$基于图 $\displaystyle \mathcal{G}$在同一空间 $\displaystyle \mathcal{X}$ 上因子分解 ($\displaystyle \textit{ p over the same space } $$\displaystyle \mathcal{X}$ $\displaystyle \textit{ factorizes according to }\mathcal{G}$)，记为 $\displaystyle F$。

4.3、条件独立因子分解定理

$$\begin{align}
\mathcal{I}(\mathcal{G})\subseteq \mathcal{I}(p)\Longleftrightarrow p(\bm{x})=\prod_{i=1}^np\big(x_i\mid \bm{x}_{pa(i)}\big)
\end{align}$$

也就是说一个联合分布 $\displaystyle p$满足一个图模型 $\displaystyle \mathcal{G}$的所有条件独立假设，与联合分布 $\displaystyle p$基于图 $\displaystyle \mathcal{G}$在同一空间 $\displaystyle \mathcal{X}$ 上因子分解等价。

于是我们有：
$$\begin{align}
O\Longleftrightarrow L \Longleftrightarrow G \Longleftrightarrow F
\end{align}$$

五、无向图模型(Undirected Graphical Model(UGM))

5.1、UGMs的特点

无向图模型 Undirected Graphical Model(UGM) ，也称为马尔可夫随机场 Markov random field(MRF) 或马尔可夫网络。它不要求我们指定边方向，而且对于一些问题，如图像分析和空间统计，更自然。

UGMs 相对 DGMs 的主要优势是:
(1)它们是对称的，因此对于某些领域(如空间或关系数据)更“自然”;
(2)定义 $\displaystyle p \big(\bm{y}\mid \bm{x}\big)$条件密度的判别 UGMs (即条件随机场 Conditional random fields, or CRFs )，比判别 DGMs 更有效。

与 DGMs 相比， UGMs 的主要缺点是:
(1)参数的可解释性更小，模块化更少。
(2)参数估计在计算成本上更加昂贵。

5.2、UGMs的条件独立性质

UGMs 通过简单的图分离来定义 CI 关系。对于节点 $ A$、 $ B$和 $ C$的集合，如果在图 $ \mathcal{G}$中 $ C$把 $ A$从 $ B$分离，我们就说 $\displaystyle \bm{x}_A \perp_{\mathcal{G}} \bm{x}_b\mid \bm{x}_c$。这意味着，当我们删除 $ C$中所有节点，如果没有任何路(Path)连接 $ A$中任何节点到 $ B$中的任何节点，就称 CI 性质。这被称为 UGMs 的全局马尔可夫性质 (global Markov property) 。

在一个图中，使与节点 $ t$有条件独立性质最小节点集称为 $ t$的马尔可夫毯 Markov blanket ；我们将用 $ mb(t)$表示。在形式上，马尔可夫毯满足以下性质:

$$\begin{align}
t\perp V(\mathcal{G})-cl(t)\mid mb(t)
\end{align}$$

其中 $\displaystyle cl(t)=mb(t)\cup \{t\}$是节点 $ t$的闭包 (closure) 。易知，在一个 UGM 中，节点的马尔可夫毯是它紧邻的集合。这叫做无向局部马尔可夫性质。

从局部马尔可夫性质，我们可以很容易看出如果两个节点之间没有直接连接的边，给定其余节点，它们是条件独立的。这叫做成对马尔可夫性质(Pairwise Markov Property) 记为 $ P$ 。

$$\begin{align}
s\perp t \mid V(\mathcal{G})-\{s,t\}\iff \mathcal{G}(s,t)=0
\end{align}$$

很明显，全局马尔可夫性质包含了局部马尔可夫性质，它意味着成对马尔可夫性质。虽然不那么明显，但仍然是正确的(假设对所有 $ x$的 $ p(x)>0$，即 $ p$是一个正密度)，这时成对马尔可夫性蕴含全局马尔可夫性质，因此所有这些马尔可夫性质都是等价的，如图19.3所示(参见Koller和Friedman 2009,p119)。这一结果的重要性在于，它通常更容易根据经验来评估成对条件独立性；可以使用这种成对条件独立性语句构造一个图形，而从这个图中提取的全局独立性语句也成立。

$$\begin{align}
G\Longrightarrow L \Longrightarrow P \mathop{===\Longrightarrow}^{\forall x\to p(x)>0} G
\end{align}$$

或者说
$$\begin{align}
\forall x\to p(x)>0 \Rightarrow G \iff L \iff P
\end{align}$$

5.3、Hammersley-Clifford定理

由于没有与无向图相关的拓扑排序，我们不能使用链式法则来表示 $ p \big(\bm{x}\big)$。因此，我们将概率密度与每个节点关联起来替换方法是，将势函数或因子与图中每个极大团联系起来。我们将团 $ c$势函数记为 $ \psi_c \big(\bm{x}_c\mid \bm{\theta}_c\big)$。势函数可以是其参数的任何非负函数。然后定义联合分布与团势函数乘积成比例。令人惊讶的是，可以通过这样的方式来表示任何可以由无向图模型表达条件独立性质的正分布。我们更正式地陈述这个结果如下

【 Hammersley-Clifford 定理】
一个正分布 $ p \big(\bm{x}\big)>0$ 能满足一个无向图模型 $ \mathcal{G}$的条件独立性质，当且仅当 $ p$能够被每个极大团因子的乘积表示。

$$\begin{align}
\forall x\to p(x)>0\Rightarrow \mathcal{I}(p)=\mathcal{I}(\mathcal{G})
\iff p \big(\bm{x}\mid \bm{\theta}\big)=\frac{1}{Z(\bm{\theta})}\prod_{c\in \mathcal{C}}\psi_c \big(\bm{x}_c\mid \bm{\theta}_c\big)
\end{align}$$

其中 $ \mathcal{C}$是图 $ \mathcal{G}$ 所有极大团的集合。 $ Z(\bm{\theta})$是配分函数：
$$\begin{align}
Z(\bm{\theta})=\sum_{\bm{x}}\prod_{c\in \mathcal{C}}\psi_c \big(\bm{x}_c\mid \bm{\theta}_c\big)
\end{align}$$

请注意，配分函数确保了整体分布总和为 $ 1$。证明从未发表过，但可以在例如(Koller and Friedman 2009)中找到。

六、比较有向图模型和无向图模型

哪一个模型有更强的“表达能力”，是有向图模型还是无向图模型？为了形式化这个问题，回顾一下：如果 $ \mathcal{I}(\mathcal{G})\subseteq \mathcal{I}(p)$，则 $ \mathcal{G}$是一个分布 $ p$的 $\text{I-Map}
$。如果 $ \mathcal{I}(\mathcal{G})= \mathcal{I}(p)$，那么就称 $ \mathcal{G}$为 $ p$的完美映射 (Perfect Map) $ \text{P-Map}$，换句话说，图可以表示分布的所有(且唯一)条件独立性质。问题就变为：对于不同分布集合，是有向图模型还是无向图模型是完美映射。从这个意义上说，两者都不是比另一个更强大的表示语言。

一些条件独立关系的例子可以完全由有向图模型建模，而无向图模型不能。考虑一个 $ v$结构$ A \searrow _C \swarrow B$，这表示 $ A\perp B$ 且 $\require{cancel} A\cancel{\perp} B\mid C$。如果我们去掉箭头，得到 $ A-C-B$，这表示 $\require{cancel} A\cancel{\perp} B$ 且 $ A\perp B\mid C$。这种去掉箭头的操作显然是不对的。事实上，没有无向图模型能精准完全唯一地表达由 $ v$结构编码的两个条件独立性质。一般的，无向图模型的条件独立性质是单调的，这里的单调有如下含义：如果 $ A \perp B \mid C$，则 $ A\perp B \mid \big(C\cup D\big)$。但在有向图模型中，条件独立性质是非单调的，因为存在附加变量的条件作用可以消除由于解释消除 $\displaystyle \textit{(explaining away)} $生产的条件独立性质。


图模型比较

一些条件独立关系的例子可以完全由无向图模型建模的，而有向图模型不能。可以考虑如图(a)所示的 $ 4$环。图(b)显示了用有向图模型建模的尝试，它能正确表达 $ A\perp C \mid B,D$，但表达的 $ B\perp D\mid A$是错误的。图(c)是另一个不正确的有向图模型，它正确地编码了 $ A\perp C \mid B,D$，但是编码的 $ B\perp D$是错误的。事实上，没有有向图模型能够精准完全唯一地表达由这个由无向图模型编码的条件独立陈述集合。

有些分布可以完全由有向图模或无向图模型建模；得到的图称为可分解 (decomposable) 或弦 (chordal) 。粗略地说，这意味着：如果我们把每个最大团的所有变量一起坍缩生成“大变量” (“mega-variables”,) ，结果图将是一棵树。当然，如果图已经是树了(包括链作为特殊情况)，它将是弦。有关详细信息，我们以后详细介绍。

七、总结

1、概率是一个好工具，这个工具的核心在于概率的条件独立性质。或者说高级一点条件期望。没有条件期望，概率论不过是测度论的一个表现形式。正是我们定义了条件概率，概率论才枝深叶茂起来。但是表达条件概率不仅仅用数学公式，还可以用图。于是一门新的学科诞生了：概率图。
2、无论是无向图、有向图，其核心都是一组条件概率假设(或者条件概率陈述)。而在非常宽泛条件下，一组条件概率假设和一个图表意是一致。这就奠定了概率图应用的基础。
3、有了图模型这一强有力的可视化建模工具，我们足矣为各种复杂场景建模，星辰大海就在前方，我们将继续探索。

版权声明
由引线小白创作并维护的柠檬CC博客采用署名-非商业-禁止演绎4.0国际许可证。
本文首发于柠檬CC [ https://www.limoncc.com ] , 版权所有、侵权必究。
本文永久链接httpss://www.limoncc.com/post/b9646fbf6c8d542fdb68ac01ad3c1c5a/
如果您需要引用本文，请参考：
引线小白. (Mar. 10, 2017). 《概率图基础》[Blog post]. Retrieved from https://www.limoncc.com/post/b9646fbf6c8d542fdb68ac01ad3c1c5a
@online{limoncc-b9646fbf6c8d542fdb68ac01ad3c1c5a,
title={概率图基础},
author={引线小白},
year={2017},
month={Mar},
date={10},
url={\url{https://www.limoncc.com/post/b9646fbf6c8d542fdb68ac01ad3c1c5a}},
}

'