Complexity of inferences in polytree-shaped semi-qualitative probabilistic networks

Cassio P. De Campos, Fabio G. Cozman

Resultado de la investigación: Contribución a una conferenciaArtículo de conferencia

2 Citas (Scopus)


Semi-qualitative probabilistic networks (SQPNs) merge two important graphical model formalisms: Bayesian networks and qualitative probabilistic networks. They provide a very general modeling framework by allowing the combination of numeric and qualitative assessments over a discrete domain, and can be compactly encoded by exploiting the same factorization of joint probability distributions that are behind the Bayesian networks. This paper explores the computational complexity of semi-qualitative probabilistic networks, and takes the polytree-shaped networks as its main target. We show that the inference problem is coNP-Complete for binary polytrees with multiple observed nodes. We also show that inferences can be performed in time linear in the number of nodes if there is a single observed node. Because our proof is constructive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynomial-time algorithm for SQPNs. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs. © 2013, Association for the Advancement of Artificial Intelligence ( All rights reserved.
Idioma originalInglés estadounidense
Número de páginas7
EstadoPublicada - 1 dic. 2013
Publicado de forma externa
EventoProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 -
Duración: 1 dic. 2013 → …


ConferenciaProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013
Período1/12/13 → …


Profundice en los temas de investigación de 'Complexity of inferences in polytree-shaped semi-qualitative probabilistic networks'. En conjunto forman una huella única.

Citar esto