| PC、PC | 您所在的位置：网站首页 › mpc与pc的主要区别是增加了 › PC、PC |
|
写在最前： 本人只是一个刚开始学习入门的学渣，写的笔记主要给自己看。要是有大佬发现有错误的地方，还望告知斧正。 PC、PC-Stable、Hiton-PC、MMPC详细描述 PC介绍PC-Stable介绍Hiton-PC介绍MMPC介绍 pc算法是顺序相关的，即输出可以取决于变量给出的顺序。这种顺序依赖性在低维中是一个小问题，在高维环境中，它可能非常明显，在那里它可能导致高度可变的结果。于是提出了对pc算法)的若干修改，以消除部分或全部的这种顺序依赖关系。 PC介绍设计用于在充足的因果假设下（即没有未测量的共同原因和没有选择变量）学习有向无环图(DAGs)。一个DAGs的马尔可夫等价类它可以被一个所谓的完整的部分有向无环图(CPDAG)唯一地描述。 骨架:把有向图G的有向边变成无向边。完全部分有向无环图(Completed Partially Directed Acyclic Graph，CPDAG)：设G=(V,E)是一个部分有向无环图，若E中的有向边都是不可逆的，并且E中的无向边都是可逆的，则称为一个CPDAG。马尔科夫等价:贝叶斯网络和马尔科夫等价,当且仅当G‘和G具有相同的骨架和V结构。 Xi⊥Xj|S表示S条件下Xi独立于Xj，其中S是一组不包含Xi和Xj的变量，S称为(Xi，Xj)的分离集，若S无子集满足独立条件，则称为最小集。该算法由三个步骤组成。步骤1（也称为邻接搜索）查找骨架和分离集，而步骤2和步骤3确定边缘的方向。 伪代码如下： Algorithm 3.1 The PC-algorithm (oracle version) Require: Conditional independence information among all variables in V, and an ordering order(V) on the variables 1: Adjacency search: Find the skeleton C and separation sets using Algorithm 3.2; 2: Orient unshielded triples in the skeleton C based on the separation sets; 3: In C orient as many of the remaining undirected edges as possible by repeated application of rules R1-R3 (see text); 4: return Output graph (C) and separation sets (sepset). 算法3.1 PC算法（Oracle版本） 要求：V中所有变量之间的条件独立信息，以及变量上的排序顺序(V) 1. 邻近搜索：使用算法3.2找到骨架C和分离集 2. 根据分离集，在骨架C中定位未屏蔽的三元组(v型结构(Xi，Xj，Xk)) 3. 在 C 中，通过重复应用规则 R1-R3（见正文），尽可能多地定位剩余的无向边 4. 返回 输出图(C)和分离集（sepset） Algorithm 3.2 Adjacency search / Step 1 of the PC-algorithm (oracle version) Require: Conditional independence information among all variables in V, and an ordering order(V) on the variables 1: Form the complete undirected graph C on the vertex set V 2: Let l = −1; 3: repeat 4: Let l = l + 1; 5: repeat 6: Select a (new) ordered pair of vertices (Xi, Xj ) that are adjacent in C and satisfy|adj(C, Xi) \ {Xj}| ≥ l , using order(V); 7: repeat 8: Choose a (new) set S ⊆ adj(C, Xi) \ {Xj} with |S| = l , using order(V); 9: if Xi and Xj are conditionally independent given S then 10: Delete edge Xi − Xj from C; 11: Let sepset(Xi, Xj ) = sepset(Xj , Xi) = S; 12: end if 13: until Xi and Xj are no longer adjacent in C or all S ⊆ adj(C, Xi) \ {Xj} with|S| = l have been considered 14: until all ordered pairs of adjacent vertices (Xi, Xj ) in C with |adj(C, Xi) \ {Xj}| ≥ l have been considered 15: until all pairs of adjacent vertices (Xi, Xj ) in C satisfy |adj(C, Xi) \ {Xj}| ≤ l 16: return C, sepset.当 l = 0 时，测试所有顶点对的边缘独立性。如果是Xi⊥Xj，则删除边Xi−Xj，并将空集保存为（Xi、Xj）和（Xj、Xi）的分离集。在考虑了所有的顶点对之后，算法将使用l=1进入下一步。 当 l = 1 时，算法选择在 C 中仍然相邻的一对有序顶点 (Xi , Xj )，并检查 Xi ⊥ Xj |S 是否成立，S为 adj(C, Xi) \ {Xj} 的大小为 l = 1 的子集 S . 如果找到这样的条件独立，则去除边Xi-Xj，将对应的条件集S保存在Xi、Xj）和（Xj、Xi）的分离集中。如果给定大小为l的所有子集的相邻顶点的所有有序对都已经考虑完毕，则该算法再次将l增加1。这个过程一直持续到当前图中的所有邻接集都小于l为止。此时，已经确定了骨架和分离集。 这个过程确实确保了我们只查询q−1阶的条件独立性，其中q是底层DAG中节点邻接集的最大大小。这使得该算法对于大型稀疏图特别有效。 步骤2确定了v型结构。特别地，它考虑C中的所有未屏蔽三元组，当且仅当Xj不属于(Xi、Xk)分离集时，将未屏蔽三元组(Xi、Xj、Xk)定位为v结构。 最后，步骤3通过重复应用以下三个规则，尽可能多地定位剩余的无向边： R1：只要存在有向边 Xi → Xj ，将 Xj − Xk 定向为 Xj → Xk，使得 Xi 和 Xk 不相邻（否则会创建新的 v 结构） R2：只要存在链 Xi → Xk → Xj，就将 Xi - Xj 定向为 Xi → Xj（否则创建有向循环） R3：当有两条链 Xi - Xk → Xj 和 Xi - Xl → Xj ，使得 Xk 和 Xl 不相邻时，将 Xi - Xj 定向为 Xi → Xj（否则会创建新的 v 结构或有向循环） Refs: [1]Colombo D, Maathuis M H. Order-independent constraint-based causal structure learning[J]. J. Mach. Learn. Res., 2014, 15(1): 3741-3782. PC-Stable介绍PC与PC-Stable之间的主要区别由后5-7行的for循环给出，它计算并存储了每个l条件下所有变量的邻接集a(Xi)。每当我们搜索给定大小的条件集时，都会使用这些存储的邻接集 a(Xi)。因此，第13行上的边删除不再影响在这个级别的上检查其他变量对的条件独立。 换句话说，在的每个级别上，PC-Stable记录了应该删除哪些边，但为了使用邻接集，它只有当它进入的下一个值时才会删除这些边。除了解决骨架估计中的顺序依赖性外，我们的算法还具有在的各级都易于并行的优点。 伪代码如下： Algorithm 3.2 Adjacency search / Step 1 of the PC-algorithm (oracle version) Require: Conditional independence information among all variables in V, and an ordering order(V) on the variables 1: Form the complete undirected graph C on the vertex set V 2: Let l = −1; 3: repeat 4: Let l = l + 1; 5: for all vertices Xi in C do 6: Let a(Xi) = adj(C, Xi) 7: end for 8: repeat 9: Select a (new) ordered pair of vertices (Xi, Xj ) that are adjacent in C and satisfy|adj(C, Xi) \ {Xj}| ≥ l , using order(V); 10: repeat 11: Choose a (new) set S ⊆ adj(C, Xi) \ {Xj} with |S| = l , using order(V); 12: if Xi and Xj are conditionally independent given S then 13: Delete edge Xi − Xj from C; 14: Let sepset(Xi, Xj ) = sepset(Xj , Xi) = S; 15: end if 16: until Xi and Xj are no longer adjacent in C or all S ⊆ adj(C, Xi) \ {Xj} with|S| = l have been considered 17: until all ordered pairs of adjacent vertices (Xi, Xj ) in C with |adj(C, Xi) \ {Xj}| ≥ l have been considered 18: until all pairs of adjacent vertices (Xi, Xj ) in C satisfy |adj(C, Xi) \ {Xj}| ≤ l 19: return C, sepset.Refs: [1]Colombo D, Maathuis M H. Order-independent constraint-based causal structure learning[J]. J. Mach. Learn. Res., 2014, 15(1): 3741-3782. Hiton-PC介绍与 PC类似，Hiton-PC应用条件独立性测试来识别变量之间的关系，但一种完全不同的方法来减少条件独立性测试的数量： 使用优先级队列用于存储与目标变量关联的所有变量，按关联强度的降序排列。优先级队列中的变量是要添加到 PC 集中的候选者。PC集是从一个空集开始，逐步扩展的。对于 PC 集的每一次扩展，从队列中取出一个候选者并暂时包含在 PC 集中，然后根据条件独立的结果来确定该候选者是否保留在 PC 中。由于与目标具有更强关联的变量较先测试，因此可以更快地识别非因果变量。对于条件独立性测试，阈值 max~k~ 用于指定要进行的测试的最高顺序。这是可选的，但是设置后效率会大大提高。算法的输入包括一组预测变量和给定目标变量的数据集，以及两个参数，一个用于限制条件独立性检验的顺序，一个用于条件独立性检验的显着性水平。算法的输出是给定目标变量的父子集。 输入：D，一组预测变量 X = {X1,X2,…,Xm} 和目标变量 Z ； maxk：条件独立性检验的阶阈值；α：显着性水平条件独立性检验。 输出：PC，X 的子集，包含 Z 的父母和孩子。 伪代码如下： Algorithm 3.1: The HITON-PC algorithm let PC = Ø let OPEN contain all variables associated with Z, sorted in descending order of strength of associations.令 OPEN 包含与 Z 关联的所有变量，按关联强度的降序排序。 while OPEN ≠ Ø do remove the first variable X from OPEN 从OPEN中移除第一个元素 insert X to the end of PC 把OPEN中移除第一个元素插入PC尾端 for each S ⊆ PC \ {X} and |S| ≤ maxk do if X,Z are independent given S at significance level α α概率X⊥Z|S then remove X from PC end if end for end while for each variable X in PC do for each S ⊂ PC \ {X} and S 不属于 PC |
| CopyRight 2018-2019 实验室设备网 版权所有 |