Extended View on Large-Sample Learning of Bayesian Networks

Speaker(s)

Paweł Betliński

Date

June 9, 2017, 3:30 p.m.

Room

room 5820

Seminar

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

---

In this talk we will consider one of the main complexity results in the field of Bayesian networks: the NP-hardness of so called large-sample Bayesian network learning (D. M. Chickering, D. Heckerman, and C. Meek. "Large-Sample Learning of Bayesian Networks is NP-Hard". Journal of Machine Learning Research, 5:1287–1330, 2004). We will present the background, motivation and statement of the considered problem.
Then we will show how this result can be extended. We will introduce a significantly new formulation of the problem standing in the interesting complementary relation with the original one - which turns out to be NP-hard too.

---