Greedy relaxations of the sparsest permutation algorithm

Wai-Yin Lam, Bryan Andrews, Joseph Ramsey
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:1052-1062, 2022.

Abstract

There has been an increasing interest in methods that exploit permutation reasoning to search for directed acyclic causal models, including the “Ordering Search’’ of Teyssier and Kohler and GSP of Solus, Wang and Uhler. We extend the methods of the latter by a permutation-based operation tuck, and develop a class of algorithms, namely GRaSP, that are computationally efficient and pointwise consistent under increasingly weaker assumptions than faithfulness. The most relaxed form of GRaSP outperforms many state-of-the-art causal search algorithms in simulation, allowing efficient and accurate search even for dense graphs and graphs with more than 100 variables.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-lam22a, title = {Greedy relaxations of the sparsest permutation algorithm}, author = {Lam, Wai-Yin and Andrews, Bryan and Ramsey, Joseph}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {1052--1062}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/lam22a/lam22a.pdf}, url = {https://proceedings.mlr.press/v180/lam22a.html}, abstract = {There has been an increasing interest in methods that exploit permutation reasoning to search for directed acyclic causal models, including the “Ordering Search’’ of Teyssier and Kohler and GSP of Solus, Wang and Uhler. We extend the methods of the latter by a permutation-based operation tuck, and develop a class of algorithms, namely GRaSP, that are computationally efficient and pointwise consistent under increasingly weaker assumptions than faithfulness. The most relaxed form of GRaSP outperforms many state-of-the-art causal search algorithms in simulation, allowing efficient and accurate search even for dense graphs and graphs with more than 100 variables.} }
Endnote
%0 Conference Paper %T Greedy relaxations of the sparsest permutation algorithm %A Wai-Yin Lam %A Bryan Andrews %A Joseph Ramsey %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-lam22a %I PMLR %P 1052--1062 %U https://proceedings.mlr.press/v180/lam22a.html %V 180 %X There has been an increasing interest in methods that exploit permutation reasoning to search for directed acyclic causal models, including the “Ordering Search’’ of Teyssier and Kohler and GSP of Solus, Wang and Uhler. We extend the methods of the latter by a permutation-based operation tuck, and develop a class of algorithms, namely GRaSP, that are computationally efficient and pointwise consistent under increasingly weaker assumptions than faithfulness. The most relaxed form of GRaSP outperforms many state-of-the-art causal search algorithms in simulation, allowing efficient and accurate search even for dense graphs and graphs with more than 100 variables.
APA
Lam, W., Andrews, B. & Ramsey, J.. (2022). Greedy relaxations of the sparsest permutation algorithm. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:1052-1062 Available from https://proceedings.mlr.press/v180/lam22a.html.

Related Material