Revisiting Bayesian Network Learning with Small Vertex Cover

Tutkimustuotos: ArtikkelijulkaisuKonferenssiartikkeliTieteellinenvertaisarvioitu


The problem of structure learning in Bayesian networks asks for a directed acyclic graph (DAG) that maximizes a given scoring function. Since the problem is NP-hard, research effort has been put into discovering restricted classes of DAGs for which the search problem can be solved in polynomial time. Here, we initiate investigation of questions that have received less attention thus far: Are the known polynomial algorithms close to the best possible, or is there room for significant improvements? If the interest is in Bayesian learning, that is, in sampling or weighted counting of DAGs, can we obtain similar complexity results? Focusing on DAGs with bounded vertex cover number-a class studied in Korhonen and Parviainen's seminal work (NIPS 2015)-we answer the questions in the affirmative. We also give, apparently the first, proof that the counting problem is #P-hard in general. In addition, we show that under the vertex-cover constraint counting is #W[1]-hard.

LehtiProceedings of Machine Learning Research
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaConference on Uncertainty in Artificial Intelligence - Pittsburgh, Yhdysvallat (USA)
Kesto: 31 heinäk. 20234 elok. 2023
Konferenssinumero: 39


Publisher Copyright:
© UAI 2023. All rights reserved.


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä