Provisional Propagation for Verifying Monotonicity of Bayesian Networks
Merel T. Rietbergen, Linda C. van der Gaag, Hans L. Bodlaender · Frontiers in artificial intelligence and applications · 2014
Many real-world Bayesian networks are expected to exhibit commonly known properties of monotonicity. Since monotonicity violations may be introduced despite careful engineering efforts, these properties need be verified before using a network in practice. We will show that the problem of verifying monotonicity in general has a prohibitively high computational complexity. We will argue however, that the runtime complexity involved can be substantially reduced by using a tailored algorithm which we coined provisional propagation. By means of this algorithm in fact, verifying monotonicity may become feasible for a range of real-world networks.