Greedy Relaxations of the Sparsest Permutation Algorithm

Wai Yin Lam; Bryan Andrews; Joseph Ramsey

Greedy Relaxations of the Sparsest Permutation Algorithm

Wai Yin Lam
, Bryan Andrews
, Joseph Ramsey

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022
Publisher	Association For Uncertainty in Artificial Intelligence (AUAI)
Pages	1052-1062
Number of pages	11
ISBN (Electronic)	9781713863298
State	Published - 2022
Externally published	Yes
Event	38th Conference on Uncertainty in Artificial Intelligence, UAI 2022 - Eindhoven, Netherlands Duration: Aug 1 2022 → Aug 5 2022

Publication series

Name	Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022

Conference

Conference	38th Conference on Uncertainty in Artificial Intelligence, UAI 2022
Country/Territory	Netherlands
City	Eindhoven
Period	8/1/22 → 8/5/22

Bibliographical note

Publisher Copyright:
© 2022 Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022. All right reserved.

Find It

Find It at U of M Libraries

Cite this

Greedy Relaxations of the Sparsest Permutation Algorithm. / Lam, Wai Yin; Andrews, Bryan; Ramsey, Joseph.
Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022. Association For Uncertainty in Artificial Intelligence (AUAI), 2022. p. 1052-1062 (Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lam, WY, Andrews, B & Ramsey, J 2022, Greedy Relaxations of the Sparsest Permutation Algorithm. in Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022. Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022, Association For Uncertainty in Artificial Intelligence (AUAI), pp. 1052-1062, 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022, Eindhoven, Netherlands, 8/1/22.

@inproceedings{7e62e35ca45f43298946c348b265fae8,

title = "Greedy Relaxations of the Sparsest Permutation Algorithm",

abstract = "There has been an increasing interest in methods that exploit permutation reasoning to search for directed acyclic causal models, including the {\textquotedblleft}Ordering Search{\textquotedblright} 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.",

author = "Lam, \{Wai Yin\} and Bryan Andrews and Joseph Ramsey",

note = "Publisher Copyright: {\textcopyright} 2022 Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022. All right reserved.; 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022 ; Conference date: 01-08-2022 Through 05-08-2022",

year = "2022",

language = "English (US)",

series = "Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022",

publisher = "Association For Uncertainty in Artificial Intelligence (AUAI)",

pages = "1052--1062",

booktitle = "Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022",

}

TY - GEN

T1 - Greedy Relaxations of the Sparsest Permutation Algorithm

AU - Lam, Wai Yin

AU - Andrews, Bryan

AU - Ramsey, Joseph

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85138716487

UR - https://www.scopus.com/pages/publications/85138716487#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:85138716487

T3 - Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022

SP - 1052

EP - 1062

BT - Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022

PB - Association For Uncertainty in Artificial Intelligence (AUAI)

T2 - 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022

Y2 - 1 August 2022 through 5 August 2022

ER -

Greedy Relaxations of the Sparsest Permutation Algorithm

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this