Inference in qualitative probabilistic networks revisited

Qualitative probabilistic networks (QPNs) are basically qualitative derivations of Bayesian belief networks. Originally, QPNs were designed to improve the speed of the construction and calculation of these networks, at the cost of specificity of the result. The formalism can also be used to facilitate cognitive mapping by means of inference in sign-based causal diagrams. Whatever the type of application, any computer based use of QPNs requires an algorithm capable of propagating information throughout the networks. Such an algorithm was developed in the 1990s. This polynomial time sign-propagation algorithm is explicitly or implicitly used in most existing QPN studies.This paper firstly shows that two types of undesired results may occur with the original sign-propagation algorithm: the results can be (1) less specific than possible at the given level of abstraction, or, more seriously (2) incorrect. Secondly, the paper identifies the causes underlying these problems. Thirdly, this paper presents an adapted sign-propagation algorithm. The worst-case running time of the adapted algorithm is still polynomial in the number of arrows. The results of the new algorithm have been compared with those of the original algorithm by applying both algorithms to a real-life constructed cognitive map. It is shown that the problems of the original algorithm are indeed prevented with the adapted algorithm.