基本定义 Skeleton ：初始化图G G G
PDAG ：设G = ( V , E ) G = (V, E) G = ( V , E ) E E E
马尔科夫等价 ：贝叶斯网络< G 1 , P 1 > <G_1, P_1> < G 1 , P 1 > < G 2 , P 2 > <G_2, P_2> < G 2 , P 2 > G 1 G_1 G 1 G 2 G_2 G 2 V V V
有向无环图G = ( V , E ) G = (V, E) G = ( V , E ) V i → V j ∈ E V_i \rightarrow V_j ∈ E V i → V j ∈ E G ′ = ( V , E ′ ) G' = (V, E') G ′ = ( V , E ′ ) G G G V j → V i ∈ E ′ V_j \rightarrow V_i ∈ E' V j → V i ∈ E ′ V i → V j V_i \rightarrow V_j V i → V j G G G
同理，对任意无向边V i → V j ∈ E V_i \rightarrow V_j ∈ E V i → V j ∈ E G 1 = ( V , E 1 ) G_1 = (V, E_1) G 1 = ( V , E 1 ) G 2 = ( V , E 2 ) G_2 = (V, E_2) G 2 = ( V , E 2 ) G G G V i → V j ∈ E 1 V_i \rightarrow V_j ∈ E_1 V i → V j ∈ E 1 V j → V i ∈ E 2 V_j \rightarrow V_i ∈ E_2 V j → V i ∈ E 2 V i → V j V_i \rightarrow V_j V i → V j G G G
CPDAG ：设G = ( V , E ) G = (V, E) G = ( V , E ) E E E E E E G G G
传统方法 算法过程参考文献 ，是经典的 PC 算法过程。
在文献 中对其 skeleton 估计进行重写，如下所示：
条件独立性优化 偏相关系数 指校正其它变量后某一变量与另一变量的相关关系，校正的意思可以理解为假定其它变量都取值为均数服从高斯分布的随机变量，条件独立性与偏相关系数为 0 等价：
假设随机变量X X X i ≠ j ∈ ( 1 , . . . , p ) ， k ⊆ ( 1 , . . . , p ) / ( i ， j ) i \not =j∈(1, ..., p)，k⊆(1, ..., p) /\ (i，j) i = j ∈ ( 1 , . . . , p ) ， k ⊆ ( 1 , . . . , p ) / ( i ， j ) ρ i ， j ∣ k ρ_{i，j|k} ρ i ， j ∣ k X ( i ) X(i) X ( i ) X ( j ) X(j) X ( j ) X ( r ) ( r ∈ k ) X^{(r)} (r∈k) X ( r ) ( r ∈ k ) X ( i ) X(i) X ( i ) X ( j ) X( j ) X ( j ) X ( r ) ( r ∈ k ) X^{(r)} (r∈k) X ( r ) ( r ∈ k ) ρ i ， j ∣ k = 0 ρ_{i，j|k}=0 ρ i ， j ∣ k = 0
∴ 条件独立性可由偏相关估计出来，条件独立性检验转偏相关系数检验。
任意两个变量i , j i, j i , j h h h h h h h < = k − 2 h<=k-2 h < = k − 2
ρ i , j ∣ k = ρ i , j ∣ k \ h − ρ i , h ∣ k \ h ρ j , h ∣ k \ h ( 1 − ρ i , h ∣ k \ h 2 ) ( 1 − ρ j , h ∣ k \ h 2 ) \rho_{i, j \mid \mathbf{k}}=\frac{\rho_{i, j \mid \mathbf{k} \backslash h} - \rho_{i, h \mid \mathbf{k} \backslash h}\rho_{j,h \mid \mathbf{k} \backslash h}}{\sqrt{\left(1-\rho_{i, h \mid \mathbf{k} \backslash h}^{2}\right)\left(1-\rho_{j, h \mid \mathbf{k} \backslash h}^{2}\right)}} ρ i , j ∣ k = ( 1 − ρ i , h ∣ k \ h 2 ) ( 1 − ρ j , h ∣ k \ h 2 ) ρ i , j ∣ k \ h − ρ i , h ∣ k \ h ρ j , h ∣ k \ h
Fisher Z Test ρ ≠ 0 ρ\not=0 ρ = 0
ρ ≠ 0 ρ\not=0 ρ = 0 t t t ρ \rho ρ
Fisher’s z-transform:
Z ( i , j ∣ k ) = 1 2 log ( 1 + ρ ^ i , j ∣ k 1 − ρ ^ i , j ∣ k ) Z(i, j \mid \mathbf{k})=\frac{1}{2} \log \left(\frac{1+\hat{\rho}_{i, j \mid \mathbf{k}}}{1-\hat{\rho}_{i, j \mid \mathbf{k}}}\right) Z ( i , j ∣ k ) = 2 1 log ( 1 − ρ ^ i , j ∣ k 1 + ρ ^ i , j ∣ k )
零假设：H 0 ( i , j ∣ k ) : ρ i ， j ∣ k ≠ 0 H_0(i,j|k): ρ_{i，j|k} \not= 0 H 0 ( i , j ∣ k ) : ρ i ， j ∣ k = 0
对立假设：H 1 ( i , j ∣ k ) : ρ i ， j ∣ k = 0 H_1(i,j|k): ρ_{i，j|k} = 0 H 1 ( i , j ∣ k ) : ρ i ， j ∣ k = 0
当n − ∣ k ∣ − 3 ∣ Z ( i , j ∣ k ) > Φ − 1 ( 1 − α / 2 ) \sqrt{n-|k|-3}|Z(i,j|k)>Φ^{-1}(1-α/2) n − ∣ k ∣ − 3 ∣ Z ( i , j ∣ k ) > Φ − 1 ( 1 − α / 2 ) H 0 H_0 H 0
∴ 用n − ∣ k ∣ − 3 ∣ Z ( i , j ∣ k ) < = Φ − 1 ( 1 − α / 2 ) \sqrt{n-|k|-3}|Z(i,j|k)<=Φ^{-1}(1-α/2) n − ∣ k ∣ − 3 ∣ Z ( i , j ∣ k ) < = Φ − 1 ( 1 − α / 2 ) i , j i,j i , j k k k d − s e p a r a t i o n d-separation d − s e p a r a t i o n
注：
条件独立性检验包含两种方式：
G-square test：基于条件交叉熵，主要用于类别变量。 Fisher-Z test：基于皮尔逊相关系数，主要用于连续变量。 详情参考：偏相关系数与条件独立性检验 https://en.wikipedia.org/wiki/Partial_correlation
CPDAG 将 Skeleton 扩展为等价的 CPDAG ：
