提出新算法求解因果模型中不可完全识别查询的概率边界。
Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models
- 利用输入的可观测变量概率简化多线性/线性规划构建。
- 单干预场景下用列生成法实现多项式规模表示，计算概率边界。
- 适合研究因果推断中不确定因素影响的学者使用。
我们研究一类因果模型中的部分可识别查询问题。聚焦于无环结构因果模型（即每个内生变量至多与一个外生混杂因子相连）的情形。当内生变量可观测且其分布已知，而外生变量未完全指定时，模型本质上表现为贝叶斯网络，其中根节点分布不唯一确定。在此情况下，可能无法精确计算目标概率值。因此我们研究紧致概率边界计算问题：一般情况下由多线性规划解决，单个混杂组件被干预时可用线性规划解决。本文提出新算法，通过利用可观测内生变量的概率来简化此类规划的构造。在单干预场景下，采用列生成技术，通过一系列辅助整数线性规划迭代求解概率边界，证明了外生变量可表示为多项式规模。实验表明，该方法优于现有技术。
原文摘要 · Abstract (English)
We investigate partially identifiable queries in a class of causal models. We focus on acyclic Structural Causal Models that are quasi-Markovian (that is, each endogenous variable is connected with at most one exogenous confounder). We look into scenarios where endogenous variables are observed (and a distribution over them is known), while exogenous variables are not fully specified. This leads to a representation that is in essence a Bayesian network where the distribution of root variables is not uniquely determined. In such circumstances, it may not be possible to precisely compute a probability value of interest. We thus study the computation of tight probability bounds, a problem that has been solved by multilinear programming in general, and by linear programming when a single confounded component is intervened upon. We present a new algorithm to simplify the construction of such programs by exploiting input probabilities over endogenous variables. For scenarios with a single intervention, we apply column generation to compute a probability bound through a sequence of auxiliary linear integer programs, thus showing that a representation with polynomial cardinality for exogenous variables is possible. Experiments show column generation techniques to be superior to existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。