Scholarlink

<p>Causal discovery from observational data is a fundamental challenge. Greedy search algorithms like Regression with Subsequent Independence Test (RESIT), commonly used for learning Additive Noise Models (ANMs), are susceptible to making irreversible errors, especially in high-variance contexts. Such settings can be caused by unmeasured confounders or by high statistical noise from finite samples. To address this, we introduce a novel generalization of RESIT that replaces its local, greedy search with a more robust beam search, framing the task as a path search on a state-space graph. Through extensive simulation experiments, we demonstrate that structural accuracy, measured by Structural Hamming Distance (SHD) and Structural Intervention Distance (SID), consistently improves as the beam width (<i>w</i>) increases. Crucially, we also show that this performance gain comes at a manageable, approximately linear increase in computational cost relative to <i>w</i>. Furthermore, our analysis across different sample sizes shows these gains are most statistically significant in intermediate regimes (<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n=250, 500\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>250</mn> <mo>,</mo> <mn>500</mn> </mrow> </math></EquationSource> </InlineEquation>). This suggests that at these sample sizes, the statistical noise is high enough to mislead the greedy search into a suboptimal ordering, an error our wider beam search corrects, while performance converges at large sample sizes (<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n=1000\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>1000</mn> </mrow> </math></EquationSource> </InlineEquation>). Our framework provides a practical, tunable algorithm that bridges the gap between fast but brittle local search methods and computationally infeasible global searches, thereby enhancing the reliability of causal discovery in complex, high-variance settings where such local errors are common.</p>

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

Causal discovery in Additive Noise Models using beam search

  • 期刊论文

  • 发表日期：

    2025年11月25日

查看全文
  • Hans Jarett J. Ong,
  • Brian Godwin S. Lim,
  • Renzo Roel P. Tan,
  • Kazushi Ikeda

摘要

Causal discovery from observational data is a fundamental challenge. Greedy search algorithms like Regression with Subsequent Independence Test (RESIT), commonly used for learning Additive Noise Models (ANMs), are susceptible to making irreversible errors, especially in high-variance contexts. Such settings can be caused by unmeasured confounders or by high statistical noise from finite samples. To address this, we introduce a novel generalization of RESIT that replaces its local, greedy search with a more robust beam search, framing the task as a path search on a state-space graph. Through extensive simulation experiments, we demonstrate that structural accuracy, measured by Structural Hamming Distance (SHD) and Structural Intervention Distance (SID), consistently improves as the beam width (w) increases. Crucially, we also show that this performance gain comes at a manageable, approximately linear increase in computational cost relative to w. Furthermore, our analysis across different sample sizes shows these gains are most statistically significant in intermediate regimes ( \(n=250, 500\) n = 250 , 500 ). This suggests that at these sample sizes, the statistical noise is high enough to mislead the greedy search into a suboptimal ordering, an error our wider beam search corrects, while performance converges at large sample sizes ( \(n=1000\) n = 1000 ). Our framework provides a practical, tunable algorithm that bridges the gap between fast but brittle local search methods and computationally infeasible global searches, thereby enhancing the reliability of causal discovery in complex, high-variance settings where such local errors are common.