Efficient interventional distribution learning in the PAC framework

Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Vedant Raval, Vinodchandran N. Variyam
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:7531-7549, 2022.

Abstract

We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let P be a causal model on a set V of observable variables on a given causal graph G. For sets $X,Y \subseteq V$, and setting x to $X$, $P_x(Y)$ denotes the interventional distribution on Y with respect to an intervention x to variables X. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), proved that the ID algorithm is sound and complete for recovering P_x(Y) from observations. We give the first provably efficient version of the ID algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph G on observable variables V, a setting x of a set $X \subseteq V$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is epsilon-close (in total variation distance) to $P_x(Y)$ where $Y = V X$, if $P_x(Y)$ is identifiable. We also show that when Y is an arbitrary subset of $V X$, there is no efficient algorithm that outputs an evaluator of a distribution that is epsilon-close to $P_x(Y)$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-bhattacharyya22a, title = { Efficient interventional distribution learning in the PAC framework }, author = {Bhattacharyya, Arnab and Gayen, Sutanu and Kandasamy, Saravanan and Raval, Vedant and Variyam, Vinodchandran N.}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {7531--7549}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/bhattacharyya22a/bhattacharyya22a.pdf}, url = {https://proceedings.mlr.press/v151/bhattacharyya22a.html}, abstract = { We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let P be a causal model on a set V of observable variables on a given causal graph G. For sets $X,Y \subseteq V$, and setting x to $X$, $P_x(Y)$ denotes the interventional distribution on Y with respect to an intervention x to variables X. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), proved that the ID algorithm is sound and complete for recovering P_x(Y) from observations. We give the first provably efficient version of the ID algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph G on observable variables V, a setting x of a set $X \subseteq V$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is epsilon-close (in total variation distance) to $P_x(Y)$ where $Y = V X$, if $P_x(Y)$ is identifiable. We also show that when Y is an arbitrary subset of $V X$, there is no efficient algorithm that outputs an evaluator of a distribution that is epsilon-close to $P_x(Y)$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms. } }
Endnote
%0 Conference Paper %T Efficient interventional distribution learning in the PAC framework %A Arnab Bhattacharyya %A Sutanu Gayen %A Saravanan Kandasamy %A Vedant Raval %A Vinodchandran N. Variyam %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-bhattacharyya22a %I PMLR %P 7531--7549 %U https://proceedings.mlr.press/v151/bhattacharyya22a.html %V 151 %X We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let P be a causal model on a set V of observable variables on a given causal graph G. For sets $X,Y \subseteq V$, and setting x to $X$, $P_x(Y)$ denotes the interventional distribution on Y with respect to an intervention x to variables X. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), proved that the ID algorithm is sound and complete for recovering P_x(Y) from observations. We give the first provably efficient version of the ID algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph G on observable variables V, a setting x of a set $X \subseteq V$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is epsilon-close (in total variation distance) to $P_x(Y)$ where $Y = V X$, if $P_x(Y)$ is identifiable. We also show that when Y is an arbitrary subset of $V X$, there is no efficient algorithm that outputs an evaluator of a distribution that is epsilon-close to $P_x(Y)$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.
APA
Bhattacharyya, A., Gayen, S., Kandasamy, S., Raval, V. & Variyam, V.N.. (2022). Efficient interventional distribution learning in the PAC framework . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:7531-7549 Available from https://proceedings.mlr.press/v151/bhattacharyya22a.html.

Related Material