大阪大学　数理・データ科学教育研究センター
Center for Mathematical Modeling and Data Science,Osaka University

Bayesian Networks, Big Data and Greedy Search

Marco Scutari (IDSIA, Italy)

1. ホーム
2. セミナー・集中講義
3. セミナー
4. Bayesian Networks, Big Data and Greedy Search

大阪大学 数理・データ科学セミナー データ科学セミナーシリーズ 第43回

Bayesian Networks, Big Data and Greedy Search

Marco Scutari (IDSIA, Italy)

Learning the structure of Bayesian networks from data is known to be a computationally challenging, NP-hard problem. The literature has long investigated how to perform structure learning from data containing large numbers of variables, following a general interest in high-dimensional applications (“small n, large p”) in systems biology and genetics. More recently, data sets with large numbers of observations (the so-called “big data”) have become increasingly common; and these data sets are not necessarily high-dimensional, sometimes having only a few tens of variables depending on the application. We revisit the computational complexity of Bayesian network structure learning in this setting, showing that the common choice of measuring it with the number of estimated local distributions leads to unrealistic time complexity estimates for the most common class of score-based algorithms, greedy search. We then derive more accurate expressions under common distributional assumptions. These expressions suggest that the speed of Bayesian network learning can be improved by taking advantage of the availability of closed-form estimators for local distributions with few parents. Furthermore, we find that using predictive instead of in-sample goodness-of-fit scores improves speed; and we confirm that it improves the accuracy of network reconstruction as well, as previously observed by Chickering and Heckerman (Stat Comput 10: 55–62, 2000). We demonstrate these results on large real-world environmental and epidemiological data; and on reference data sets available from public repositories.

Keywords
Bayesian networks Structure Learning Big Data Computational Complexity