Provisional Propagation for Verifying Monotonicity of Bayesian Networks

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.