揭示了因果发现中等价类规模的下界，说明放松假设后学习受限
Lower Bounds on the Size of Markov Equivalence Classes
- 在三种图模型中证明等价类大小呈指数级下界
- 当放宽无环、充分性等假设时，平均等价类规模极大增长
- 适合研究因果推断理论边界的研究者阅读
因果发现算法通常只能在不加额外参数假设的情况下恢复因果图的马尔可夫等价类。这些等价类的大小反映了仅从观测数据中能学到的因果结构上限。在无环性、因果充分性和均匀先验假设下，马尔可夫等价类平均较小。本文表明，一旦放宽任一假设，情况即不再成立。具体地，我们证明了在三种情形下：稀疏随机有向无环图、均匀随机有向无环混合图、以及均匀随机有向环图中，马尔可夫等价类的期望大小具有指数级下界。
原文摘要 · Abstract (English)
Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。