PC 算法

Baste · 发表于 2021-11-19 19:44

把大三的时候在实验室摸鱼看贝叶斯网络和 PC 算法时写的笔记整理到这里来，免得哪天我换电脑时把笔记搞没了。
P.S. 我博客上的排版大概会稍微好一点？
概率图模型

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

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

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

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

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

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

有向图模型

贝叶斯网络

信念网络

有向无环图

无向图模型

马尔可夫随机场

图片来源：《神经网络与深度学习》：https://nndl.github.io

本文只讨论有向图模型，即贝叶斯网络。
<hr/>贝叶斯网络

定义

有向无环图  中，每个节点对应  维随机向量  中的一个变量，有向边 $e_{ij}$ 表示随机变量  和  之间具有因果关系，父节点是『因』，子节点是『果』，显然这两个点之间一定非条件独立。
令 $X_{\pi_k}$ 为变量  的所有父节点变量集合， $P(X_k \mid X_{\pi_k})$ 表示每个随机变量的局部条件概率分布（Local Conditional Probability Distribution）。

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

$p(x) = \prod_{k=1}^K p(x_k \mid x_{\pi_k})$
那么称 $(G,X)$ 构成了一个贝叶斯网络。
局部马尔可夫性质

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

$X_k \perp Z \mid X_{\pi_k}$
其中  为  的非后代节点。
基本问题

学习问题

结构学习

评分搜索

依赖统计分析

PC 算法

参数学习

不含隐变量

隐变量

最大似然

含隐变量

隐变量

$z$

EM 算法

变分推断

变分自编码器

推断问题

<hr/>PC 算法

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

设是输入点集，有以下步骤：

$k$

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

节点集合能 d 分隔节点与节点，当且仅当：给定时，与之间不存在有效路径（active path），即和在下条件独立（记作 $i \perp j \mid O$ ）。
用表示能够 d 分隔和的点集，用 $adj(G, x)$ 表示图中节点的相邻点集，那么 PC 算法检验条件独立性的具体流程为[3]：

Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

简单总结一下：

$\ell = 1$

repeat

for 每个相邻点对

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

$i - j$

$O(j, i)$

break

$\ell = \ell + 1$

until

Fisher Z Test

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

偏相关系数指校正其它变量后某一变量与另一变量的相关关系，校正的意思可以理解为假定其它变量都取值为均数。任意两个变量的阶（排除其他个变量的影响后， $h<=k-2$ ）偏相关系数为：

$\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})}}$

为了判断是否为 0，需要将通过 Fisher Z 变换[6]转换成正态分布：

$Z(i, j \mid K) = \frac{1}{2} \log (\frac{1 + \hat{\rho}_{i,j \mid K}}{1 - \hat{\rho}_{i,j \mid K}})$

定义零假设和对立假设：

$H_0(i,j \mid K): \rho_{i,j \mid K} \not= 0$

$H_1(i,j \mid K): \rho_{i,j \mid K} = 0$

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

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

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

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

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

如果间所有的路径都是阻塞的，那么关于条件独立；否则，不关于关于条件独立。
而我们已经记录了 d 分隔和的点集，因此我们可以由 d 分隔的结论反推出贝叶斯网络中边的方向，方向的判断方法可以转换成以下三条规则：

规则 1

$X \rightarrow Y - Z$

$Y - Z$

$Y \rightarrow Z$

规则 2

$X \rightarrow Z \rightarrow Y$

规则 3

$X - Z_1 \rightarrow Y$

$X - Z_2 \rightarrow Y$

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

规则 4

$X - Z_1 \rightarrow Z_2$

$Z_1 \rightarrow Z_2 \rightarrow Y$

但很显然这种情况是矛盾的，不可能存在，所以不用考虑。
总结一下：

Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

这样我们就可以得到一个完全部分有向无环图。
马尔科夫等价类

很明显，完全部分有向无环图（CPDAG）跟有向无环图看上去就不一样。首先来看什么是部分有向无环图（Partially Directed Acyclic Graph，PDAG）：假设  是一个图，若边集  中包含有向边和无向边，且不存在有向环，则称  是一个部分有向无环图。

而完全部分有向无环图指：假设  是一个部分有向无环图，若  中的有向边都是不可逆的，并且  中的无向边都是可逆的，则称  是一个完全部分有向无环图。
关于可逆和不可逆：对于有向无环图  中的任意有向边 $V_i \rightarrow V_j \in E$ ，如果存在图 $G' = (V, E')$ 与  等价，且 $V_j \rightarrow V_i \in E'$ ，则称有向边 $V_i \rightarrow V_j$ 在  中是可逆的，否则是不可逆的。同理，对任意无向边 $V_i - V_j \in E$ ，若存在、  均与  等价，且 $V_i \rightarrow V_j \in E_1$ 、 $V_j \rightarrow V_i \in E_2$ ，则称无向边 $V_i - V_j$ 在  中是可逆的，否则是不可逆的。
换句话说用 PC 算法得到的图是含有无向边的。这是因为依据 d 分隔确定的条件独立性所构造的网络结构不具有唯一性，它们只是真实的贝叶斯网络的马尔科夫等价类（Markov Equivalence Class）：

有向无环图  和  有相同的顶点集合和骨架，  为顶点集合， $E_1$ 和   $E_2$ 为边的集合。对于任意的不相交的顶点集合 $A, B, C \in V$ ，如果满足 $A, B$ 在  和  中都被 $C$ 所 d 分隔（也叫有相同的  结构），则称图  和  是马尔科夫等价的。
举个栗子：

马尔科夫等价类

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

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

^An Algorithm for Fast Recovery of Sparse Causal Graphs. Peter Spirtes and Clark Glymour. Social Science Computer Review 1991.http://shelf2.library.cmu.edu/Tech/28463803.pdf
^Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm. Markus Kalisch and Peter Buhlmann. JMLR 2007.https://arxiv.org/pdf/1304.1505.pdf
^d-Separation: From Theorems to Algorithms. Dan Geiger, et al. UAI 1989.https://www.jmlr.org/papers/volume8/kalisch07a/kalisch07a.pdf
^Frequency Distribution of the Values of the Correlation Coefficient in Samples from an Indefinitely Large Population. R. A. Fisher. Biometrika 1915.https://www.quantresearch.org/Fisher%20transform%20seminal%20paper.pdf
^Elements of Graphical Models. Steffen L. Lauritzen. 2011.http://www.stats.ox.ac.uk/~steffen/teaching/gm10/stflournotes.pdf
^Wikipedia: Fisher transformationhttps://en.wikipedia.org/wiki/Fisher_transformation

闲鱼技术01 · 发表于 2021-11-19 19:48

我想问一下，我们通常说的PC算法，是91年提出的那个还是07年的那个[捂脸]

		自动登录	找回密码
密码			立即注册

PC 算法

本帖子中包含更多资源