[PGM] I-map和D-separation

之前在概率图模型对概率图模型做了简要的介绍。此处介绍有向图模型中几个常常提到的概念，之前参考的多为英文资料，本文参考的是《概率图模型-原理与技术的》中译版本。很新的书，纸质很好，翻译没有很差。

1. 贝叶斯网络-不同视角

概率图模型，究其目的，在于描述多个（单个就没有意义了）变量概率分布之间的关系。有向图模型的描述方法是有指向性的，如果两变量之间有因果关系，这种描述方法就极为恰当。从这个角度上来说，考虑概率之间因子分解的过程，有向图模型是这一过程的一种表现方式。

而最初的考虑，即“变量概率分布之间的关系”，我们可以认为，有向图模型是条件独立性集合的表示。从简单的例子可以看出这一点，譬如有向图模型

意味着

。这是很好理解的，因为

通过

影响

，如果

作为已知条件，那么

如何影响

呢？可以通过因子分解过程验证这一过程

这也恰恰表明了，这两种不同的贝叶斯网络看待方式是等价的，对于这一点，书中总结为（“它”指贝叶斯网络）

• 它是提供了以因子分解的方式紧凑表示联合分布骨架的数据结构；
• 它是关于一个分布的一系列条件独立性假设的紧凑表示。

2. 独立性断言和I-map

记贝叶斯网络为

，概率分布为

。

是

的一个I-map是指

中表现出的独立性的集合是

中表现出的独立性的集合的子集。采用数学语言描述，给出以下定义。

是定义在

上的形如

的独立性断言的集合。令

是独立性集合

构成的贝叶斯网络，如果

，那么

是

的一个I-map。

根据定义，如果

，那么

是任意一个分布的I-map。当然这里

和

描述的对象要是一样的。从这个角度考虑，如果贝叶斯网络的没两个节点之间有边连接，那么它是所有

的I-map。显然，分布的I-map有多个，共同特点是图的限制比分布的少（子集关系），也就意味着这些图都可以表示这一分布。

注意：这里仅仅只定义了针对分布

的

，上文中的

也是一个分布，而不是图。

3. d-分离(D-separation)

上节给出了对应分布的独立性断言集合

，同时我们还希望能够得到对应给定的图

的独立性断言集合。首先仔细考虑图中节点之间的结构

：已知

的情况下

，

之间独立。

: 同上

：同上

：没有观测到

及其后代下

，

之间独立。（v-结构）

如果我们希望了解图上表示的条件独立特性，根据上述的四点，可以得出图上任意两节点之间的条件独立关系。对于上述的前三种情况，如果

未知，那么就认为

，

之间存在路径；对于第四种情况，如果

或其后代已知，认为

，

之间存在路径。对于任意两个节点，在给定已知节点集合后，如果存在相互影响的路径，记为存在有效的迹。了解了上面几点之后，给出以下定义。

如果

，

，

是图中的三个节点集合，在给定

下，如果任取

，

中不存在有效的迹，那么记

以上就是d-分离的定义，同时记d-分离的集合为

gif

这个集合也被称为全局马尔可夫独立性集。

4. 可靠性和完备性

上节定义的全局马尔可夫独立性集和分布的独立性集合的表现形式并没有区别。但是

在最初的定义中就表现了

是

中所有独立性断言的集合，这个所有意味着

中不存在

不属于

（完备性），而

中的每一独立性断言在

中都是成立的（可靠性）。贝叶斯网络往往对应着分布，也希望从贝叶斯网络中观测出的d-分离特性有相同的特点，但是全局马尔可夫独立性集合的定义中并不能直接看出这两点，本节将探讨这一问题。

可靠性

据说后面（书4.5.1节）会有证明，但我还没看到那里。

完备性

我们自然希望d-分离可以检测出所有的独立性。可简单的理解为分布P中的任何独立性都体现在了图的d-分离性质中，但这是不成立的。分布可以表现出结构中没有显示的独立性。比如说网络

gif[1]

的分布依旧可以为(对于这一点我还是不太明白，这难道不应该是I-map中所谓的可以有多个吗？)

所以最后给出的完备性定义比较弱，即 对于几乎所有的G上的因子分集的P（除去参数化条件概率空间中测度为0的分布），我们有I(P)=I(G)。

5. 最小I-map和P-map

最小I-map

前面讨论了那么多分布和图的相关知识，如果说将分布采用合适的图结构表现，那么很多独立性结构就一目了然了。从I-map来考虑，显然一个完全图的独立性断言是空集，是任何分布的I-map，但是这毫无意义。我们只关注能够体现分布的独立性关系的具有最少边的图，这就是最小I-map。

注意：似乎只要G是分布P的一个最小I-map，那么就能够从G中读出P的所有独立性，但这种认识是错误的。（不同的构建顺序会产生截然不同的结果）

P-map

考虑到这一问题，我们的下一个目标变成了找到可以准确刻画P中的所有独立性的图G。定义P-map：对于独立性集I，如果I(k)=I，称图k是I的一个P-map，如果I(k)=I(P)，那么成k是P的一个p-map。（条件强于I-map）

我们希望找到分布的P-map，但不幸的是不是所有分布都有P-map。

7. 其他

书中给出了d-分离的算法等，但这些内容我都没有看。书中的贝叶斯网表示这一节中有一个专栏，讨论了诸如变量选择、是否该引入隐变量，结构选择、概率选择等问题。其中那个提到了我们不应该赋值0概率，以及敏感性分析。我想这些都是在实际问题中需要考虑的，但对于这些我都还没有过实践。

或许，阅读、学习只是寻找一点寄托，不然自己整天无所事事闲的发慌吧；这总归是不会失败不会失去太多的生活方式。而实践往往就难很多，需要有机遇、有决心，要付出很大的努力，可能还要面临失败的结果。