An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models

Ilya Shpitser, Thomas S. Richardson, James M. Robins
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:732-741, 2011.

Abstract

Probabilistic inference in graphical models is the task of computing marginal and conditional densities of interest from a factorized representation of a joint probability distribution. Inference algorithms such as variable elimination and belief propagation take advantage of constraints embedded in this factorization to compute such densities efficiently. In this paper, we propose an algorithm which computes interventional distributions in latent variable causal models represented by acyclic directed mixed graphs(ADMGs). To compute these distributions efficiently, we take advantage of a recursive factorization which generalizes the usual Markov factorization for DAGs and the more recent factorization for ADMGs. Our algorithm can be viewed as a generalization of variable elimination to the mixed graph case. We show our algorithm is exponential in the mixed graph generalization of treewidth.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-shpitser11a, title = {An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models}, author = {Shpitser, Ilya and Richardson, Thomas S. and Robins, James M.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {732--741}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/shpitser11a/shpitser11a.pdf}, url = {https://proceedings.mlr.press/r9/shpitser11a.html}, abstract = {Probabilistic inference in graphical models is the task of computing marginal and conditional densities of interest from a factorized representation of a joint probability distribution. Inference algorithms such as variable elimination and belief propagation take advantage of constraints embedded in this factorization to compute such densities efficiently. In this paper, we propose an algorithm which computes interventional distributions in latent variable causal models represented by acyclic directed mixed graphs(ADMGs). To compute these distributions efficiently, we take advantage of a recursive factorization which generalizes the usual Markov factorization for DAGs and the more recent factorization for ADMGs. Our algorithm can be viewed as a generalization of variable elimination to the mixed graph case. We show our algorithm is exponential in the mixed graph generalization of treewidth.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models %A Ilya Shpitser %A Thomas S. Richardson %A James M. Robins %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-shpitser11a %I PMLR %P 732--741 %U https://proceedings.mlr.press/r9/shpitser11a.html %V R9 %X Probabilistic inference in graphical models is the task of computing marginal and conditional densities of interest from a factorized representation of a joint probability distribution. Inference algorithms such as variable elimination and belief propagation take advantage of constraints embedded in this factorization to compute such densities efficiently. In this paper, we propose an algorithm which computes interventional distributions in latent variable causal models represented by acyclic directed mixed graphs(ADMGs). To compute these distributions efficiently, we take advantage of a recursive factorization which generalizes the usual Markov factorization for DAGs and the more recent factorization for ADMGs. Our algorithm can be viewed as a generalization of variable elimination to the mixed graph case. We show our algorithm is exponential in the mixed graph generalization of treewidth. %Z Reissued by PMLR on 04 October 2026.
APA
Shpitser, I., Richardson, T.S. & Robins, J.M.. (2011). An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:732-741 Available from https://proceedings.mlr.press/r9/shpitser11a.html. Reissued by PMLR on 04 October 2026.

Related Material