Skip to content

Renovamen/pcalg-py

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

PC 算法

如何使用

  1. 安装依赖:

    pip install -r requirements.txt
  2. 修改 data/test.csv 中的数据

  3. 运行:

    python run.py

 

算法

博客

这里只是简要解释了一下 PC 算法的流程,如果想看更详细的说明(或无法加载公式),可以看我的博客:博客 / 知乎

 

依赖关系确立

skeleton

图片来源:Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

line 11: 需要条件独立关系

 

条件独立性 -> 偏相关系数

偏相关系数:校正其它变量后某一变量与另一变量的相关关系,校正的意思可以理解为假定其它变量都取值为均数。

PC 算法默认随机变量服从多元高斯分布,这时条件独立性与偏相关系数为 0 等价。

表述得更准确一点:假设随机变量 $X$ 服从多元高斯分布,对于 $i \not = j \in (1, \dots, p), k \in (1, \dots, p) \backslash {i, j}$,用 $\rho_{i, j \mid k}$ 表示 $X(i)$$X(j)$$X^{(r)} (r \in k)$ 之间的偏相关系数。当且仅当 $X(i)$$X(j)$ 条件独立与 $X^{(r)} (r \in k)$ 时,$\rho_{i, j \in k} = 0$。

这个结论是多元高斯分布的基本特性,证明过程可以参考 Elements of Graphical Models 第 4.2.1 节。

所以条件独立性可由偏相关估计出来,所以条件独立性检验转偏相关系数检验。

任意两个变量 $i, j$$h$(排除其他 $h$ 个变量的影响后,$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})}} $$

 

Fisher Z Test

用 Fisher Z Test 来判断 $\rho$ 是否为 0。显著性检验要求 $\rho$ 为正态分布,所以需要先将 $\rho$ 进行 Fisher's z-transformation,转换后可以认为是正态分布:

$$ 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$

检验规则为:当 $\sqrt{n - |K| - 3}| Z(i,j \mid K) \leq \Phi^{-1} (1 - \alpha/2)$ 时(其中 $\Phi(\cdot)$$\mathcal{N}(0, 1)$ 的累积分布函数),拒绝 $H_0$,$H_1$ 成立,$i, k$ 关于 $K$ 条件独立。

所以将上面伪代码的 line 11 替换为 $\sqrt{n - |K| - 3}| Z(i,j \mid K) \leq \Phi^{-1} (1 - \alpha/2)$

 

依赖方向确立:骨架 -> CPDAGE

依赖关系确立后,得到了一个无向图(骨架),现在需要确立依赖方向,把无向边变成有向边。

extend-to-cpdag

图片来源:Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

得到一个完全部分有向无环图(CPDAG)。

可以看到 PC 算法得到的图是含有无向边的,这个图只是一个 CPDAG(依然有无向边),而不是真正意义上的贝叶斯网络(有向无环图),具体原因可以参考我的博客

但任意贝叶斯网络都存在唯一的 CPDAG 与之马尔科夫等价,因此,CPDAG 可以作为贝叶斯网络的表示。

 

一些定义

  • 部分有向无环图(Partially Directed Acyclic Graph,PDAG):假设 $G = (V, E)$ 是一个图,若边集 $E$ 中包含有向边和无向边,且不存在有向环,则称 $G$ 是一个部分有向无环图

  • 马尔科夫等价类(Markov Equivalence Class):$G_1 = (V, E_1)$ 和 $G_2 = (V, E_2)$ 马尔科夫等价, 当且仅当 $G_1$$G_2$ 具有相同的骨架和 $V$ 结构

  • 可逆

    • 有向无环图 $G = (V, E)$,任意有向边 $V_i \rightarrow V_j \in E$,若存在图 $G' = (V, E')$$G$ 等价,且 $V_j \rightarrow V_i \in E'$,则称有向边 $V_i \rightarrow V_j$$G$ 中是可逆的,否则是不可逆的

    • 同理,对任意无向边 $V_i - V_j \in E$,若存在 $G_1 = (V, E_1)$、$G_2 = (V, E_2)$ 均与 $G$ 等价,且 $V_i \rightarrow V_j \in E_1$、$V_j \rightarrow V_i \in E_2$,则称无向边 $V_i - V_j$$G$ 中是可逆的,否则是不可逆的

  • 完全部分有向无环图(Completed Partially Directed Acyclic Graph,CPDAG:设 $G = (V, E)$ 是一个部分有向无环图,若 $E$ 中的有向边都是不可逆的,并且 $E$ 中的无向边都是可逆的,则称 $G$ 是一个完全部分有向无环图(CPDAG)

 

参考

Releases

No releases published

Packages

No packages published

Languages