Enumerating Equivalence Classes of Bayesian Networks using EC Graphs

Eunice Yuh-Jie Chen, Arthur Choi Choi, Adnan Darwiche
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:591-599, 2016.

Abstract

We consider the problem of learning Bayesian network structures from complete data. In particular, we consider the enumeration of their k-best equivalence classes. We propose a new search space for A* search, called the EC graph, that facilitates the enumeration of equivalence classes, by representing the space of completed, partially directed acyclic graphs. We also propose a canonization of this search space, called the EC tree, which further improves the efficiency of enumeration. Empirically, our approach is orders of magnitude more efficient than the state-of-the-art at enumerating equivalence classes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-chen16b, title = {Enumerating Equivalence Classes of Bayesian Networks using EC Graphs}, author = {Chen, Eunice Yuh-Jie and Choi, Arthur Choi and Darwiche, Adnan}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {591--599}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/chen16b.pdf}, url = {https://proceedings.mlr.press/v51/chen16b.html}, abstract = {We consider the problem of learning Bayesian network structures from complete data. In particular, we consider the enumeration of their k-best equivalence classes. We propose a new search space for A* search, called the EC graph, that facilitates the enumeration of equivalence classes, by representing the space of completed, partially directed acyclic graphs. We also propose a canonization of this search space, called the EC tree, which further improves the efficiency of enumeration. Empirically, our approach is orders of magnitude more efficient than the state-of-the-art at enumerating equivalence classes.} }
Endnote
%0 Conference Paper %T Enumerating Equivalence Classes of Bayesian Networks using EC Graphs %A Eunice Yuh-Jie Chen %A Arthur Choi Choi %A Adnan Darwiche %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-chen16b %I PMLR %P 591--599 %U https://proceedings.mlr.press/v51/chen16b.html %V 51 %X We consider the problem of learning Bayesian network structures from complete data. In particular, we consider the enumeration of their k-best equivalence classes. We propose a new search space for A* search, called the EC graph, that facilitates the enumeration of equivalence classes, by representing the space of completed, partially directed acyclic graphs. We also propose a canonization of this search space, called the EC tree, which further improves the efficiency of enumeration. Empirically, our approach is orders of magnitude more efficient than the state-of-the-art at enumerating equivalence classes.
RIS
TY - CPAPER TI - Enumerating Equivalence Classes of Bayesian Networks using EC Graphs AU - Eunice Yuh-Jie Chen AU - Arthur Choi Choi AU - Adnan Darwiche BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-chen16b PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 591 EP - 599 L1 - http://proceedings.mlr.press/v51/chen16b.pdf UR - https://proceedings.mlr.press/v51/chen16b.html AB - We consider the problem of learning Bayesian network structures from complete data. In particular, we consider the enumeration of their k-best equivalence classes. We propose a new search space for A* search, called the EC graph, that facilitates the enumeration of equivalence classes, by representing the space of completed, partially directed acyclic graphs. We also propose a canonization of this search space, called the EC tree, which further improves the efficiency of enumeration. Empirically, our approach is orders of magnitude more efficient than the state-of-the-art at enumerating equivalence classes. ER -
APA
Chen, E.Y., Choi, A.C. & Darwiche, A.. (2016). Enumerating Equivalence Classes of Bayesian Networks using EC Graphs. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:591-599 Available from https://proceedings.mlr.press/v51/chen16b.html.

Related Material