Scholarlink

<p>The problem of learning causal directed acyclic graphs (DAGs) has attracted considerable attention. The Peter-Clark (PC) algorithm (Spirtes et al. Causation, Prediction, and Search, MIT Press, Cambridge, 2001), which relies solely on faithfulness and Markov assumptions, can identify a causal DAG up to its Markov equivalence class (MEC). In contrast, the linear non-Gaussian acyclic model (LiNGAM) (Shimizu et al. in J Mach Learn Res 7:2003–2030, 2006) achieves the full identifiability of edge orientations in a causal DAG by additionally assuming linearity and continuous non-Gaussian disturbances for the causal model. By combining the strength of the PC algorithm, namely, not requiring any specification of exogenous disturbances, with that of LiNGAM in orienting causal edges, the PC-LiNGAM (Hoyer et al. in: Proceedings of the twenty-fourth conference on uncertainty in artificial intelligence, UAI2008, 2008) can identify a causal DAG up to its distribution-equivalence pattern (DEP), even in the presence of Gaussian disturbances. However, in the worst case, the PC-LiNGAM suffers from <i>O</i>(<i>p</i>!) time complexity, where <i>p</i> is the number of variables, making it impractical for high-dimensional settings. In this paper, we propose an algorithm for learning the DEP of a linear causal model with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(p^{3})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time complexity, which is much lower than that of PC-LiNGAM. The proposed method builds on the causal ancestor-finding algorithm in Maeda and Shimizu (in: Proceedings of the twenty third international conference on artificial intelligence and statistics, 2020), (Int. J. Data Sci. Anal. 13:77–89, 2022) and Maeda (Behaviormetrika 49:329–341, 2022), extending it to accommodate Gaussian disturbances. Through detailed computer experiments and real-data applications, we confirm that the proposed method retains accuracy comparable to existing methods while achieving lower computational cost.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Learning linear acyclic causal model containing Gaussian disturbances using ancestral relationships

  • 期刊论文

  • 发表日期：

    2026年5月6日

查看全文
  • Ming Cai,
  • Penggang Gao,
  • Hisayuki Hara

摘要

The problem of learning causal directed acyclic graphs (DAGs) has attracted considerable attention. The Peter-Clark (PC) algorithm (Spirtes et al. Causation, Prediction, and Search, MIT Press, Cambridge, 2001), which relies solely on faithfulness and Markov assumptions, can identify a causal DAG up to its Markov equivalence class (MEC). In contrast, the linear non-Gaussian acyclic model (LiNGAM) (Shimizu et al. in J Mach Learn Res 7:2003–2030, 2006) achieves the full identifiability of edge orientations in a causal DAG by additionally assuming linearity and continuous non-Gaussian disturbances for the causal model. By combining the strength of the PC algorithm, namely, not requiring any specification of exogenous disturbances, with that of LiNGAM in orienting causal edges, the PC-LiNGAM (Hoyer et al. in: Proceedings of the twenty-fourth conference on uncertainty in artificial intelligence, UAI2008, 2008) can identify a causal DAG up to its distribution-equivalence pattern (DEP), even in the presence of Gaussian disturbances. However, in the worst case, the PC-LiNGAM suffers from O(p!) time complexity, where p is the number of variables, making it impractical for high-dimensional settings. In this paper, we propose an algorithm for learning the DEP of a linear causal model with \(O(p^{3})\) O ( p 3 ) time complexity, which is much lower than that of PC-LiNGAM. The proposed method builds on the causal ancestor-finding algorithm in Maeda and Shimizu (in: Proceedings of the twenty third international conference on artificial intelligence and statistics, 2020), (Int. J. Data Sci. Anal. 13:77–89, 2022) and Maeda (Behaviormetrika 49:329–341, 2022), extending it to accommodate Gaussian disturbances. Through detailed computer experiments and real-data applications, we confirm that the proposed method retains accuracy comparable to existing methods while achieving lower computational cost.