Statistically Efficient Greedy Equivalence Search

Max Chickering
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:241-249, 2020.

Abstract

We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.

Cite this Paper

BibTeX
@InProceedings{pmlr-v124-chickering20a, title = {Statistically Efficient Greedy Equivalence Search}, author = {Chickering, Max}, booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)}, pages = {241--249}, year = {2020}, editor = {Peters, Jonas and Sontag, David}, volume = {124}, series = {Proceedings of Machine Learning Research}, month = {03--06 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v124/chickering20a/chickering20a.pdf}, url = {https://proceedings.mlr.press/v124/chickering20a.html}, abstract = {We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.} }
Endnote
%0 Conference Paper %T Statistically Efficient Greedy Equivalence Search %A Max Chickering %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-chickering20a %I PMLR %P 241--249 %U https://proceedings.mlr.press/v124/chickering20a.html %V 124 %X We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.
APA
Chickering, M.. (2020). Statistically Efficient Greedy Equivalence Search. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:241-249 Available from https://proceedings.mlr.press/v124/chickering20a.html.

Related Material