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.

As we see later, the mathematical derivations are more elaborate A Bayesian network is a probabilistic graphical model that than those recently introduced for BIC and AIC criteria relies on a structured dependency among random variables (de Campos, Zeng, and Ji 2009), and the reduction in the to represent a joint probability distribution in a compact and search space and cache size are less effective when priors efficient manner. It is composed by a directed acyclic graph are strong, but still relevant. This is expected, as the BIC (DAG) where nodes are associated to random variables and score is known to penalize complex graphs more than BD conditional probability distributions are defined for variables scores do. We show that the search space can be reduced given their parents in the graph. Learning the graph (or without losing the global optimality guarantee and that the structure) of these networks from data is one of the most memory requirements are small in many practical cases.