Membership Testing in Markov Equivalence Classes via Independence Query Oracles
通过独立性查询预言机检验马尔可夫等价类成员资格AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要直接研究因果图的马尔可夫等价类检验及其与因果结构学习的关系。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
通过独立性查询预言机检验马尔可夫等价类成员资格
- 研究问题
- 给定一个马尔可夫等价类，如何利用条件独立性查询判断数据生成的因果图是否属于该类，所需查询次数由什么决定？
- 方法与思路
- 作者研究基于约束的成员资格检验，以给定等价类最大无向团的大小建立查询复杂度上下界，并给出相应算法。
- 材料陈述的贡献
- 摘要称，最坏情形的查询次数上下界均随最大团大小呈指数增长；在高入度、小团图中，检验可比学习节省指数级查询。
- 阅读关注点
- 应核对独立性预言机的准确性假设、等价类的输入表示、复杂度参数的定义，以及查询界与有限样本检验之间的关系。
- 阅读边界
- 这是 arXiv 预印本，同行评审及期刊接收未核实；摘要未说明带统计误差的独立性检验如何影响预言机模型下的保证。
原文摘要
Understanding causal relationships between variables is a fundamental problem with broad impact in numerous scientific fields. While extensive research has been dedicated to learning causal graphs from data, its complementary concept of testing causal relationships has remained largely unexplored. While learning involves the task of recovering the Markov equivalence class (MEC) of the underlying causal graph from observational data, the testing counterpart addresses the following critical question: Given a specific MEC and observational data from some causal graph, can we determine if the data-generating causal graph belongs to the given MEC? We explore constraint-based testing methods by establishing bounds on the required number of conditional independence tests. Our bounds are in terms of the size of the maximum undirected clique ($s$) of the given MEC. In the worst case, we show a lower bound of $\exp(Ω(s))$ independence tests. We then give an algorithm that resolves the task with $\exp(O(s))$ tests, matching our lower bound. Compared to the learning problem, where algorithms often use a number of independence tests that is exponential in the maximum in-degree, this shows that testing is relatively easier. In particular, it requires exponentially less independence tests in graphs featuring high in-degrees and small clique sizes. Additionally, using the DAG associahedron, we provide a geometric interpretation of testing versus learning and discuss how our testing result can aid learning.