基于递归分解的因果结构学习算法  

Causal Structure Learning Algorithm Based on Recursive Decomposition

作　　者：蔡瑞初[1] 张文辉 乔杰 郝志峰[1,2] CAI Ruichu;ZHANG Wenhui;QIAO Jie;HAO Zhifeng(School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China;College of Science,Shantou University,Shantou 515063,Guangdong,China)

机构地区：[1]广东工业大学计算机学院,广州510006 [2]汕头大学理学院,广东汕头515063

出　　处：《计算机工程》2023年第3期87-94,共8页Computer Engineering

基　　金：国家优秀青年科学基金(6212200101);国家自然科学基金(61876043,61976052)。

摘　　要：在高维小样本场景下,针对现有基于约束的因果结构学习方法存在因果结构学习效率低、马尔可夫等价类的问题,以非线性非高斯的高维小样本为研究对象,提出一种基于递归分解的因果结构学习算法CADR。在高维小样本的因果结构学习效率方面,结合递归分解的思想,将高维变量集递归分解为多个更小的子集,直到无法再分解或子集的大小达到阈值为止。在该过程中,变量集的减少缩减了条件独立性检验的条件候选集的搜索空间,从而提高学习效率。同时,为进一步识别马尔可夫等价类,根据非线性非高斯模型的因果方向的不可逆性,通过判断拟合噪声项与原因变量是否独立来识别马尔可夫等价类的因果方向。在仿真数据和真实因果结构数据上的实验结果表明,CADR不仅提高条件独立性检验的效率,而且能有效地区分马尔可夫等价类,学习到更精确的因果结构,其中,在真实因果结构实验中,与现有Xie_rec、PC_ANM和Notear_Sob方法相比,F1评分提高5%~12%。In the case of high-dimensional small samples,owing to the problems of low efficiency and Markov equivalence class in the existing constraint-based causal structure learning methods,a causal structure learning algorithm,CADR,based on recursive decomposition,is proposed for nonlinear non-Gaussian high-dimensional small samples.When the learning efficiency of the causal structure of high-dimensional small samples is combined with the idea of recursive decomposition,the high-dimensional variable set is recursively decomposed into multiple smaller subsets exhaustively or until the subset size reaches a threshold.The reduced variable set reduces the search space of the conditional candidate set for the conditional independence test,thus improving the learning efficiency.Moreover,to identify the Markov equivalence class further,according to the irreversibility of the causal direction of the nonlinear nonGaussian model,identify the causal direction of the Markov equivalence class by determining whether the fitting noise item is independent of the causal variable.The experimental results of simulation and real causal structure data indicate that CADR improves the efficiency of the conditional independence test and can effectively distinguish Markov equivalence classes and learn an accurate causal structure.In the real causal structure experiment,the F1 score increased by 5%-12%when the existing Xie_rec,PC_ANM,and Notear_Sob method are compared with the proposed method.

关 键 词：因果关系发现 条件独立性检验 高维小样本 递归分解 马尔可夫等价类 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]