Random Bayesian networks with bounded indegree

Eunice Yuh-Jie Chen, Judea Pearl
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:114-121, 2014.

Abstract

Bayesian networks (BN) are an extensively used graphical model for representing a probability distribution in artificial intelligence, data mining, and machine learning. In this paper, we propose a simple model for large random BNs with bounded indegree, that is, large directed acyclic graphs (DAG) where the edges appear at random and each node has at most a given number of parents. Using this model, we can study useful asymptotic properties of large BNs and BN algorithms with basic combinatorics tools. We estimate the expected size of a BN, the expected size increase of moralization, the expected size of the Markov blanket, and the maximum size of a minimal d-separator. We also provide an upper bound on the average time complexity of an algorithm for finding a minimal d-separator. In addition, the estimates are evaluated against BNs learned from real world data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-chen14a, title = {{Random Bayesian networks with bounded indegree}}, author = {Chen, Eunice Yuh-Jie and Pearl, Judea}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {114--121}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/chen14a.pdf}, url = {https://proceedings.mlr.press/v33/chen14a.html}, abstract = {Bayesian networks (BN) are an extensively used graphical model for representing a probability distribution in artificial intelligence, data mining, and machine learning. In this paper, we propose a simple model for large random BNs with bounded indegree, that is, large directed acyclic graphs (DAG) where the edges appear at random and each node has at most a given number of parents. Using this model, we can study useful asymptotic properties of large BNs and BN algorithms with basic combinatorics tools. We estimate the expected size of a BN, the expected size increase of moralization, the expected size of the Markov blanket, and the maximum size of a minimal d-separator. We also provide an upper bound on the average time complexity of an algorithm for finding a minimal d-separator. In addition, the estimates are evaluated against BNs learned from real world data.} }
Endnote
%0 Conference Paper %T Random Bayesian networks with bounded indegree %A Eunice Yuh-Jie Chen %A Judea Pearl %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-chen14a %I PMLR %P 114--121 %U https://proceedings.mlr.press/v33/chen14a.html %V 33 %X Bayesian networks (BN) are an extensively used graphical model for representing a probability distribution in artificial intelligence, data mining, and machine learning. In this paper, we propose a simple model for large random BNs with bounded indegree, that is, large directed acyclic graphs (DAG) where the edges appear at random and each node has at most a given number of parents. Using this model, we can study useful asymptotic properties of large BNs and BN algorithms with basic combinatorics tools. We estimate the expected size of a BN, the expected size increase of moralization, the expected size of the Markov blanket, and the maximum size of a minimal d-separator. We also provide an upper bound on the average time complexity of an algorithm for finding a minimal d-separator. In addition, the estimates are evaluated against BNs learned from real world data.
RIS
TY - CPAPER TI - Random Bayesian networks with bounded indegree AU - Eunice Yuh-Jie Chen AU - Judea Pearl BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-chen14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 114 EP - 121 L1 - http://proceedings.mlr.press/v33/chen14a.pdf UR - https://proceedings.mlr.press/v33/chen14a.html AB - Bayesian networks (BN) are an extensively used graphical model for representing a probability distribution in artificial intelligence, data mining, and machine learning. In this paper, we propose a simple model for large random BNs with bounded indegree, that is, large directed acyclic graphs (DAG) where the edges appear at random and each node has at most a given number of parents. Using this model, we can study useful asymptotic properties of large BNs and BN algorithms with basic combinatorics tools. We estimate the expected size of a BN, the expected size increase of moralization, the expected size of the Markov blanket, and the maximum size of a minimal d-separator. We also provide an upper bound on the average time complexity of an algorithm for finding a minimal d-separator. In addition, the estimates are evaluated against BNs learned from real world data. ER -
APA
Chen, E.Y. & Pearl, J.. (2014). Random Bayesian networks with bounded indegree. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:114-121 Available from https://proceedings.mlr.press/v33/chen14a.html.

Related Material