提出新算法，高效验证含隐变量因果模型的独立性关系
Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies
- 基于c-组件局部马尔可夫性质，压缩复杂度
- 首次实现隐变量模型下条件独立性的多项式延迟生成
- 适合需要快速验证复杂因果结构的研究者
在观测数据中检验假设的因果模型是因果推断的关键前提。传统方法需验证模型假设的大量条件独立关系（CIs），但数量可能指数级增长，不切实际。因果图通过局部马尔可夫性质将这些关系压缩至多项式空间，从而只需测试少量关键约束。然而，现有算法在存在隐变量和非参数分布时，生成单个约束即需指数时间。本文提出针对含隐变量因果图的c-组件局部马尔可夫性质（C-LMP），并设计首个多项式延迟算法，可在多项式间隔内生成所有相关条件独立性约束。该算法支持任意数据分布，且实验表明在真实与合成数据上均具实用性。这是首次实现隐变量模型下条件独立性测试的多项式延迟算法。
原文摘要 · Abstract (English)
Testing a hypothesized causal model against observational data is a key prerequisite for many causal inference tasks. A natural approach is to test whether the conditional independence relations (CIs) assumed in the model hold in the data. While a model can assume exponentially many CIs (with respect to the number of variables), testing all of them is both impractical and unnecessary. Causal graphs, which encode these CIs in polynomial space, give rise to local Markov properties that enable model testing with a significantly smaller subset of CIs. Model testing based on local properties requires an algorithm to list the relevant CIs. However, existing algorithms for realistic settings with hidden variables and non-parametric distributions can take exponential time to produce even a single CI constraint. In this paper, we introduce the c-component local Markov property (C-LMP) for causal graphs with hidden variables. Since C-LMP can still invoke an exponential number of CIs, we develop a polynomial delay algorithm to list these CIs in poly-time intervals. To our knowledge, this is the first algorithm that enables poly-delay testing of CIs in causal graphs with hidden variables against arbitrary data distributions. Experiments on real-world and synthetic data demonstrate the practicality of our algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。