概率建模与推断(3)—— 有向图与独立性假设

1 minute read

Published:

作者:Michael Gutmann(迈克尔·古特曼)
译者:郭尚敏(Shangmin Guo),shawnguo.cn@gmail.com
版权声明:本系列博客翻译自作者 迈克尔·古特曼 在爱丁堡大学(The University of Edinburgh)2019春季学期“概率建模与推断”(Probabilistic Modelling and Reasoning,INFR11134)课程的授课课件。译者已经取得原作者的翻译授权。

0. 扼要回顾

之前我们主要讨论了以下几个问题:

  • 我们能够做一些合理的弱假设来对概率模型进行有效表示;
  • 独立性假设能够减少相互作用的变量数量;
  • 参数族假设能够限制变量相互作用的形式;
  • (条件)独立假设能够推出pdf/pmf的因式分解,比如:
    • $p(x,y,z) = p(x)p(y)p(z)$
    • $p(x_1, \dots, x_d) = p(x_d|x_{d-3}, x_{d-2}, x_{d-1})p(x_1, \dots, x_{d-1})$

接下来,在本篇中将主要讨论以下问题:

  1. 因式分解与有序马尔科夫性(Ordered Markov Property)的等价性
    • 链式法则
    • 从有序马尔科夫性到因式分解
    • 从因式分解到有序马尔科夫性
  2. 从因式分解的角度理解模型
    • 可视化为有向图
    • 有向图及拓扑序的性质

1. 因式分解与有序马尔科夫性的等价性问题

1.1. 链式法则

通过迭代使用乘积法则,我们可以将一个联合分布的pdf(pmf)$p(x) = p(x_1, x_2, \dots, x_d)$因式分解为条件pdf(pmf)的乘积:

在上式 $ pre_i=p(x_i)= \left\{ x_1, \dots, x_{i-1} \right\}, pre_1=\varnothing\ \ \mbox{并且}\ \ p(x_1| \varnothing)=p(x_1)$。

需要注意的是,链式法则可以应用到任意顺序$x_{k_1}, \dots, x_{k_d}$,所以不同地顺序会得出不同地因式分解。

1.2. 从(条件)独立性到因式分解

上节中,我们得出 $p(x) =\prod_{i=1}^{d}p(x_i|pre_i)$ for the ordering $x_1, \dots, x_d$。通过观察,该方程满足如下性质:

  • 每一个$x_i$都依赖于(condition on)所有前序变量;
  • 假设,对于每一个$i$,都有一个最小变量集合$\pi_i \subseteq pre_i$使得$p(x)$满足如下性质:
  • 此时称$p(x)$满足有序马尔科夫性

根据条件独立的定义,可以推出 $p(x_i|x_1, \dots, x_{i-1}) = p(x_i|pre_i) = p(x_i|\pi_i)$。方便起见,我们可以定义$\pi_1=\varnothing$,那么可以得到如下分解:

后面我们会推导出,此处的$\pi_i$即对应有向图中节点$x_i$的双亲节点。

假设所有的变量排序为$x_1, \dots, x_d$,同时设$pre_i=\left\{ x_1, \dots, x_{i-1} \right\}$并且$\pi_i \subseteq pre_i$,我们已经得出如下结论:

此时,若$\pi_i=pre_i$,那么上式仍然满足链式法则。

但我们的问题是,相反的推论是否成立呢?也就是:

1.3. 从因式分解到(条件)独立性

对于上节中最后的问题,我们首先检查$x_d ⫫ \left\{ pre_d \setminus \pi_d \right\} | \pi_d$是否成立。通过其定义,我们知道这等于检查下式是否成立:

根据条件概率的定义,我们知道$p(x_d|x_1, \dots, x_{d-1}) = \frac{ p(x1,\dots, x_d) }{ p(x_1, \dots, x_{d-1}) }$,所以,我们首先从$p(x_1, \dots, x_{d-1})$的计算开始。

假设$x_i$的顺序为$x_1, \dots, x_d$并且$p(x_1, \dots, x_d) = \prod_{i=1}^{d} p(x_i\pi_i)\ \ \text{其中}\ \pi_i\subseteq pre_i$。那么通过求和法则可以知道:

所以,

从而,$p(x_d|x_1, \dots, x_{d-1}) = p(x_d|pre_d) = p(x_d|\pi_d)$ 即是想要的$x_d ⫫ \left\{ pre_d \setminus \pi_d \right\} | \pi_d$。

由于$p(x_1, \dots, x_{d-1})$ 与$p(x_1, \dots, x_d)$具有相同的形式,我们可以对所有的$k\leq d-1$的分布$p(x_1, \dots, x_k)$做同样的分解。从而可以证明:

  1. $p(x_1, \dots, x_k) = \prod_{i=1}^{k} p(x_i|\pi_i)$
  2. 因式分解即意味着$x_i ⫫ \big\{ pre_i \setminus \pi_i \big\} | \pi_i \ \ \forall\ i$

1.4. 小结及意义解释

记$x_i$所有的前序节点依次为$pre_i=\big\{x_1, \dots, x_{i-1} \big\}$并且$\pi_i \subseteq pre_i$,那么有

这为什么重要呢?原因如下:

  • 相对较强结果:以上性质不仅对单一pdf/pmf成立,也对pdf/pmf集合成立;
  • 对于集合中的所有成员:分布的表示只需要更少数量的变量(带来了计算的优势);
  • 当给定独立性时,我们可以推导出$p(x)$的形式(有助于指定模型参数);
  • 可以加深对模型性质的理解(独立性与数据生成机制)
  • 可视化为图的基础,有了上述性质,我们可以轻易导出有向图。

2. 从因式分解的角度理解模型

2.1. 因式分解可视化为有向图

如果有$p(x) = \prod_{i=1}^{d} p(x_i|\pi_i)\ \ \text{其中}\ \pi_i\subseteq pre_i$,那么以随机变量$x_i$作为节点,从$x_j\in \pi_i$向$x_i$连接有向边,我们既可以得到一个有向无环图(DAG)。

比如,我们有下式:

那么,可以将其表示为一个有向图,如下: FIG3.1

另外一个例子为:

其可以可视化为: FIG3.2

有上述例子我们不难发现:基于链式法则得出的因式分解$\equiv$全连接有向无环图

2.2. 图概念回顾

  • 有向图:所有的边都是有向的
  • 有向无环图(DAG):沿着边的方向遍历,不会访问同一个节点两次及以上
  • 如果有一条边从$x_i$连接到$x_j$,那么称$x_i$为$x_j$的父节点。在这里,我们将$x_i$的所有父节点表示为$pa(x_i) = pa_i$,比如$pa(x_3) = pa_3 = \big\{ x_1, x_2 \big\}$。
  • 若$x_i\in pa(x_j)$则称$x_j$是$x_i$的子节点,如下图中$x_3$和$x_5$都是$x_2$的子节点FIG3.1
  • 从$x_i$到$x_j$的一条路径(path/trail)是指一系列从$x_i$开始、到$x_j$结束的相互连接的节点。方向在此并不考虑。比如说在上图中,$x_5,x_2,x_3,x_1$是一条路径。
  • 有向路径中则需要考虑箭头的方向性。比如说,上图中,$x_1,x_3,x_4$是一条有向路径,但$x_5,x_2,x_3,x_1$就不是。
  • 节点$x_i$的祖先$anc(x_i)$是指能够通过有向路径访问$x_i$的节点。比如上图中,$anc(x_4) = \big\{ x_1, x_2, x_3 \big\}$。
  • 节点$x_i$的后代$desc(x_i)$是指从$x_i$出发能够通过有向路径访问到的所有节点。比如上图中,$desc(x_1) = \big\{ x_3,x_4 \big\}$。

    有时$x_i$也会被列在其祖先或后代集合中。

  • 节点$x_i$的非后代是指除了$x_i$和$desc(x_i)$意外的所有节点。比如上图中,$x_3$的非后代为$\big\{ x_1, x_2, x_5 \big\}$.
  • 拓扑序:若一个排序$\left( x_1, \dots, x_d \right)$中所有的父节点都出现在子节点之前,则该排序为图的一个拓扑序。(对于所有可以通过有向边访问$x_j$的节点$x_i$,$x_i$总是出现在$x_j$之前。)
  • 所有的DAG都至少有一个拓扑序。

在2.1.节中,我们曾举例,如果我们有因式分解如下:

那么其可以被可视化为下图: FIG3.1

我们需要注意:用于因式分解的顺序总是对应的有向图的一个拓扑序。同时,在上例中,$\pi_i$和$pa_i$都对应于$x_i$的父节点集合。

3. 扼要回顾

接下来,在本篇中主要讨论了以下问题:

  1. 因式分解与有序马尔科夫性(Ordered Markov Property)的等价性
    • 链式法则
    • 有序马尔科夫性蕴含着因式分解
    • 因式分解蕴含着有序马尔科夫性
  2. 从因式分解的角度理解模型
    • 可视化为有向图
    • 有向图及拓扑序的性质

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...