LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments

Ali Ahmaditeshnizi, Saber Salehkaleybar, Negar Kiyavash
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:125-133, 2020.

Abstract

The causal relationships among a set of random variables are commonly represented by a Directed Acyclic Graph (DAG), where there is a directed edge from variable $X$ to variable $Y$ if $X$ is a direct cause of $Y$. From the purely observational data, the true causal graph can be identified up to a Markov Equivalence Class (MEC), which is a set of DAGs with the same conditional independencies between the variables. The size of an MEC is a measure of complexity for recovering the true causal graph by performing interventions. We propose a method for efficient iteration over possible MECs given intervention results. We utilize the proposed method for computing MEC sizes and experiment design in active and passive learning settings. Compared to previous work for computing the size of MEC, our proposed algorithm reduces the time complexity by a factor of $O(n)$ for sparse graphs where $n$ is the number of variables in the system. Additionally, integrating our approach with dynamic programming, we design an optimal algorithm for passive experiment design. Experimental results show that our proposed algorithms for both computing the size of MEC and experiment design outperform the state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-ahmaditeshnizi20a, title = {{L}azy{I}ter: A Fast Algorithm for Counting {M}arkov Equivalent {DAG}s and Designing Experiments}, author = {Ahmaditeshnizi, Ali and Salehkaleybar, Saber and Kiyavash, Negar}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {125--133}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/ahmaditeshnizi20a/ahmaditeshnizi20a.pdf}, url = {https://proceedings.mlr.press/v119/ahmaditeshnizi20a.html}, abstract = {The causal relationships among a set of random variables are commonly represented by a Directed Acyclic Graph (DAG), where there is a directed edge from variable $X$ to variable $Y$ if $X$ is a direct cause of $Y$. From the purely observational data, the true causal graph can be identified up to a Markov Equivalence Class (MEC), which is a set of DAGs with the same conditional independencies between the variables. The size of an MEC is a measure of complexity for recovering the true causal graph by performing interventions. We propose a method for efficient iteration over possible MECs given intervention results. We utilize the proposed method for computing MEC sizes and experiment design in active and passive learning settings. Compared to previous work for computing the size of MEC, our proposed algorithm reduces the time complexity by a factor of $O(n)$ for sparse graphs where $n$ is the number of variables in the system. Additionally, integrating our approach with dynamic programming, we design an optimal algorithm for passive experiment design. Experimental results show that our proposed algorithms for both computing the size of MEC and experiment design outperform the state of the art.} }
Endnote
%0 Conference Paper %T LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments %A Ali Ahmaditeshnizi %A Saber Salehkaleybar %A Negar Kiyavash %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-ahmaditeshnizi20a %I PMLR %P 125--133 %U https://proceedings.mlr.press/v119/ahmaditeshnizi20a.html %V 119 %X The causal relationships among a set of random variables are commonly represented by a Directed Acyclic Graph (DAG), where there is a directed edge from variable $X$ to variable $Y$ if $X$ is a direct cause of $Y$. From the purely observational data, the true causal graph can be identified up to a Markov Equivalence Class (MEC), which is a set of DAGs with the same conditional independencies between the variables. The size of an MEC is a measure of complexity for recovering the true causal graph by performing interventions. We propose a method for efficient iteration over possible MECs given intervention results. We utilize the proposed method for computing MEC sizes and experiment design in active and passive learning settings. Compared to previous work for computing the size of MEC, our proposed algorithm reduces the time complexity by a factor of $O(n)$ for sparse graphs where $n$ is the number of variables in the system. Additionally, integrating our approach with dynamic programming, we design an optimal algorithm for passive experiment design. Experimental results show that our proposed algorithms for both computing the size of MEC and experiment design outperform the state of the art.
APA
Ahmaditeshnizi, A., Salehkaleybar, S. & Kiyavash, N.. (2020). LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:125-133 Available from https://proceedings.mlr.press/v119/ahmaditeshnizi20a.html.

Related Material