Hybrid Local Causal Structure Learning

doi:10.3778/j.issn.1673-9418.2005041

Abstract

Abstract:

Local causal structure learning focuses on identifying the direct causes and direct effects of a given target variable without learning an entire causal network. Existing local causal structure learning algorithms are usually completed by two steps. Step 1 uses constraint-based methods to learn the Markov blanket (MB) or parents and children (PC) set of the target variable by conditional independence tests. However, due to small sample sizes, this may lead to unreliable tests and the accuracy of this step is usually not very high. Step 2 uses found V structures and Meek rules for distinguishing direct causes from direct effects of the target variable. But this step depends on the discovery of V structure extremely and synchronous sampling is also affected by limited samples. The accuracy of the algorithm is not very high. To solve the above problems, this paper proposes a hybrid local causal structure learning algorithm based on the combination of scoring and constraint. In step 1, a new PC learning algorithm SIAPC (score-based incremental association parents and children) is proposed by adding scoring idea into the constraint based algorithm. In step 2, the direction of the edge is determined by using the intersection of the orientation result obtained by PC algorithm and the orientation result obtained by grading some data sets, so as to reduce the dependence on V structure and alleviate the finite sample problem. After that, this paper uses independence test to modify the orientation results of the edges to further improve the accuracy of the algorithm, and then proposes HLCS (hybrid local causal structure learning) algorithm. Using benchmark Bayesian networks, the experimental results show that the algorithm proposed in this paper has better performance than the existing algorithms in terms of learning accuracy and reducing the data efficiency.

Key words: Bayesian network, local causal structure learning, Markov blanket (MB), V-structure

摘要：

局部因果结构学习是发现和学习给定一个目标变量的直接原因和直接结果而无需学习一个完整因果网络的过程。目前已有算法通常由两个步骤完成：步骤1使用约束类算法利用独立性测试学习目标变量的马尔科夫毯（MB）或父子节点集（PC），但是该步骤由于受到有限的数据样本量等因素影响使得独立性测试存在一定的错误性，而导致该步骤精度通常不是很高；步骤2利用V结构及Meek规则来进行边的定向，但是该步骤由于极其依赖于V结构的发现且同样受到有限样本的影响，使得算法精度相对不是很高。基于上述问题，提出利用打分和限制相结合的混合方式来缓减有限样本问题且提高算法精度。步骤1通过在基于限制的算法中加入打分思想来提高数据有效性，进而提出SIAPC算法；步骤2通过利用PC算法得到的定向结果和对部分数据集打分得到的定向结果的交集来确定边的方向，以此来降低对V结构的依赖性且缓减有限样本问题，之后使用独立性测试修正边的定向结果来进一步提高算法精度，进而提出HLCS算法。在标准贝叶斯网络上，实验验证了该算法相对于已有算法在精度方面具有更好的性能且能够有效缓减数据效率问题。

关键词: 贝叶斯网络, 局部因果结构学习, 马尔科夫毯（MB）, V结构

WANG Yunxia, CAO Fuyuan, LING Zhaolong. Hybrid Local Causal Structure Learning[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 754-765.

王雲霞, 曹付元, 凌兆龙. 混合局部因果结构学习[J]. 计算机科学与探索, 2021, 15(4): 754-765.

References

[1] YU K, LIU L, LI J Y, et al. Multi-source causal feature selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42(9): 2240-2256.
[2] YU K, LIU L, LI J Y. Discovering Markov blanket from multiple interventional datasets[J]. arXiv:1801.08295, 2018.
[3] YU K, WU X D, DING W, et al. Markov blanket feature selection using representative sets[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(11): 2775-2788.
[4] BEYAZIT E, ALAGURAJAH J, WU X D. Online learning from data streams with varying feature spaces[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, Honolulu, Jan 27-Feb 1, 2019. Menlo Park: AAAI, 2019: 3232-3239.
[5] PEARL J, MACKENZIE D. The book of why: the new science of cause and effect[M]. New York: Basic Books, 2018.
[6] SCH?LKOPF B. Causality for machine learning[J]. arXiv:1911.10500, 2019.
[7] SPIRTES P, GLYMOUR C, SCHEINES R. Causation, prediction, and search[M]. Cambridge: MIT Press, 2000.
[8] COLOMBO D, MAATHUIS M H, KALISCH M, et al. Learning high-dimensional directed acyclic graphs with latent and selection variables[J]. The Annals of Statistics, 2012, 40(1): 294-321.
[9] SILVERSTEIN C, BRIN S, MOTWANI R, et al. Scalable techniques for mining causal structures[J]. Data Mining and Knowledge Discovery, 2000, 4(2/3): 163-192.
[10] MANI S, COOPER G F. Causal discovery using a Bayesian local causal discovery algorithm[C]//Proceedings of the 11th World Congress on Medical Informatics, San Francisco, Sep 7-11, 2004. Amsterdam: IOS Press, 2004: 731-735.
[11] YIN J X, ZHOU Y, WANG C Z, et al. Partial orientation and local structural learning of causal networks for prediction [C]//Proceedings of the Causation and Prediction Challenge at WCCI 2008, Hong Kong, China, Jun 1-6, 2008: 93-105.
[12] GAO T, JI Q. Efficient Markov blanket discovery and its application[J]. IEEE Transactions on Cybernetics, 2017, 47(5): 1169-1179.
[13] GAO T, JI Q. Local causal discovery of direct causes and effects[C]//Proceedings of the Annual Conference on Neural Information Processing Systems, Montreal, Dec 7-12, 2015. Red Hook: Curran Associates, 2015: 2512-2520.
[14] TSAMARDINOS I, BROWN L E, Aliferis C F. The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65(1): 31-78.
[15] TSAMARDINOS I, ALIFERIS C F, Statnikov A R. Algorithms for large scale Markov blanket discovery[C]//Proceedings of the 16th International Florida Artificial Intelligence Research Society Conference, St. Augustine, May 12-14, 2003. Menlo Park: AAAI, 2003: 376-381.
[16] BORBOUDAKIS G, TSAMARDINOS I. Forward-backward selection with early dropping[J]. Journal of Machine Learning Research, 2019, 20: 8.
[17] GAO T, JI Q. Efficient score-based Markov blanket discovery[J]. International Journal of Approximate Reasoning, 2017, 80: 277-293.
[18] ALIFERIS C F, STATNIKOV A R, TSAMARDINOS I, et al. Local causal and Markov blanket induction for causal discovery and feature selection for classification part II: analysis and extensions[J]. Machine Learning Research, 2010, 11: 235-284.
[19] YU K, LIU L, LI J, et al. Mining Markov blankets without causal sufficiency[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(12): 6333-6347.
[20] WANG H, LING Z L, YU K, et al. Towards efficient and effective discovery of Markov blankets for feature selection[J]. Information Sciences, 2019, 509: 227-242.
[21] YU K, LIU L, LI J. A unified view of causal and non-causal feature selection[J]. arXiv:1802.05844v4, 2018.