Report

Using Markov Blankets for Causal Structure Learning Jean-Philippe Pellet Andre Ellisseeff Presented by Na Dai Motivation • Why structure learning? • What are Markov blankets? • Relationship between feature selection and Markov blankets? Previous work • Score-based approaches • Constraint-based approaches • Hybrid approaches Central Ideas • Building up local structures from Markov blankets. • Generating global graph structure from local structure. • How to generate Markov blankets? Background • Feature selection – Conditional independence – Strong relevance – Weak relevance – Irrelevance – Feature selection task Background • Causal structure learning – Goal: learn the full structure of the network – D-separation: 1) A --> C --> B 2) A <-- C <-- B 3) A <-- C --> B 4) A --> C <-- B Background • Perfect map • Causal Markov condition • Faithfulness condition Background • Causal sufficiency assumption • V-structure Causal Network Construction • Properties of Markov blankets Recovering Local Structure • Remove possible spouse links – Find d-separation set • Orient the arcs Algorithm 1 Example of Local Causal Structure Potential Improvements • Two passes becomes one pass – Combine spouse link detection and edge orientation. • If can find S to make X and Y conditionally independent, then X and Y are spouse. • If Z \in Mb(X) and Mb(Y) is not in S is a mutual child, the direction between X, Y, Z is determined. • Transform the problem to identify dseparation set. Algorithm 2 Generic Algorithm based on Feature Selection • Find the conjectured Markov blanket of each variable with feature selection. • Build the moral graph. • Remove spouse links and orient V-structure. • Propagate orientation constraints. Algorithm 3 Algorithm 4 Algorithms for Causal Feature Selection • RFE based approach • TC and TCbw algorithm Conclusion • Causal discovery is close to feature selection • Three steps to build up the causal structure from Markov blankets. More efficient, and even better than previous methods.