Editing Bayesian network (section)

===Marginal independence structure===
In general, learning a Bayesian network from data is known to be [[NP-hardness|NP-hard]].<ref>{{cite journal |last1=Chickering |first1=David M. |last2=Heckerman |first2=David |last3=Meek |first3=Christopher |title=Large-sample learning of Bayesian networks is NP-hard |journal=Journal of Machine Learning Research |date=2004 |volume=5 |pages=1287–1330 |url=https://www.jmlr.org/papers/volume5/chickering04a/chickering04a.pdf}}</ref> This is due in part to the [[combinatorial explosion]] of [[Directed acyclic graph#Combinatorial enumeration|enumerating DAGs]] as the number of variables increases. Nevertheless, insights about an underlying Bayesian network can be learned from data in polynomial time by focusing on its marginal independence structure:<ref>{{cite journal |last1=Deligeorgaki |first1=Danai |last2=Markham |first2=Alex |last3=Misra |first3=Pratik |last4=Solus |first4=Liam |title=Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks |journal=Algebraic Statistics |date=2023 |volume=14 |issue=2 |pages=233–286 |doi=10.2140/astat.2023.14.233|arxiv=2210.00822 }}</ref> while the conditional independence statements of a distribution modeled by a Bayesian network are encoded by a DAG (according to the factorization and Markov properties above), its marginal independence statements—the conditional independence statements in which the conditioning set is empty—are encoded by a [[Graph (discrete mathematics)|simple undirected graph]] with special properties such as equal [[Intersection number (graph theory)|intersection]] and [[Independent set (graph theory)|independence numbers]].