Causal Discovery Algorithm Based on Non-stationary Additive Noise Model

doi:10.19678/j.issn.1000-3428.0066901

Abstract

Abstract: Causal discovery aims to mine the causal relationship between variables through observed data. Most existing methods assume that the data-generation process is stationary. However, this assumption is often not satisfied in the application environments, leading to unreliable results. This study reveals that non-stationary disturbances in some scenes are highly correlated with time-series information. Therefore, based on the additive noise model, the method portrays non-stationary disturbances as a mapping of time series information and proposes a non-stationary additive noise model and its identification conditions. This study proposes a two-stage causality discovery algorithm based on identification conditions. Specifically, residuals are obtained through regression analysis and are used to evaluate the independence of selecting a leaf node in the initial phase of the algorithm. The causal order of the observed variable sets is thereafter obtained iteratively until all the variables have been included. In the second phase of the algorithm, regression analysis and independence tests are performed again to eliminate redundant causal relationships identified in the first stage, which helps to obtain the final causal structure of the observed variable set. Experimental results demonstrate that the proposed algorithm outperforms other algorithms such as Constraint-based causal Discovery heterogeneous/Non-stationary Data (CD-NOD), LPCMCI, and TiMINo. For the synthetic datasets, the proposed algorithm achieves an average F1 value of 0.85. In real-world structural datasets, the F1 value of the proposed algorithm increases by an average of 41.12%, signifying that the algorithm can learn more information about the causal structure from a dataset of non-stationary variables.

Key words: causal discovery, causal structure, non-stationary disturbances, additive noise model, functional causal model

摘要： 因果发现旨在通过观测数据挖掘变量间的因果关系。现有的因果发现方法大多假定数据的产生过程是平稳的,然而在实际环境下往往不满足稳态假设,导致结果不可靠。研究发现,在一些场景中的非稳态扰动与时序信息高度相关。因此,在加性噪声模型基础上将非稳态扰动刻画为一项关于时序信息的函数,设计非稳态加性噪声模型,并给出非稳态加性噪声模型的识别条件,提出一种两阶段的因果关系学习算法。第1阶段利用回归计算得到变量残差,再检验残差与回归特征集的独立性从而选出叶子节点,迭代得到观测变量集的因果次序;第2阶段再次进行回归计算和独立性检验,消除第1阶段中冗余的因果关系,从而得到观测变量集的因果结构。实验结果表明,与基于约束的异构/非平稳因果发现、LPCMCI和TiMINo算法相比,该算法在仿真数据集上取得了最优的效果,平均F1值达到0.85;而在真实因果结构数据集中,该算法的F1值平均提升41.12%,能够从非稳态数据集中恢复出更多因果结构的信息。

关键词: 因果发现, 因果结构, 非稳态扰动, 加性噪声模型, 函数式因果模型

CLC Number:

TP301.6

HAO Zhifeng, DING Kaipei, CAI Ruichu, CHEN Wei. Causal Discovery Algorithm Based on Non-stationary Additive Noise Model[J]. Computer Engineering, 2024, 50(4): 78-86.

郝志峰, 丁凯培, 蔡瑞初, 陈薇. 基于非稳态加性噪声模型的因果发现算法[J]. 计算机工程, 2024, 50(4): 78-86.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0066901

https://www.ecice06.com/EN/Y2024/V50/I4/78

References

[1] WANG L J, ADIGA A, CHEN J Z, et al. CausalGNN:causal-based graph neural networks for spatio-temporal epidemic forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence.[S.1.]:AAAI Press, 2022:12191-12199.
[2] ZHANG H, YAN C X, XIA Y W, et al. Causal gene identification using non-linear regression-based independence tests[J]. ACM Transactions on Computational Biology and Bioinformatics, 2022, 20:185-195.
[3] 姚宏亮, 马晓琴, 王浩, 等. 基于形态特征与因果岭回归的股市态势预测算法[J]. 计算机工程, 2016, 42(2):175-183. YAO H L, MA X Q, WANG H, et al. Stock market trend prediction algorithm based on morphological characteristics and causal ridge regression[J]. Computer Engineering, 2016, 42(2):175-183.(in Chinese)
[4] CAI R C, ZHANG Z J, HAO Z F, et al. Understanding social causalities behind human action sequences[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(8):1801-1813.
[5] CHEN W, CAI R C, HAO Z F, et al. Mining hidden non-redundant causal relationships in online social networks[J]. Neural Computing and Applications, 2020, 32(11):6913-6923.
[6] ERNÁN M A, ROBINS J M. Causal inference[M]. Boca Raton, USA:CRC Press, 2010.
[7] RUNGE J, NOWACK P, KRETSCHMER M, et al. Detecting and quantifying causal associations in large nonlinear time series datasets[J]. Science Advances, 2019, 5(11):4996.
[8] RUNGE J. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets[EB/OL].[2023-01-05]. http://arxiv.org/abs/2003.03685v1.
[9] GERHARDUS A, RUNGE J. High-recall causal discovery for autocorrelated time series with latent confounders[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems. New York, USA:ACM Press, 2020:12615-12625.
[10] PETERS J, JANZING D, SCHÖLKOPF B. Causal inference on time series using restricted structural equation models[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems. New York, USA:ACM Press, 2013:154-162.
[11] HYVÄRINEN A, SHIMIZU S, HOYER P O. Causal modelling combining instantaneous and lagged effects:an identifiable model based on non-Gaussian[C]//Proceedings of the 25th International Conference on Machine learning. New York, USA:ACM Press, 2008:424-431.
[12] HUANG B W, ZHANG K, ZHANG J J, et al. Causal discovery from heterogeneous/nonstationary data[EB/OL].[2023-01-05]. http://arxiv.org/abs/1903.01672v5.
[13] 蔡瑞初, 陈薇, 张坤, 等. 基于非时序观察数据的因果关系发现综述[J]. 计算机学报, 2017, 40(6):1470-1490. CAI R C, CHEN W, ZHANG K, et al. A survey on non-temporal series observational data based causal discovery[J]. Chinese Journal of Computers, 2017, 40(6):1470-1490.(in Chinese)
[14] SPIRTES P, GLYMOUR C, SCHEINES R. Causation, prediction, and search[M].[S. 1.]:The MIT Press, 2001.
[15] VERMA T S, PEARL J. Equivalence and synthesis of causal models[C]//Proceedings of the 6th Annual Conference on Uncertainty in Artificial Intelligence. New York, USA:ACM Press, 2022:221-236.
[16] OYER P, JANZING D, MOOIJ J M, et al. Nonlinear causal discovery with additive noise models[C]//Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. New York, USA:ACM Press, 2008:689-696.
[17] SHIMIZU S, HOYER P O, HYVÄRINEN A, et al. A linear non-Gaussian acyclic model for causal discovery[J]. Journal of Machine Learning Research, 2006, 7:2003-2030.
[18] HANG K, HYVARINEN A. On the identifiability of the post-nonlinear causal model[C]//Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence.[S.1.]:AUAI Press, 2009:647-655.
[19] PETERS J, MOOIJ J M, JANZING D, et al. Causal discovery with continuous additive noise models[J]. Journal of Machine Learning Research, 2014, 15:2009-2053.
[20] ETERS J, MOOIJ J M, JANZING D, et al. Identifiability of Causal Graphs Using Functional Models[EB/OL].[2023-01-05]. https://export.arxiv.org/ftp/arxiv/papers/1202/1202.3757.pdf.
[21] GRETTON A, HERBRICH R, SMOLA A, et al. Kernel methods for measuring independence[J]. Journal of Machine Learning Research, 2005, 6:2075-2129.
[22] GRETTON A, FUKUMIZU K, TEO C H, et al. A kernel statistical test of independence[C]//Proceedings of 2007 Conference on Advances in Neural Information Processing Systems. Cambridge, USA:MIT Press,2008:585-592.
[23] SUN J, TAYLOR D, BOLLT E M. Causal network inference by optimal causation entropy[J]. SIAM Journal on Applied Dynamical Systems, 2015, 14(1):73-106.
[24] HANG K, PETERS J, JANZING D, et al. Kernel-based conditional independence test and application in causal discovery[EB/OL].[2023-01-05]. https://arxiv.org/ftp/arxiv/papers/1202/1202.3775.pdf.
[25] EICHENBACK H. The direction of time[M].[M. 1.]:Dover Publications Inc., 1989.
[26] BABA K, SHIBATA R, SIBUYA M. Partial correlation and conditional correlation as measures of conditional independence[J]. Australian & New Zealand Journal of Statistics, 2004, 46(4):657-664.

Please choose a citation manager

Content to export