PGM 读书笔记节选(一)

很遗憾前面只看过 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 的三大问题就是

  • representation:什么样的 graph 是合理的假设?
  • inference:如何在给定一些条件下推断出来其他的未知变量
  • learning:如何在给定一些样本情况下对系统的参数进行辨识

我们从 Bayesian nets 开始,这里略过一些,只记录比较感兴趣的一些东西。

笔记

BN 里面有意思的一点是 reasoning pattern,我们有如下一些形式:

  • causal reasoning,即通过增加起上游(ancestor)的信息(观测)即“原因”用来 reason 下游某个现象发生的概率
  • evidential reasoning(explanation),即通过增加下游的信息(观测),即“现象、效果”用来 reason 上游某个原因是否发生的概率
  • inter-causal reasoning(explanation away),同一个现象可能是多个原因引起的,当观测到现象时,这些原因之间就会产生相互作用(尽管一开始他们可能是先验独立的),比较常见的一种情况是,一旦某个原因(它很可能引起这个现象)成立,其他原因出现的概率反而因此下降。

事实上正是最后这种比较特殊的情况导致了 BN 里面一些特别的 case。直观上 BN 希望获得的独立性是如果给定某个节点的 parent,那么所有非 descendant 节点都与之条件独立(这作为 BN 的定义)。为了更加精确的表示 BN 所诱导的分解与独立性断言(independency assertions)之间的等价性,我们引入所谓的 I-map。我们记 \mathcal{I}(P) 是分布 P 上的独立性断言,如果一个 graph 所诱导的独立性断言集合 \mathcal{I}(G) \subseteq \mathcal{I},我们就称 GP 上的 I-map:为什么只需要子集就行了?其实很简单,如果只是 claim 了一部分独立性,说明这个 graph 能够描述的关系肯定包含对应全部满足的情况(独立性断言越多,变量之间的关系越少)。

从 I-map 到分解:当我们拥有一个 graph,我们可以根据其 topological order 进行条件概率的分解,这时所有的 node 都会 condition 在所有的 ancestor 上(不仅仅是 parent),我们通过 I-map 里面的独立性断言就可以将其中一部分进行简化,得到最终的 factorization 的结果,即

\displaystyle \Pr(X_1, \ldots, X_n) = \prod_{i = 1}^n \Pr(x_i \mid \pi (x_i) )

其中 \pi(x_i)x_i 的父节点集合。我们首先可以证明如果图 G 是 I-map,则可以产生我们这里提到的分解。证明就直接利用如上思路展开后,继而根据 BN 的定义对此关系进行简化,结果就是我们这里 claim 的分解形式。

从分解到 I-map:如果概率 P 根据图 G 具有类似的分解,则 GP 的 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,我们记这个独立性断言集合为 \mathcal{I}(G)),可以证明如果概率 P 对图 G 能分解,则 G 的 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,一个分布 PG faithful,表示如果存在 (X \perp Y \mid Z) \in \mathcal{I}(P),那么 XY 就在给定 Z 时是 d-separated 的。但事实上我们不能简单的 claim,而只能证明:如果对任意分布 P 其能按 G 分解都满足 (X \perp Y \mid Z),才能有给定 Z 时两者 d-sep。等价的说法时如果两者不是 d-sep,则存在分布使得给定 ZX, Y 不独立。

这个说明了 \mathcal{I}(G) 的最大性(\mathcal{I}(P) \subseteq \mathcal{I}(G))。事实上两者差的并不多,可以证明几乎所有(almost all)的分布(除掉一个零测集)如果能按照图 G 分解其独立性断言和 global Markov independencies 是一样的。

一个实际的问题就是给定随机变量 X 个某些已知的随机变量 Z,怎么找到与 X 独立的随机变量呢?这很容易,应用 Bayesian ball theorem 以及 DFS/BFS 即可将无法断言的节点获得。

通过独立性断言集合(给定图以后,根据 global Markov independencies 获得)我们可以脱离图结构本身:如果两个图具有相同的 \mathcal{I}(G_i),则我们称这两个图 G_i 是 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 转向。

另外两个相关的概念是

  • minimal I-map,给定一个独立性断言集合,图 G 是 minimal I-map 当且仅当其对应的独立性断言集合相等,且去掉任意一条边都会导致不等,获得这个 graph 并不困难,我们通过条件概率分解之后,尝试选择一个集合,使得 (X_i \perp \{ X_1, \ldots, X_{i - 1}\} - U \mid U) 时的最小集合 U 作为 X_i 的父节点即可。
  • perfect I-map,如果给定独立性断言集合,对应的 perfect I-map 是 \mathcal{I}(G) = \mathcal{I}。如果给定的是分布 P,则是其分布的 perfect I-map 当且仅当 \mathcal{I}(G) = \mathcal{I}(P)。寻找 perfect I-map 却比较复杂,这里略去。

后面我们讨论 Markov random field(MRF)以及其与 BN 之间的关系。

——————
And Abraham got up early in the morning to the place where he stood before the LORD:

Advertisements
PGM 读书笔记节选(一)

一个有关“PGM 读书笔记节选(一)”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

w

Connecting to %s