hi@zxh
_

贝叶斯网络与 PC 算法

Apr 26, 2021 · 15 min · machine learning , bayesian

把大三的时候在实验室摸鱼看贝叶斯网络和 PC 算法时写的笔记整理到这里来,免得哪天我换电脑时把笔记搞没了。

这里是当时写的 PC 算法的 Python 实现: Renovamen/pcalg-py

概率图模型

对于一个 KK 维随机向量 X=[X1,X2,,XK]X = [X_1, X_2, \dots, X_K]^{\top},一般难以直接建模。因为如果每个变量为离散变量并有 MM 个可能取值,在不作任何独立性假设的前提下,需要 MK1M^K -1 个参数才能表示其概率分布,参数数量会非常庞大。

一种减少参数数量的方法是独立性假设。把 XX 的联合概率分解为 KK 个条件概率的乘积:

p(X=x)=k=1Kp(xkx1,,xk1)p(X = x) = \prod_{k=1}^K p(x_k | x_1, \dots, x_{k-1})

xx 为随机向量 XX 的取值。可以看到,如果某些变量之间存在条件独立,参数数量就可以大幅减少。

因此,概率图模型(Probabilistic Graphical Model,PGM)用图结构来描述多元随机变量之间的条件独立关系,从而为研究高维空间中的概率模型带来了很大的便捷。

概率图模型中,每个节点表示一个(或一组)随机变量,边表示这些随机变量之间的概率依赖关系。常见的概率图模型可以分为有向图模型和无向图模型。

  • 有向图模型(Directed Graphical Model),也称为贝叶斯网络(Bayesian Network)或信念网络(Belief Network),使用有向无环图(Directed Acyclic Graph,DAG)来描述变量之间的关系。如果两个节点之间有连边,表示这两个变量之间有因果关系,即不存在其他变量使得这两个变量条件独立。

  • 无向图模型,也称为马尔可夫随机场(Markov Random Field,MRF),使用无向图来描述变量之间的关系。两个节点之间有连边代表这两个变量之间有概率依赖关系,但不一定是因果关系。

pcg

图片来源:《神经网络与深度学习》,邱锡鹏

本文只讨论有向图模型,即贝叶斯网络。

贝叶斯网络

定义

有向无环图 GG 中,每个节点对应 KK 维随机向量 XX 中的一个变量,有向边 eije_{ij} 表示随机变量 XiX_iXjX_j 之间具有因果关系,父节点 XiX_i 是『因』,子节点 XjX_j 是『果』,显然这两个点之间一定非条件独立。

XπkX_{\pi_k} 为变量 XkX_k 的所有父节点变量集合,P(XkXπk)P(X_k \mid X_{\pi_k}) 表示每个随机变量的局部条件概率分布(Local Conditional Probability Distribution)

如果 XX 的联合概率分布可以分解为每个随机变量 XkX_k 的局部条件概率的连乘形式,即:

p(x)=k=1Kp(xkxπk)p(x) = \prod_{k=1}^K p(x_k \mid x_{\pi_k})

那么称 (G,X)(G,X) 构成了一个贝叶斯网络。

局部马尔可夫性质

每个随机变量在给定父节点的情况下,条件独立于它的非后代节点:

Xk ⁣ ⁣ ⁣ZXπk\newcommand{\indep}{\perp \!\!\! \perp} X_k \indep Z \mid X_{\pi_k}

其中 ZZXkX_k 的非后代节点。

基本问题

  • 学习问题

    • 结构学习:那么怎样才可以获得这个神奇的有向无环图呢,这就是结构学习问题。即学习出最优网络结构,也就是各节点之间的依赖关系。主流的结构学习方法主要可以分为:

      • 基于评分搜索的方法:利用搜索算法和评分函数,对每一个搜索到的网络结构进行评分,最终搜索出评分最高的网络结构。搜索算法的复杂度和精确度直接决定了学习算法的搜索效率,评分函数的优劣也直接决定了算法的计算复杂度和精确度。所以选择合理的优化搜索算法和评分函数是该类方法的核心问题。

        该类方法容易陷入局部最优解而无法达到全局最优,并且结构空间的⼤⼩随节点的增加呈指数增加(空间复杂度)。

      • 基于依赖统计分析的方法:分析变量间的依赖关系,在依赖性较大的两节点之间添加连接边,得到无向图。然后根据包含关系等方式确定无向图中边的方向,得到最终的有向无环图。本文要讨论的 PC 算法就是这类方法中(比较古老)的一种。

        该类方法能获得全局最优解,但随着节点的增加,算法的时间复杂度会增加得很快;并且它不能区分同属于一个马尔可夫等价类的图,这一点后面会讲到。

    • 参数学习:在给定网络结构时,确定网络参数,即参数估计问题:

      • 不含隐变量:如果图模型中不含隐变量(latent variable),即所有变量都是可观测的,那么网络参数一般可以直接通过最大似然来进行估计。

      • 含隐变量:有些时候 XX 中的变量有很复杂的依赖关系,这时通常会引入隐变量 zz 来简化模型。如果图模型中包含隐变量,即有部分变量是不可观测的,这时就需要用 EM 算法(Expectation Maximum,期望最大化算法)来进行参数估计。

        如果 EM 算法中的后验是 intractable 的,那么又需要用变分推断(Variational Inference)来寻找一个简单分布来近似后验。

        而在深度学习大行其道的今天,你可能会想到用神经网络去拟合这个后验不就完事儿了,是的这就是变分自编码器(Variational Auto-Encoder,VAE)的思想,去学它吧朋友。

      本文不讨论参数学习问题,但我在我的笔记本上写了一些参数学习相关的东西,有兴趣的话可以看一看。

  • 推断问题:在已知部分变量时,计算其他变量的条件概率分布

PC 算法

好的现在讲主题了,用 PC 算法1来学习出贝叶斯网络的结构。如上文所述,PC 算法会先确定节点间的依赖关系(但不确定方向),即先生成一个无向图,然后再确定依赖方向,把无向图扩展为完全部分有向无环图(Completed Partially Directed Acyclic Graph,CPDAG)。

依赖关系确立

VV 是输入点集,有以下步骤:

  • VV 上生成完全无向图 GG
  • 对于 GG 中的两个相邻点 i,ji, j,如果 iijj 能在给定节点 kk 时条件独立,则删除 iijj 之间的边

这样会得到一个无向图,图中的无向边表示它连接的两个节点之间有依赖(因果)关系,这样的无向图叫骨架(skeleton)。PC 算法把上述过程转化为了 dd 分隔(d-separation)2问题。

d 分隔

d 分隔的定义

节点集合 OOdd 分隔节点 ii 与节点 jj,当且仅当:

给定 OO 时,iijj 之间不存在有效路径(active path),即 iijjOO 下条件独立(记作 ijOi \perp j \mid O)。

O(i,j)O(i, j) 表示能够 dd 分隔 iijj 的点集,用 adj(G,x)adj(G, x) 表示图 GG 中节点 xx 的相邻点集,那么 PC 算法检验条件独立性的具体流程为3

pc-skeleton

Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm. Markus Kalisch and Peter Buhlmann. JMLR 2007.

简单总结一下:

  • =1\ell = 1

  • repeat

    • for 每个相邻点对 (i,j)(i, j)

      • for adj(G,i)\{j}adj(G, i) \backslash \{j\}adj(G,i)\{i}adj(G, i) \backslash \{i\} 的所有可能的节点数为 \ell 的子集 KK

        • 测试 KK 能否 dd 分隔 (i,j)(i, j)

        • 如果能,说明 iijj 之间不存在有效的依赖关系,所以删除边 iji - j,并将这个点集加入 O(i,j)O(i, j)O(j,i)O(j, i)break

    • =+1\ell = \ell + 1

  • until 当前图中的所有的邻接点集都小于 \ell

Fisher Z Test

为了判断 dd 分隔,我们需要对任意两个节点进行条件独立性检验,PC 算法采用了 Fisher Z Test4 作为条件独立性检验方法。实际上 Fisher Z Test 是一种相关性检验方法,但 PC 算法认为这一堆随机变量整体上服从多元高斯分布,这时变量条件独立与变量之间的偏相关系数为 0 等价(多元高斯分布的基本特性,证明过程可以参考 Steffen L. Lauritzen 的课件5第 4.2.1 节),所以可以用 Fisher Z Test 进行条件独立性检验。

偏相关系数指校正其它变量后某一变量与另一变量的相关关系,校正的意思可以理解为假定其它变量都取值为均数。任意两个变量 i,ji, jhh 阶(排除其他 hh 个变量的影响后,h<=k2h<=k-2)偏相关系数为:

ρi,jK=ρi,jK\hρi,hK\hρj,hK\h(1ρi,hK\h2)(1ρj,hK\h2)\rho_{i,j \mid K} = \frac{\rho_{i,j \mid K \backslash h} - \rho_{i,h \mid K \backslash h} \rho_{j,h \mid K \backslash h}}{\sqrt{(1 - \rho^2_{i,h \mid K \backslash h}) (1 - \rho^2_{j,h \mid K \backslash h})}}

为了判断 ρ\rho 是否为 0,需要将 ρ\rho 通过 Fisher Z 变换6转换成正态分布:

Z(i,jK)=12log(1+ρ^i,jK1ρ^i,jK)Z(i, j \mid K) = \frac{1}{2} \log (\frac{1 + \hat{\rho}_{i,j \mid K}}{1 - \hat{\rho}_{i,j \mid K}})

定义零假设和对立假设:

  • 零假设:H0(i,jK):ρi,jK0H_0(i,j \mid K): \rho_{i,j \mid K} \not= 0
  • 对立假设:H1(i,jK):ρi,jK=0H_1(i,j \mid K): \rho_{i,j \mid K} = 0

然后给定一个显著性水平 α(0,1)\alpha \in (0, 1),那么(双侧)检验的规则为,如果有:

nK3Z(i,jK)Φ1(1α/2)\sqrt{n - |K| - 3}| Z(i,j \mid K) \leq \Phi^{-1} (1 - \alpha/2)

其中 Φ()\Phi(\cdot)N(0,1)\mathcal{N}(0, 1) 的累积分布函数,则拒绝零假设,i,ki, k 关于 KK 条件独立。所以将上面伪代码的第 11 行替换为 if nK3Z(i,jK)Φ1(1α/2)\sqrt{n - |K| - 3}| Z(i,j \mid K) \leq \Phi^{-1} (1 - \alpha/2)

依赖关系方向确立

经过上一个阶段,我们得到了一个无向图。现在我们要利用 dd 分隔的原理来确定图中边的依赖方向,把骨架扩展为 DAG。

对于任意三个以有效依赖关系边相连的节点 XZYX-Z-Y,其依赖关系必为下图的四种关系之一:

link

dd 分隔的结论为:对于有向无环图 EE,有两个节点 X,YX, Y 和一个点集 OO,为了判断 XXYY 是否关于 OO 条件独立,考虑 EE 中所有 XXYY 之间的无向路径,对于其中一条路径,如果它满足以下两个条件中的任意一条,则称这条路径是阻塞的:

  • 路径中存在某个节点 ZZ 是 head-to-tial(图中情况 a, b)或 tail-to-tail 节点(图中情况 c),且 ZZ 包含在 OO
  • 路径中存在某个节点 ZZ 是 head-to-head 节点(图中情况 d),且 ZZ 没有被包含在 OO

如果 X,YX,Y 间所有的路径都是阻塞的,那么 X,YX,Y 关于 OO 条件独立;否则,X,YX,Y 不关于 OO 条件独立。

而我们已经记录了 dd 分隔 XXYY 的点集 OO,因此我们可以由 dd 分隔的结论反推出贝叶斯网络中边的方向,方向的判断方法可以转换成以下三条规则:

  • 规则 1:如果存在 XYZX \rightarrow Y - Z,把 YZY - Z 变为 YZY \rightarrow Z
  • 规则 2:如果存在 XZYX \rightarrow Z \rightarrow Y,把 XYX - Y 变为 XYX \rightarrow Y
  • 规则 3: 如果存在 XZ1YX - Z_1 \rightarrow YXZ2YX - Z_2 \rightarrow Y,且 Z1,Z2Z_1, Z_2 不相邻,把 XYX - Y 变为 XYX \rightarrow Y

实际上还可以推出一个规则 4:

  • 规则 4:如果存在 XZ1Z2X - Z_1 \rightarrow Z_2Z1Z2YZ_1 \rightarrow Z_2 \rightarrow Y,且 Z1,Z2Z_1, Z_2 不相邻,把 XYX - Y 变为 XYX \rightarrow Y

但很显然这种情况是矛盾的,不可能存在,所以不用考虑。

总结一下:

extend-to-cpdag

Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm. Markus Kalisch and Peter Buhlmann. JMLR 2007.

这样我们就可以得到一个完全部分有向无环图。

马尔科夫等价类

很明显,完全部分有向无环图(CPDAG)跟有向无环图看上去就不一样。首先来看什么是部分有向无环图(Partially Directed Acyclic Graph,PDAG):

部分有向无环图

假设 G=(V,E)G = (V, E) 是一个图,若边集 EE 中包含有向边和无向边,且不存在有向环,则称 GG 是一个部分有向无环图。

完全部分有向无环图指:

完全部分有向无环图

假设 G=(V,E)G = (V, E) 是一个部分有向无环图,若 EE 中的有向边都是不可逆的,并且 EE 中的无向边都是可逆的,则称 GG 是一个完全部分有向无环图。

关于可逆和不可逆:

可逆 / 不可逆

对于有向无环图 G=(V,E)G = (V, E) 中的任意有向边 ViVjEV_i \rightarrow V_j \in E,如果存在图 G=(V,E)G' = (V, E')GG 等价,且 VjViEV_j \rightarrow V_i \in E',则称有向边 ViVjV_i \rightarrow V_jGG 中是可逆的,否则是不可逆的。

同理,对任意无向边 ViVjEV_i - V_j \in E,若存在 G1=(V,E1)G_1 = (V, E_1)G2=(V,E2)G_2 = (V, E_2) 均与 GG 等价,且 ViVjE1V_i \rightarrow V_j \in E_1VjViE2V_j \rightarrow V_i \in E_2,则称无向边 ViVjV_i - V_jGG 中是可逆的,否则是不可逆的。

换句话说用 PC 算法得到的图是含有无向边的。这是因为依据 dd 分隔确定的条件独立性所构造的网络 结构不具有唯一性,它们只是真实的贝叶斯网络的马尔科夫等价类(Markov Equivalence Class):

马尔科夫等价类

有向无环图 G1=(V,E1)G_1 = (V, E_1)G2=(V,E2)G_2 = (V, E_2) 有相同的顶点集合和骨架,VV 为顶点集合,E1E_1E2E_2 为边的集合。

对于任意的不相交的顶点集合 A,B,CVA, B, C \in V,如果满足 A,BA, BG1G_1G2G_2 中都被 CCdd 分隔(也叫有相同的 VV 结构),则称图 G1G_1G2G_2 是马尔科夫等价的。

举个栗子:

markov-equivalence-class

马尔科夫等价类

上图 G1G_1G2G_2 是马尔科夫等价类,它们左上角的那条有向边方向并不相同,这时 PC 算法就无法判断这条边的方向了,只能输出无向边,即 G3G_3

所以,严格来说,PC 算法以及大多数基于依赖统计分析的贝叶斯网络结构学习算法,得到的都只是一个 CPDAG(依然有无向边),而不是真正意义上的贝叶斯网络(有向无环图)。

参考

Footnotes

  1. An Algorithm for Fast Recovery of Sparse Causal Graphs. Peter Spirtes and Clark Glymour. Social Science Computer Review 1991.

  2. d-Separation: From Theorems to Algorithms. Dan Geiger, et al. UAI 1989.

  3. Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm. Markus Kalisch and Peter Buhlmann. JMLR 2007.

  4. Frequency Distribution of the Values of the Correlation Coefficient in Samples from an Indefinitely Large Population. R. A. Fisher. Biometrika 1915.

  5. Elements of Graphical Models. Steffen L. Lauritzen. 2011.

  6. Wikipedia: Fisher transformation