L.C. van der Gaag, H.L. Bodlaender and A. Feelders. Monotonicity
in Bayesian Networks. In M. Chickering and
J. Halpern (editors), Proceedings of the Twentieth Conference
on Uncertainty in
Artificial Intelligence, AUAI Press, Arlington, Virginia, pp.
569–576, 2004. (full paper)
For many real-life Bayesian networks, common knowledge dictates
that
the output established for the main variable of interest increases with
higher values for the observable variables. We define two concepts of
monotonicity to capture this type of knowledge. We say that a network
is isotone in distribution if the probability distribution computed for
the output variable given specific observations is stochastically
dominated by any such distribution given higher-ordered observations; a
network is isotone in mode if a probability distribution given higher
observations has a higher mode. We show that establishing whether a
network exhibits any of these properties of monotonicity is
coNPPP-complete in general, and remains coNP-complete for polytrees. We
present an approximate algorithm for deciding whether a network is
monotone in distribution and illustrate its application to a real-life
network in oncology.