TY - GEN
T1 - DL-Lite Bayesian networks: A tractable probabilistic graphical model
AU - Mauá, Denis D.
AU - Cozman, Fabio G.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - © Springer International Publishing Switzerland 2015. The construction of probabilistic models that can represent large systems requires the ability to describe repetitive and hierarchical structures. To do so, one can resort to constructs from description logics. In this paper we present a class of relational Bayesian networks based on the popular description logic DL-Lite. Our main result is that, for this modeling language, marginal inference and most probable explanation require polynomial effort. We show this by reductions to edge covering problems, and derive a result of independent interest; namely, that counting edge covers in a particular class of graphs requires polynomial effort.
AB - © Springer International Publishing Switzerland 2015. The construction of probabilistic models that can represent large systems requires the ability to describe repetitive and hierarchical structures. To do so, one can resort to constructs from description logics. In this paper we present a class of relational Bayesian networks based on the popular description logic DL-Lite. Our main result is that, for this modeling language, marginal inference and most probable explanation require polynomial effort. We show this by reductions to edge covering problems, and derive a result of independent interest; namely, that counting edge covers in a particular class of graphs requires polynomial effort.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951873460&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84951873460&origin=inward
U2 - 10.1007/978-3-319-23540-0_4
DO - 10.1007/978-3-319-23540-0_4
M3 - Conference contribution
SN - 9783319235394
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 50
EP - 64
BT - DL-Lite Bayesian networks: A tractable probabilistic graphical model
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Y2 - 1 January 2018
ER -