PC 算法
把大三的时候在实验室摸鱼看贝叶斯网络和 PC 算法时写的笔记整理到这里来，免得哪天我换电脑时把笔记搞没了。P.S. 我博客上的排版大概会稍微好一点？
概率图模型
对于一个维随机向量 https://www.zhihu.com/equation?tex=X+%3D+%5BX_1%2C+X_2%2C+%5Cdots%2C+X_K%5D%5E%7B%5Ctop%7D，一般难以直接建模。因为如果每个变量为离散变量并有 https://www.zhihu.com/equation?tex=M 个可能取值，在不作任何独立性假设的前提下，需要 https://www.zhihu.com/equation?tex=M%5EK+-1 个参数才能表示其概率分布，参数数量会非常庞大。
一种减少参数数量的方法是独立性假设。把 的联合概率分解为个条件概率的乘积：
https://www.zhihu.com/equation?tex=p%28X+%3D+x%29+%3D+%5Cprod_%7Bk%3D1%7D%5EK+p%28x_k+%7C+x_1%2C+%5Cdots%2C+x_%7Bk-1%7D%29
为随机向量的取值。可以看到，如果某些变量之间存在条件独立，参数数量就可以大幅减少。
因此，概率图模型（Probabilistic Graphical Model，PGM）用图结构来描述多元随机变量之间的条件独立关系，从而为研究高维空间中的概率模型带来了很大的便捷。
概率图模型中，每个节点表示一个（或一组）随机变量，边表示这些随机变量之间的概率依赖关系。常见的概率图模型可以分为有向图模型和无向图模型。
有向图模型（Directed Graphical Model），也称为贝叶斯网络（Bayesian Network）或信念网络（Belief Network），使用有向无环图（Directed Acyclic Graph，DAG）来描述变量之间的关系。如果两个节点之间有连边，表示这两个变量之间有因果关系，即不存在其他变量使得这两个变量条件独立。无向图模型，也称为马尔可夫随机场（Markov Random Field，MRF），使用无向图来描述变量之间的关系。两个节点之间有连边代表这两个变量之间有概率依赖关系，但不一定是因果关系。
图片来源：《神经网络与深度学习》：https://nndl.github.io
本文只讨论有向图模型，即贝叶斯网络。
<hr/>贝叶斯网络
定义
有向无环图中，每个节点对应维随机向量中的一个变量，有向边 https://www.zhihu.com/equation?tex=e_%7Bij%7D 表示随机变量和之间具有因果关系，父节点 是『因』，子节点 是『果』，显然这两个点之间一定非条件独立。
令 https://www.zhihu.com/equation?tex=X_%7B%5Cpi_k%7D 为变量的所有父节点变量集合， https://www.zhihu.com/equation?tex=P%28X_k+%5Cmid+X_%7B%5Cpi_k%7D%29 表示每个随机变量的局部条件概率分布（Local Conditional Probability Distribution）。
如果 的联合概率分布可以分解为每个随机变量的局部条件概率的连乘形式，即：
https://www.zhihu.com/equation?tex=p%28x%29+%3D+%5Cprod_%7Bk%3D1%7D%5EK+p%28x_k+%5Cmid+x_%7B%5Cpi_k%7D%29
那么称 https://www.zhihu.com/equation?tex=%28G%2CX%29 构成了一个贝叶斯网络。
局部马尔可夫性质
每个随机变量在给定父节点的情况下，条件独立于它的非后代节点：
https://www.zhihu.com/equation?tex=X_k+%5Cperp+Z+%5Cmid+X_%7B%5Cpi_k%7D
其中为的非后代节点。
基本问题
学习问题
结构学习：那么怎样才可以获得这个神奇的有向无环图呢，这就是结构学习问题。即学习出最优网络结构，也就是各节点之间的依赖关系。传统的的结构学习方法主要可以分为：
基于评分搜索的方法：利用搜索算法和评分函数，对每一个搜索到的网络结构进行评分，最终搜索出评分最高的网络结构。搜索算法的复杂度和精确度直接决定了学习算法的搜索效率，评分函数的优劣也直接决定了算法的计算复杂度和精确度。所以选择合理的优化搜索算法和评分函数是该类方法的核心问题。该类方法容易陷入局部最优解而无法达到全局最优，并且结构空间的随节点的增加呈指数增加(空间复杂度)。基于依赖统计分析的方法：分析变量间的依赖关系，在依赖性较大的两节点之间添加连接边，得到无向图。然后根据包含关系等方式确定无向图中边的方向，得到最终的有向无环图。本文要讨论的 PC 算法就是这类方法中（比较古老）的一种。该类方法能获得全局最优解，但随着节点的增加，算法的时间复杂度会增加得很快；并且它不能区分同属于一个马尔可夫等价类的图，这一点后面会讲到。
参数学习：在给定网络结构时，确定网络参数，即参数估计问题：
不含隐变量：如果图模型中不含隐变量（latent variable），即所有变量都是可观测的，那么网络参数一般可以直接通过最大似然来进行估计。含隐变量：有些时候 中的变量有很复杂的依赖关系，这时通常会引入隐变量 https://www.zhihu.com/equation?tex=z来简化模型。如果图模型中包含隐变量，即有部分变量是不可观测的，这时就需要用 EM 算法（Expectation Maximum，期望最大化算法）来进行参数估计。如果 EM 算法中的后验是 intractable 的，那么又需要用变分推断（Variational Inference）来寻找一个简单分布来近似后验。你可能会想到用神经网络去拟合这个后验不就完事儿了，是的这就是变分自编码器（Variational Auto-Encoder，VAE）的思想。本文不讨论参数学习问题，但我在我的笔记本上写了一些参数学习相关的东西，有兴趣的话可以看一看。
推断问题：在已知部分变量时，计算其他变量的条件概率分布
<hr/>PC 算法
好的现在讲主题了，用 PC 算法来学习出贝叶斯网络的结构。如上文所述，PC 算法会先确定节点间的依赖关系（但不确定方向），即先生成一个无向图，然后再确定依赖方向，把无向图扩展为完全部分有向无环图（Completed Partially Directed Acyclic Graph，CPDAG）。
依赖关系确立
设 是输入点集，有以下步骤：
在上生成完全无向图对于中的两个相邻点，如果和能在给定节点 https://www.zhihu.com/equation?tex=k 时条件独立，则删除和之间的边
这样会得到一个无向图，图中的无向边表示它连接的两个节点之间有依赖（因果）关系，这样的无向图叫骨架（skeleton）。PC 算法把上述过程转化为了 d 分隔（d-separation）问题。
d 分隔
节点集合能 d 分隔节点与节点，当且仅当：给定时，与之间不存在有效路径（active path），即和在下条件独立（记作 https://www.zhihu.com/equation?tex=i+%5Cperp+j+%5Cmid+O ）。
用表示能够 d 分隔和的点集，用 https://www.zhihu.com/equation?tex=adj%28G%2C+x%29 表示图中节点的相邻点集，那么 PC 算法检验条件独立性的具体流程为：
Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm
简单总结一下：
https://www.zhihu.com/equation?tex=%5Cell+%3D+1 repeat
for 每个相邻点对
for https://www.zhihu.com/equation?tex=adj%28G%2C+i%29+%5Cbackslash+%5C%7Bj%5C%7D 或https://www.zhihu.com/equation?tex=adj%28G%2C+i%29+%5Cbackslash+%5C%7Bi%5C%7D 的所有可能的节点数为 的子集
测试能否 d 分隔 如果能，说明和之间不存在有效的依赖关系，所以删除边 https://www.zhihu.com/equation?tex=i+-+j ，并将这个点集加入 和https://www.zhihu.com/equation?tex=O%28j%2C+i%29 ，break
https://www.zhihu.com/equation?tex=%5Cell+%3D+%5Cell+%2B+1 until 当前图中的所有的邻接点集都小于
Fisher Z Test
为了判断 d 分隔，我们需要对任意两个节点进行条件独立性检验，PC 算法采用了 Fisher Z Tes作为条件独立性检验方法。实际上 Fisher Z Test 是一种相关性检验方法，但 PC 算法认为这一堆随机变量整体上服从多元高斯分布，这时变量条件独立与变量之间的偏相关系数为 0 等价（多元高斯分布的基本特性，证明过程可以参考 Steffen L. Lauritzen 的课件第 4.2.1 节），所以可以用 Fisher Z Test 进行条件独立性检验。
偏相关系数指校正其它变量后某一变量与另一变量的相关关系，校正的意思可以理解为假定其它变量都取值为均数。任意两个变量的阶（排除其他个变量的影响后， https://www.zhihu.com/equation?tex=h%3C%3Dk-2 ）偏相关系数为：
https://www.zhihu.com/equation?tex=%5Crho_%7Bi%2Cj+%5Cmid+K%7D+%3D+%5Cfrac%7B%5Crho_%7Bi%2Cj+%5Cmid+K+%5Cbackslash+h%7D+-+%5Crho_%7Bi%2Ch+%5Cmid+K+%5Cbackslash+h%7D+%5Crho_%7Bj%2Ch+%5Cmid+K+%5Cbackslash+h%7D%7D%7B%5Csqrt%7B%281+-+%5Crho%5E2_%7Bi%2Ch+%5Cmid+K+%5Cbackslash+h%7D%29+%281+-+%5Crho%5E2_%7Bj%2Ch+%5Cmid+K+%5Cbackslash+h%7D%29%7D%7D
为了判断是否为 0，需要将通过 Fisher Z 变换转换成正态分布：
https://www.zhihu.com/equation?tex=Z%28i%2C+j+%5Cmid+K%29+%3D+%5Cfrac%7B1%7D%7B2%7D+%5Clog+%28%5Cfrac%7B1+%2B+%5Chat%7B%5Crho%7D_%7Bi%2Cj+%5Cmid+K%7D%7D%7B1+-+%5Chat%7B%5Crho%7D_%7Bi%2Cj+%5Cmid+K%7D%7D%29
定义零假设和对立假设：
零假设： https://www.zhihu.com/equation?tex=H_0%28i%2Cj+%5Cmid+K%29%3A++%5Crho_%7Bi%2Cj+%5Cmid+K%7D+%5Cnot%3D+0 对立假设： https://www.zhihu.com/equation?tex=H_1%28i%2Cj+%5Cmid+K%29%3A++%5Crho_%7Bi%2Cj+%5Cmid+K%7D+%3D+0
然后给定一个显著性水平 https://www.zhihu.com/equation?tex=%5Calpha+%5Cin+%280%2C+1%29 ，那么（双侧）检验的规则为，如果有：
https://www.zhihu.com/equation?tex=%5Csqrt%7Bn+-+%7CK%7C+-+3%7D%7C+Z%28i%2Cj+%5Cmid+K%29+%5Cleq+%5CPhi%5E%7B-1%7D+%281+-+%5Calpha%2F2%29+
其中https://www.zhihu.com/equation?tex=%5CPhi%28%5Ccdot%29为 https://www.zhihu.com/equation?tex=%5Cmathcal%7BN%7D%280%2C+1%29 的累积分布函数，则拒绝零假设，https://www.zhihu.com/equation?tex=i%2C+k 关于 条件独立。所以将上面伪代码的第 11 行替换为 “ifhttps://www.zhihu.com/equation?tex=%5Csqrt%7Bn+-+%7CK%7C+-+3%7D%7C+Z%28i%2Cj+%5Cmid+K%29+%5Cleq+%5CPhi%5E%7B-1%7D+%281+-+%5Calpha%2F2%29 “。
依赖关系方向确立
经过上一个阶段，我们得到了一个无向图。现在我们要利用 d 分隔的原理来确定图中边的依赖方向，把骨架扩展为 DAG。
对于任意三个以有效依赖关系边相连的节点 https://www.zhihu.com/equation?tex=X-Z-Y ，其依赖关系必为下图的四种关系之一：
d 分隔的结论为：对于有向无环图 ，有两个节点和一个点集，为了判断和是否关于条件独立，考虑中所有和之间的无向路径，对于其中一条路径，如果它满足以下两个条件中的任意一条，则称这条路径是阻塞的：
路径中存在某个节点是 head-to-tial（图中情况 a, b）或 tail-to-tail 节点（图中情况 c），且包含在中路径中存在某个节点是 head-to-head 节点（图中情况 d），且没有被包含在中
如果间所有的路径都是阻塞的，那么关于条件独立；否则， 不关于关于条件独立。
而我们已经记录了 d 分隔和的点集 ，因此我们可以由 d 分隔的结论反推出贝叶斯网络中边的方向，方向的判断方法可以转换成以下三条规则：
规则 1：如果存在 https://www.zhihu.com/equation?tex=X+%5Crightarrow+Y+-+Z ，把 https://www.zhihu.com/equation?tex=Y+-+Z 变为 https://www.zhihu.com/equation?tex=Y+%5Crightarrow+Z 规则 2：如果存在 https://www.zhihu.com/equation?tex=X+%5Crightarrow+Z+%5Crightarrow+Y，把变为规则 3：如果存在 https://www.zhihu.com/equation?tex=X+-+Z_1+%5Crightarrow+Y， https://www.zhihu.com/equation?tex=X+-+Z_2+%5Crightarrow+Y ，且不相邻，把变为
实际上还可以推出一个规则 4：
规则 4：如果存在 https://www.zhihu.com/equation?tex=X+-+Z_1+%5Crightarrow+Z_2 和 https://www.zhihu.com/equation?tex=Z_1+%5Crightarrow+Z_2+%5Crightarrow+Y ，且不相邻，把变为
但很显然这种情况是矛盾的，不可能存在，所以不用考虑。
总结一下：
Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm
这样我们就可以得到一个完全部分有向无环图。
马尔科夫等价类
很明显，完全部分有向无环图（CPDAG）跟有向无环图看上去就不一样。首先来看什么是部分有向无环图（Partially Directed Acyclic Graph，PDAG）：假设是一个图，若边集中包含有向边和无向边，且不存在有向环，则称是一个部分有向无环图。
而完全部分有向无环图指：假设是一个部分有向无环图，若中的有向边都是不可逆的，并且中的无向边都是可逆的，则称是一个完全部分有向无环图。
关于可逆和不可逆：对于有向无环图中的任意有向边 https://www.zhihu.com/equation?tex=V_i+%5Crightarrow+V_j+%5Cin+E，如果存在图 https://www.zhihu.com/equation?tex=G%27+%3D+%28V%2C+E%27%29 与等价，且 https://www.zhihu.com/equation?tex=V_j+%5Crightarrow+V_i+%5Cin+E%27，则称有向边 https://www.zhihu.com/equation?tex=V_i+%5Crightarrow+V_j 在中是可逆的，否则是不可逆的。同理，对任意无向边 https://www.zhihu.com/equation?tex=V_i+-+V_j+%5Cin+E，若存在 、均与等价，且 https://www.zhihu.com/equation?tex=V_i+%5Crightarrow+V_j+%5Cin+E_1、https://www.zhihu.com/equation?tex=V_j+%5Crightarrow+V_i+%5Cin+E_2，则称无向边 https://www.zhihu.com/equation?tex=V_i+-+V_j 在中是可逆的，否则是不可逆的。
换句话说用 PC 算法得到的图是含有无向边的。这是因为依据 d 分隔确定的条件独立性所构造的网络结构不具有唯一性，它们只是真实的贝叶斯网络的马尔科夫等价类（Markov Equivalence Class）：
有向无环图和有相同的顶点集合和骨架，为顶点集合， https://www.zhihu.com/equation?tex=E_1 和https://www.zhihu.com/equation?tex=E_2 为边的集合。对于任意的不相交的顶点集合 https://www.zhihu.com/equation?tex=A%2C+B%2C+C+%5Cin+V ，如果满足 https://www.zhihu.com/equation?tex=A%2C+B 在和中都被 https://www.zhihu.com/equation?tex=C 所 d 分隔（也叫有相同的结构），则称图和是马尔科夫等价的。
举个栗子：
马尔科夫等价类
上图和是马尔科夫等价类，它们左上角的那条有向边方向并不相同，这时 PC 算法就无法判断这条边的方向了，只能输出无向边，即 https://www.zhihu.com/equation?tex=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
我想问一下，我们通常说的PC算法，是91年提出的那个还是07年的那个[捂脸]
页:
[1]