2012/06/27 by Or Zuk, Zuk, Or, Shiri Margel +3
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1206.6862
openalex publication_date 2012/06/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Bayesian Networks (BNs) are useful tools giving a natural and compact representation of joint probability distributions. In many applications one needs to learn a Bayesian Network (BN) from data. In this context, it is important to understand the number of samples needed in order to guarantee a successful learning. Previous work have studied BNs sample complexity, yet it mainly focused on the requirement that the learned distribution will be close to the original distribution which generated the data. In this work, we study a different aspect of the learning, namely the number of samples needed in order to learn the correct structure of the network. We give both asymptotic results, valid in the large sample limit, and experimental results, demonstrating the learning behavior for feasible sample sizes. We show that structure learning is a more difficult task, compared to approximating the correct distribution, in the sense that it requires a much larger number of samples, regardless of the computational power available for the learner.