很遗憾前面只看过 Michael Jordan 写的一部分,这次打算把 Daphne Koller 和 Nir Friedman 合著的 Probabilistic Graphical Models: Principles and Techniques 好好过一遍。
作者认为与通常写一个 specific 程序解决一个具体的统计问题不一样,probabilistic graphical model 试图从另外一个角度来看这些问题,给出具有普适性的算法,而这依赖于一个 declarative representation(声明性的表达)
The key property of a declarative representation is the separation of knowledge and reasoning. The representation has its own clear semantics, separate from the algorithm that one can apply to it. Thus we can develop a general suite of the algorithms that apply any model within a broad class, whether in the domain of medical diagnosis or speech recognition. Conversely, we can improve our model for a specific application domain without having to modify our reasoning algorithms constantly.
引入 PGM 可以从两个方面来解释,一个是为了描述 independent r.v.s set,一个是为了通过 factorization 简化 probability distribution,
It turns out that these two perspectives — the graph as a representation of a set of independencies, and the graph as a skeleton for factorizing a distribution — are in a deep sense, equivalent. The independece properties of the distribution are precisely what allow it to be represented compactlt in a factorized form. Conversely, a particular factorization of the distribution guarantees that certain independencies hold.
这个我们在后面的某些具体情况下会看到相关的证明。
这样一来,PGM 的三大问题就是
我们从 Bayesian nets 开始,这里略过一些,只记录比较感兴趣的一些东西。
BN 里面有意思的一点是 reasoning pattern,我们有如下一些形式:
事实上正是最后这种比较特殊的情况导致了 BN 里面一些特别的 case。直观上 BN 希望获得的独立性是如果给定某个节点的 parent,那么所有非 descendant 节点都与之条件独立(这作为 BN 的定义)。为了更加精确的表示 BN 所诱导的分解与独立性断言(independency assertions)之间的等价性,我们引入所谓的 I-map。我们记 是分布 上的独立性断言,如果一个 graph 所诱导的独立性断言集合 ,我们就称 是 上的 I-map:为什么只需要子集就行了?其实很简单,如果只是 claim 了一部分独立性,说明这个 graph 能够描述的关系肯定包含对应全部满足的情况(独立性断言越多,变量之间的关系越少)。
从 I-map 到分解:当我们拥有一个 graph,我们可以根据其 topological order 进行条件概率的分解,这时所有的 node 都会 condition 在所有的 ancestor 上(不仅仅是 parent),我们通过 I-map 里面的独立性断言就可以将其中一部分进行简化,得到最终的 factorization 的结果,即
其中 是 的父节点集合。我们首先可以证明如果图 是 I-map,则可以产生我们这里提到的分解。证明就直接利用如上思路展开后,继而根据 BN 的定义对此关系进行简化,结果就是我们这里 claim 的分解形式。
从分解到 I-map:如果概率 根据图 具有类似的分解,则 是 的 I-map。这样的话我们只需要验证 BN 定义中的那些独立性断言成立(根据分解形式进行计算,看看是否真的独立)。
这样我们根据 BN 的定义得到了分解,那么这个结构的概率是否还蕴含着其他的独立性断言呢?为了研究这个问题,我们引入了所谓 d-separation。我们从相邻的两个节点开始,这个很明显无论其他的节点如何,这部分总“可以有”依赖关系(注意独立性断言是说一定独立,其相反的并不是“一定不独立”,而是“不一定独立”)。然后我们讨论中间隔了一个节点的情况,我们可以很容易例举 4 种连接形势下,中间节点是否存在观测时候这两个节点的独立性情况,只有 inter-causal reasoning 的情况下出现了不一样:如果中间节点没有观测,则其他情况都可以不独立,而作为 prior 的两个 cause 是先验独立的;如果中间节点被观测到了,则其他情况均为独立,而两 cause 却因此而可能不是独立的了。对于一般情形,如果存在一个 trail 从某个 r.v. 能够根据以上情形(独立时无法通过,无法 claim 独立时能够通过)抵达另一个 r.v. 那么两者无法 claim 独立;而如果不存在如此路径,即这两顶点是 d-separated,则独立。这个方法也叫 Bayesian ball theorem。
我们通过 d-separation 定义的 independence set 称为满足 global Markov independencies(相对的定义中使用的可以认为是 local Markov independencies,我们记这个独立性断言集合为 ),可以证明如果概率 对图 能分解,则 的 I-map 必然是 global Markov independencies 的子集(soundness of d-separation):这是显然的,我们只需要说明我们在 BN 定义中 claim 的那些独立性都是 d-separated 的 case,事实上给定了 parent 之后,如果想到达那些 non-descendant 我们只能通过给定的 parent 或者未知的 child:如果时通过 parent,因为 parent 给定,仅有“结果给定时才能通过”,那么原因给定都没法走;如果通过 child,由于是 non-descendant,所以只能是 child 的 ancestor,这样就变成了 common effect,两者也是 d-separated。为了证明反过来的 case(completeness),我们引入 faithfulness,一个分布 对 faithful,表示如果存在 ,那么 和 就在给定 时是 d-separated 的。但事实上我们不能简单的 claim,而只能证明:如果对任意分布 其能按 分解都满足 ,才能有给定 时两者 d-sep。等价的说法时如果两者不是 d-sep,则存在分布使得给定 时 不独立。
这个说明了 的最大性()。事实上两者差的并不多,可以证明几乎所有(almost all)的分布(除掉一个零测集)如果能按照图 分解其独立性断言和 global Markov independencies 是一样的。
一个实际的问题就是给定随机变量 个某些已知的随机变量 ,怎么找到与 独立的随机变量呢?这很容易,应用 Bayesian ball theorem 以及 DFS/BFS 即可将无法断言的节点获得。
通过独立性断言集合(给定图以后,根据 global Markov independencies 获得)我们可以脱离图结构本身:如果两个图具有相同的 ,则我们称这两个图 是 I-equivalent 的,通过这个关系我们可以获得图的等价类。那么什么样的图会是 I-equivalent 的呢?我们可以利用 skeleton 这个概念(一个 BN 的 skeleton 是一个 undirected graph,包含 BN 的所有顶点,每条有向边都对应一条无向边):如果两个图含有相同的 skeleton 且对应的 v-structure(common effect)相同,则他们是 I-equivalent 的。不过这是一个充分条件,而不是必要的。这是因为我们要求所有 v-structure 都一样,这并不是必须的。事实上,只需要其中 immoral 的一部分即可:如果 v-structure 中没有两个 prior 之间的边,我们就称这个 v-structure 时 immorality,否则这条边称为 covering edge。换一种说法,如果两个图是 I-equivalent,当且仅当存在一个 graph 序列,每两个相邻的仅仅将 covering edge 转向。
另外两个相关的概念是
后面我们讨论 Markov random field(MRF)以及其与 BN 之间的关系。
——————
And Abraham got up early in the morning to the place where he
stood before the LORD:
原文:http://www.cnblogs.com/focus-ml/p/3775435.html