概率图笔记:表述

该笔记整理自Probabilistic Graphical Models.

该部分的目的是:采用更加紧凑的方式来表达概率分布,从而减少运算和表达的冗余。

为了达到目的,将从6个方向考虑紧凑表达的问题:

  • 独立性

独立性


考虑n次投币事件 $\{X_{i}|i=1,..,n. \forall i,j,X_{i} \perp X_{j} \}$,则有:

$P(X_{i},...,X_{n}) = \prod_{i=1}^{n}P(X_{i})$

需要 $2^{n}$ 个值来表示联合概率分布。

若定义n个参数 $\theta_{1},...,\theta_{n}$ 代表各枚硬币取正面的概率,取 $\theta_{x_{i}} = \theta_{i},\ when\ x_{i} = x_{i}^{1}$ 和 $\theta_{x_{i}} = 1 - \theta_{i},\ when\ x_{i} = x_{i}^{0}$,则有:

$P(x_{1},...,x_{n}) = \prod_{i}\theta_{x_{i}}$

上述表示存在局限性,因为很多情况下我们无法给 $\theta_{1},...,\theta_{n}$ 赋值。事实上,联合概率分布处在 $\mathbb{R}^{2^{n}}$ 空间的 $2^{n} - 1$ 维子空间 $\{(p_{1},...,p_{2^{n}}) \in \mathbb{R}^{2^{n}}: p_{1} + ... + p_{n} = 1 \}$ 上,或者从因式分解的角度来讲,是 $\mathbb{R}^{2^{n}}$ 上的n维流型。


在贝叶斯网络中,有:

$\forall X_{i}, (X_{i} \perp NonDescendants(X_{i}) | Pa_{X_{i}^{G}})$

即,当父节点已知时,节点条件独立于其非子节点,简称局部独立

从形式语义学的角度来看,贝叶斯网络图可以表述为一系列的独立断言的集合;另一方面,贝叶斯网络图又能表述为由一系列条件独立分割成的链式表达式对应的联合概率分布。由此可知这两种表述应该是等价的。以局部独立断言为例,一个分布 $P$ 在图 $G$ 中满足局部独立断言,当且仅当 $P$ 可由 $G$ 中一组条件独立的连结所表述时成立。


定义分布 $P$ 上所有形式为 $(X \perp Y | Z)$ 的独立断言的集合为 $I(P)$。则我们可以将形如:

$P$ 在 $G$ 上满足局部独立

表述为:

$I_{l}(G) \subseteq I(P)$

此时,我们称 $G$ 为 $P$ 的I-map,又称独立图

由上述描述可知,任何在 $G$ 上推断出的独立性都应存在于 $P$ 上,而 $P$ 上可以存在不在 $G$ 上的独立性。

以随机变量 $X,Y$ 为例,共有三种可能的图 $G_{\varnothing},G_{X \to Y},G_{Y \to X}$,考虑如下两组分布:

左图分布 $P_{1}$ 有 $P(x^{1}) = 0.48 + 0.12 = 0.6, P(y^{1}) = 0.8, P(x^{1}, y^{1}) = 0.48 = P(x^{1}) * P(y^{1})$ ,所以有 $(X \perp Y) \in I(P_{1})$

又 $I_{l}(G_{\varnothing}) = \{(X \perp Y)\} \subseteq I(P_{1}), I_{l}(G_{X \to Y}) = I_{l}(G_{Y \to X}) = \{\varnothing\} \subseteq I(p_{1})$

所以可知 $G_{\varnothing},G_{X \to Y},G_{Y \to X}$ 都是 $P_{1}$ 的I-map。

而右图分布 $P_{2}$ 中,$(X \perp Y) \nsubseteq I(P_{2})$,易知 $G_{\varnothing}$ 不是 $P_{2}$ 的I-map,而 $G_{X \to Y},G_{Y \to X}$ 是 $P_{2}$ 的I-map。

由上述分析可知,一个贝叶斯网络图 $G$ 定义了一组条件独立假设的集合;对任意一个使得 $G$ 为 I-map的分布 $P$ 必须是满足这些假设的。


对于随机变量 $X_{1},...,X_{n}$ 上的贝叶斯网络图 $G$,若分布 $P$ 可被表述为:

$P(X_{1},...,X_{n}) = \prod_{i=1}^{n} P(X_{i}|Pa_{X_{i}}^{G})$

则称 $P$ 可被 $G$ 在相同空间上因式分解。其中,$P(X_{i}|Pa_{X_{i}}^{G})$ 称为条件概率分布,简记为CPDs,又称局部概率模型

至此,考虑随机变量 $\chi$ 上的贝叶斯网络图 $G$,以及该空间上的分布 $P$。若有 $G$ 是 $P$ 的I-map,则 $P$ 可在 $G$ 上因式分解。

证明:

不失一般性,假设 $X_{1},...,X_{n}$ 为 $\chi$ 在 $G$ 上的一个拓扑序,其对应的链式分解为:

$P(X_{1},...,X_{n}) = \prod_{i=1}^{n}P(X_{i}|X_{1},...,X_{i - 1})$

考虑其中某一个因式 $P(X_{i}|X_{1},...,X_{i - 1})$,由于 $G$ 是 $P$ 的I-map,所以有 $(X_{i} \perp NonDescendants(X_{i})|Pa_{X_{i}}^{G}) \in I(P)$。

又根据拓扑序假设有

$\{X_{1},...,X_{i - 1}\} = Pa_{X_{i}} \cup Z, Z \subset NonDescendants(X_{i})$

所以有

$(X_{i} \perp Z|Pa_{X_{i}})$

所以有

$P(X_{i}|X_{1},...,X_{i - 1}) = P(X_{i}|Pa_{X_{i}})$

得证。

至此我们可知,条件独立意味着存在因式分解,可因式分解意味着存在条件独立。


接下的目标是判定 $(\mathbb{X} \perp \mathbb{Y} | \mathbb{Z})$ 在贝叶斯网络中成立的情况有哪些。

  • 当 $X,Y$ 直接相连时,此两随机变量总是相互影响的
  • 当 $X,Y$ 经由 $Z$ 相连时:
    • $X \rightarrow Z \rightarrow Y$:仅当 $Z$ 未被观测到时有影响
    • $X \leftarrow Z \leftarrow Y$:仅当 $Z$ 未被观测到时有影响
    • $X \leftarrow Z \rightarrow Y$:仅当 $Z$ 未被观测到时有影响
    • $X \rightarrow Z \leftarrow Y$:仅当 $Z$ 被观测到时有影响。该结构又称v-结构
  • 更一般的情况下,当 $X_{1} \rightleftharpoons ... \rightleftharpoons X_{n}$ 中每个 $X_{i-1} \rightleftharpoons X_{i} \rightleftharpoons X_{i+1}$ 都能传递影响时,$X_{1},X_{n}$ 相互影响

综上,在贝叶斯网络图 $G$ 中,有迹 $X_{1} \rightleftharpoons ... \rightleftharpoons X_{n}$ 和被观测到随机变量集合的子集 $\mathbb{Z}$,当

  • 对于任意一个v-结构 $X_{1} \rightleftharpoons ... \rightleftharpoons X_{n}$,有 $X_{i} \subseteq \mathbb{Z}$ 或 $descendants(X_{i}) \subseteq \mathbb{Z}$
  • 其它迹上的节点都不在 $\mathbb{Z}$ 中

此时对于 $\mathbb{Z}$ 以及该条迹,$X_{1},X_{n}$ 是相互影响的。

考虑随机变量间存在多条迹的情况,记 $\mathbb{X},\mathbb{Y},\mathbb{Z}$ 为 $G$ 中三类节点的集合,当给定 $\mathbb{Z}$ 时,对于 $\forall x,y \in X,Y$,不存在传递影响的迹,则我们称 $\mathbb{X},\mathbb{Y}$ 被 $\mathbb{Z}$ d-分隔,记作 $d-sep_{G}(\mathbb{X};\mathbb{Y}|\mathbb{Z})$。我们记这些d-分隔出的独立性断言的集合为:

$I(G) = \{(\mathbb{X} \perp \mathbb{Y} | \mathbb{Z}):d-sep_{G}(\mathbb{X};\mathbb{Y}|\mathbb{Z})\}$

该集合又称为全局马克科夫独立性


下面从数学上证明d-分隔中随机变量相互独立。

正确性:若分布 $P$ 可根据 $G$ 因式分解,则有 $I(G) \subseteq I(P)$

完备性:d-分隔包含了所有的独立性信息。

若对任意断言 $(X \perp Y | Z) \in I(P)$,都有 $d-sep_{G}(X;Y|Z)$,则我们称分布 $P$ 对于 $G$ 是可信的


$I(G)$ 所代表的一系列独立断言的集合给我们提供一个不同的视角去描述一个贝叶斯网络,也能使我们能精确的描述两个贝叶斯网络的某种相似性。

若 $\mathbb{X}$ 上的结构 $K_{1}, K_{2}$ 满足 $I(K_{1}) = I(K_{2})$,则我们称 $K_{1}, K_{2}$ 是 I-等价的。所有 $\mathbb{X}$ 上的结构将由I等价划到各自的I-等价簇。以三个随机变量 $X,Y,Z$ 上的结构为例,$X \to Z \to Y, Y \to Z \to X, X \leftarrow Z \to Y$ 为同一个I-等价簇,而v-结构 $X \to Z \leftarrow Y$ 是另一个单独的I-等价簇。

I-等价簇的概念意味着,我们无法对分布 $P$ 在该簇中区分两种结构的优劣,以随机变量 $X,Y$ 的分布 $P(X,Y)$ 为例,我们无法区分 $X \to Y$ 和 $Y \to X$ 中,哪个方向是正确的。


若有 $\mathbb{X}$ 上贝叶斯网络结构 $G$,定义 $\mathbb{X}$ 上的无向图且包含所有在 $G$ 中的边,则称该无向图为该贝叶斯网络的骨架

进一步,若 $\mathbb{X}$ 两个贝叶斯网络结构 $G_{1},G_{2}$ 含有相同骨架且其中v-结构相同,则可认为两者是I-等价的,既前者是I-等价的充分条件。

另一方面,前者并不是I-等价的必要条件。

xiehao

Read more posts by this author.