提出新方法破解高阶依赖导致的因果推断难题
High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption
- 用k阶松弛替代经典忠实假设，捕捉变量间高阶关联
- 在真实与样本误差导致的违背下仍能准确发现马尔可夫毯
- 适合处理含异或等复杂关系的因果发现与特征选择任务
从数据中学习变量的图形马尔可夫毯（MB）在贝叶斯网络结构学习、马尔可夫随机场、因果发现和特征选择等领域有广泛应用。然而，现有方法普遍依赖忠实性假设——即分布中的条件独立性对应图结构中的分离。该假设可能被异或、奇偶性等高阶依赖关系破坏，且在有限样本下，统计误差甚至会引入真实分布中不存在的虚假依赖。为此，本文提出一种“k阶”忠实性假设松弛，可刻画k+2个变量间的奇偶性关系。进而设计了概念验证算法kOMB，利用该松弛进行马尔可夫毯发现。实验表明，kOMB能在真实及经验性违背忠实性的场景下有效恢复变量的马尔可夫毯。代码已开源：https://github.com/lklee9/k-order-Markov-blanket
原文摘要 · Abstract (English)
The problem of learning the graphical Markov blanket (MB) of a variable from data has applications in many areas such as structure learning for Bayesian networks and Markov random fields, causal discovery, and feature selection. However, a common assumption most methods make is that the conditional independencies in the distribution imply the same separation in the graphical structure -- also known as the faithfulness assumption. Unfortunately, this assumption can be violated by higher-order dependencies such as XOR and parity-type relations, and -- on finite samples -- by empirical violations that, in extreme cases, even induce spurious dependencies absent from the true distribution. Therefore, in this paper we propose a "k-order" relaxation of the faithfulness assumption that captures parity type relationships between k+2 variables. We then propose a proof of concept algorithm called k-order Markov blanket (kOMB) that uses this relaxation for MB discovery. Finally, we empirically show how kOMB can recover the MB of a variable under both true and empirical violations of faithfulness. Code available at: https://github.com/lklee9/k-order-Markov-blanket
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。